Метод Горнера для вычисления полиномов

Введение

Алгоритм вычисления значения полинома

В математике и информатике метод Хорнера (или схема Хорнера) — это алгоритм вычисления значения полинома. Хотя этот метод назван в честь Уильяма Джорджа Хорнера, он значительно старше, поскольку сам Хорнер приписывал его Жозефу Луи Лагранжу, а его истоки можно проследить на многие сотни лет назад к китайским и персидским математикам. После появления компьютеров этот алгоритм стал основополагающим для эффективных вычислений с полиномами. Алгоритм основан на правиле Хорнера, в котором полином представляется в вложенной форме:

Это позволяет вычислить значение полинома степени n, используя только *n* умножений и *n-1* сложений. Это оптимально, поскольку существуют полиномы степени n, которые нельзя вычислить с меньшим количеством арифметических операций. Кроме того, метод Хорнера также относится к методу приближенного нахождения корней полиномов, описанному Хорнером в 1819 году. Это вариант метода Ньютона-Рафсона, оптимизированный для ручных вычислений благодаря применению правила Хорнера. Он широко использовался до начала широкого распространения компьютеров примерно в 1970 году.

Эффективность

Оценка с использованием мономиальной формы многочлена степени *n* требует не более *n* сложений и *n* умножений, если степени вычисляются путем повторного умножения и каждый член многочлена вычисляется отдельно. Количество операций можно сократить до *n-1* сложений и *n-1* умножений, вычисляя степени *x* итеративно. Если числовые данные представлены в виде цифр (или битов), то наивный алгоритм также требует хранения приблизительно *n* раз больше битов, чем необходимо для хранения *x*: вычисленный многочлен имеет приблизительную величину, и само *x* также необходимо хранить. В отличие от этого, метод Горнера требует только *n* сложений и *n* умножений, а объем требуемой памяти составляет лишь *n* раз больше, чем количество битов для хранения *x*. Кроме того, метод Горнера можно вычислить с использованием *n* объединенных операций умножения и сложения. Метод Горнера также можно расширить для вычисления первых *k* производных многочлена, используя *k* сложений и *k* умножений. Метод Горнера оптимален в том смысле, что любой алгоритм для вычисления произвольного многочлена требует не менее такого же количества операций. Александр Островский доказал в 1954 году, что количество необходимых сложений минимально. Виктор Пан доказал в 1966 году, что количество необходимых умножений минимально. Однако, если *x* является матрицей, метод Горнера перестает быть оптимальным. Это предполагает, что многочлен вычисляется в мономиальной форме и не допускается предварительная обработка представления, что оправдано, если многочлен вычисляется только один раз. Однако, если предварительная обработка разрешена и многочлен необходимо вычислять многократно, то возможны более быстрые алгоритмы, включающие преобразование представления многочлена. В общем случае, многочлен степени *n* можно вычислить, используя всего +2 умножения и *n* сложений.

Применение к умножению и делению с плавающей запятой

Метод Хорнера — это быстрый и компактный метод умножения и деления двоичных чисел на микроконтроллере, не имеющем аппаратного умножителя. Одно из двоичных чисел, подлежащих умножению, представляется в виде простого полинома, где (используя вышеприведенные обозначения) , а затем x (или x в некоторой степени) последовательно выносится как множитель. В этой двоичной системе счисления (основание 2) , поэтому последовательно выносятся степени числа 2.

Пример

Например, чтобы найти произведение двух чисел (0,15625) и m:

Другие применения

Метод Хорнера может использоваться для преобразования между различными позиционными системами счисления, где x является основанием системы счисления, а коэффициенты ai – цифрами числа в этой системе счисления. Он также применим, если x является матрицей, при этом достигается еще большая вычислительная эффективность. Однако для таких случаев существуют более быстрые методы.

Поиск корней полиномов

Используя алгоритм деления в столбик в сочетании с методом Ньютона, можно приближенно вычислить действительные корни многочлена. Алгоритм работает следующим образом. Для многочлена степени *n* с корнями *r_i* сделайте начальное приближение *x₀* такое, чтобы *f(x₀)* было близко к нулю. Затем итеративно выполняйте следующие два шага:

1. Используя метод Ньютона, найдите наибольший корень *r_k* многочлена *f(x)*, используя приближение *x₀*.
2. Используя метод Горнера, разделите *f(x)* на *(x - r_k)*, чтобы получить многочлен *f₁(x)*.
Вернитесь к шагу 1, но используйте многочлен *f₁(x)* и начальное приближение *x₀*.

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