Участник:Alexander34396/Обобщенный метод минимальных невязок

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

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

Обобщённый метод минимальных невязок (англ. Generalized minimal residual method, GMRES) - итерационный метод численного решения системы линейных алгебраических уравнений с невырожденной матрицей. Метод основан на минимизации квадратичного функционала невязки на подпространствах Крылова. Разработан Юсефом Саадом и Мартином Шульцем в 1986 году как обобщение метода MINRES на случай систем с несимметричными матрицами.

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

Исходные данные:

• система линейных алгебраических уравнений вида $Ax = b$, где $A$ — невырожденная матрица размера $m$-на-$m$;
• подпространство Крылова размерности $n$, порождённое вектором $b$ и матрицей $A$:

$K_n = K_n(A,b) = \operatorname{span} \, \{ b, Ab, A^2b, \ldots, A^{n-1}b \}. \,$

Вычисляемые данные:

• $x_n \in K_n$ - приближённое решение исходной системы.

Метод GMRES приближает точное решение исходной системы $Ax = b$ вектором $x_n \in K_n$, минимизирующим Евклидову норму невязки $r_n= Ax_n-b$.

Для решения исходной системы GMRES, используя $l_2$-ортонормальный базис пространства $K_n$, выполняет поиск приближённого решения $x_n$ в виде:

$x_n = x_0 + z_n$,

где $x_0$ - некоторое начальное приближение, $z_n \in K_n$ - поправка решения.

Для построения ортонормального базиса $K_n$ метод использует ортогонализацию Арнольди. При введении для базиса $K_n$ матричного обозначения $V_n$ можно записать:

$z_n = V_ny_n$,

где $y_n \in \mathbb{R}^n$ - вектор коэффициентов.

В общем виде алгоритм метода GMRES может быть записан следующим образом:

1. найти ортонормальный базис $V_n$ подпространства $K_n$ с помощью ортогонализации Арнольди;
2. найти $y_n$, минимизирующий $\|r_n\|_2$;
3. посчитать $x_n = x_0 + V_ny_n$;
4. повторить, если требуемая точность не была достигнута.

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

Вычислительное ядро последовательной версии метода GMRES состоит из двух частей:

• Вычисление ортонормального базиса $K_n$ с помощью ортогонализации Арнольди:

Вычисление $(Av_j, v_i)$: требует $mn + NZ$ мультипликативных операций, где NZ - количество ненулевых элементов матрицы A.

Вычисление $Av_j - \sum_{i=1}^j (Av_j, v_i)v_{i}$: требует $mj$ мультипликативных операций.

Вычисление $\|\hat{v}_{j+1}\|_2$: содержит $m$ мультипликативных операций.

• Формирование приближенного решения Xo+ VkYk

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

Для решения исходной системы методом GMRES можно воспользоваться следующим алгоритмом:

Подготовка перед итерационным процессом

1. Выбрать начальное приближение $x_0$;
2. Посчитать невязку $r_0 = b - Ax_0$;
3. Вычислить $v_1 = \frac{r_0}{\|r_0\|_2}$.

$n$-я итерация метода

Построение ортонормального базиса $K_n$:

Для всех $j$ от 1 до n по нарастанию выполнять

1. $h_{ij} := (Av_j, v_i), \quad i=1,\ldots,j$;
2. $\hat{v}_{j+1} := Av_j - \sum_{i=1}^j h_{ij}v_{i}$;
3. $h_{j+1j} = \|\hat{v}_{j+1}\|_2$;
4. $v_{j+1} = \frac{\hat{v}_{j+1}}{h_{j+1j}}$.

Вычисление приближённого решения $x_n$:

$x_n = x_0 + V_ny_n$,

где $y_n$ минимизирует $\|r_0 - AV_ny_n\|_2$.