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

Автор: Эльвира Ахиярова

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

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

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

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

Основная идея метода 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.