Схема Горнера

Схема Горнера - один из простейших способов деления многочлена на бином x-a. Конечно, делением применение схемы Горнера не исчерпывается, но для начала рассмотрим именно это. Применение алгоритма поясним на примерах. Разделим на . Составим таблицу из двух строк: в первой строке запишем коэффициенты многочлена по убыванию степеней переменной. Заметьте, что данный многочлен не содержит х, т.е. коэффициент перед х равен 0. Так как мы делим на , во второй строке запишем единицу:

Начнем заполнять пустые ячейки во второй строке. В первую пустую ячейку запишем 5, просто перенеся ее из соответствующей ячейки первой строки:

Следующую ячейку заполним по такому принципу:

Аналогично заполним и четвертую: :

Для пятой ячейки получим :

И, наконец, для последней, шестой ячейки, имеем :

Задача решена, осталось только записать ответ:

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

Полученный результат говорит также и о том, что 1 является корнем многочлена .

Приведем еще один пример. Разделим многочлен на . Сразу оговорим, что выражение нужно представить в форме . В схеме Горнера будет участвовать именно -3.

Если наша цель - найти все корни многочлена, то схему Горнера можно применять несколько раз подряд, - до тех пор, пока мы не исчерпаем все корни. Например, отыщем все корни многочлена . Целые корни нужно искать среди делителей свободного члена, т.е. среди делителей 8. Т.е., целыми корнями могут быть числа -8, -4, -2, -1, 1, 2, 4, 8. Проверим, к примеру, 1:

Итак, в остатке имеем 0, т.е. единица действительно является корнем данного многочлена. Попробуем проверить единицу еще несколько раз. Новую таблицу для этого создавать не будем, а продолжим использование предыдущей:

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

Итог: .

Конечно, данный метод подбора малоэффективен в общем случае, когда корни не являются целыми числами, но для целых корней метод довольно-таки неплох.