Схема Горнера в математике¶

Схема Горнера — алгоритм вычисления значения многочлена одной переменной и деления многочлена на линейный двучлен вида \(x - c\), основанный на последовательном вычислении коэффициентов по рекуррентной формуле. Метод назван по имени британского математика Уильяма Джорджа Горнера (1786–1837), опубликовавшего его в 1819 году, хотя сходные приёмы встречаются в работах итальянца Паоло Руффини (1804) и в китайских источниках XIII века. Схема широко применяется в вычислительной математике, алгебре и программировании благодаря минимальному числу арифметических операций.

¶Суть метода

Пусть задан многочлен степени \(n\):

\(P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0\).

Требуется вычислить \(P(c)\) для заданного числа \(c\). Наивный способ требует возведения в степень и \(2n-1\) умножений и \(n\) сложений. Схема Горнера переписывает многочлен в эквивалентной форме:

\(P(x) = a_0 + x(a_1 + x(a_2 + \dots + x(a_{n-1} + a_n x)\dots))\).

Вычисления ведутся по рекуррентной формуле: \(b_n = a_n\), \(b_{k} = a_k + c \cdot b_{k+1}\) для \(k = n-1, \dots, 0\). Итоговое значение \(b_0\) равно \(P(c)\). Число операций сокращается до \(n\) умножений и \(n\) сложений, что существенно при больших степенях.

¶Табличная запись

На практике схему оформляют таблицей, где в первой строке выписывают коэффициенты многочлена, а во второй — промежуточные значения.

Каждое следующее число получается умножением предыдущего результата на \(c\) и прибавлением очередного коэффициента.

¶Деление на двучлен

Схема Горнера одновременно решает задачу деления многочлена \(P(x)\) на \(x - c\). По теореме Безу остаток от такого деления равен \(P(c)\), то есть последнему числу \(b_0\). Частное представляет собой многочлен степени \(n-1\) с коэффициентами \(b_n, b_{n-1}, \dots, b_1\). Это свойство делает схему основным инструментом при разложении многочлена на множители и поиске корней.

Если \(P(c) = 0\), то \(c\) — корень многочлена, а \(x - c\) — его делитель. Повторное применение схемы позволяет выделять кратные корни и понижать степень, что используется в алгоритмах решения алгебраических уравнений.

¶Пример

Рассмотрим \(P(x) = 2x^3 - 6x^2 + 2x - 1\) и \(c = 3\).

Промежуточные шаги: \(2\); \(2 \cdot 3 + (-6) = 0\); \(0 \cdot 3 + 2 = 2\); \(2 \cdot 3 + (-1) = 5\). Значит, \(P(3) = 5\), а частное от деления на \(x - 3\) равно \(2x^2 + 0x + 2\).

¶Применение

• Вычисление значений многочленов в численных методах, в том числе при интерполяции и аппроксимации функций.
• Поиск корней: подбор целых и рациональных корней многочленов с целыми коэффициентами.
• Разложение на множители и приведение многочленов к каноническому виду.
• Перевод чисел между системами счисления: схема эквивалентна алгоритму перевода из позиционной системы по основанию \(c\) в десятичную.
• Программирование: реализуется одним циклом, легко векторизуется и применяется в библиотеках компьютерной алгебры.
• Схема Горнера — Руффини в теории многочленов и в анализе устойчивости систем.

¶Вычислительные свойства

Метод обладает высокой численной устойчивостью для многих практических задач и требует \(O(n)\) операций и \(O(1)\) дополнительной памяти при вычислении значения. В отличие от прямого вычисления степеней, схема Горнера снижает накопление погрешностей округления при работе с плавающей запятой. Существуют обобщения: деление на многочлен произвольной степени, вычисление производных, работа с матричными коэффициентами.

¶История

Приём, известный как схема Горнера, встречается в китайском трактате «Математика в девяти книгах» и в трудах Цинь Цзюшао (1247). В Европе метод описал Паоло Руффини в 1804 году, а Уильям Горнер независимо изложил его в 1819 году в работе, посвящённой численному решению уравнений. В русскоязычной литературе закрепилось название «схема Горнера», хотя в зарубежных источниках часто используется термин «метод Горнера — Руффини» или «синтетическое деление».

¶Обобщения

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

Источники: учебники по алгебре и численным методам, справочная математическая литература, материалы по истории математики.