ru.wikipedia.org

Правило Руффини — Википедия

Правило Руффини — эффективная техника деления многочлена на бином вида {\displaystyle x-r.} В 1804 году её описал Паоло Руффини.[1] Правило Руффини — частный случай синтетического деления, когда делитель является линейным.

Правило устанавливает метод для деления многочлена

{\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}

на бином

{\displaystyle Q(x)=x-r}

для получения частного

{\displaystyle R(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\cdots +b_{1}x+b_{0}};

На самом деле алгоритм осуществляет деление столбиком P(x) на Q(x).

Для того, чтобы поделить P(x) на Q(x) согласно данному алгоритму, нужно

  1. Взять коэффициенты P(x) и записать их по порядку. Затем записать r слева, непосредственно над линией:
    {\displaystyle {\begin{array}{c|c c c c c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&&&&\\\hline &&&&&\\&&&&&\\\end{array}}}
  2. Спустить крайний левый коэффициент (an) вниз, сразу под линию:
    {\displaystyle {\begin{array}{c|c c c c c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&&&&\\\hline &a_{n}&&&&\\&=b_{n-1}&&&&\\\end{array}}}
  3. Умножить крайнее правое число под линией на r и записать следующим его над линией:
    {\displaystyle {\begin{array}{c|c c c c c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&b_{n-1}r&&&\\\hline &a_{n}&&&&\\&=b_{n-1}&&&&\\\end{array}}}
  4. Сложить два значения, расположенные в одном столбце:
    {\displaystyle {\begin{array}{c|c c c c c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&b_{n-1}r&&&\\\hline &a_{n}&a_{n-1}+(b_{n-1}r)&&&\\&=b_{n-1}&=b_{n-2}&&&\\\end{array}}}
  5. Повторять шаги 3 и 4 пока есть числа:
    {\displaystyle {\begin{array}{c|c c c c c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&b_{n-1}r&&&\\\hline &a_{n}&a_{n-1}+(b_{n-1}r)&\cdots &a_{1}+b_{1}r&a_{0}+b_{0}r\\&=b_{n-1}&=b_{n-2}&\cdots &=b_{0}&=s\\\end{array}}}

Числа bi являются коэффициентами частного (R(x)), степень которого на единицу меньше, чем степень P(x). Последнее полученное значение s - это остаток. Согласно теореме Безу, этот остаток равен P(r).

Рабочий пример деления многочленов по алгоритму, описанному выше.

Пусть:

{\displaystyle P(x)=2x^{3}+3x^{2}-4,}
{\displaystyle Q(x)=x+1.}

Мы хотим найти {\displaystyle P(x)/Q(x)} используя правило Руффини. Основная проблема в том, что {\displaystyle Q(x)} это не бином вида {\displaystyle x-r,}, а скорее {\displaystyle x+r.} Мы должны переписать его так:

{\displaystyle Q(x)=x+1=x-(-1).}

Теперь применяем алгоритм:

1. Выписываем коэффициенты и число {\displaystyle r.} Заметим, что поскольку {\displaystyle P(x)} не содержит коэффициента {\displaystyle x^{1},} мы записываем 0:

{\displaystyle {\begin{array}{c|c c c c}&2&3&0&-4\\-1&&&&\\\hline &&&&\\&&&&\\\end{array}}}

2. Спускаем первый коэффициент:

{\displaystyle {\begin{array}{c|c c c c}&2&3&0&-4\\-1&&&&\\\hline &2&&&\\\end{array}}}

3. Умножаем последнее полученное значение {\displaystyle r:}

{\displaystyle {\begin{array}{c|c c c c}&2&3&0&-4\\-1&&-2&&\\\hline &2&&&\\\end{array}}}

4. Складываем значения:

{\displaystyle {\begin{array}{c|c c c c}&2&3&0&-4\\-1&&-2&&\\\hline &2&1&&\\\end{array}}}

5. Повторяем шаги 3 и 4:

{\displaystyle {\begin{array}{c|c c c c}&2&3&0&-4\\-1&&-2&-1&1\\\hline &2&1&-1&-3\\\end{array}}}
{\displaystyle 2,1,-1} — коэффициенты частного,
{\displaystyle -3} — остаток.

Итак, поскольку исходное число = делитель × частное + остаток, тогда

{\displaystyle P(x)=Q(x)R(x)+s}, где
{\displaystyle R(x)=2x^{2}+x-1,\ s=-3;\quad \Rightarrow 2x^{3}+3x^{2}-4=(2x^{2}+x-1)(x+1)-3.}
  1. ↑ Кажори, Florian. Horner's method of approximation anticipated by Ruffini (англ.) // Bulletin of the American Mathematical Society : journal. — 1911. — Vol. 17, no. 8. — P. 389—444. Архивировано 12 декабря 2019 года.