Рассмотрим частный случай деления многочленов – деление многочлена на двучлен вида x - b₀. Алгоритм деления для этого случая называется схемой Горнера или методом сокращенного деления многочлена на двучлен. Пусть требуется поделить многочлен
на двучлен b(x) = x - b₀, то есть требуется представить многочлен a(x) в виде
a(x)=b(x)*c(x) + r(x), где степень частного c(x) равна n-1, а степень остатка r(x) равна 0. Пусть
То есть Перемножим x - b₀ и c(x), сложим с r₀ и приравняем коэффициенты многочленов при одинаковых степенях x в левой и правой частях равенства:
a₀=c₁,
a₁=c₂ - c₁*b₀,
...
a_n-2=c_n-1 - c_n-2*b₀,
a_n-1=c_n - c_n-1*b₀,
a_n=r₀ - c_n*b₀,

Из этих равенств получим рекуррентные формулы для определения значений c_i и остатка r₀.
c₁=a₀,
c₂=a₁ + c₁*b₀,
...
c_n-1=a_n-2 + c_n-2*b₀,
c_n=a_n-1 + c_n-1*b₀,
r₀=a₀ + c_n*b₀.

Для удобства вычислений по этим формулам создается таблица, заполняемая слева направо.
В первой строке записываются коэффициенты делимого в порядке убывания степеней x и число b₀.
Во второй строке - соответствующие значения выражений с_i*b₀ (первое число 0, так как c₀=0).
Числа в первой строке складываются с числами во второй и записываются в третью строку. В результате в третьей строке мы получаем коэффициенты частного, а последнее число – это остаток.



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

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

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

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

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

Это число опять умножаем на последнее число первой строки 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

Ответ:

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

Рассмотрим еще одно применение схемы Горнера – разложение многочлена по степеням двучлена. Для любого многочлена где a₀ ≠ 0, n ≥ 1, и для любого числа b₀ можно написать разложение a(x) по степеням x - b₀:
Как видно из этой формулы, чтобы вычислить p_n, необходимо разделить многочлен a(x) на x - b₀ и найти остаток r = p_n . В частном мы получим многочлен


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


Далее продолжаем деление до тех пор, пока в частном не получится число. Полученный на последнем шаге остаток будет равен p₁, а частное d_n=p₀.
На каждом шаге деление на 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.