Приложение 5 - История изменений

ASA: Полностью удалено содержимое страницы

2015-09-17T08:11:55Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 08:11, 17 сентября 2015
Строка 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 />~~

ASA в 08:11, 17 сентября 2015

2015-09-17T08:11:29Z

← Предыдущая версия	Версия от 08:11, 17 сентября 2015
Строка 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 />

ASA: Полностью удалено содержимое страницы

2015-09-16T14:01:51Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 14:01, 16 сентября 2015
Строка 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 />~~

ASA в 14:01, 16 сентября 2015

2015-09-16T14:01:21Z

← Предыдущая версия	Версия от 14:01, 16 сентября 2015
Строка 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 />

ASA: Полностью удалено содержимое страницы

2015-09-11T08:05:37Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 08:05, 11 сентября 2015
Строка 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 />~~

ASA: Новая страница: «= Скалярное произведение векторов, вещественная версия, последовательно-параллельный в…»

2015-09-11T08:04:59Z

Новая страница: «= Скалярное произведение векторов, вещественная версия, последовательно-параллельный в…»

Новая страница

= Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант =

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

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

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

Схема Горнера решает задачу деления многочлена <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 />