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

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

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

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

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

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

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

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

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

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

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

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

$x_m = x_0 + z_m$,

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

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

$z_m = V_my_m$,

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

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

1. найти ортонормальный базис $V_m$ подпространства $K_m$ с помощью ортогонализации Арнольди;
2. найти $y_m$, минимизирующий $\|r_m\|_2$;
3. посчитать $x_m = x_0 + V_my_m$;
4. посчитать $r_m$ и остановиться,если требуемая точность была достигнута, иначе повторить.

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

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

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

на одной итерации алгоритма $m(m + 1) n + mNZ$ мультипликативных операций, где NZ - количество ненулевых элементов матрицы $A$;

• Формирование приближенного решения $x_0 + V_mY_m$:

$nm$ мультипликативных операций.

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

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

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

1.1 Выбрать начальное приближение $x_0$;

1.2 Посчитать невязку $r_0 = b - Ax_0$;

1.3 Вычислить $v_1 = \frac{r_0}{\|r_0\|_2}$.

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

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

2.1 $h_{ij} := (Av_j, v_i), \quad i=1,\ldots,j$;

2.2 $\hat{v}_{j+1} := Av_j - \sum_{i=1}^j h_{ij}v_{i}$;

2.3 $h_{j+1j} = \|\hat{v}_{j+1}\|_2$;

2.4 $v_{j+1} = \frac{\hat{v}_{j+1}}{h_{j+1j}}$.

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

3.1 $x_m = x_0 + V_my_m$, где $y_m$ минимизирует $\|r_0 - AV_my_m\|_2$;

3.2 Вычислить $r_m$;

3.3 Если требуемая точность достигнута, остановиться.

4 Рестарт:

4.1 $x_0 = x_m$;

4.2 $v_1 = \frac{r_m}{\|r_m\|_2}$;

4.3 Перейти к шагу 2.