Стабилизированный метод бисопряженных градиентов (BiCGStab) - История изменений

ASA в 11:19, 20 февраля 2025

2025-02-20T11:19:59Z

← Предыдущая версия		Версия от 11:19, 20 февраля 2025
Строка 8:		Строка 8:
	\| pf_height = <math> O(k\cdot(6 \sqrt N + 4N + 5 \lceil \frac{N}{p} \rceil)) </math>		\| pf_height = <math> O(k\cdot(6 \sqrt N + 4N + 5 \lceil \frac{N}{p} \rceil)) </math>
	\| pf_width = <math> 2 \sqrt N </math>		\| pf_width = <math> 2 \sqrt N </math>
	\| input_data = ~~матрица~~ <math>~~A \in R^{N \times N}</math> ( <math>C^{N \times N}</math> ) и вектор правой части <math>b \in R^~~N~~</math> ( <math>C~~^N</math> )		\| input_data = <math>N^2+N</math>
	\| output_data = ~~вектор решения системы~~ <math>~~x \in R^N</math> ( <math>C^~~N</math> )		\| output_data = <math>N</math>
	}}		}}

ASA в 08:59, 12 июля 2022

2022-07-12T08:59:02Z

← Предыдущая версия		Версия от 08:59, 12 июля 2022
Строка 170:		Строка 170:
	== Литература ==		== Литература ==

	<references \>		<references />

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

	[[en:Biconjugate gradient stabilized method (BiCGStab)]]		[[en:Biconjugate gradient stabilized method (BiCGStab)]]

ASA в 08:54, 12 июля 2022

2022-07-12T08:54:28Z

@@ Строка 1: / Строка 1: @@
 Авторы описания:
-[https://algowiki-project.org/ru/Участник:Novikov_alexander<b>А.Новиков</b>] (разделы 1.4, 1.6, 1.7, 2.4, 2.7, 3),
+[https://algowiki-project.org/ru/Участник:Novikov_alexander<b>А.Новиков</b>] (разделы 1.4, 1.6, 1.7, 3),
-[https://algowiki-project.org/ru/Участник:EasyBreezy<b>А.Гаврилов</b>] (разделы 1.1-1.3, 1.5, 1.8, 1.9, 2.7, 3)
+[https://algowiki-project.org/ru/Участник:EasyBreezy<b>А.Гаврилов</b>] (разделы 1.1-1.3, 1.5, 1.8, 1.9, 3)
 {{algorithm
@@ Строка 164: / Строка 164: @@
 === Особенности реализации последовательного алгоритма ===
 === Возможные способы и особенности параллельной реализации алгоритма ===
-=== Масштабируемость алгоритма и его реализации ===
+=== Результаты прогонов ===
 === Выводы для классов архитектур ===
 == Литература ==

Kprlns: Исправлен тег "" на " $"$

2018-05-20T21:53:10Z

Исправлен тег "<marh>" на "<math>"

← Предыдущая версия		Версия от 21:53, 20 мая 2018
Строка 32:		Строка 32:
	Пусть для СЛАУ известно некоторое приближение <math>x^0</math> точного решения <math>x^*</math>. Данное приближение требуется уточнить поправкой <math> \delta: b - Ax^0 + \delta \perp L</math>. Невязка уточненного решения имеет вид: <math>r_{new} = b - Ax^0 + \delta = r^0- A\delta</math>. Условие Петрова-Галеркина тогда можно переписать так: <math>(r_{new}, z)= r^0 - (A\delta, z) = 0, \forall z \in L</math>		Пусть для СЛАУ известно некоторое приближение <math>x^0</math> точного решения <math>x^*</math>. Данное приближение требуется уточнить поправкой <math> \delta: b - Ax^0 + \delta \perp L</math>. Невязка уточненного решения имеет вид: <math>r_{new} = b - Ax^0 + \delta = r^0- A\delta</math>. Условие Петрова-Галеркина тогда можно переписать так: <math>(r_{new}, z)= r^0 - (A\delta, z) = 0, \forall z \in L</math>

	Пусть <math>\rm dim K = dim L = m, V = (v_1, ..., v_n) \in R^{n \times m}, W = (w_1, ... w_n) \in R^{n \times m}</math>, где <~~marh~~>V</math> и <math>W</math> – матрицы, столбцы которых образуют базисы пространств <math>K</math> и <math>L</math> соответственно. Пусть так же <math> \delta = Vy, z = Wq</math>, где <math>y</math> – коэффициенты разложения вектора поправки по базису пространства <math>K</math>, а <math>q</math> – коэффициенты разложения вектора <math>z</math> в пространстве <math>L</math>. Тогда новое приближение решения можно записать в виде: <math>x^1 = x^0 + \delta= x^0 + Vy</math>. Из условия ортогональности Петрова-Галеркина получаем, что: <math>(r - AVy, Wq) = (W^Tr^0 - AVy, q) = 0</math>. Поскольку <math>q \neq 0</math>, то получаем СЛАУ для вектора <math>y</math>: <math>W^TAVy = W^Tr^0</math>. Если предположить, что матрица <math>W^TAVy</math> невырождена, то вектор y однозначно определяется и равен: <math>y = W^TAV^{-1}W^Tr^0</math>. Подставляя найденные коэффициенты разложения в выражение для первого приближения получаем: <math>x^1 = x^0 + \delta = x^0 + W^TAV^{-1}W^Tr^0y</math>		Пусть <math>\rm dim K = dim L = m, V = (v_1, ..., v_n) \in R^{n \times m}, W = (w_1, ... w_n) \in R^{n \times m}</math>, где <math>V</math> и <math>W</math> – матрицы, столбцы которых образуют базисы пространств <math>K</math> и <math>L</math> соответственно. Пусть так же <math> \delta = Vy, z = Wq</math>, где <math>y</math> – коэффициенты разложения вектора поправки по базису пространства <math>K</math>, а <math>q</math> – коэффициенты разложения вектора <math>z</math> в пространстве <math>L</math>. Тогда новое приближение решения можно записать в виде: <math>x^1 = x^0 + \delta= x^0 + Vy</math>. Из условия ортогональности Петрова-Галеркина получаем, что: <math>(r - AVy, Wq) = (W^Tr^0 - AVy, q) = 0</math>. Поскольку <math>q \neq 0</math>, то получаем СЛАУ для вектора <math>y</math>: <math>W^TAVy = W^Tr^0</math>. Если предположить, что матрица <math>W^TAVy</math> невырождена, то вектор y однозначно определяется и равен: <math>y = W^TAV^{-1}W^Tr^0</math>. Подставляя найденные коэффициенты разложения в выражение для первого приближения получаем: <math>x^1 = x^0 + \delta = x^0 + W^TAV^{-1}W^Tr^0y</math>

	Подведем итог. Общий порядок шагов любого проекционного метода следующий:		Подведем итог. Общий порядок шагов любого проекционного метода следующий:

ASA в 12:45, 14 марта 2018

2018-03-14T12:45:44Z

← Предыдущая версия		Версия от 12:45, 14 марта 2018
Строка 204:		Строка 204:

	<references \>		<references \>

			[[Категория:Статьи в работе]]

			[[en:Biconjugate gradient stabilized method (BiCGStab)]]

Konshin: /* Ресурс параллелизма алгоритма */

2018-01-16T10:37:51Z

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

← Предыдущая версия		Версия от 10:37, 16 января 2018
Строка 138:		Строка 138:
	Высота ЯПФ операции умножения вектора на число равна <math>\frac{N}{p}</math>, а ширина <math>p</math>.		Высота ЯПФ операции умножения вектора на число равна <math>\frac{N}{p}</math>, а ширина <math>p</math>.

	Высота ЯПФ операции вычисления разности векторов = <math> \log_2 p </math>, а ширина <math>p</math>.		Высота ЯПФ операции вычисления разности векторов равна <math> \log_2 p </math>, а ширина <math>p</math>.

	В конечном счете общую высоту ЯПФ одной итерации алгоритма можно оценить, как <math>6 \sqrt N-3 + 4N + 3 + 1 + 3\lceil \frac{N}{p} \rceil + 2 \lceil \frac{N}{p} \rceil = 4N + 6 \sqrt N + 5 \lceil \frac{N}{p} \rceil + 1</math>, а ширину, как <math>2 \sqrt N</math>, если не брать в рассчет проверку критерия сходимости и упрощенности первой итерации по сравнению с остальными.		В конечном счете общую высоту ЯПФ одной итерации алгоритма можно оценить, как <math>6 \sqrt N-3 + 4N + 3 + 1 + 3\lceil \frac{N}{p} \rceil + 2 \lceil \frac{N}{p} \rceil = 4N + 6 \sqrt N + 5 \lceil \frac{N}{p} \rceil + 1</math>, а ширину, как <math>2 \sqrt N</math>, если не брать в рассчет проверку критерия сходимости и упрощенности первой итерации по сравнению с остальными.

Konshin: /* Ресурс параллелизма алгоритма */

2018-01-16T10:37:23Z

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

← Предыдущая версия		Версия от 10:37, 16 января 2018
Строка 140:		Строка 140:
	Высота ЯПФ операции вычисления разности векторов = <math> \log_2 p </math>, а ширина <math>p</math>.		Высота ЯПФ операции вычисления разности векторов = <math> \log_2 p </math>, а ширина <math>p</math>.

	В конечном счете общую высоту ЯПФ одной итерации алгоритма можно оценить, как <math>6 \sqrt N-3 + 4N + 3 + 1 + 3\lceil \frac{N}{p} \rceil + 2 \lceil \frac{N}{p} \rceil = 6 \sqrt N ~~+ 4N~~ + 5 \lceil \frac{N}{p} \rceil + 1</math>, а ширину, как <math>2 \sqrt N</math>, если не брать в рассчет проверку критерия сходимости и упрощенности первой итерации по сравнению с остальными.		В конечном счете общую высоту ЯПФ одной итерации алгоритма можно оценить, как <math>6 \sqrt N-3 + 4N + 3 + 1 + 3\lceil \frac{N}{p} \rceil + 2 \lceil \frac{N}{p} \rceil = 4N + 6 \sqrt N + 5 \lceil \frac{N}{p} \rceil + 1</math>, а ширину, как <math>2 \sqrt N</math>, если не брать в рассчет проверку критерия сходимости и упрощенности первой итерации по сравнению с остальными.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

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

2018-01-16T10:36:05Z

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

← Предыдущая версия		Версия от 10:36, 16 января 2018
Строка 56:		Строка 56:

	Основной итерационный процесс задается формулами:		Основной итерационный процесс задается формулами:
	<center><math>x^{k + 1} = x^k + \alpha_k p_k + \omega_k s_k,</math></center>		<center><math>x^{k + 1} = x^k + \alpha_k p_k + \omega_k s_k</math></center>
	<center><math>p^{k + 1} = r^{k + 1} + \beta_k p_k - \omega_k Ap_k,</math></center>		<center><math>p^{k + 1} = r^{k + 1} + \beta_k p_k - \omega_k Ap_k</math></center>
	где:		где:
	#<math>x^{k + 1}</math> - приближение на следующей итерации		#<math>x^{k + 1}</math> - приближение на следующей итерации

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

2018-01-16T10:35:45Z

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

← Предыдущая версия		Версия от 10:35, 16 января 2018
Строка 47:		Строка 47:

	Рассмотрим СЛАУ с вещественными коэффициентами:		Рассмотрим СЛАУ с вещественными коэффициентами:
	<center><math>Ax = b, \quad A \in R^{N \times N}, \quad b \in R^N~~</math></center>~~		<center><math>Ax = b, \quad A \in R^{N \times N}, \quad b \in R^N.</math></center>
	~~<center><math>~~</math></center>

	В основу алгоритма ложиться идея проекционного метода и использование свойства A-бисопряженности системы векторов, а именно: векторы <math>p^1, p^2, ...</math> и <math>\overline p^1, \overline p^2, ...</math> бисопряжены, если <math>(Ap^i,p^j ) = 0</math>, при <math>i \neq j</math>. Фактически, данное условие эквивалентно биортогональности относительно энергетического скалярного произведения.		В основу алгоритма ложиться идея проекционного метода и использование свойства A-бисопряженности системы векторов, а именно: векторы <math>p^1, p^2, ...</math> и <math>\overline p^1, \overline p^2, ...</math> бисопряжены, если <math>(Ap^i,p^j ) = 0</math>, при <math>i \neq j</math>. Фактически, данное условие эквивалентно биортогональности относительно энергетического скалярного произведения.

	Общая концепция проекционных методов предписывает нам выбрать два подпространства. В нашем случае подпространства мы выберем два подпространства, задаваемые матрицей системы А, вектором невязки на нулевой итерации <math>r^0</math> и вектором <math>\overline r^0</math>. который выбирается из условия <math>(r^0, \overline r^0) \neq 0</math>:		Общая концепция проекционных методов предписывает нам выбрать два подпространства. В нашем случае подпространства мы выберем два подпространства, задаваемые матрицей системы А, вектором невязки на нулевой итерации <math>r^0</math> и вектором <math>\overline r^0</math>. который выбирается из условия <math>(r^0, \overline r^0) \neq 0</math>:
	<center><math>K = K^k(A, r^0),\quad L = K^k(A, \overline r^0)</math></center>		<center><math>K = K^k(A, r^0),\quad L = K^k(A, \overline r^0).</math></center>
	Метод основан на построении биортогонального базиса <math>p^0, p^1, ..., p^k, ... </math> пространства <math>K^k (A, r^0) </math> и вычислении поправки такой, что новое приближение на очередной итерации было бы ортогонально второму подпространству Крылова. Базисные вектора строятся до тех пор, пока не будет достигнут критерий остановки итерационного процесса, а каждое последующее приближение формируется, как сумма приближения на предыдущей итерации и найденной поправки. Критерием останова итерационного процесса является достижение невязкой значения, которое меньше некоторого наперед заданного <math>\epsilon</math>.		Метод основан на построении биортогонального базиса <math>p^0, p^1, ..., p^k, ... </math> пространства <math>K^k (A, r^0) </math> и вычислении поправки такой, что новое приближение на очередной итерации было бы ортогонально второму подпространству Крылова. Базисные вектора строятся до тех пор, пока не будет достигнут критерий остановки итерационного процесса, а каждое последующее приближение формируется, как сумма приближения на предыдущей итерации и найденной поправки. Критерием останова итерационного процесса является достижение невязкой значения, которое меньше некоторого наперед заданного <math>\epsilon</math>.

	Основной итерационный процесс задается формулами:		Основной итерационный процесс задается формулами:
	<center><math>x^{k + 1} = x^k + \alpha_k p_k + \omega_k s_k</math></center>		<center><math>x^{k + 1} = x^k + \alpha_k p_k + \omega_k s_k,</math></center>
	<center><math>p^{k + 1} = r^{k + 1} + \beta_k p_k - \omega_k Ap_k</math></center>		<center><math>p^{k + 1} = r^{k + 1} + \beta_k p_k - \omega_k Ap_k,</math></center>
	где:		где:
	#<math>x^{k + 1}</math> - приближение на следующей итерации		#<math>x^{k + 1}</math> - приближение на следующей итерации

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

2018-01-16T10:34:25Z

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

← Предыдущая версия		Версия от 10:34, 16 января 2018
Строка 47:		Строка 47:

	Рассмотрим СЛАУ с вещественными коэффициентами:		Рассмотрим СЛАУ с вещественными коэффициентами:
	<center><math>Ax = b, A \in R^{N \times N}, b \in R^N</math></center>		<center><math>Ax = b, \quad A \in R^{N \times N}, \quad b \in R^N</math></center>
	<center><math></math></center>		<center><math></math></center>

	В основу алгоритма ложиться идея проекционного метода и использование свойства A-бисопряженности системы векторов, а именно: векторы <math>p^1, p^2, ...</math> и <math>\overline p^1, \overline p^2, ...</math> бисопряжены, если <math>(Ap^i,p^j ) = 0,</math> при <math>i \neq j</math>. Фактически, данное условие эквивалентно биортогональности относительно энергетического скалярного произведения.		В основу алгоритма ложиться идея проекционного метода и использование свойства A-бисопряженности системы векторов, а именно: векторы <math>p^1, p^2, ...</math> и <math>\overline p^1, \overline p^2, ...</math> бисопряжены, если <math>(Ap^i,p^j ) = 0</math>, при <math>i \neq j</math>. Фактически, данное условие эквивалентно биортогональности относительно энергетического скалярного произведения.

	Общая концепция проекционных методов предписывает нам выбрать два подпространства. В нашем случае подпространства мы выберем два подпространства, задаваемые матрицей системы А, вектором невязки на нулевой итерации <math>r^0</math> и вектором <math>\overline r^0</math>. который выбирается из условия <math>(r^0, \overline r^0) \neq 0</math>:		Общая концепция проекционных методов предписывает нам выбрать два подпространства. В нашем случае подпространства мы выберем два подпространства, задаваемые матрицей системы А, вектором невязки на нулевой итерации <math>r^0</math> и вектором <math>\overline r^0</math>. который выбирается из условия <math>(r^0, \overline r^0) \neq 0</math>:
	<center><math>K = K^k(A, r^0), L = K^k(A, \overline r^0)</math></center>		<center><math>K = K^k(A, r^0),\quad L = K^k(A, \overline r^0)</math></center>
	Метод основан на построении биортогонального базиса <math>p^0, p^1, ... p^k .. </math> пространства <math>K^k (A, r^0) </math> и вычислении поправки такой, что новое приближение на очередной итерации было бы ортогонально второму подпространству Крылова. Базисные вектора строятся до тех пор, пока не будет достигнут критерий остановки итерационного процесса, а каждое последующее приближение формируется, как сумма приближения на предыдущей итерации и найденной поправки. Критерием останова итерационного процесса является ~~достижения~~ невязкой значения, которое меньше некоторого наперед заданного ~~числа~~ <math>\epsilon</math>.		Метод основан на построении биортогонального базиса <math>p^0, p^1, ..., p^k, ... </math> пространства <math>K^k (A, r^0) </math> и вычислении поправки такой, что новое приближение на очередной итерации было бы ортогонально второму подпространству Крылова. Базисные вектора строятся до тех пор, пока не будет достигнут критерий остановки итерационного процесса, а каждое последующее приближение формируется, как сумма приближения на предыдущей итерации и найденной поправки. Критерием останова итерационного процесса является достижение невязкой значения, которое меньше некоторого наперед заданного <math>\epsilon</math>.

	Основной итерационный процесс задается формулами:		Основной итерационный процесс задается формулами:

Стабилизированный метод бисопряженных градиентов (BiCGStab) - История изменений

ASA в 11:19, 20 февраля 2025

ASA в 08:59, 12 июля 2022

ASA в 08:54, 12 июля 2022

Kprlns: Исправлен тег "" на ""

ASA в 12:45, 14 марта 2018

Konshin: /* Ресурс параллелизма алгоритма */

Konshin: /* Ресурс параллелизма алгоритма */

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

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

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

Kprlns: Исправлен тег "" на " $"$