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

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

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

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

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

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.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.