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

1 Описание свойств и структуры алгоритма

1.1 Словесное описание алгоритма

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

Какую задачу решает схема Горнера? Зачастую в учебной литературе её почему-то сводят к вычислению значения многочлена [math]P_n(x)[/math] в точке [math]\alpha[/math]. Между тем, в процессе вычислений схема Горнера решает попутно ценную задачу деления этого самого многочлена на двучлен [math]x - \alpha[/math], давая в качестве промежуточных результатов коэффициенты многочлена [math]Q_{n - 1}(x)[/math] из соотношения

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

1.1.2 Общая схема

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

1.2 Математическое описание

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

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

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

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

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

[math] \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]b_n[/math] значение [math]P_n(\alpha)[/math], то, подставив канонический вид в исходное соотношение и приравняв коэффициенты соответствующих степеней, в качестве решения получаем:

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

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

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

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

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

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

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

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

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

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

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

Опишем граф алгоритма в виде рисунка. Изображён граф для [math]n = 9[/math]. Как видно, граф чисто последовательный.

Файл:Basic sequental graph.png

800px

1.8 Описание ресурса параллелизма алгоритма

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

1.9 Описание входных и выходных данных

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

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

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

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

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

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

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

2 Программная реализация

2.1 Особенности реализации последовательного алгоритма

На Фортране можно записать так:

	b(0) = a(0)
	DO I = 1, N
		b(I) = a(I)+b(I-1)*alpha
	END DO

2.7 Существующие реализации алгоритма

Помимо выписанной выше простейшей реализации, существуют более примитивные коды, реализующие часть функционала схемы Горнера. Это объясняется тем, что для многих нужно только значение многочлена (остаток от деления), но не нужен многочлен-частное. В таком случае вместо всех элементов массива [math]b[/math] используется один и тот же скаляр.