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

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

• 1 Алгоритм
• 2 Пример
• 3 использования
  • 3.1 Полиномиальное нахождение корня
    • 3.1.1 Метод 1
    • 3.1.2 Метод 2
    • 3.1.3 Метод 3
      • 3.1.3.1 Примеры
        • 3.1.3.1.1 Поиск корней без применения правила Руффини
        • 3.1.3.1.2 Нахождение корней по правилу Руффини и получение (полной) факторизации
  • 3.2 Полиномиальное разложение
    • 3.2.1 Пример 1: без остатка
    • 3.2.2 Пример 2: с остатком
    • 3.2.3 Факторинг по комплексам
    • 3.2.4 Ограничения
• 4 История
• 5 См. Также
• 6 Ссылки
• 7 Внешние ссылки

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

${\ 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 | cccc | c} amp; a_ {n} amp; a_ {n-1} amp; \ dots amp; a_ {1} amp; a_ {0} \\ r amp;amp;amp;amp;amp; \\\ hline amp;amp;amp;amp;amp; \\\ end { множество}}}$

2. Передайте крайний левый коэффициент ( a n) вниз, прямо под линией.

   ${\ displaystyle {\ begin {array} {c | cccc | c} amp; a_ {n} amp; a_ {n-1} amp; \ dots amp; a_ {1} amp; a_ {0} \\ r amp;amp;amp;amp;amp; \\\ hline amp; a_ {n} amp;amp;amp;amp; \ \ amp; = b_ {n-1} amp;amp;amp;amp; \ end {массив}}}$

3. Умножьте крайнее правое число под строкой на r и напишите его над строкой и на одну позицию вправо.

   ${\ displaystyle {\ begin {array} {c | cccc | c} amp; a_ {n} amp; a_ {n-1} amp; \ dots amp; a_ {1} amp; a_ {0} \\ r amp;amp; b_ {n-1} \ cdot r amp;amp;amp; \\ \ hline amp; a_ {n} amp;amp;amp;amp; \\ amp; = b_ {n-1} amp;amp;amp;amp; \ end {array}}}$

4. Добавьте два значения, только что помещенных в один столбец.

   ${\ displaystyle {\ begin {array} {c | cccc | c} amp; a_ {n} amp; a_ {n-1} amp; \ dots amp; a_ {1} amp; a_ {0} \\ r amp;amp; b_ {n-1} \ cdot r amp;amp;amp; \\ \ hline amp; a_ {n} amp; b_ {n-1} \ cdot r + a_ {n-1} amp;amp;amp; \\ amp; = b_ {n-1} amp; = b_ {n-2} amp;amp;amp; \ end {array}}}$

5. Повторяйте шаги 3 и 4, пока не останутся цифры.

   ${\ displaystyle {\ begin {array} {c | cccc | c} amp; a_ {n} amp; a_ {n-1} amp; \ dots amp; a_ {1} amp; a_ {0} \\ r amp;amp; b_ {n-1} \ cdot r amp; \ dots amp; b_ {1} \ cdot r amp; b_ {0} \ cdot r \\\ hline amp; a_ {n} amp; b_ {n-1} \ cdot r + a_ {n-1} amp; \ dots amp; b_ {1} \ cdot r + a_ { 1} amp; a_ {0} + b_ {0} \ cdot r \\ amp; = b_ {n-1} amp; = b_ {n-2} amp; \ dots amp; = b_ {0} amp; = R \\\ end {массив }}}$

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

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

Позволять:

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

${\ Displaystyle Q (х) = х + 1. \, \!}$

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

${\ Displaystyle Q (х) = х + 1 = х - (- 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 |{result coefficients}{remainder}

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

${\ Displaystyle Р (х) = Q (х) р (х) + s \, \!}$, где

${\ Displaystyle R (х) = 2x ^ {2} + х-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 1 x + a 0, все коэффициенты которого (от a n до a 0) являются целыми числами, реальные рациональные корни всегда вид р / д, где р представляет собой целое число делитель в 0 и Q представляет собой целое число делителя в п. Таким образом, если наш многочлен

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

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

${\ displaystyle {\ text {Возможные корни:}} \ left \ {+ 1, -1, + 2, -2 \ right \}.}$

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

Следовательно, полагая 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 1: правило Руффини может быть применено для определения

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

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

Р ( х) = ( х - г 1) Q ( х)

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Q (-1) = 0 → х 2 = -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 \ {{\ t_dv {корни}} P (x) \ in \ mathbb {Q} \ right \} \, \!}$ найденные корни, тогда рассмотрим продукт

${\ Displaystyle R (x) = a_ {n} {\ prod (xr)} {\ t_dv {для всех}} r \ in R. \, \!}$

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

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

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

${\ Displaystyle Р (х) = р (х) \ CDOT S (х). \, \!}$

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

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

Позволять

${\ Displaystyle Р (х) = х ^ {3} + 2x ^ {2} -x-2. \, \!}$

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

${\ Displaystyle R = \ влево \ {+ 1, -1, -2 \ вправо \}. \, \!}$

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

${\ Displaystyle R (х) = 1 (х-1) (х + 1) (х + 2). \, \!}$

И P ( x) / R ( x):

${\ Displaystyle S (х) = 1. \, \!}$

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

${\ Displaystyle Р (х) = (х-1) (х + 1) (х + 2). \, \!}$

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

Позволять

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

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

${\ Displaystyle R = \ влево \ {- 1, + 2 \ вправо \}. \, \!}$

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

${\ Displaystyle R (х) = (х + 1) (х-2). \, \!}$

И P ( x) / R ( x)

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

При факторизованном многочлене P ( x) = R ( x) S ( x): ${\ Displaystyle S (х) {\ 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 году.

• Метод Лилла, выполняющий деление графически
• Метод Хорнера
• Полиномиальное деление в столбик

1. ^ Каджори, Флориан (1911). "Метод приближения Хорнера, предвиденный Руффини" (PDF). Бюллетень Американского математического общества. 17 (8): 389–444. DOI : 10.1090 / s0002-9904-1911-02072-9.

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