Сдвиг аргументов многочлена по схеме Горнера, вещественная версия, последовательный вариант
Описание свойств и структуры алгоритма[править]
Словесное описание алгоритма[править]
Решаемая задача[править]
Для данного многочлена
- [math]\displaystyle{ P_n(x) = a_0 x^n + a_1 x^{n - 1} + \dots + a_{n - 1} x + a_n }[/math]
с данного скаляра [math]\displaystyle{ \alpha }[/math] нужно выписать этот же многочлен по степеням [math]\displaystyle{ x - \alpha }[/math], то есть представить его в виде
- [math]\displaystyle{ P_n(x) = b_0 (x - \alpha)^n + b_1 (x - \alpha)^{n - 1} + \dots + b_{n - 1} (x - \alpha) + b_n }[/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) = (x - \alpha) Q_{n - 1}(x)+P_n(\alpha) }[/math]
видно, что [math]\displaystyle{ b_n = P_n(\alpha) }[/math]. Разделив многочлен на [math]\displaystyle{ x - \alpha }[/math] по схеме Горнера, мы находим последний искомый коэффициент, а также видим, что остальная часть равна [math]\displaystyle{ (x - \alpha) Q_{n - 1}(x) }[/math]. Поэтому достаточно применять схему Горнера к многочленам-«частным», чтобы получить в конце все искомые коэффициенты.
Вычислительное ядро алгоритма[править]
Вычислительное ядро сдвига аргументов многочлена по схеме Горнера в последовательном варианте можно представить как в качестве последовательного применения [math]\displaystyle{ n }[/math] схем Горнера с уменьшающимся порядком, так и в качестве набора [math]\displaystyle{ \frac{n (n + 1)}{2} }[/math] «двойных» операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).
Макроструктура алгоритма[править]
Как уже записано в описании ядра алгоритма, основную часть сдвига аргументов многочлена по схеме Горнера в последовательном варианте можно представить как в качестве последовательного применения [math]\displaystyle{ n }[/math] схем Горнера с уменьшающимся порядком, так и в качестве набора [math]\displaystyle{ \frac{n (n + 1)}{2} }[/math] «двойных» операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).
Описание схемы реализации последовательного алгоритма[править]
Схема метода описана выше. Последовательность исполнения - по возрастанию индексов, с укорачиванием внутреннего цикла. Простейшая программа приведена в разделе «Особенности реализации последовательного алгоритма».
Последовательная сложность алгоритма[править]
Для вычисления сдвига аргументов многочлена по схеме Горнера для многочлена степени [math]\displaystyle{ n }[/math], количество операций умножения равно количеству операций сложения и равно [math]\displaystyle{ \frac{n (n + 1)}{2} }[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам квадратичной сложности по количеству последовательных операций.
Информационный граф[править]
Опишем граф алгоритма в виде рисунка. Изображён граф для [math]\displaystyle{ n = 9 }[/math]. Как видно, граф регулярный, занимает собой треугольную область. Каждая вершина соответствует операции [math]\displaystyle{ c d + e }[/math].
Описание ресурса параллелизма алгоритма[править]
Последовательный вариант вычисления сдвига аргументов многочлена по схеме Горнера, несмотря на название, имеет хороший ресурс параллелизма. В получившемся алгоритме высота параллельной формы будет равна [math]\displaystyle{ n }[/math] операций умножения плюс [math]\displaystyle{ n }[/math] операций сложения (и равна, таким образом, высоте одной схемы Горнера). В таком виде алгоритм должен быть отнесён к алгоритмам линейной сложности по высоте параллельной формы. Ширина параллельной формы равна [math]\displaystyle{ n }[/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].
Свойства алгоритма[править]
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является линейной функцией [math]\displaystyle{ \frac{(n + 1)}{2} }[/math]. При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — также [math]\displaystyle{ \frac{(n + 1)}{2} }[/math]. При этом алгоритм полностью детерминирован. Дуги информационного графа локальны и регулярны.
Программная реализация[править]
Особенности реализации последовательного алгоритма[править]
На Фортране алгоритм можно записать так:
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]\displaystyle{ n }[/math] может оказаться полезным использовать блочную версию алгоритма, чтобы эффективно использовать кэш. Аналогичное соображение следует применять и для параллельных версий.