3.1.2. Метод Руффини-Горнера

В этом разделе мы рассмотрим два эффективных алгоритма, которые помогут нам (1) вычислить значение полинома в данной точке и (2) вычислить новый полином где .

Рассмотрим область целостности и полином

из этой области, значение которого в точке мы хотим вычислить. Очевидно, наиболее прямой способ достигнуть этого состоит в том, чтобы заменить на а в выписанном полиномиальном выражении и вычислять каждый член отдельно. Заметим, что это довольно трудоемкий процесс. Существует, однако, другой способ, а именно можно использовать метод Руффини-Горнера. [Он хорошо известен как метод Горнера, но Руффини опередил Горнера на 15 лет; см. статью Кайори (Cajori, 1911).]

Метод Руффини-Горнера для эффективного вычисления работает следующим образом. Положим умножив это равенство на а и прибавив получим Затем,

умножив на а и прибавив получим и т.д. То есть рекурсивная схема этого процесса такова:

и мы получаем вложенную форму

Анализ времени работы метода Руффини-Горнера.

Мы рассмотрим следующие два случая:

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

Случай b. Коэффициенты полинома и точка а принадлежат кольцу целых чисел. В этом случае мы имеем сложений и умножений длинных целых чисел, и, как мы отмечали в разд. 1.2, время умножений доминирует над временем сложений; поэтому мы предполагаем, что только умножаем различных членов на а, где Если — значение наибольшего члена, полученного при выполнении метода Руффини-Горнера, то, очевидно,

Чтобы оценить положим [наибольший по абсолютному значению коэффициент и рассмотрим «наихудший» возможный случай, когда все коэффициенты полинома равны тогда получается из следующей схемы:

То есть наибольший член, получающийся в течение вычислений, — это значение в точке

Однако и, следовательно,

Однако во всех практических приложениях и, поскольку мы имеем

Пример. Вычислим значение полинома в точке работая с целыми числами. Пользуясь методом Руффини-Горнера, получаем

Мы действуем следующим образом. В первой строке выписываем все коэффициенты полинома включая нулевые; старший коэффициент стоит слева. Вторая строка получается так: первый (крайний левый) элемент второй строки — это старший коэффициент полинома Этот первый элемент умножаем на а, прибавляем к произведению второй элемент (первой строки) и записываем сумму как второй элемент второй строки; в нашем примере и мы имеем . В общем случае, чтобы вычислить «следующий» элемент второй строки, умножаем последний вычисленный элемент второй строки на а и прибавляем к произведению «следующий» коэффициент из первой строки. Таким образом, продолжая наш пример, мы имеем что дает

Заметим, что последний элемент второй строки в приведенном примере, — остаток, полученный при делении на . Частное этого деления также вычисляется в упомянутой выше схеме и получается из остальных элементов второй строки; а именно Этот метод известен также как синтетический алгоритм деления.

Рассмотрим теперь в области целостности следующий полином от

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

Используя первое и последнее выражения в мы покажем, что коэффициенты - преобразованного полинома могут быть получены последовательным применением синтетического алгоритма деления.

Мы можем написать

где — полином степени — коэффициент . Если мы выразим в виде

подставим в и приравняем коэффициенты при одинаковых степенях в обеих частях равенства, то получим

что является синтетическим алгоритмом деления, рассмотренным выше. Заметим, что последний коэффициент в точности остаток или коэффициент

Дальнейшее применение того же самого процесса дает

где — полином степени Сочетая мы получаем

Если процесс повторить раз, то получим

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

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

Руффини (1804) Горнер (1819)

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