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

Тон или стиль этой статьи могут не отражать энциклопедический тон, используемый в Википедии . Рекомендации по написанию статей можно найти в руководстве Википедии . ( Февраль 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В математике , правило Руффини в практический способ для целлюлозно-карандаш вычисления евклидова деления из многочлена с помощью биномиального вида х - р . Он был описан Паоло Руффини в 1804 году. ^[1] Правило является частным случаем синтетического деления, в котором делитель является линейным множителем.

Алгоритм [ править ]

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

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

биномом

${\ Displaystyle Q (x) = xr}$

чтобы получить фактор-полином

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

Алгоритм на самом деле длинное деление на Р ( х ) на Q ( х ).

Чтобы разделить 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}\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}}}$

Значения b являются коэффициентами полинома результата ( R ( x )), степень которого на единицу меньше, чем у P ( x ). Полученное окончательное значение s представляет собой остаток. Теорема полиномиального остатка утверждает, что остаток равен P ( r ), а значение многочлена в r .

Пример [ править ]

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

Позволять:

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

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

P ( x ) будет разделено на Q ( x ) по правилу Руффини. Основная проблема в том, что Q ( x ) не является двучленом вида x - r , а скорее x + r . Q ( x ) необходимо переписать как

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

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

1. Запишите коэффициенты и r . Обратите внимание, что, поскольку P ( x ) не содержит коэффициента для x , записывается 0:

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

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

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

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

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

Использует [ редактировать ]

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

Полиномиальное нахождение корня [ править ]

Теорема о рациональном корне утверждает, что для многочлена f ( x ) = a _n x ⁿ + a _{n −1} x ^{n −1} + ⋯ + a ₁ x + a _0, все коэффициенты которого (от a _n до a ₀ ) являются целыми числами , действительные рациональные корни всегда имеют вид p / q , где p является целым делителем a ₀ и qпредставляет собой целое число делитель в _п . Таким образом, если наш многочлен

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

возможные рациональные корни - это все целые делители числа a ₀ (−2):

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

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

Следовательно, полагая r равным каждому из возможных корней по очереди, многочлен делится на ( x - r ). Если полученное частное не имеет остатка, корень был найден.

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

Метод 1 [ править ]

Деление P ( x ) на бином ( x - каждый возможный корень). Если остаток равен 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}}}$

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

${\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 [ править ]

• Определите множество возможных целочисленных или рациональных корней многочлена в соответствии с теоремой о рациональных корнях .
• Для каждого возможного корня r вместо выполнения деления P ( x ) / ( x - r ) примените теорему о полиномиальном остатке , которая утверждает, что остаток от деления равен P ( r ), многочлену, вычисленному для x = r .

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

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

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

Q ( x ) = P ( x ) / ( x - r ₁ ).

Это позволяет частичную факторизацию полинома как

Р ( х ) = ( х - г ₁ ) · Q ( х )

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

Таким образом, вы можете продолжить вычисление Q ( r ) вместо P ( r ) и (если вы можете найти другой корень, r ₂ ) деление Q ( r ) на ( x - r ₂ ).

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

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

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

Примеры [ править ]

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

Р ( х ) = х ³ + 2 х ² - х - 2

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

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

а остаток от ( x ³ + 2 x ² - x - 2) / ( x - 2) равен 12

• Р (-2) = 0 → х ₃ = -2

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

Р ( х ) = х ³ + 2 х ² - х - 2

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

• Р (1) = 0 → х ₁ = 1

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

( х ³ + 2 х ² - х - 2) / ( х - 1) = х ² + 3 х + 2

х ³ + 2 х ² - х - 2 = ( х - 1) ( х ² + 3 х + 2)

Здесь r ₁ = −1 и Q ( x ) = x ² + 3 x + 2

• Q (-1) = 0 → х ₂ = -1

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

( х ² + 3 х + 2) / ( х + 1) = х + 2

х ³ + 2 х ² - х - 2 = ( х - 1) ( х ² + 3 х + 2) = ( х - 1) ( х + 1) ( х + 2)

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

Полиномиальный факторинг [ править ]

Используя приведенный выше результат « p / q » (или, честно говоря, любые другие средства), чтобы найти все действительные рациональные корни определенного многочлена, это всего лишь тривиальный шаг дальше, чтобы частично разложить этот многочлен на множители , используя эти корни. Как известно, каждому линейному множителю ( x - r ), который делит данный многочлен, соответствует корень r и наоборот .

Так что если

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

По основной теореме алгебры , R ( х ) должен быть равен Р ( х ), если все корни Р ( х ) рациональны. Однако, поскольку метод находит только рациональные корни, весьма вероятно, что R ( x ) не равно P ( x ); это очень вероятно , что Р ( х ) имеет некоторые иррациональные или комплексные корни не в R . Так что считайте

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

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

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

Можно назвать это полное разложение из Р ( х ) над Q (рациональных чисел) , если S ( х ) = 1. В противном случае, есть только частичное разложение по Р ( х ) над Q , которые могут или не могут быть дополнительно факторизуема над рациональными числами, но, безусловно, в дальнейшем будет факторизован над действительными или, в худшем случае, комплексной плоскостью. (Обратите внимание, что «полная факторизация» P ( x ) над Q означает факторизацию как произведение многочленов с рациональными коэффициентами, так что каждый множитель неприводим над Q, ans «неприводимый над Q » означает, что множитель не может быть записан как произведение двух непостоянных многочленов с рациональными коэффициентами и меньшей степенью.)

Пример 1: без остатка [ править ]

Позволять

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

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

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

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

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

И P ( x ) / R ( x ):

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

Следовательно, факторизованный многочлен P ( x ) = R ( x ) · 1 = R ( x ):

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

Пример 2: с остатком [ править ]

Позволять

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

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

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

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

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

И P ( x ) / R ( x )

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

При факторизованном многочлене P ( x ) = R ( x ) · S ( x ):${\displaystyle S(x){\neq }1}$

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

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

Ограничения [ править ]

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

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

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

История [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

• Вайсштейн, Эрик В. «Правило Руффини» . MathWorld .
• СМИ, связанные с правлением Руффини на Викискладе?