Разбор схемы Горнера: что это и как работает

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

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

Пусть имеется полином S(х), его надо разделить на многочлен Z(x). Так как операция деления является обратной к операции умножения, задача сводится к нахождению полинома W(х), удовлетворяющего условию S(х)= Z(x)* W(х). Как и в элементарной алгебре, S(х) является делимым, Z(x) делителем, а W(х) — частным. И точно также, Z(x)≠0, так как деление на ноль запрещено.

Делить полиномы между собой можно так же, как и обычные числа — «уголком». Однако, алгоритм деления требует освоения.

Пусть имеется полином . Его требуется поделить столбиком на бином х+1. Надо записать полиномы по обычной форме:

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

Следующий шаг — подбор такого одночлена, что при умножении его на х (первое слагаемое бинома) получился x³. Это будет x² — его надо записать в поле частного.

Затем умножим x² на делитель и запишем получившийся полином x³+x² под делимым.

Далее по известному с начальных классов порядку ставится знак минус проводится горизонтальная черта и производится вычитание.

Дальше шаги повторяются, только в качестве делимого уже будет 5x²+11x+6:

·                   подбор такого множителя, чтобы первое слагаемое бинома совпало с первым слагаемым делимого (очевидно, что это  5x);

·                   умножение этого множителя на делитель (результат — 5x²+5x);

·                   вычитание одного полинома из другого.

Этот алгоритм повторяется снова и снова, пока в остатке получится ноль.

Следовательно, один полином без остатка делится на другой. Эта ситуация встречается не всегда, поэтому деление надо остановить тогда, когда степень делимого станет меньше степени делителя. Получившееся число будет остатком от деления. В приведенном ниже примере таким остатком будет двучлен -6х+24.

Однако в математике разработаны методы, позволяющие выполнять деление и нахождение остатка более простыми и менее громоздкими способами, чем непосредственное вычисление «углом«. Основным математическим утверждением, используемом при операциях деления полиномов, является теорема Безу для многочленов. Наиболее ее распространенная формулировка гласит, что остаток r от деления полинома  на бином Z(x)=(х-а) равен значению этого многочлена в точке а: r=S(a). Для доказательства подставим в выражение в теореме х=a: S(a)= Z(a)*(х-a)+r. Так как (a—a)=0, то S(a)=r. Это означает, что теорема доказана.

На практике применяется не только и не столько теорема Безу, но и следствия из нее.

1. Если остаток r равен нулю, значит деление S(x)  на бином (х-a) получилось без остатка, а это возможно только в том случае, если число a является корнем полинома S(x).
2. Другое следствие теоремы Безу — свободный член a нацело делится на любой целый корень полинома S(x), если множители при переменных полинома целые.
3. Теорема применима не только к биномам вида (х-a), но и к произвольным двучленам вида кх+b.

Чтобы вычислить значение многочлена при заданном значении переменной, можно воспользоваться прямой подстановкой. Она предполагает несколько операций возведения в степень, несколько операций перемножения и сложения. Если выбранное значение не подходит под условия теоремы Безу (остаток не равен нулю), придется выбирать новое значение а и продолжать прямые вычисления. Это потребуется, например, при разложении многочлена на множители. Суть этой операции в том, что при делении многочлена R(x) на бином х-a без остатка R(а)=0), получается запись R(х)=Е(х)*(х-a). Это означает, что мы разложили исходный полином на множители.

В общем случае может потребоваться сделать это несколько раз, пока не найдется число, подходящее под условия, что достаточно громоздко и чревато вычислительными ошибками. Хотя следствие 2 во многих случаях ограничивает множество корней. Например, для полинома  список корней ограничивается списком чисел, на которые 48 делится нацело:

• ±1;
• ±2;
• ±3;
• ±4;
• ±6;
• ±8;
• ±12;
• ±16;
• ±24.

Однако и в этой ситуации в самом худшем случае придется перебрать 18 значений переменной.

А можно воспользоваться методом Горнера. Суть метода (который также называют теоремой Горнера) состоит в построении таблицы, состоящей из k+1 столбцов, где k — степень полинома. Обычно предусматривают еще один дополнительный столбец или клетку для записи значения a — точки, в которой считается многочлен. Итак, имеется полином вида . Запишем в верхнюю строчку множители при переменной, записанные по убыванию степеней. В левой клетке записано значение х, в котором надо вычислить значение полинома. Таблица примет следующий вид:

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

По этому же принципу высчитывается величина остальных чисел нижней строки и таблица последовательно заполняется вплоть до элемента

Осталась последняя клетка. Формула для нее отличий не имеет и выглядит, как . Но это число можно обозначить, как r. Таблица принимает вид:

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

Полученный результат позволяет записать исходный многочлен в виде .  Нумерация множителей  символизирует снижение степени старшей степени переменной  по сравнению с исходной записью. Очевидно, что эта схема является инструментом для деления полинома на бином первой степени. А еще у нее есть замечательное свойство — число r является не только остатком от деления, но и значением многочлена в точке а, вычисленное без операции возведения в степень.

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

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

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

Пример 1.

Найти значение полинома    при значении переменной m=-1.

Составляем и заполняем таблицу по схеме Горнера. Множители в нее вносятся с учетом знака.

	1	6	-7	2	7	-12
-1	1	5	-12	14	-7	-5

Решением является число -5. Можно проверить вычисления, непосредственно подставив в полином -1 вместо m.

Пример 2.

Пусть имеется многочлен 4 степени, записанный как . В данном случае часть коэффициентов равна нулю, то есть . При выполнении схемы Горнера пропускать нулевые коэффициенты исходного полинома нельзя, поэтому таблица все равно должна состоять из  6 столбцов (4+1 плюс ячейка для записи точки a). Найдем значение полинома при переменной x=2.

	8	0	-6	2	0
2	8	16	26	54	108

Проверка непосредственной подстановкой подтверждает верность решения.

Пример 3.

Особенно эффективен метод Горнера для нахождения значений полиномов, если точка х является дробным числом. В этом случае сложность всех арифметических операций «в лоб» многократно возрастает, одновременно возрастает вероятность ошибки.  Например требуется найти значение полинома  в точке 3,5. Составим таблицу.

	6	-5	14	-2	18
3,5	6	16	70	243	868,5

Решение найдено. При вычислении ни разу не пришлось возводить 3,5 в какую-либо степень. 

Пример 4.

Разделить с остатком полином x⁴+3x³+4x²−5x−47 на x+3.

Бином х+3 надо записать в виде x-(-3). Теперь можно выполнить алгоритм Горнера, создав таблицу:

	1	3	4	-5	47
-3	1	0	4	-17	4

Следовательно, неполное частное можно записать в виде x³+4x-17, а остатком будет 4.

Проверим результат, если поделить полиномы столбиком. В поле делимого запишем исходный полином, в поле делителя — x+3. Подберем множитель так, чтобы первые члены делимого и делителя совпали. Это будет x³ — его надо записать в поле частного, а затем умножить на этот одночлен делитель.

Вычитаем полученный результат из делителя.

Подбираем второй член частного, это будет 4х. Умножим делитель на этот одночлен.

Следующим членом делителя будет число -17.

Деление завершено — степень при переменной остатка меньше 1. Полученные результаты совпадают.

Пример 5.

Найти остаток от деления многочлена  на бином , не выполняя операцию деления непосредственно.

Бином G(х) является стандартным двучленом, и в  соответствии с основным тождеством Безу ненулевой остаток от деления будет равен G(3). Решение найдем по схеме Горнера.

	-5	2	-2	7	24
3	-5	-13	-41	-116	-324

Остаток от деления равен — 324.

Пример 6.

Представить полином   как произведение полинома степени 3 на бином z—a.

Задача сводится к разложению исходного выражения на множители. Сначала надо найти решение уравнения . Сделаем это методом перебора потенциальных корней. Так как, вероятно, решение является делителем свободного множителя, то искать его лучше начинать среди значений ±1, ±2, ±5. Выполняем схему Горнера для значения a=1.

	2	9	-10	-27	-10
1	2	11	1	-26	-36

В последней клетке получилось -36 — число, не равное нулю. Значит, единица в качестве корня не подходит. Возьмем а=-1 и снова выполним вычисления по схеме Горнера, заполнив вторую строку в таблице.

	2	9	-10	-27	-10
1	2	11	1	-26	-36
-1	2	7	-17	-10	0

В остатке ноль — следовательно, корень найден, все данные для разложения полинома имеются.  Пользуясь основной теоремой Безу, можно записать исходное выражение в виде  

.

Пример 6.

Разложить на множители многочлен с двумя переменными U(m,t)=tm²+3tm+m-4t-1.

Для решения надо сгруппировать все слагаемые относительно переменной с высшей степенью m:

U(m,t)=tm²+(3t+1)m+(-4t-1). Теперь полином выглядит, как многочлен с одной переменной, где вторая переменная является частью множителей. Можно выполнить разложение Горнера относительно m. Для этого надо подобрать число a так, чтобы U(a) равнялось нулю. Так как множитель содержит переменную, придется действовать методом перебора. Например, подставить 1.

	t	3t+1	-4t-1
1	t	4t+1	0

Здесь успех обеспечила первая же попытка — получился нулевой остаток. Исходный полином переписывается в виде U(m,t)=(tm+4t+1)(m-1). Получившийся результат дальше разложить невозможно, так как это выражение линейно по обеим переменным.

Теорема Безу и схема Горнера в связке являются мощным математическим инструментом, позволяющим упростить многие математические операции с громоздким полиномами высших порядков. Научившись пользоваться, можно развивать навыки решения алгебраических задач и двигаться дальше в изучении математики.