|
|
| Строка 1: |
Строка 1: |
| = Схема Горнера, вещественная версия, последовательный вариант =
| |
|
| |
|
| == Свойства и структура алгоритма ==
| |
|
| |
| === Общее описание алгоритма ===
| |
|
| |
| ==== Решаемая задача ====
| |
|
| |
| Схема Горнера решает задачу деления многочлена <math>P_n(x)</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>,
| |
|
| |
| а также <math>P_n(\alpha)</math> (значение многочлена <math>P_n(x)</math> в точке <math>\alpha</math>)
| |
|
| |
| К сожалению, зачастую в учебной литературе схему Горнера сводят к вычислению значения многочлена <math>P_n(x)</math> в точке <math>\alpha</math>.
| |
|
| |
| ==== Общая схема ====
| |
|
| |
| Фактически схема Горнера реализует «деление уголком» многочлена на двучлен <math>x - \alpha</math>, с нахождением остатка, который, по теореме Безу, равен значению многочлена <math>P_n(x)</math> в точке <math>\alpha</math>.
| |
|
| |
| === Математическое описание алгоритма ===
| |
|
| |
| Исходные данные: одномерный массив <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>
| |
|
| |
| что и является '''формулами схемы Горнера'''.
| |
|
| |
| === Вычислительное ядро алгоритма ===
| |
|
| |
| Вычислительное ядро схемы Горнера в последовательном варианте можно представить в качестве последовательного набора <math>n</math> «двойных» операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).
| |
|
| |
| === Макроструктура алгоритма ===
| |
|
| |
| Как уже записано в описании ядра алгоритма, основную часть вычисления схемы Горнера произведения составляет массовый последовательный набор «двойных› операций (умножение элементов получаемого массива на один и тот же скаляр и добавление результата к следующему элементу входного массива).
| |
|
| |
| === Схема реализации последовательного алгоритма ===
| |
|
| |
| Формулы метода описаны выше. Последовательность исполнения — по возрастанию индекса ''k''.
| |
|
| |
| === Последовательная сложность алгоритма ===
| |
|
| |
| Для вычисления схемы Горнера для многочлена степени <math>n</math>, количество операций умножения равно количеству операций сложения и равно <math>n</math>. Поэтому алгоритм должен быть отнесён к алгоритмам ''линейной'' сложности по количеству последовательных операций.
| |
|
| |
| === Информационный граф ===
| |
|
| |
| На рис.1 изображён граф алгоритма для <math>n = 9</math>. Как видно, граф чисто последовательный. Ввод и вывод обозначен только для начального коэффициента и значения многочлена. Op - операция "умножить входное данное на скаляр и прибавить к другому данному".
| |
|
| |
| [[file:Basic sequental algorithm graph.png|center|thumb|800px|Рисунок 1. Схема Горнера: последовательная версия]]
| |
|
| |
| === Ресурс параллелизма алгоритма ===
| |
|
| |
| Последовательный вариант вычисления схемы Горнера не имеет ресурсов параллелизма. Его ярусно-параллельная форма (ЯПФ) — единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет равна <math>n</math> операций умножения плюс <math>n</math> операций сложения. В таком виде алгоритм должен быть отнесён к алгоритмам ''линейной'' сложности по высоте параллельной формы. Ширина параллельной формы равна <math>1</math>, что даёт нам ''постоянную'' сложность по ширине параллельной формы.
| |
|
| |
| === Входные и выходные данные алгоритма ===
| |
|
| |
| Входные данные: массив <math>a</math> (элементы <math>a_i</math> с номерами от <math>0</math> до <math>n</math>), скаляр <math>\alpha</math>.
| |
|
| |
| Дополнительные ограничения: отсутствуют.
| |
|
| |
| Объём входных данных: <nowiki/><math>n + 2</math>.
| |
|
| |
| Выходные данные: массив <math>b</math> (элементы <math>b_k</math> с номерами от <math>0</math> до <math>n</math>).
| |
|
| |
| Объём выходных данных: <nowiki/><math>n + 1</math>.
| |
|
| |
| === Свойства алгоритма ===
| |
|
| |
| Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''константой'' (1). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего ''1 (входных и выходных данных даже на 1 больше, чем количество операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа локальны. По устойчивости схема Горнера оптимальна для вычисления значения многочлена с известными коэффициентами.
| |
|
| |
| == Литература ==
| |
| <references />
| |