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

Разделим  �3−6�2+11�−6 на  �−2:

Новый многочлен  �2−4�+3.
Пусть �1(�)=4�4−6�3+3�−5 �(�)=2�3−6�2+2�−1 и  �2(�)=2�−1. Разделим �1(�)  на  , �2(�)используя метод Горнера.

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

Также с помощью схемы Горнера можно вычислять значение числа в позиционной системе исчисления.
Примечания
Если целочисленный многочлен обладает целыми корнями, то они будут найдены среди делителей свободного члена. Курош А. Г. § 57. Рациональные корни целочисленных многочленов // Курс высшей алгебры. – Наука. – Москва, 1968. Архивная копия от 18 октября 2013 на Wayback Machine
Литература
1. Левитин А. В. Глава 6. Метод преобразования: Схема Горнера и возведение в степень // Алгоритмы. Введение в разработку и анализ – М.: Вильямс, 2006. – С. 284 – 291. – 576 с. – ISBN 978-5-8459-0987-9
2. Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера // Численные методы. – Учеб. пособие для вузов. – 2-е изд., испр. – М.: Наука, 1987. – 248 с.
3. С. Б. Гашков. § 14. Схема Горнера и перевод из одной позиционной системы в другую // Системы счисления и их применение. – М.: МЦНМО, 2004. – С. 37–39. – (Библиотека «Математическое просвещение»). – ISBN 5-94057-146-8.


§ 14. CХЕМА ГОРНЕРА И ПЕРЕВОД ИЗ ОДНОЙ ПОЗИЦИОННОЙ СИСТЕМЫ В ДРУГУЮ
Использованный в бинарном методе (см. § 2) приём вычисления числа по его двоичной записи является примером более общего алгоритма, называемого схемой Горнера. Схема Горнера – это алгоритм для вычисления частного и остатка от деления многочлена p(x) на х−a. Кратко опишем, как он устроен и как связан с переводом числа из одной системы в другую.
Пусть дан произвольный многочлен .
Деление этого многочлена на x−a — это представление его в виде p(x)=(x−a)h(x)+r, h(x) = v_n−1x_n−1 +...+ v₁x + v₀.
Непосредственно можно проверить, что коэффициенты частного можно найти по формулам v_n−1=u_n, v_n−2=u_n−1+av_n−1, ..., v₀=u₁+av₁, а остаток можно вычислить по формулам
r=u0+av0=u0+a(u1+av1)=u0+a(u1+a(u2+av2))=...
...=u0+a(u1+a(...(un−1+aun)...)=unan+...+u1a+u0=p(a).

Этот метод вычисления и называется схемой Горнера. Слово <схема> в названии алгоритма связано с тем, что обычно его выполнение оформляют следующим образом. Сначала рисуют таблицу 2×(n+2). В левой нижней клетке записывают число a, а в верхней строке — коэффициенты u_n, u_n−1, ... , u₀ многочлена p(x), при этом левую верхнюю клетку оставляют пустой:

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

Число, которое после выполнения алгоритма оказывается записанным в правой нижней клетке, и есть остаток p(a) деления многочлена p(x) на x−a. Другие числа v_n−1, v_n−2, ... нижней строки являются коэффициентами частного.

Например, деление многочлена p(x) = x³ − 2x + 3 на x − 2 по описанному алгоритму выполняется так: