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

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

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

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

Для данного многочлена

[math]P_n(x) = a_0 x^n + a_1 x^{n - 1} + \dots + a_{n - 1} x + a_n[/math]

с данного скаляра [math]\alpha[/math] нужно выписать этот же многочлен по степеням [math]x - \alpha[/math], то есть представить его в виде

[math]P_n(x) = b_0 (x - \alpha)^n + b_1 (x - \alpha)^{n - 1} + \dots + b_{n - 1} (x - \alpha) + b_n[/math]

1.1.2 Общая схема

Решение задачи с помощью схемы Горнера состоит в последовательном применении её и вычисления коэффициентов.

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) = (x - \alpha) Q_{n - 1}(x)+P_n(\alpha)[/math]

видно, что [math]b_n = P_n(\alpha)[/math]. Разделив многочлен на [math]x - \alpha[/math] по схеме Горнера, мы находим последний искомый коэффициент, а также видим, что остальная часть равна [math](x - \alpha) Q_{n - 1}(x)[/math]. Поэтому достаточно применять схему Горнера к многочленам-«частным», чтобы получить в конце все искомые коэффициенты.

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

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

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

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

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

Схема метода описана выше. Последовательность исполнения - по возрастанию индексов, с укорачиванием внутреннего цикла. Простейшая программа приведена в разделе «Особенности реализации последовательного алгоритма».

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

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

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

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

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

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

Последовательный вариант вычисления сдвига аргументов многочлена по схеме Горнера, несмотря на название, имеет хороший ресурс параллелизма. В получившемся алгоритме высота параллельной формы будет равна [math]n[/math] операций умножения плюс [math]n[/math] операций сложения (и равна, таким образом, высоте одной схемы Горнера). В таком виде алгоритм должен быть отнесён к алгоритмам линейной сложности по высоте параллельной формы. Ширина параллельной формы равна [math]n[/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 Свойства алгоритма

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является линейной функцией [math]\frac{(n + 1)}{2}[/math]. При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — также [math]\frac{(n + 1)}{2}[/math]. При этом алгоритм полностью детерминирован. Дуги информационного графа локальны и регулярны.

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

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

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

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

При больших [math]n[/math] может оказаться полезным использовать блочную версию алгоритма, чтобы эффективно использовать кэш. Аналогичное соображение следует применять и для параллельных версий.