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

Основные авторы описания: Анюшева Ирина (614 группа), Исхаков Эльдар (614 группа)

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

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

Обобщенный метод минимальных невязок (GMRES) для решения системы линейных алгебраических уравнений аппроксимирует решение с помощью вектора в подпространства Крылова с минимальным остатком. Метод GMRES разработан Ю.Саадом и Мартин Х. Шульцом в 1986 году. Метод по праву считается одним из самых эффективных численных методов решения несимметричных систем. Он гарантирует неувеличение нормы невязки в ходе итерационного процесса, который строится основан на построении базиса в соответствующей системе подпространстве Крылова $K_j(A, r_0)$. Затем решение уточняется некоторой добавкой, представленной в виде разложения по этому базису.

Метод обобщенных минимальных невязок популярен из-за наличия ряда преимуществ: он ошибкоустойчив, допускает эффективное распараллеливание, не требует нахождения параметра релаксации, обладает суперлинейной скоростью сходимости. Однако в чистом виде для больших систем метод не используется из-за чрезвычайно больших затрат памяти. Зато широкое распространение получила перезапускаемая версия метода, подоразумевающая перезапуск метода каждые m итераций. Уменьшение размерности пространства может привести к стагнации метода – процессу, при котором с каждой следующей итерацией норма невязки уменьшается незначительно, либо не уменьшается вовсе.

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

Исходные данные: система линейных алгебраических уравнений $Ax=b$, где:

$A=(a_{ij})$ $-$ вещественная матрица размера $n \times n$;

$b$ и $x$ вектора из $n$ элементов;

$x^*$ $-$ точное решение системы.

Вычисляемые данные: $x^{(s)} -$приближенное решение системы.

1.2.1 Ортогонализация Арнольди

Для построения базиса в подпространстве Крылова в методе GMRES применяется ортогонализация Арнольди.

Формулы метода:

$\begin{align} (h_{i+1,i}v_{i+1}) & = Av_i - \sum_{j = 1}^{i} h_{j,i}v_j, \\ v_1 &= \frac{r_0}{\parallel r_0 \parallel}, \end{align}$

В матрично-векторных обозначениях соотношение может быть записано как

$\begin{align} AV_i &= V_i H_i + h_{i+1,i}v_{i+1} e_i^T &=V_{i+1}\overline{H_i}, \end{align}$

$\begin{align} V_i &= [v_1|v_2|...|v_i], \overline{H} - \end{align}$ верхняя матрица Хессенберга размерности $(i+1)\times i$

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

1. Выбрать произвольное $x_0$; вычислить $r_0=b-Ax_0$ и $v_1=\frac{r_0}{\parallel r_0 \parallel}$

2. Задать матрицу $\overline{H}_m$ размерности $(m+1)\times m$ и всем ее элементам присвоить нулевые значения

3. Для $j=1,\dots,m$ выполнять: