Приложение 5: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
(Полностью удалено содержимое страницы)
Строка 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 />

Версия 11:11, 17 сентября 2015

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

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

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

1.1.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].

1.1.1.2 Общая схема

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

1.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.1.3 Вычислительное ядро алгоритма

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

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

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

1.1.5 Схема реализации последовательного алгоритма

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

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

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

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

На рис.1 изображён граф алгоритма для [math]n = 9[/math]. Как видно, граф чисто последовательный. Ввод и вывод обозначен только для начального коэффициента и значения многочлена. Op - операция "умножить входное данное на скаляр и прибавить к другому данному".

Рисунок 1. Схема Горнера: последовательная версия

1.1.8 Ресурс параллелизма алгоритма

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

1.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.1.10 Свойства алгоритма

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

1.2 Литература

Источник — https://algowiki-project.org/w/ru/index.php?title=Приложение_5&oldid=2543