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

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

АлгоритмПравить

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

$P(x)=a_n{x}^n+a_{n-<!--\; -\; -->1}{x}^{n-<!--\; -\; -->1}+\cdots <!--\; \cdots \; -->+a_{1}x+a_0$$P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}$ 

на бином

$Q(x)=x-<!--\; -\; -->r$$Q(x)=x-r$ 

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

$R(x)=b_{n-<!--\; -\; -->1}{x}^{n-<!--\; -\; -->1}+b_{n-<!--\; -\; -->2}{x}^{n-<!--\; -\; -->2}+\cdots <!--\; \cdots \; -->+b_{1}x+b_0$$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,$$P(x)=2x^{3}+3x^{2}-4,$ 

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

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

$Q(x)=x+1=x-<!--\; -\; -->(-<!--\; -\; -->1).$$Q(x)=x+1=x-(-1).$ 

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

1. Выписываем коэффициенты и число $r.$$r.$  Заметим, что поскольку $P(x)$$P(x)$  не содержит коэффициента $x^1,$$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:$$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$$2,1,-1$  — коэффициенты частного,

$-<!--\; -\; -->3$$-3$  — остаток.

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

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

$R(x)=2x^2+x-<!--\; -\; -->1,s=-<!--\; -\; -->3;\Rightarrow <!--\; \Rightarrow \; -->2x^3+3x^2-<!--\; -\; -->4=(2x^2+x-<!--\; -\; -->1)(x+1)-<!--\; -\; -->3.$$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.