Повторная прогонка, точечный вариант - История изменений

Frolov: дублирование, редирект после переноса

2016-12-12T07:58:07Z

дублирование, редирект после переноса

VolkovNikita94: Поправил размер n в caption к изображениям ГА, чтобы соответствовало поправленным изображениям ( сделал 7 вместо 8 ).

2016-09-28T10:01:35Z

Поправил размер n в caption к изображениям ГА, чтобы соответствовало поправленным изображениям ( сделал 7 вместо 8 ).

← Предыдущая версия		Версия от 10:01, 28 сентября 2016
Строка 12:		Строка 12:
	== Свойства и структура алгоритма ==		== Свойства и структура алгоритма ==

	[[file:ProgonkaRep.png\|thumb\|right\|200px\|Рисунок 1. Граф алгоритма повторной прогонки при n=8 без отображения входных и выходных данных. '''/''' - деление, '''''f''''' - операция '''''a+bc'''''.]]		[[file:ProgonkaRep.png\|thumb\|right\|200px\|Рисунок 1. Граф алгоритма повторной прогонки при n=7 без отображения входных и выходных данных. '''/''' - деление, '''''f''''' - операция '''''a+bc'''''.]]
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

Строка 20:		Строка 20:

	для того случая, когда ранее уже была выполнена прогонка для СЛАУ с той же матрицей, но с другой правой частью. В этом случае та часть формул прогонки, что связана только с матрицей, уже предвычислена, и повторять её не надо.		для того случая, когда ранее уже была выполнена прогонка для СЛАУ с той же матрицей, но с другой правой частью. В этом случае та часть формул прогонки, что связана только с матрицей, уже предвычислена, и повторять её не надо.
	[[file:ProgonkaRepMul.png\|thumb\|left\|200px\|Рисунок 2. Граф алгоритма повторной прогонки с предвычислением обратных чисел при n=8 без отображения входных и выходных данных. '''m''' - умножение на предвычисленное обратное число, '''''f''''' - операция '''''a+bc'''''.]]		[[file:ProgonkaRepMul.png\|thumb\|left\|200px\|Рисунок 2. Граф алгоритма повторной прогонки с предвычислением обратных чисел при n=7 без отображения входных и выходных данных. '''m''' - умножение на предвычисленное обратное число, '''''f''''' - операция '''''a+bc'''''.]]

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===

ASA в 15:28, 26 февраля 2016

2016-02-26T15:28:34Z

← Предыдущая версия		Версия от 15:28, 26 февраля 2016
Строка 155:		Строка 155:
	[[En:Two-sided elimination method, pointwise version]]		[[En:Two-sided elimination method, pointwise version]]
	[[Категория:Алгоритмы с низким уровнем параллелизма]]		[[Категория:Алгоритмы с низким уровнем параллелизма]]
	[[Категория:~~Статьи в работе~~]]		[[Категория:Законченные статьи]]

Икрамов в 12:57, 31 января 2016

2016-01-31T12:57:03Z

← Предыдущая версия		Версия от 12:57, 31 января 2016
Строка 153:		Строка 153:
	<references />		<references />

			[[En:Two-sided elimination method, pointwise version]]
	[[Категория:Алгоритмы с низким уровнем параллелизма]]		[[Категория:Алгоритмы с низким уровнем параллелизма]]
	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

Frolov: /* Общее описание алгоритма */

2015-12-18T13:07:07Z

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

@@ Строка 17: / Строка 17: @@
 '''Повторная прогонка''' - часть метода [[Прогонка, точечный вариант|прогонки]] в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида<ref name="SETKI">Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.</ref>
-:<math>
+{{Шаблон:Трёхдиагональная_СЛАУ_в_сеточном_виде}}
 для того случая, когда ранее уже была выполнена прогонка для СЛАУ с той же матрицей, но с другой правой частью. В этом случае та часть формул прогонки, что связана только с матрицей, уже предвычислена, и повторять её не надо.

Frolov: /* Схема реализации последовательного алгоритма */

2015-12-08T14:45:25Z

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

← Предыдущая версия		Версия от 14:45, 8 декабря 2015
Строка 71:		Строка 71:
	1. Инициализируется прямой ход прогонки:		1. Инициализируется прямой ход прогонки:

	:<math>		<math>\beta_{1} = f_{0}/c_{0}</math>,
	\beta_{1} = f_{0}/c_{0}~~, \\~~
	</math>

	2. Последовательно для всех i от 1 до N-1 выполняются формулы прямого хода:		2. Последовательно для всех i от 1 до N-1 выполняются формулы прямого хода:

Frolov: /* Математическое описание алгоритма */

2015-12-08T14:44:52Z

Математическое описание алгоритма

← Предыдущая версия		Версия от 14:44, 8 декабря 2015
Строка 45:		Строка 45:
	В приведённых обозначениях в повторной прогонке сначала выполняют её прямой ход - вычисляют коэффициенты		В приведённых обозначениях в повторной прогонке сначала выполняют её прямой ход - вычисляют коэффициенты

	:<math>		<math>\beta_{1} = f_{0}/c_{0}</math>,
	\beta_{1} = f_{0}/c_{0}, \\
	\beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i}), \quad i = 1, 2, \cdots , N.		<math>\beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i})</math>, <math>\quad i = 1, 2, \cdots , N</math>.
	</math>
	после чего вычисляют решение с помощью обратного хода		после чего вычисляют решение с помощью обратного хода
	:<math>
	y_{N} = \beta_{N+1}, \\		<math>y_{N} = \beta_{N+1}</math>,
	y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}, \quad i = N-1, N-2, \cdots , 1, 0.
	</math>		<math>y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}</math>, <math>\quad i = N-1, N-2, \cdots , 1, 0</math>.

	В литературе<ref name="SETKI" /> указывается, что данные формулы эквивалентны вычислению решений двухдиагональных систем методом обратной подстановки в условиях предвычисленного <math>LU</math>-разложения матрицы системы.		В литературе<ref name="SETKI" /> указывается, что данные формулы эквивалентны вычислению решений двухдиагональных систем методом обратной подстановки в условиях предвычисленного <math>LU</math>-разложения матрицы системы.

Frolov: /* Особенности реализации последовательного алгоритма */

2015-11-27T11:20:16Z

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

← Предыдущая версия		Версия от 11:20, 27 ноября 2015
Строка 133:		Строка 133:

	В зависимости от нужд вычислений, возможны как разные способы хранения разложения матрицы СЛАУ, так и разные способы хранения вычисляемых коэффициентов.		В зависимости от нужд вычислений, возможны как разные способы хранения разложения матрицы СЛАУ, так и разные способы хранения вычисляемых коэффициентов.

			Вот пример подпрограммы, реализующей повторную прогонку, где предвычисленные коэффициенты хранятся на месте ненужных элементов матрицы. Предполагается, что уже однажды выполнена первая прогонка (см. [[Прогонка, точечный вариант#Особенности реализации последовательного алгоритма\|пример из статьи о прогонке]]).

			<source lang="fortran">
			subroutine prorep (a,x,N)
			real a(3,0:N), x(0:N)
			x(0)=x(0)*a(2,0) ! beta 1
			do 10 i=1,N-1
			x(i)=(x(i)-a(1,i)x(i-1))a(2,i) ! beta i+1
			10 continue
			x(N)=(x(N)-a(1,N)x(N-1))a(2,N) ! y N
			do 20 i=N-1,0,-1
			x(i)=a(3,i)*x(i+1)+x(i) ! y i
			20 continue
			return
			end
			</source>

	=== Локальность данных и вычислений ===		=== Локальность данных и вычислений ===

Frolov в 11:12, 3 сентября 2015

2015-09-03T11:12:17Z

Внесённые изменения

Frolov: /* Последовательная сложность алгоритма */

2015-09-03T10:53:35Z

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

← Предыдущая версия		Версия от 10:53, 3 сентября 2015
Строка 103:		Строка 103:
	* <math>3n-2</math> умножений.		* <math>3n-2</math> умножений.

	При классификации по последовательной сложности, таким образом, прогонка относится к алгоритмам ''с линейной сложностью''.		При классификации по последовательной сложности, таким образом, повторная прогонка относится к алгоритмам ''с линейной сложностью''.

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