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

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

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

Метод минимальных невязок представляет собой итерационный метод для численного решения несимметричной системы линейных уравнений. Метод приближает решение вектором в подпространстве Крылова с минимальной невязкой. Чтобы найти этот вектор используется итерация Арнольди.

Впервые метод минимальных невязок был описан в книге Марчука и Кузнецова "Итерационные методы и квадратичные функционалы" и представлял собой геометрическую реализацию метода минимальных невязок.

Алгебраическая реализация метода минимальных невязок была предложена Саадом и Шульцем в 1986 году . С их подачи за методом закрепилась аббревиатура GMRES (обобщенный метод минимальных невязок).

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

Для решения системы $Ax = b$ с невырожденной матрицей $A$, выбирается начальное приближение $x_0$, затем решается редуцированная система $Au = r_0$, где $r_0 = b - Ax_0, x = x_0 + u$. Подпространства Крылова строятся для редуцированной системы (в предположении, что $r_0 \neq 0$).

Пусть $x_i = x_0 + y$, где $y \in K_i$. Невязка имеет вид $r_i = r_0 - Ay$, а её длина минимальна, в силу теоремы Пифагора, в том и только том случае, когда $r_i \perp AK_i$.

Таким образом, для реализации $i$-го шага требуется опустить перпендикуляр из вектора $r_0$ на подпространство $AK_i$. Проще всего это сделать, если в данном подпространстве уже найден ортогональный базис.

Геометрическая реализация метода минимальных невязок заключается в построении последовательности векторов $q_1, q_2,...$ таким образом, что $q_1, q_2,.., q_i$ дают базис в подпространстве Крылова $K_i$ и при этом вектора $p_1 = Aq_1, ..., p_i = Aq_i$ образуют ортогональный базис в подпространстве $AK_i$. Вектор $q_{i+1} \notin K_i$ должен обладать следующими свойствами: $q_{i+1} \in K_{i+1}, p_{i+1} = Aq_{i+1} \perp AK_i$