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

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

Алгоритм

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

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

на бином

$Q(x)=x-r$

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

$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 слева, непосредственно над линией:

   ${\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) вниз, сразу под линию:

   ${\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 и записать следующим его над линией:

   ${\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. Сложить два значения, расположенные в одном столбце:

   ${\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 пока есть числа:

   ${\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).

Использование

Деление на многочлен x - r

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

Пусть:

$P(x)=2x^{3}+3x^{2}-4,$

$Q(x)=x+1.$

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

$Q(x)=x+1=x-(-1).$

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

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

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

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

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

3. Умножаем последнее полученное значение $r:$

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

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

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

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

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

$2,1,-1$ — коэффициенты частного,

$-3$ — остаток.

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

$P(x)=Q(x)R(x)+s$, где

$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.