Правило Руффини

Правило Руффини — эффективная техника деления многочлена на бином вида ${\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. Спустить крайний левый коэффициент (a_n) вниз, сразу под линию:

   ${\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}}}$

Числа b_i являются коэффициентами частного (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.}$

• Weisstein, Eric W. Правило Руффини (англ.) на сайте Wolfram MathWorld.