Участник:Макарова Алёна/Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок)
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Метод минимальных невязок представляет собой итерационный метод для численного решения несимметричной системы линейных уравнений. Метод приближает решение вектором в подпространстве Крылова с минимальной невязкой. Чтобы найти этот вектор используется итерация Арнольди.
Впервые метод минимальных невязок был описан в книге Марчука и Кузнецова "Итерационные методы и квадратичные функционалы" [1] и представлял собой геометрическую реализацию метода минимальных невязок.
Алгебраическая реализация метода минимальных невязок была предложена Саадом и Шульцем в 1986 году [2]. С их подачи за методом закрепилась аббревиатура GMRES (обобщенный метод минимальных невязок).
1.2 Математическое описание алгоритма
Для решения системы [math]Ax = b[/math] с невырожденной матрицей [math]A[/math], выбирается начальное приближение [math]x_0[/math], затем решается редуцированная система [math]Au = r_0[/math], где [math]r_0 = b - Ax_0, x = x_0 + u[/math]. Подпространства Крылова строятся для редуцированной системы (в предположении, что [math]r_0 \neq 0[/math]).
Пусть [math]x_i = x_0 + y[/math], где [math] y \in K_i [/math]. Невязка имеет вид [math]r_i = r_0 - Ay[/math], а её длина минимальна, в силу теоремы Пифагора, в том и только том случае, когда [math] r_i \perp AK_i [/math].
Таким образом, для реализации [math]i[/math]-го шага требуется опустить перпендикуляр из вектора [math]r_0[/math] на подпространство [math]AK_i[/math]. Проще всего это сделать, если в данном подпространстве уже найден ортогональный базис.
Геометрическая реализация метода минимальных невязок заключается в построении последовательности векторов [math]q_1, q_2,...[/math] таким образом, что [math]q_1, q_2,.., q_i[/math] дают базис в подпространстве Крылова [math]K_i[/math] и при этом вектора [math]p_1 = Aq_1, ..., p_i = Aq_i[/math] образуют ортогональный базис в подпространстве [math]AK_i[/math]. Вектор [math]q_{i+1} \notin K_i[/math] должен обладать следующими свойствами: [math]q_{i+1} \in K_{i+1}, p_{i+1} = Aq_{i+1} \perp AK_i[/math]
2 Литература
- ↑ Г.И. Марчук, Ю.А. Кузнецов, Итерационные методы и квадратичные функционалы, Методы вычислительной математики, Новосибирск, 1975, с. 4-143.
- ↑ Y.Saad, M.H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Scientific and Stat. Comp. 7: 856-869 (1986).
