Участник:Макарова Алёна/Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок): различия между версиями
Начало |
Продолжение |
||
| Строка 19: | Строка 19: | ||
''Геометрическая реализация'' метода минимальных невязок заключается в построении последовательности векторов <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_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> | <math>q_{i+1} \in K_{i+1}, p_{i+1} = Aq_{i+1} \perp AK_i</math>. | ||
Его можно получить с помощью процесса ортогонализации, применённого к вектору <math>p = Aq</math>, где <math>q = Aq_i</math>. В геометрической реализации необходимо хранить две системы векторов: <math>q_1, ..., q_i</math> и <math>p_1, ..., p_i</math>. | |||
''Алгебраическая реализация'' метода минимальных невязок использует лишь одну систему векторов, образующих ортогональные базисы в подпространствах <math>K_i</math>. | |||
<math>q_1 = r_0/||r_0||_2</math>. Чтобы получить ортонормированный базис <math>q_1, ..., q_{i+1}</math> в <math>K_{i+1} = K_{i+1}(r_0, A)</math>, проводим ортогонализацию вектора <math>Aq_i</math> к векторам <math>q_1, ..., q_i</math>. Если <math>Q_i \equiv [q_1, ..., q_i] \in C^{nxi}</math>, то получим <math>AQ_i = Q_{i+1}H_i, H_i = []</math>, где <math>H_i</math> - верхняя хессенбергова матрица порядка <math>i</math>. | |||
== Литература == | == Литература == | ||
Версия от 12:39, 15 октября 2016
Свойства и структура алгоритма
Общее описание алгоритма
Метод минимальных невязок представляет собой итерационный метод для численного решения несимметричной системы линейных уравнений. Метод приближает решение вектором в подпространстве Крылова с минимальной невязкой. Чтобы найти этот вектор используется итерация Арнольди.
Впервые метод минимальных невязок был описан в книге Марчука и Кузнецова "Итерационные методы и квадратичные функционалы" [1] и представлял собой геометрическую реализацию метода минимальных невязок.
Алгебраическая реализация метода минимальных невязок была предложена Саадом и Шульцем в 1986 году [2]. С их подачи за методом закрепилась аббревиатура GMRES (обобщенный метод минимальных невязок).
Математическое описание алгоритма
Для решения системы [math]\displaystyle{ Ax = b }[/math] с невырожденной матрицей [math]\displaystyle{ A }[/math], выбирается начальное приближение [math]\displaystyle{ x_0 }[/math], затем решается редуцированная система [math]\displaystyle{ Au = r_0 }[/math], где [math]\displaystyle{ r_0 = b - Ax_0, x = x_0 + u }[/math]. Подпространства Крылова строятся для редуцированной системы (в предположении, что [math]\displaystyle{ r_0 \neq 0 }[/math]).
Пусть [math]\displaystyle{ x_i = x_0 + y }[/math], где [math]\displaystyle{ y \in K_i }[/math]. Невязка имеет вид [math]\displaystyle{ r_i = r_0 - Ay }[/math], а её длина минимальна, в силу теоремы Пифагора, в том и только том случае, когда [math]\displaystyle{ r_i \perp AK_i }[/math].
Таким образом, для реализации [math]\displaystyle{ i }[/math]-го шага требуется опустить перпендикуляр из вектора [math]\displaystyle{ r_0 }[/math] на подпространство [math]\displaystyle{ AK_i }[/math]. Проще всего это сделать, если в данном подпространстве уже найден ортогональный базис.
Геометрическая реализация метода минимальных невязок заключается в построении последовательности векторов [math]\displaystyle{ q_1, q_2,... }[/math] таким образом, что [math]\displaystyle{ q_1, q_2,.., q_i }[/math] дают базис в подпространстве Крылова [math]\displaystyle{ K_i }[/math] и при этом вектора [math]\displaystyle{ p_1 = Aq_1, ..., p_i = Aq_i }[/math] образуют ортогональный базис в подпространстве [math]\displaystyle{ AK_i }[/math]. Вектор [math]\displaystyle{ q_{i+1} \notin K_i }[/math] должен обладать следующими свойствами: [math]\displaystyle{ q_{i+1} \in K_{i+1}, p_{i+1} = Aq_{i+1} \perp AK_i }[/math].
Его можно получить с помощью процесса ортогонализации, применённого к вектору [math]\displaystyle{ p = Aq }[/math], где [math]\displaystyle{ q = Aq_i }[/math]. В геометрической реализации необходимо хранить две системы векторов: [math]\displaystyle{ q_1, ..., q_i }[/math] и [math]\displaystyle{ p_1, ..., p_i }[/math].
Алгебраическая реализация метода минимальных невязок использует лишь одну систему векторов, образующих ортогональные базисы в подпространствах [math]\displaystyle{ K_i }[/math].
[math]\displaystyle{ q_1 = r_0/||r_0||_2 }[/math]. Чтобы получить ортонормированный базис [math]\displaystyle{ q_1, ..., q_{i+1} }[/math] в [math]\displaystyle{ K_{i+1} = K_{i+1}(r_0, A) }[/math], проводим ортогонализацию вектора [math]\displaystyle{ Aq_i }[/math] к векторам [math]\displaystyle{ q_1, ..., q_i }[/math]. Если [math]\displaystyle{ Q_i \equiv [q_1, ..., q_i] \in C^{nxi} }[/math], то получим [math]\displaystyle{ AQ_i = Q_{i+1}H_i, H_i = [] }[/math], где [math]\displaystyle{ H_i }[/math] - верхняя хессенбергова матрица порядка [math]\displaystyle{ i }[/math].
Литература
- ↑ Г.И. Марчук, Ю.А. Кузнецов, Итерационные методы и квадратичные функционалы, Методы вычислительной математики, Новосибирск, 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).