Метод релаксации матрицы - История изменений

Овсиенко Олеся в 04:04, 9 декабря 2025

2025-12-09T04:04:52Z

← Предыдущая версия		Версия от 04:04, 9 декабря 2025
Строка 1:		Строка 1:
	{{algorithm		{{algorithm
	\| name = Метод релаксации ~~для уравнения Лапласа~~		\| name = Метод релаксации матрицы
	\| serial_complexity = <math>O(it\_max \cdot N^2)</math>		\| serial_complexity = <math>O(it\_max \cdot N^2)</math>
	\| pf_height = <math>O(it\_max)</math>		\| pf_height = <math>O(it\_max)</math>

Овсиенко Олеся в 04:03, 9 декабря 2025

2025-12-09T04:03:51Z

Овсиенко Олеся в 03:46, 9 декабря 2025

2025-12-09T03:46:32Z

← Предыдущая версия		Версия от 03:46, 9 декабря 2025
Строка 1:		Строка 1:

	{{algorithm		{{algorithm
	\| name = Метод релаксации для уравнения Лапласа		\| name = Метод релаксации для уравнения Лапласа
Строка 8:		Строка 7:
	\| output_data = <math>N^2</math> (матрица значений)		\| output_data = <math>N^2</math> (матрица значений)
	}}		}}


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

Овсиенко Олеся в 03:42, 9 декабря 2025

2025-12-09T03:42:53Z

← Предыдущая версия		Версия от 03:42, 9 декабря 2025
Строка 26:		Строка 26:
	в прямоугольной области <math>[0,1]\times[0,1]</math> с нулевыми граничными условиями.		в прямоугольной области <math>[0,1]\times[0,1]</math> с нулевыми граничными условиями.

	Дискретизация на равномерной сетке <math>N \times N</math> с шагом <math>h = 1/(N-1)</math> приводит к системе линейных уравнений, которая решается методом ~~Якоби~~:		Дискретизация на равномерной сетке <math>N \times N</math> с шагом <math>h = 1/(N-1)</math> приводит к системе линейных уравнений, которая решается методом релаксации:

	Для каждого внутреннего узла <math>(i,j)</math> на итерации <math>k</math>:		Для каждого внутреннего узла <math>(i,j)</math> на итерации <math>k</math>:
Строка 258:		Строка 258:
	=== Результаты прогонов===		=== Результаты прогонов===

	Для получения ~~полных~~ результатов ~~необходимо провести серию~~ экспериментов с различными:		Для получения результатов была проведена серия экспериментов с различными:
	# Размерами сетки ( <math>N</math> = 512, 1024, 2048, 4096 )		# Размерами сетки ( <math>N</math> = 512, 1024, 2048, 4096 )
	# Количеством процессов ( 1, 2, 3, ... , 28 )		# Количеством процессов ( 1, 2, 3, ... , 28 )
	# Параметрами точности ( <math>max\_eps</math> = 0.1e-7 )		# Параметрами точности ( <math>max\_eps</math> = 0.1e-7 )

	~~Результаты~~:		[[file:correct_result.png\|thumb\|center\|700px\|Зависимость времени выполнения от размера матрицы и числа процессов]]
	* Ускорение работы с ростом числа процессов (до определённого предела)
	* Увеличение времени выполнения ~~с ростом N~~
	* Зависимость числа итераций от ~~точности~~ и ~~размера сетки~~
	* Накладные расходы на коммуникации в MPI-версии

			Результаты экспериментов подтверждают корректность и эффективность MPI-реализации :
			* Время выполнения растёт пропорционально квадрату размера сетки, демонстрируя сложность <math>O(N²)</math>.
			* Алгоритм хорошо масштабируется: для <math>N</math> = 4096 использование 28 процессов ускоряет вычисления в 20 раз по сравнению с последовательной версией.
			* Значения контрольной суммы сохраняются при любом количестве процессов, что подтверждает корректность обмена данными.
			* Наилучшая эффективность достигается при балансе между объёмом вычислений на процесс и затратами на коммуникации.

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

Овсиенко Олеся: /* Информационный граф алгоритма */

2025-12-09T02:19:23Z

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

← Предыдущая версия		Версия от 02:19, 9 декабря 2025
Строка 104:		Строка 104:

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

			Информационный граф алгоритма состоит из четырёх групп вершин, расположенных в целочисленных узлах областей различной размерности.

	[[file:information_graph.png\|thumb\|center\|1150px\|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]		[[file:information_graph.png\|thumb\|center\|1150px\|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]

Овсиенко Олеся в 01:50, 9 декабря 2025

2025-12-09T01:50:47Z

@@ Строка 102: / Строка 102: @@
 * 1 вычитание и взятие модуля для погрешности
-Граф алгоритма представляет собой регулярную структуру:
+=== Информационный граф алгоритма ===
-[[file:information_graph.png|thumb|center|970px|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]
+[[file:information_graph.png|thumb|center|1150px|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]
 === Ресурс параллелизма алгоритма ===
@@ Строка 196: / Строка 259: @@
 # Размерами сетки ( <math>N</math> = 512, 1024, 2048, 4096 )
 # Количеством процессов ( 1, 2, 3, ... , 28 )
-# Параметрами точности ( <math>maxeps</math> = 0.1e-7 )
+# Параметрами точности ( <math>max\_eps</math> = 0.1e-7 )
 Результаты:
@@ Строка 207: / Строка 270: @@
 == Литература ==
-. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. — М.: Наука, 1978.
+# Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. — М.: Наука, 1978.
+# Самарский А. А., Гулин А. В. Численные методы. - M.: Наука, 1989.
-. Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge University Press, 2007.
+# Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge University Press, 2007.
+# Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. — 3rd ed. — MIT Press, 2014.
-. Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. — 3rd ed. — MIT Press, 2014.
+# Документация по MPI: https://www.mpi-forum.org/docs/

Овсиенко Олеся в 00:37, 9 декабря 2025

2025-12-09T00:37:13Z

← Предыдущая версия		Версия от 00:37, 9 декабря 2025
Строка 106:		Строка 106:
	Граф алгоритма представляет собой регулярную структуру:		Граф алгоритма представляет собой регулярную структуру:

	~~<gallery>~~		[[file:information_graph.png\|thumb\|center\|970px\|Информационный граф метода релаксации для <math>N</math> = 4 , <math>max\_it</math> = 2]]
	~~File:information_graph.png\|Информационный граф метода релаксации для <math>N</math> = 4, <math>max\_it</math> = 2~~
	~~</gallery>~~

	[[~~Файл~~:information_graph.png\|Информационный граф метода релаксации для <math>N</math> = 4, <math>max\_it</math> = 2]]

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

Овсиенко Олеся в 00:31, 9 декабря 2025

2025-12-09T00:31:09Z

← Предыдущая версия		Версия от 00:31, 9 декабря 2025
Строка 109:		Строка 109:
	File:information_graph.png\|Информационный граф метода релаксации для <math>N</math> = 4, <math>max\_it</math> = 2		File:information_graph.png\|Информационный граф метода релаксации для <math>N</math> = 4, <math>max\_it</math> = 2
	</gallery>		</gallery>

			[[Файл:information_graph.png\|Информационный граф метода релаксации для <math>N</math> = 4, <math>max\_it</math> = 2]]

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

Овсиенко Олеся в 00:18, 9 декабря 2025

2025-12-09T00:18:34Z

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

Овсиенко Олеся: Новая страница: «''417 группа, ММП ВМК МГУ''
''Овсиенко Олеся Павловна''
== Математическая постановка мето...»

2025-11-05T10:08:30Z

Новая страница: «''417 группа, ММП ВМК МГУ''<br> ''Овсиенко Олеся Павловна''<br> == Математическая постановка мето...»

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

''417 группа, ММП ВМК МГУ''<br>
''Овсиенко Олеся Павловна''<br>

== Математическая постановка метода релаксации матрицы ==

Требуется численно решить краевую задачу для уравнения Лапласа на прямоугольной области:

<math>
\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0, \quad (x,y) \in \Omega = [0,1] \times [0,1]
</math>

с граничными условиями Дирихле:

<math>
u(x,y) = g(x,y), \quad (x,y) \in \partial\Omega,
</math>

где <math>\partial\Omega</math> — граница области.

==== Дискретизация задачи ====

Вводится равномерная сетка с шагом <math>h = \frac{1}{N-1}</math>:

<math>
x_i = i \cdot h, \quad y_j = j \cdot h, \quad i,j = 0, 1, \dots, N-1.
</math>

Аппроксимируя вторые производные конечными разностями, получаем дискретный аналог уравнения Лапласа для внутренних узлов сетки:

<math>
\frac{u_{i-1,j} - 2u_{i,j} + u_{i+1,j}}{h^2} + \frac{u_{i,j-1} - 2u_{i,j} + u_{i,j+1}}{h^2} = 0,
</math>

что после преобразования даёт:

<math>
u_{i,j} = \frac{u_{i-1,j} + u_{i+1,j} + u_{i,j-1} + u_{i,j+1}}{4}.
</math>

==== Итерационный метод решения ====

Для решения полученной системы линейных уравнений используется метод Якоби (релаксации). На каждой итерации <math>k</math> новые значения вычисляются как:

<math>
u_{i,j}^{(k)} = \frac{u_{i-1,j}^{(k-1)} + u_{i+1,j}^{(k-1)} + u_{i,j-1}^{(k-1)} + u_{i,j+1}^{(k-1)}}{4},
</math>

где <math>i,j = 1, 2, \dots, N-2</math> — индексы внутренних узлов.

==== Критерий остановки ====

Итерационный процесс прекращается, когда максимальное изменение между итерациями становится меньше заданной точности:

<math>
\max_{i,j} |u_{i,j}^{(k)} - u_{i,j}^{(k-1)}| < \varepsilon_{\text{max}}.
</math>

==== Начальные и граничные условия ====

В конкретной реализации:
* Граничные условия: <math>u_{0,j} = u_{N-1,j} = u_{i,0} = u_{i,N-1} = 0</math>
* Начальное приближение для внутренних точек: <math>u_{i,j}^{(0)} = 1 + i + j</math>

==== Контроль корректности ====

Для верификации результата вычисляется контрольная сумма:

<math>
S = \frac{1}{N^2} \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} u_{i,j} \cdot (j+1) \cdot (i+1),
</math>

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

← Предыдущая версия		Версия от 04:03, 9 декабря 2025
Строка 118:		Строка 118:
	Результат: элементы массива <math>A[i][j]</math> на итерации 0.		Результат: элементы массива <math>A[i][j]</math> на итерации 0.
	Все вершины этой группы являются источниками (входными данными алгоритма).		Все вершины этой группы являются источниками (входными данными алгоритма).
	На рисунке соответствуют синим прямоугольникам слева с надписью <math>A[i][j]~~⁽⁰⁾~~</math>.		На рисунке соответствуют синим прямоугольникам слева с надписью <math>A[i][j]^{(0)}</math>.

	2) Вторая группа вершин (релаксация — вычисление нового слоя) :		2) Вторая группа вершин (релаксация — вычисление нового слоя) :
Строка 134:		Строка 134:
	четыре значения <math>A[⋅][⋅]</math> с предыдущего слоя (итерации <math>k−1</math>).		четыре значения <math>A[⋅][⋅]</math> с предыдущего слоя (итерации <math>k−1</math>).

	Результат срабатывания: элемент нового слоя <math>B[i][j]~~⁽ᵏ⁾~~</math>.		Результат срабатывания: элемент нового слоя <math>B[i][j]^{(k)}</math>.
	На рисунке — зелёные блоки с надписью <math>B[i][j]~~⁽ᵏ⁾~~</math>.		На рисунке — зелёные блоки с надписью <math>B[i][j]^{(k)}</math>.

	3) Третья группа вершин (вычисление невязки и обновление <math>A</math>) :		3) Третья группа вершин (вычисление невязки и обновление <math>A</math>) :
Строка 142:		Строка 142:
	Операция выполняется сразу после второй группы на той же итерации <math>k</math> :		Операция выполняется сразу после второй группы на той же итерации <math>k</math> :

	# <math>e = \|A[i][j]~~⁽ᵏ⁻¹⁾~~ − B[i][j]~~⁽ᵏ⁾~~\|</math>		# <math>e = \|A[i][j]^{(k-1)} − B[i][j]^{(k)}\|</math>
	# <math>A[i][j]~~⁽ᵏ⁾~~ = B[i][j]~~⁽ᵏ⁾~~</math>		# <math>A[i][j]^{(k)} = B[i][j]^{(k)}</math>
	# <math>~~eps⁽ᵏ⁾~~ = max(~~eps⁽ᵏ⁾~~, e)</math>		# <math>eps^{(k)} = max(eps^{(k)}, e)</math>

	Аргументы: значения <math>A[i][j]~~⁽ᵏ⁻¹⁾~~</math> из первой группы вершин и <math>B[i][j]~~⁽ᵏ⁾~~</math> из второй группы вершин.		Аргументы: значения <math>A[i][j]^{(k-1)}</math> из первой группы вершин и <math>B[i][j]^{(k)}</math> из второй группы вершин.

	Результат:		Результат:
	* обновлённое значение <math>A[i][j]~~⁽ᵏ⁾~~</math>, которое будет использовано на следующей итерации,		* обновлённое значение <math>A[i][j]^{(k)}</math>, которое будет использовано на следующей итерации,
	* вклад в глобальную норму невязки <math>~~eps⁽ᵏ⁾~~</math>.		* вклад в глобальную норму невязки <math>eps^{(k)}</math>.

	На рисунке — жёлтые блоки с надписями вида <math>A[i][j]~~⁽ᵏ⁾~~ = B[i][j]~~⁽ᵏ⁾~~</math>.		На рисунке — жёлтые блоки с надписями вида <math>A[i][j]^{(k)} = B[i][j]^{(k)}</math>.

	4) Четвёртая группа вершин (условия завершения) :		4) Четвёртая группа вершин (условия завершения) :
Строка 158:		Строка 158:
	Состоит из двух типов вершин скалярной размерности (координата <math>k</math>):		Состоит из двух типов вершин скалярной размерности (координата <math>k</math>):

	* Вершины сравнения <math>~~eps⁽ᵏ⁾~~ < max\_eps</math> :		* Вершины сравнения <math>eps^{(k)} < max\_eps</math> :
	** Координата <math>k ∈ [1, it\_max]</math>.		** Координата <math>k ∈ [1, it\_max]</math>.
	** Аргумент — накопленное на итерации <math>k</math> значение <math>~~eps⁽ᵏ⁾~~</math>.		** Аргумент — накопленное на итерации <math>k</math> значение <math>eps^{(k)}</math>.
	** На рисунке — фиолетовые овалы с надписью <math>~~eps⁽ᵏ⁾~~ < max\_eps</math>.		** На рисунке — фиолетовые овалы с надписью <math>eps^{(k)} < max\_eps</math>.

	* Вершина проверки числа итераций <math>iteration = it\_max</math> : На рисунке — красный прямоугольник справа.		* Вершина проверки числа итераций <math>iteration = it\_max</math> : На рисунке — красный прямоугольник справа.