Пусть требуется поделить многочлен

a(x)= a_n*xⁿ + a_n-1*x^n-1 + a_n-2*x^n-2 + ... + a₁*x + a₀

на двучлен b(x)= x - b₀, то есть требуется представить многочлен a(x) в виде

a(x)=b(x)*c(x) + r(x), где степень частного c(x) равна n-1, а степень остатка r(x) равна 0. Пусть

c(x)= c_n-1*x^n-1 + c_n-2*x^n-2 +  ... + c₁*x + c₀,

r(x)=r₀.

То есть a(x) = (x - b₀)*(c_n-1*x^n-1 + c_n-2*x^n-2 +  ... + c₁*x + c₀) + r₀.

Перемножим x - b₀ и c(x), сложим с r₀ и приравняем коэффициенты многочленов при одинаковых степенях x в левой и правой частях равенства. Получим рекуррентные формулы для определения значений c_i и остатка r₀.

c_n-1=a₀,

c_n-2=a₁ + c_n-1*b₀,

...

c₁=a_n-2 + c₂*b₀,

c₀=a_n-1 + c₁*b₀,

r₀=a_n + c₀*b₀. Для удобства вычислений по этим формулам создается таблица, заполняемая слева направо.

В первой строке записываются коэффициенты делимого в порядке убывания степеней x и число b₀.

Во второй строке - соответствующие значения выражений с_i*b₀ (первое число 0, так как c_n=0).

Числа в первой строке складываются с числами во второй и записываются в третью строку. В результате в третьей строке мы получаем коэффициенты частного, а последнее число – это остаток.



Заполняют эту таблицу в таком порядке:

Сначала заполняют первую строку. Под первым числом первой строки пишем 0.

Складываем числа в первом столбце, и результат будет первым числом третьей строки.

Затем первое число третьей строки c_n-1 умножаем на последнее число первой строки b₀, результат записываем на второе место второй строки.

Складываем числа второго столбца и получаем второе число третьей строки c_n-2.

Это число опять умножаем на последнее число первой строки b₀, результат записываем на третье место во второй строке.

Складываем числа третьего столбца, и получаем третье число третьей строки и т.д.

Хотя объяснение выглядит довольно громоздким, но выполнять деление с помощью схемы Горнера очень просто и удобно. Рассмотрим применение схемы Горнера на примерах.

Пример 1. Разделить многочлен x⁴ - 3x³ - 3x² + 7x + 6 на двучлен x-3 используя схему Горнера.

Решение.

Делимое a(x)=x⁴ - 3x³ - 3x² + 7x + 6, b₀=3. В соответствии со схемой Горнера заполняем таблицу



Таким образом, остаток r (это последнее число в третьей строке) равен нулю. Значит, многочлен x⁴ - 3x³ - 3x² + 7x + 6 разделился на x - 3 нацело. Частное с(x)=1*x³ + 0*x² - 3x - 2.

Ответ: x⁴ - 3x³ - 3x² + 7x + 6=(x³ - 3x - 2)*(x - 3).

Пример 2. Разделить многочлен 2x⁵ + 5x⁴ - 4x³ + 612 на двучлен x + 4 используя схему Горнера.

Решение.

Делимое a(x)= 2x⁵ + 5x⁴ - 4x³ + 612, b₀=-4. В соответствии со схемой Горнера заполняем таблицу



Остаток r = 100 - это последнее число в третьей строке. Частное с(x)=2*x⁴ - 3*x³ - 8*x² - 32*x + 128.

Ответ: 2x⁵ + 5x⁴ - 4x³ + 612 = (2x⁴ - 3x³ - 8x² - 32x + 128)*(x + 4) + 100.

Деление многочлена a(x) на двучлен вида b₁ x - b₀ легко сводится к случаю деления на x - b₀.

Пусть a(x) = (b₁x - b₀)* c(x) + r₀, можно преобразовать это выражение



Анализ последнего выражения показывает, что остаток от деления a(x) на b₁x - b₀ тот же самый, что и остаток от деления a(x) на x - b₀/b₁, а коэффициенты частного c(x) получаются из коэффициентов частного от деления на x - b₀/b₁ делением их на b₁.

Пример 3. Разделить многочлен x³ - 6x² + 5x + 2 на двучлен 2x + 1 используя схему Горнера.

Решение.

Так как 2x + 1=2(x + 1/2), с помощью схемы Горнера будем делить исходный многочлен на x + 1/2, затем полученные коэффициенты частного разделим на 2.



Остаток r₀ = -17/8. Коэффициенты частного получим, разделив коэффициенты в третьей строке таблицы на 2. Таким образом, частное от деления исходного многочлена на 2x + 1



Ответ:


Пример 4. Разделить многочлен x⁵ - x³ + 2x - 1 на двучлен 3 - 2x.

Решение.

Так как 3 - 2x = - 2(x - 3/2), с помощью схемы Горнера будем делить исходный многочлен на x - 3/2, затем полученные коэффициенты частного разделим на -2.



Остаток r₀ = 199/32. Коэффициенты частного получим, разделив коэффициенты в третьей строке таблицы на -2. Таким образом, частное от деления исходного многочлена на 3 - 2x



Ответ:

Использование схемы Горнера для разложения многочлена по степеням двучлена

Рассмотрим еще одно применение схемы Горнера – разложение многочлена по степеням двучлена. Для любого многочлена

где и для любого числа b₀ можно написать разложение a(x) по степеням x - b₀:



Как видно из этой формулы, чтобы вычислить p₀, необходимо разделить многочлен a(x) на x - b₀ и найти остаток r = p₀ . В частном мы получим многочлен



Теперь, чтобы вычислить p₁, необходимо разделить многочлен d₁ (x) на x - b₀ и найти остаток r=p₁. В частном получим многочлен

Далее продолжаем деление до тех пор, пока в частном не получится число. Полученный на последнем шаге остаток будет равен p_n-1, а частное d_n=p_n.

На каждом шаге деление на x - b₀ будем проводить с помощью схемы Горнера. При этом очень удобно результаты вычислений записывать в одну общую таблицу. Рассмотрим соответствующие примеры.

Пример 5. Разложить многочлен 2x⁴ + x³ - 5x + 3 по степеням двучлена x + 1.

Решение.

Все вычисления проведем, последовательно заполняя таблицу в соответствии с алгоритмом.

Таким образом, получаем, что остаток от деления исходного многочлена на x+1 равен 9, коэффициенты частного 2,-7,9,-10.

Ответ: 2x⁴ + x³ - 5x + 3 = 2(x + 1)⁴ - 7(x + 1)³ + 9(x + 1)² - 10(x + 1) + 9.

Вычисление значения многочлена в заданной точке с помощью схемы Горнера

Еще одна задача, которую можно решать с помощью схемы Горнера – вычисление значения многочлена в заданной точке. Пусть многочлен a(x) делится на двучлен x - b₀ с остатком r₀. То есть



Если в это равенство подставить значение x=b₀, получим a(b₀)=r₀. Таким образом, мы доказали теорему Безу.

Теорема Безу. Если x₀ - произвольное число, то при делении многочлена a(x) на двучлен x-x₀ получается остаток, равный значению многочлена при x=x₀, то есть r₀= a(x₀).

Таким образом, с помощью схемы Горнера можно находить значение многочлена при заданном значении x=x₀ как остаток от деления этого многочлена на двучлен x-x₀. Иногда это сделать гораздо проще, чем подставлять x₀ в исходный многочлен.

У теоремы Безу есть очень важное следствие.

Следствие. Число x₀ является корнем многочлена a(x) тогда и только тогда, когда многочлен a(x) делится нацело на двучлен x-x₀.

Это следствие позволяет проверять, является ли число x₀ корнем многочлена, вычисляя остаток от деления многочлена на двучлен x-x₀.

Пример 6. Вычислить значение многочлена 2x⁶ + 6x⁵ + x⁴ - 4x³ + 3x² - x - 1 при x=-3.

Решение.

Вычислить значение многочлена при x=-3 равносильно найти остаток при делении этого многочлена на x+3. Для этого воспользуемся схемой Горнера



Остаток r (это последнее число в третьей строке) равен 218.

(Частное с(x)=2x⁵ + x³ - 7x² + 24x - 73;
2x⁶ + 6x⁵ + x⁴ - 4x³ + 3x² - x - 1=(2x⁵ + x³ - 7x² + 24x - 73)*(x+3)+218).

Ответ: 218.