Правило Руффини - Ruffinis rule - Wikipedia

В математика, Правило Руффини это практический способ вычисления на бумаге и карандаша Евклидово деление из многочлен по биномиальный формы Икс – р. Это было описано Паоло Руффини в 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}}$;

По сути, алгоритм длинное деление из п(Икс) к Q(Икс).

Делить п(Икс) к Q(Икс):

1. Возьмем коэффициенты при п(Икс) и запишите их по порядку. Затем написать р в нижнем левом углу, сразу над линией:

   ${\displaystyle {\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&&&&\\\hline &&&&&\\\end{array}}}$

2. Передайте крайний левый коэффициент (а_п) внизу, под линией:

   ${\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. Умножьте крайнее правое число под чертой на р и напишите его через строку и на одну позицию вправо:

   ${\displaystyle {\begin{array}{c|c c c c|c}&a_{n}&a_{n-1}&\dots &a_{1}&a_{0}\\r&&b_{n-1}\cdot 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}\cdot r&&&\\\hline &a_{n}&b_{n-1}\cdot r+a_{n-1}&&&\\&=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}\cdot r&\dots &b_{1}\cdot r&b_{0}\cdot r\\\hline &a_{n}&b_{n-1}\cdot r+a_{n-1}&\dots &b_{1}\cdot r+a_{1}&a_{0}+b_{0}\cdot r\\&=b_{n-1}&=b_{n-2}&\dots &=b_{0}&=R\\\end{array}}}$

В б значения - это коэффициенты результата (р(Икс)) многочлен, степень которого на единицу меньше, чем у п(Икс). Полученное окончательное значение, s, это остаток. В теорема о полиномиальном остатке утверждает, что этот остаток равен п(р) значение полинома при р.

Пример использования

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

Позволять:

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

${\displaystyle Q(x)=x+1.\,\!}$

п(Икс) будет делиться на Q(Икс) по правилу Руффини. Основная проблема в том, что Q(Икс) не является двучленом вида Икс − р, скорее Икс + р. Q(Икс) надо переписать так:

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

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

1. Запишите коэффициенты и р. Обратите внимание, как п(Икс) не содержал коэффициента для Икс, 0 пишется:

    |     2     3     0     -4    |                                     -1 |                                    ----|----------------------------    |                                        |

2. Передайте первый коэффициент вниз:

    |     2     3     0     -4    |                                     -1 |                                    ----|----------------------------    |     2                                  |

3. Умножьте последнее полученное значение на р:

    |     2     3     0     -4    |                                     -1 |          -2                         ----|----------------------------    |     2                                  |

4. Добавьте значения:

    |     2     3     0     -4    | -1 |          -2----|----------------------------    |     2     1    |

5. Повторяйте шаги 3 и 4, пока не закончите:

    | 2 3 0 -4 | -1 | -2 -1 1 ---- | ---------------------------- | 2 1 -1 -3 | {результирующие коэффициенты} {остаток}

Так что если исходный номер = делитель × частное + остаток, тогда

${\displaystyle P(x)=Q(x)R(x)+s\,\!}$, куда

${\displaystyle R(x)=2x^{2}+x-1\,\!}$ и ${\displaystyle s=-3;\quad \Rightarrow 2x^{3}+3x^{2}-4=(2x^{2}+x-1)(x+1)-3\!}$

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

Правило Руффини имеет множество практических применений; большинство из них полагаются на простое деление (как показано ниже) или общие расширения, приведенные ниже.

Полиномиальное нахождение корня

Смотрите также: Алгоритм поиска корней § Корни многочленов

В теорема о рациональном корне утверждает, что для полинома ж(Икс) = а_пИкс^п + а_п−1Икс^п−1 + ... + а₁Икс + а₀ все коэффициенты (а_п через а₀) находятся целые числа, реальный рациональный корни всегда имеют форму п/q, куда п является целым делителем а₀ и q является целым делителем а_п. Таким образом, если наш многочлен

${\displaystyle P(x)=x^{3}+2x^{2}-x-2=0\,\!,}$

тогда возможные рациональные корни являются целыми делителями а₀ (−2):

${\displaystyle {\text{Possible roots:}}\left\{+1,-1,+2,-2\right\}.}$

(Этот пример прост, потому что многочлен моник (т.е. а_п = 1); для немонических многочленов множество возможных корней будет включать некоторые дроби, но только их конечное число, поскольку а_п и а₀ имеют только конечное число целых делителей.) В любом случае, для монических многочленов каждый рациональный корень является целым числом, и поэтому каждый целочисленный корень является просто делителем постоянный срок (т.е. а₀). Можно показать, что это остается верным для немонических многочленов, т.е. чтобы найти целые корни любых многочленов с целыми коэффициентами, достаточно проверить делители постоянного члена.

Итак, установив р равный каждому из этих возможных корней по очереди, многочлен будет разделен на (Икс − р). Если полученное частное не имеет остатка, корень найден.

Вы можете выбрать один из следующих трех методов: все они дадут одинаковые результаты, за исключением того, что только с помощью второго метода и третьего метода (при применении правила Руффини для получения факторизации) вы можете обнаружить, что данный корень повторяется. . (Ни один из методов не обнаружит иррациональных или сложных корней.)

Способ 1

Разделение п(Икс) на бином (Икс - каждый возможный корень). Если остаток равен 0, выбранное число является корнем (и наоборот):

    |    +1    +2    -1     -2                      |    +1    +2    -1    -2    |                                               | +1 |          +1    +3     +2                   -1 |          -1    -1    +2----|----------------------------               ----|---------------------------    |    +1    +3    +2      0                      |    +1    +1    -2     0

    |    +1    +2    -1     -2                      |    +1    +2    -1    -2    |                                               | +2 |          +2    +8    +14                   -2 |          -2     0    +2----|----------------------------               ----|---------------------------    |    +1    +4    +7    +12                      |    +1     0    -1     0

${\displaystyle {\begin{cases}x_{1}=+1\\x_{2}=-1\\x_{3}=-2\end{cases}}}$

В этом примере п(Икс) - многочлен третьей степени. Посредством основная теорема алгебры, он может иметь не более трех сложных решений. Следовательно, многочлен факторизуется следующим образом:

${\displaystyle P(x)=(x-x_{1})(x-x_{2})(x-x_{3})=(x-1)(x+1)(x+2)=x^{3}+2x^{2}-x-2.}$

Способ 2

Начните так же, как в методе 1, пока не будет найден действительный корень. Затем, вместо того, чтобы перезапускать процесс с другими возможными корнями, продолжайте тестирование возможных корней по результатам Руффини на действительном корне, найденном в настоящее время, пока не останется только коэффициент (помните, что корни могут повторяться: если вы застряли, попробуйте каждый действительный корень дважды):

    |    +1    +2    -1    -2                      |    +1    +2    -1    -2    |                                              | -1 |          -1    -1    +2                   -1 |          -1    -1    +2----|---------------------------               ----|---------------------------    |    +1    +1    -2   | 0                      |    +1    +1    -2   | 0    |                                              | +2 |          +2    +6                         +1 |          +1    +2-------------------------                      -------------------------    |    +1    +3   |+4                            |    +1    +2   | 0                                                   |                                                -2 |          -2                                               -------------------                                                   |    +1   | 0

${\displaystyle {\begin{cases}x_{1}=-1\\x_{2}=+1\\x_{3}=-2\end{cases}}}$

Способ 3

• Определите набор возможных целочисленных или рациональных корней многочлена в соответствии с теорема о рациональном корне.
• Для каждого возможного корня р, вместо выполнения деления п(Икс)/(Икс–р), примените теорема о полиномиальном остатке, в котором говорится, что остаток от этого деления равен п(р), т.е. полином, вычисленный для Икс = р.

Таким образом, для каждого р в нашем наборе, р фактически является корнем многочлена тогда и только тогда, когда п(р)=0

Это показывает, что открытие целочисленный и рациональный корни многочлена не требуют ни деления, ни применения правила Руффини.

Однако, как только действительный корень найден, назовите его р₁: вы можете применить правило Руффини, чтобы определить

Q(Икс)=п(Икс)/(Икс–р₁).

Это позволяет вам частично факторизовать многочлен как

п(Икс)=(Икс–р₁)·Q(Икс)

Любой дополнительный (рациональный) корень многочлена также является корнем Q(Икс) и, конечно, все еще можно найти среди возможных корней, определенных ранее, которые еще не были проверены (любое значение, уже определенное нет быть корнем п(Икс) не является корнем Q(Икс) либо; более формально, п(р)≠0 → Q(р)≠0 ).

Таким образом, вы можете продолжить оценку Q(р) вместо п(р), и (пока вы можете найти другой корень, р₂) разделение Q(р) к (Икс–р₂).

Даже если вы ищете только корни, это позволяет вам оценивать многочлены все меньшей степени по мере выполнения факторизации.

Если, как это часто бывает, вы также факторизуете многочлен степени п, тогда:

• если вы нашли п=п рациональные решения вы получите полную факторизацию (см. ниже) в п=п линейные факторы;
• если вы нашли п<п рациональные решения вы получите частичную факторизацию (см. ниже) в п линейные факторы и другой нелинейный фактор степени п–п, которые, в свою очередь, могут иметь иррациональные или сложные корни.

Примеры

Поиск корней без применения правила Руффини

п(Икс)=Икс³+2Икс²–Икс–2

Возможные корни = {1, –1, 2, -2}

• п(1) = 0 → Икс₁ = 1
• п(-1) = 0 → Икс₂ = -1
• п(2) = 12 → 2 не является корнем многочлена

а остальная часть (Икс³+2Икс²-Икс-2)/(Икс-2) 12 лет

• п(-2) = 0 → Икс₃ = -2

Нахождение корней с применением правила Руффини и получение (полной) факторизации

п(Икс) = Икс³+2Икс²-Икс-2

Возможные корни = {1, -1, 2, -2}

• п(1) = 0 → Икс₁ = 1

Затем, применяя правило Руффини:

(Икс³+2Икс²-Икс-2)/(Икс-1) = (Икс²+3Икс+2)

Икс³+2Икс²-Икс-2 = (Икс-1)(Икс²+3Икс+2)

Здесь, р₁= -1 и Q(Икс) = Икс²+3Икс+2

• Q(-1) = 0 → Икс₂ = -1

Опять же, применяя правило Руффини:

(Икс²+3Икс+2)/(Икс+1) = (Икс+2)

Икс³+2Икс²-Икс-2 = (Икс-1)(Икс²+3Икс+2) = (Икс-1)(Икс+1)(Икс+2)

Поскольку можно было полностью разложить полином на множители, ясно, что последний корень равен -2 (предыдущая процедура дала бы тот же результат с конечным частным, равным 1).

Полиномиальное разложение

Смотрите также: Факторизация многочленов

Используя "п/q"приведенный выше результат (или, честно говоря, любой другой способ), чтобы найти все действительные рациональные корни определенного многочлена, это всего лишь тривиальный шаг к частичному фактор этот многочлен, использующий эти корни. Как известно, каждый линейный множитель (Икс − р), который делит данный многочлен, соответствует корню р, и наоборот.

Так что если

${\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}\,\!}$ наш полином; и

${\displaystyle R=\left\{{\mbox{roots of }}P(x)\in \mathbb {Q} \right\}\,\!}$ найденные корни, тогда рассмотрим продукт

${\displaystyle R(x)=a_{n}{\prod (x-r)}{\mbox{ for all }}r\in R.\,\!}$

Посредством основная теорема алгебры, р(Икс) должно быть равно п(Икс), если все корни п(Икс) рациональны. Но поскольку используемый метод находит только рациональные корни, весьма вероятно, что р(Икс) не равно п(Икс); очень вероятно, что п(Икс) имеет какие-то иррациональные или сложные корни не в р. Так что рассмотрите

${\displaystyle S(x)={\frac {P(x)}{R(x)}}\,\!}$, который можно рассчитать с помощью полиномиальное деление в столбик.

Если S(Икс) = 1, то известно р(Икс) = п(Икс) и процедура завершена. Иначе, S(Икс) сам будет многочленом; это еще один фактор п(Икс), не имеющий реальных рациональных корней. Поэтому полностью выпишите правую часть следующего уравнения:

${\displaystyle P(x)=R(x)\cdot S(x).\,\!}$

Это можно назвать полная факторизация из п(Икс) над Q (рациональные), если S(Икс) = 1. В противном случае существует только частичная факторизация из п(Икс) над Q, которые могут или не могут быть в дальнейшем факторизованы над рациональными; но который, безусловно, будет в дальнейшем факторизован на вещественной или, в худшем случае, комплексной плоскости. (Примечание: путем «полной факторизации» п(Икс) над Q, означает факторизацию как произведение многочленов с рациональными коэффициентами, так что каждый множитель является неприводимым над Q, где «неприводимая над Q"означает, что коэффициент не может быть записан как произведение двух непостоянных многочленов с рациональными коэффициентами и меньшей степенью.)

Пример 1: без остатка

Позволять

${\displaystyle P(x)=x^{3}+2x^{2}-x-2.\,\!}$

Используя описанные выше методы, рациональные корни п(Икс) находятся:

${\displaystyle R=\left\{+1,-1,-2\right\}.\,\!}$

Тогда произведение (Икс - каждый корень)

${\displaystyle R(x)=1(x-1)(x+1)(x+2).\,\!}$

И п(Икс)/р(Икс):

${\displaystyle S(x)=1.\,\!}$

Следовательно, факторизованный полином равен п(Икс) = р(Икс) · 1 = р(Икс):

${\displaystyle P(x)=(x-1)(x+1)(x+2).\,\!}$

Пример 2: с остатком

Позволять

${\displaystyle P(x)=2x^{4}-3x^{3}+x^{2}-2x-8.\,\!}$

Используя описанные выше методы, рациональные корни п(Икс) находятся:

${\displaystyle R=\left\{-1,+2\right\}.\,\!}$

Тогда произведение (Икс - каждый корень)

${\displaystyle R(x)=(x+1)(x-2).\,\!}$

И п(Икс)/р(Икс)

${\displaystyle S(x)=2x^{2}-x+4.\,\!}$

В качестве ${\displaystyle S(x){\neq }1}$, факторизованный полином равен п(Икс) = р(Икс) · S(Икс):

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

Факторинг по комплексам

Чтобы полностью разложить данный полином на множители C, комплексные числа, все его корни должны быть известны (и могут включать иррациональные и / или комплексные числа). Например, рассмотрим полином выше:

${\displaystyle P(x)=2x^{4}-3x^{3}+x^{2}-2x-8.\,\!}$

Извлечение его рациональных корней и факторинг дает:

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

Но это не полностью учитывается C. Если факторизация полинома должна завершиться произведением линейных множителей, необходимо рассмотреть квадратичный множитель:

${\displaystyle {2x^{2}-x+4}=0.\,\!}$

Самый простой способ - использовать квадратичная формула, что дает

${\displaystyle x={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}={\frac {1\pm {\sqrt {(-1)^{2}-4\cdot 2\cdot 4}}}{2\cdot 2}}={\frac {1\pm {\sqrt {-31}}}{4}}\,\!}$

и решения

${\displaystyle x_{1}={\frac {1+{\sqrt {-31}}}{4}}\,\!}$

${\displaystyle x_{2}={\frac {1-{\sqrt {-31}}}{4}}.\,\!}$

Таким образом, полностью факторизованный многочлен по C будет:

${\displaystyle P(x)=2(x+1)(x-2)\left(x-{\frac {1+i{\sqrt {31}}}{4}}\right)\left(x-{\frac {1-i{\sqrt {31}}}{4}}\right).\,\!}$

Однако нельзя ожидать, что все будет так просто; аналог квадратичной формулы для полиномов четвертого порядка очень запутан, и такого аналога не существует для полиномов 5-го или более высокого порядка. Видеть Теория Галуа для теоретического объяснения того, почему это так, и см. числовой анализ для способов приблизительный корни многочленов численно.

Ограничения

Вполне возможно, что при поиске корней заданного многочлена можно получить сложный многочлен высшего порядка для S (x), который в дальнейшем факторизуем по рациональные еще до рассмотрения иррациональных или сложных факторингов. Рассмотрим многочлен Икс⁵ − 3Икс⁴ + 3Икс³ − 9Икс² + 2Икс - 6. Методом Руффини находят только один корень (Икс = 3); с учетом: п(Икс) = (Икс⁴ + 3Икс² + 2)(Икс − 3).

Как объяснено выше, если заявленное присвоение должно было «учитывать неснижаемые сверх C", было бы необходимо найти способ проанализировать квартику и найти ее иррациональные и / или комплексные корни. Но если бы присвоение было" разложить на несократимые над Q", можно подумать, что это уже сделано, но важно понимать, что это не обязательно так.

В этом случае квартика фактически факторизуется как произведение двух квадратичных (Икс² + 1)(Икс² + 2). Они, наконец, неприводимы по отношению к рациональным числам (и, действительно, действительным числам также в этом примере); что завершает метод; п(Икс) = (Икс² + 1)(Икс² + 2)(Икс - 3). В этом случае на самом деле легко разложить нашу квартику на множители, рассматривая ее как биквадратное уравнение; но найти такие разложения полинома более высокой степени может быть очень сложно.

История

Этот метод был изобретен Паоло Руффини. Он принял участие в конкурсе, организованном Итальянским научным обществом (Сорока). Необходимо было ответить на вопрос, как найти корни любого многочлена. Было получено пять материалов. В 1804 году Руффини был удостоен первого места, и метод был опубликован. Руффини опубликовал уточнения метода в 1807 и 1813 годах.

Метод Хорнера был опубликован в 1819 году, а в уточненной версии - в 1845 году.

Смотрите также

• Метод Хорнера
• Полиномиальное деление в столбик

Рекомендации

1. Кахори, Флориан (1911). «Аппроксимационный метод Хорнера, предвиденный Руффини» (PDF). Бюллетень Американского математического общества. 17 (8): 389–444. Дои:10.1090 / с0002-9904-1911-02072-9.

внешняя ссылка

• Вайсштейн, Эрик В. "Правило Руффини". MathWorld.
• СМИ, связанные с Правило Руффини в Wikimedia Commons