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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Схе́ма Го́рнера (или правило Горнера, метод Горнера) — алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена[1], а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида . Метод назван в честь Уильяма Джорджа Горнера.

Описание алгоритма[править | править вики-текст]

Задан многочлен :

.

Пусть требуется вычислить значение данного многочлена при фиксированном значении . Представим многочлен в следующем виде:

.

Определим следующую последовательность:

Искомое значение есть . Покажем, что это так.

В полученную форму записи подставим и будем вычислять значение выражения, начиная с внутренних скобок. Для этого будем заменять подвыражения через :

Использование схемы Горнера для деления многочлена на бином[править | править вики-текст]

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

При этом коэффициенты результирующего многочлена удовлетворяют рекуррентным соотношениям:

, .

Таким же образом можно определить кратность корней (использовать схему Горнера для нового полинома). Так же схему можно использовать для нахождения коэффициентов при разложении полинома по степеням :

Примечания[править | править вики-текст]

  1. Если целочисленный многочлен обладает целыми корнями, то они будут найдены среди делителей свободного члена. Курош А.Г. §57 Рациональные корни целочисленных многочленов // Курс высшей алгебры. — Наука. — Москва, 1968.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]