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

{{level-a}}

{{algorithm
| name              = Схема Горнера для деления многочлена n-й степени на приведённый двучлен
| serial_complexity = <math>2n</math>
| pf_height         = <math>2n</math>
| pf_width          = <math>1</math>
| input_data        = <math>n+2</math>
| output_data       = <math>n+1</math>
}}
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]].

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

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

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

Схема Горнера<ref>Н.Я. Виленкин, Р.С. Гутер, С.И. Шварцбурд, Б.В. Овчинский, В.Г. Ашкинузе. Алгебра. Учебное пособие для 9-10 классов средних школ с математической специализацией. М.: Просвещение, 1972</ref> решает задачу деления многочлена <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 больше, чем количество операций)''. При этом алгоритм полностью детерминирован. Дуги информационного графа локальны. По устойчивости схема Горнера оптимальна для вычисления значения многочлена с известными коэффициентами.

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

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

На Фортране схему Горнера можно записать так:
<source lang="fortran">
	b(0) = a(0)
	DO I = 1, N
		b(I) = a(I)+b(I-1)*alpha
	END DO
</source>

=== Возможные способы и особенности параллельной реализации алгоритма ===

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

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

=== Результаты прогонов ===
=== Выводы для классов архитектур ===

Схема Горнера - метод для архитектуры классического, фон-неймановского типа. Даже на современных суперскалярных одноядерных системах эффективность её исполнения очень низка.

== Литература ==

<references />

[[en: Horners method]]

[[Категория:Законченные статьи]]
[[Категория:Алгоритмы с низким уровнем параллелизма]]