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

Материал из Алговики
Перейти к навигации Перейти к поиску
← Предыдущая правкаСледующая правка →
Строка 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>
:<math>
\begin{align}
\begin{align}
Ax = f
\|r_k{\|}_2 &= \|Ax_k-b{\|}_2 \to \min\limits_{x_k \in K_k}
\end{align}
\end{align}
</math>
</math>
Приближенное  решение <math>x_k</math> для системы линейных алгебраических уравнений
с произвольной невырожденной матрицей <math>A</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>A</math> (элементы <math>a_{ij}</math>), начальное приближение <math> x_0 </math>


Вычисляемые данные: Приближенное решение уравнения <math>x_k</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> . Здесь мы этот вариант алгоритма не рассматриваем. Заметим только, что он имеет худшие параллельные характеристики, чем представленный.
:''[[Разложение Холецкого (метод квадратного корня)|Читать полностью…]]''


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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

Литература

  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).
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Участница:Эльвира_Ахиярова/Итерационный_метод_решения_системы_линейных_алгебраических_уравнений_GMRES_(обобщенный_метод_минимальных_невязок)&oldid=11224