Схема горнера (или правило Горнера, метод Руффини-Горнера)

СХЕМА ГОРНЕРА
Схема Горнера (или правило Горнера, метод Горнера, метод Руффини-Горнера) – алгоритм вычисления значения многочлена, записанного в виде суммы мономов (одночленов), при заданном значении переменной. Метод Горнера позволяет найти корни многочлена[1], а также вычислить производные полинома в заданной точке. Схема Горнера также является простым алгоритмом для деления многочлена на бином вида
Метод назван в честь Уильяма Джорджа Горнера, однако Паоло Руффини опередил Горнера на 15 лет, а китайцам этот способ был известен еще в XIII веке.


ОПИСАНИЕ АЛГОРИТМА
Задан многочлен

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

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

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

ИСПОЛЬЗОВАНИЕ СХЕМЫ ГОРНЕРА ДЛЯ ДЕЛЕНИЯ МНОГОЧЛЕНА НА БИНОМ
При делении многочлена на получается многочлен
с остатком (см. теорема Безу).
При этом коэффициенты результирующего многочлена удовлетворяют рекуррентным соотношениям

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

�(�)=��+��−1(�−�)+��−2(�−�)2+⋯+�0(�−�)�.Схема Горнера может использоваться для нахождения производных многочлена:

ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ
Рассчитать  �(�)=2�3−6�2+2�−1 для  . �=3.Используем синтетическое деление:

Здесь в первой строке записаны значение �0x₀ и коэффициенты многочлена.
Значения (по столбцам) в третьей строке соответствуют сумме значений первой и второй строки ( ��−1=��−1+���0), а значения второй строки произведению x на значение в третьей строке предыдущего столбца ( ���0).
Например, если �3=2,�2=−6,�1=2,�0=−1a₃= 2, a₂ = – 6, a₁= 2, a₀= –1 мы видим, что �3=2,�2=0,�1=2,�0=5 b₃= 2, b₂ = 0, b₁ = 2, b₀ = 5 – значения в третьей строке. Так синтетическое деление базируется на методе Горнера.