Участник:Макарова Алёна/Итерационный метод решения системы линейных алгебраических уравнений 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$.

Его можно получить с помощью процесса ортогонализации, применённого к вектору $p = Aq$, где $q = Aq_i$. В геометрической реализации необходимо хранить две системы векторов: $q_1, ..., q_i$ и $p_1, ..., p_i$.

Алгебраическая реализация метода минимальных невязок использует лишь одну систему векторов, образующих ортогональные базисы в подпространствах $K_i$.

$q_1 = r_0/||r_0||_2$. Чтобы получить ортонормированный базис $q_1, ..., q_{i+1}$ в $K_{i+1} = K_{i+1}(r_0, A)$, проводим ортогонализацию вектора $Aq_i$ к векторам $q_1, ..., q_i$. Если $Q_i \equiv [q_1, ..., q_i] \in C^{nxi}$, то получим $AQ_i = Q_{i+1}H_i, H_i = []$, где $H_i$ - верхняя хессенбергова матрица порядка $i$.