Участница:Эльвира Ахиярова/Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок): различия между версиями

Версия 21:55, 15 октября 2016

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

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

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

Обобщенный метод минимальных невязок (GMRES) является итерационным методом нахождения решения для системы линейных алгебраических уравнений с произвольной невырожденной матрицей. Метод основан на минимизации квадратичного функционала невязки на подпространствах Крылова. GMRES был предложен Йозефом Саадом и Мартином Шульцем в 1986 году.^[1] Наиболее популярные реализации метода основаны на модифицированном алгоритме ортогонализации Грама-Шмидта и на использовании рестартов для управления требуемым объемом памяти.

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

Основная идея метода GMRES основана на минимизации нормы невязки на каждом итерационном шаге. На каждой [math]k[/math]-й итерации точное решение [math]x^* = A^{-1}b[/math] приближается к вектору [math]x_k \in K_k[/math](k-е подпространство Крылова) в том смысле, что

[math] \begin{align} \|r_k{\|}_2 &= \|Ax_k-b{\|}_2 \to \min\limits_{x_k \in K_k} \end{align} [/math]

Приближенное решение [math]x_k[/math] для системы линейных алгебраических уравнений

с произвольной невырожденной матрицей [math]A[/math] ищется в виде:

Исходные данные: Матрица [math]A[/math] (элементы [math]a_{ij}[/math]), начальное приближение [math] x_0 [/math]

Вычисляемые данные: Приближенное решение уравнения [math]x_k[/math].

1.3 Вычислительное ядро алгоритма

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

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

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

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

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

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

1.10 Свойства алгоритма

In mathematics, the generalized minimal residual method (usually abbreviated GMRES) is an iterative method for the numerical solution of a nonsymmetric system of linear equations. The method approximates the solution by the vector in a Krylov subspace with minimal residual. The Arnoldi iteration is used to find this vector.

The GMRES method was developed by Yousef Saad and Martin H. Schultz in 1986.[1] GMRES is a generalization of the MINRES method developed by Chris Paige and Michael Saunders in 1975. GMRES also is a special case of the DIIS method developed by Peter Pulay in 1980. DIIS is also applicable to non-linear systems.

2 Программная реализация алгоритма

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

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

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности

2.2.1.2 Количественная оценка локальности

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

↑ Y.Saad, M.H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Scientific and Stat. Comp. 7: 856-869 (1986).

[1] Y.Saad, M.H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Scientific and Stat. Comp. 7: 856-869 (1986).

[1]

@@ Строка 6: / Строка 6: @@
 === Математическое описание алгоритма ===
-Приближенное  решение <math>x_k</math> для системы линейных алгебраических уравнений
+Основная идея метода GMRES основана на минимизации нормы невязки на каждом итерационном шаге.  На каждой <math>k</math>-й итерации   точное решение <math>x^* = A^{-1}b</math> приближается к вектору <math>x_k \in K_k</math>(k-е подпространство Крылова) в том смысле, что
 :<math>
 \begin{align}
-Ax = f
+\|r_k{\|}_2 &= \|Ax_k-b{\|}_2 \to \min\limits_{x_k \in K_k}
 \end{align}
 </math>
+Приближенное  решение <math>x_k</math> для системы линейных алгебраических уравнений
 с произвольной невырожденной матрицей <math>A</math> ищется в виде:
-:<math>
-\begin{align}
-x_k & = x_0+z_k \\
-z_k & \in K_k = <r_0, Ar_0, \dots A^{k-1}r_0>,\\
-\end{align}
-</math>
-где <math>r_0 = Ax_0-b</math>
 Исходные данные: Матрица <math>A</math> (элементы <math>a_{ij}</math>), начальное приближение <math> x_0 </math>
 Вычисляемые данные: Приближенное решение уравнения <math>x_k</math>.
-Формулы метода:
-:<math>
-\begin{align}
-l_{11} & = \sqrt{a_{11}}, \\
-l_{j1} & = \frac{a_{j1}}{l_{11}}, \quad j \in [2, n], \\
-l_{ii} & = \sqrt{a_{ii} - \sum_{p = 1}^{i - 1} l_{ip}^2}, \quad i \in [2, n], \\
-l_{ji} & = \left (a_{ji} - \sum_{p = 1}^{i - 1} l_{ip} l_{jp} \right ) / l_{ii}, \quad i \in [2, n - 1], j \in [i + 1, n].
-\end{align}
-</math>
-Существует также блочная версия метода, однако в данном описании разобран только точечный метод.
-В ряде реализаций деление на диагональный элемент выполняется в два этапа: вычисление <math>1/l_{ii}</math> и затем умножение на него всех (видоизменённых) <math>a_{ji}</math> . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.
-:''[[Разложение Холецкого (метод квадратного корня)|Читать полностью…]]''
 === Вычислительное ядро алгоритма ===