Приложение 5

Схема Горнера, вещественная версия, последовательный вариант

Свойства и структура алгоритма

Общее описание алгоритма

Решаемая задача

Схема Горнера решает задачу деления многочлена [math]\displaystyle{ P_n(x) }[/math] с известными коэффициентами на двучлен [math]\displaystyle{ x - \alpha }[/math]. В качестве результатов выступают коэффициенты многочлена [math]\displaystyle{ Q_{n - 1}(x) }[/math] из соотношения

[math]\displaystyle{ P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x) }[/math],

а также [math]\displaystyle{ P_n(\alpha) }[/math] (значение многочлена [math]\displaystyle{ P_n(x) }[/math] в точке [math]\displaystyle{ \alpha }[/math])

К сожалению, зачастую в учебной литературе схему Горнера сводят к вычислению значения многочлена [math]\displaystyle{ P_n(x) }[/math] в точке [math]\displaystyle{ \alpha }[/math].

Общая схема

Фактически схема Горнера реализует «деление уголком» многочлена на двучлен [math]\displaystyle{ x - \alpha }[/math], с нахождением остатка, который, по теореме Безу, равен значению многочлена [math]\displaystyle{ P_n(x) }[/math] в точке [math]\displaystyle{ \alpha }[/math].

Математическое описание алгоритма

Исходные данные: одномерный массив [math]\displaystyle{ n + 1 }[/math] чисел [math]\displaystyle{ a_k }[/math] и скаляр [math]\displaystyle{ \alpha }[/math].

Вычисляемые данные: одномерный массив [math]\displaystyle{ n + 1 }[/math] чисел [math]\displaystyle{ b_k }[/math].

Формулы метода с выводом: из соотношения

[math]\displaystyle{ P_n(x) - P_n(\alpha) = (x - \alpha) Q_{n - 1}(x) }[/math]

если записать оба многочлена в каноническом виде

[math]\displaystyle{ \begin{align} P_n(x) & = a_0 x^n+ a_1 x^{n - 1} + \dots + a_{n - 1} x + a_n, \\ Q_{n - 1}(x) & = b_0 x^{n - 1} + b_1 x^{n - 2} + \dots + b_{n - 2} x + b_{n - 1} \end{align} }[/math]

и приписать «свободному» [math]\displaystyle{ b_n }[/math] значение [math]\displaystyle{ P_n(\alpha) }[/math], то, при подстановке многочленов в каноническом виде в исходное соотношение и приравнивании коэффициентов равных степеней, в качестве решения получается

[math]\displaystyle{ \begin{align} b_0 & = a_0, \\ b_k & = a_k + \alpha b_{k - 1}, \quad k = 1, \dots, n \end{align} }[/math]

что и является формулами схемы Горнера.

Вычислительное ядро алгоритма

Вычислительное ядро схемы Горнера в последовательном варианте можно представить в качестве последовательного набора [math]\displaystyle{ n }[/math] «двойных» операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).

Макроструктура алгоритма

Как уже записано в описании ядра алгоритма, основную часть вычисления схемы Горнера произведения составляет массовый последовательный набор «двойных› операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).

Схема реализации последовательного алгоритма

Формулы метода описаны выше. Последовательность исполнения — по возрастанию индекса k.

Последовательная сложность алгоритма

Для вычисления схемы Горнера для многочлена степени [math]\displaystyle{ n }[/math], количество операций умножения равно количеству операций сложения и равно [math]\displaystyle{ n }[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.

Информационный граф

На рис.1 изображён граф алгоритма для [math]\displaystyle{ n = 9 }[/math]. Как видно, граф чисто последовательный. Ввод и вывод обозначен только для начального коэффициента и значения многочлена. Op - операция "умножить входное данное на скаляр и прибавить к другому данному".

Рисунок 1. Схема Горнера: последовательная версия

Ресурс параллелизма алгоритма

Последовательный вариант вычисления схемы Горнера не имеет ресурсов параллелизма. Его ярусно-параллельная форма (ЯПФ) — единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет равна [math]\displaystyle{ n }[/math] операций умножения плюс [math]\displaystyle{ n }[/math] операций сложения. В таком виде алгоритм должен быть отнесён к алгоритмам линейной сложности по высоте параллельной формы. Ширина параллельной формы равна [math]\displaystyle{ 1 }[/math], что даёт нам постоянную сложность по ширине параллельной формы.

Входные и выходные данные алгоритма

Входные данные: массив [math]\displaystyle{ a }[/math] (элементы [math]\displaystyle{ a_i }[/math] с номерами от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ n }[/math]), скаляр [math]\displaystyle{ \alpha }[/math].

Дополнительные ограничения: отсутствуют.

Объём входных данных: [math]\displaystyle{ n + 2 }[/math].

Выходные данные: массив [math]\displaystyle{ b }[/math] (элементы [math]\displaystyle{ b_k }[/math] с номерами от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ n }[/math]).

Объём выходных данных: [math]\displaystyle{ n + 1 }[/math].

Свойства алгоритма

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является константой (1). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 1 (входных и выходных данных даже на 1 больше, чем количество операций). При этом алгоритм полностью детерминирован. Дуги информационного графа локальны. По устойчивости схема Горнера оптимальна для вычисления значения многочлена с известными коэффициентами.