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

Материал из Алговики
Перейти к навигации Перейти к поиску
(Продолжение)
(Описание)
Строка 14: Строка 14:
 
Для решения системы <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>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>x_i = x_0 + y</math>, где <math> y \in \mathcal{K}_i </math>. Невязка имеет вид <math>r_i = r_0 - Ay</math>, а её длина минимальна, в силу теоремы Пифагора, в том и только том случае, когда  
  
Таким образом, для реализации <math>i</math>-го шага требуется опустить перпендикуляр из вектора <math>r_0</math> на подпространство <math>AK_i</math>. Проще всего это сделать, если в данном подпространстве уже найден ортогональный базис.
+
:<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> должен обладать следующими свойствами:
+
r_i \perp A\mathcal{K}_i
<math>q_{i+1} \in K_{i+1}, p_{i+1} = Aq_{i+1} \perp AK_i</math>.
+
 
 +
</math>.
 +
 
 +
Таким образом, для реализации <math>i</math>-го шага требуется опустить перпендикуляр из вектора <math>r_0</math> на подпространство <math>A\mathcal{K}_i</math>. Проще всего это сделать, если в данном подпространстве уже найден ортогональный базис.
 +
 
 +
==== Геометрическая реализация ====
 +
 
 +
''Геометрическая реализация'' метода минимальных невязок заключается в построении последовательности векторов <math>q_1, q_2,...</math> таким образом, что <math>q_1, q_2,.., q_i</math> дают базис в подпространстве Крылова <math>\mathcal{K}_i</math> и при этом вектора <math>p_1 = Aq_1, ..., p_i = Aq_i</math> образуют ортогональный базис в подпространстве <math>A\mathcal{K}_i</math>. Вектор <math>q_{i+1} \notin \mathcal{K}_i</math> должен обладать следующими свойствами:
 +
:<math>
 +
 
 +
q_{i+1} \in \mathcal{K}_{i+1}, p_{i+1} = Aq_{i+1} \perp A\mathcal{K}_i
 +
 
 +
</math>.
  
 
Его можно получить с помощью процесса ортогонализации, применённого к вектору <math>p = Aq</math>, где <math>q = Aq_i</math>. В геометрической реализации необходимо хранить две системы векторов: <math>q_1, ..., q_i</math> и <math>p_1, ..., p_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>\mathcal{K}_i</math>.
 +
 
 +
<math>q_1 = r_0/||r_0||_2</math>. Чтобы получить ортонормированный базис  <math>q_1, ..., q_{i+1}</math> в <math>\mathcal{K}_{i+1} = \mathcal{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 \mathbb{C}^{n*i}</math>, то получим
 +
 
 +
:<math>
 +
 
 +
AQ_i = Q_{i+1}\hat{H_i}, \hat{H_i}= \begin{bmatrix} H_i \\ 0 ... 0 & h_{i+1 i} \end{bmatrix},
 +
 
 +
</math>
 +
 
 +
где <math>H_i</math> - верхняя хессенбергова матрица порядка <math>i</math>.
 +
 
 +
Далее рассмотрим <math>QR</math>-разложение прямоугольной матрицы <math>\hat{H_i}</math>:
 +
 
 +
:<math>
 +
 
 +
\hat{H_i} = U_iR_i, R_i \in \mathbb{C}^{i*i}
 +
 
 +
</math>.
 +
 
 +
Тогда минимум невязки <math>||r_0 - AQ_iy||_2</math> по всем <math>y</math> будет достигаться в том случае, если <math>y = y_i</math> удовлетворяет уравнению
 +
 
 +
:<math>
 +
 
 +
R_iy_i = z_i \equiv ||r_0||_2U^*_ie_1, e_1 = \begin{bmatrix} 1 0 ... 0 \end{bmatrix}^T,
 +
 
 +
</math>.
 +
 
 +
Матрица <math>R_i</math> невырожденная, следовательно,
 +
 
 +
:<math>
 +
 
 +
x_i = x_0 + Q_iy_i = x_0 + Q_iR_i^{-1}z_i
 +
 
 +
</math>.
 +
 
 +
=== Вычислительное ядро алгоритма ===
 +
 
 +
Главные затраты <math>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>.
+
=== Свойства алгоритма ===
  
 
== Литература ==
 
== Литература ==

Версия 16:59, 15 октября 2016

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 \mathcal{K}_i [/math]. Невязка имеет вид [math]r_i = r_0 - Ay[/math], а её длина минимальна, в силу теоремы Пифагора, в том и только том случае, когда

[math] r_i \perp A\mathcal{K}_i [/math].

Таким образом, для реализации [math]i[/math]-го шага требуется опустить перпендикуляр из вектора [math]r_0[/math] на подпространство [math]A\mathcal{K}_i[/math]. Проще всего это сделать, если в данном подпространстве уже найден ортогональный базис.

1.2.1 Геометрическая реализация

Геометрическая реализация метода минимальных невязок заключается в построении последовательности векторов [math]q_1, q_2,...[/math] таким образом, что [math]q_1, q_2,.., q_i[/math] дают базис в подпространстве Крылова [math]\mathcal{K}_i[/math] и при этом вектора [math]p_1 = Aq_1, ..., p_i = Aq_i[/math] образуют ортогональный базис в подпространстве [math]A\mathcal{K}_i[/math]. Вектор [math]q_{i+1} \notin \mathcal{K}_i[/math] должен обладать следующими свойствами:

[math] q_{i+1} \in \mathcal{K}_{i+1}, p_{i+1} = Aq_{i+1} \perp A\mathcal{K}_i [/math].

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

1.2.2 Алгебраическая реализация

Алгебраическая реализация метода минимальных невязок использует лишь одну систему векторов, образующих ортогональные базисы в подпространствах [math]\mathcal{K}_i[/math].

[math]q_1 = r_0/||r_0||_2[/math]. Чтобы получить ортонормированный базис [math]q_1, ..., q_{i+1}[/math] в [math]\mathcal{K}_{i+1} = \mathcal{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 \mathbb{C}^{n*i}[/math], то получим

[math] AQ_i = Q_{i+1}\hat{H_i}, \hat{H_i}= \begin{bmatrix} H_i \\ 0 ... 0 & h_{i+1 i} \end{bmatrix}, [/math]

где [math]H_i[/math] - верхняя хессенбергова матрица порядка [math]i[/math].

Далее рассмотрим [math]QR[/math]-разложение прямоугольной матрицы [math]\hat{H_i}[/math]:

[math] \hat{H_i} = U_iR_i, R_i \in \mathbb{C}^{i*i} [/math].

Тогда минимум невязки [math]||r_0 - AQ_iy||_2[/math] по всем [math]y[/math] будет достигаться в том случае, если [math]y = y_i[/math] удовлетворяет уравнению

[math] R_iy_i = z_i \equiv ||r_0||_2U^*_ie_1, e_1 = \begin{bmatrix} 1 0 ... 0 \end{bmatrix}^T, [/math].

Матрица [math]R_i[/math] невырожденная, следовательно,

[math] x_i = x_0 + Q_iy_i = x_0 + Q_iR_i^{-1}z_i [/math].

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

Главные затраты [math]i[/math]-ой итерации связаны с ортогонализацией.

1.4 Макроструктура алгоритма

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

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Литература

  1. Г.И. Марчук, Ю.А. Кузнецов, Итерационные методы и квадратичные функционалы, Методы вычислительной математики, Новосибирск, 1975, с. 4-143.
  2. 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).