Участник:Alexander34396/Обобщенный метод минимальных невязок: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 48: Строка 48:
  
 
Построение ортонормального базиса <math> K_n </math>:
 
Построение ортонормального базиса <math> K_n </math>:
 +
 
Для всех <math> j </math> от 1 до n по нарастанию выполнять
 
Для всех <math> j </math> от 1 до n по нарастанию выполнять
 
#<math> h_{ij} := (Av_j, v_i), \quad i=1,\ldots,j </math>;
 
#<math> h_{ij} := (Av_j, v_i), \quad i=1,\ldots,j </math>;
Строка 54: Строка 55:
 
#<math> v_{j+1} = \frac{\hat{v}_{j+1}}{h_{j+1j}} </math>.
 
#<math> v_{j+1} = \frac{\hat{v}_{j+1}}{h_{j+1j}} </math>.
 
Вычисление приближённого решения <math> x_n </math>:
 
Вычисление приближённого решения <math> x_n </math>:
:<math> x_n = x_0 + V_ny_n </math>.
+
:<math> x_n = x_0 + V_ny_n </math>,
 +
где <math>y_n</math> минимизирует <math>\|r_0 - AV_ny_n\|_2</math>.

Версия 17:37, 15 октября 2016

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

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

Обобщённый метод минимальных невязок (англ. Generalized minimal residual method, GMRES) - итерационный метод численного решения системы линейных алгебраических уравнений с невырожденной матрицей. Метод основан на минимизации квадратичного функционала невязки на подпространствах Крылова. Разработан Юсефом Саадом и Мартином Шульцем в 1986 году как обобщение метода MINRES на случай систем с несимметричными матрицами.

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

Исходные данные:

  • система линейных алгебраических уравнений вида [math] Ax = b [/math], где [math] A [/math] — невырожденная матрица размера [math]m[/math]-на-[math] m [/math];
  • подпространство Крылова размерности [math] n [/math], порождённое вектором [math] b [/math] и матрицей [math] A [/math]:
[math] K_n = K_n(A,b) = \operatorname{span} \, \{ b, Ab, A^2b, \ldots, A^{n-1}b \}. \, [/math]

Вычисляемые данные:

  • [math] x_n \in K_n [/math] - приближённое решение исходной системы.

Метод GMRES приближает точное решение исходной системы [math] Ax = b [/math] вектором [math] x_n \in K_n [/math], минимизирующим Евклидову норму невязки [math]r_n= Ax_n-b[/math].

Для решения исходной системы GMRES, используя [math] l_2 [/math]-ортонормальный базис пространства [math] K_n [/math], выполняет поиск приближённого решения [math] x_n [/math] в виде:

[math] x_n = x_0 + z_n [/math],

где [math] x_0 [/math] - некоторое начальное приближение, [math] z_n \in K_n [/math] - поправка решения.

Для построения ортонормального базиса [math] K_n [/math] метод использует ортогонализацию Арнольди. При введении для базиса [math] K_n [/math] матричного обозначения [math] V_n [/math] можно записать:

[math] z_n = V_ny_n [/math],

где [math] y_n \in \mathbb{R}^n [/math] - вектор коэффициентов.

В общем виде алгоритм метода GMRES может быть записан следующим образом:

  1. найти ортонормальный базис [math] V_n [/math] подпространства [math] K_n [/math] с помощью ортогонализации Арнольди;
  2. найти [math] y_n [/math], минимизирующий [math] \|r_n\|_2 [/math];
  3. посчитать [math] x_n = x_0 + V_ny_n [/math];
  4. повторить, если требуемая точность не была достигнута.

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

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

Для решения исходной системы методом GMRES можно воспользоваться следующим алгоритмом:

Подготовка перед итерационным процессом
  1. Выбрать начальное приближение [math] x_0 [/math];
  2. Посчитать невязку [math] r_0 = b - Ax_0 [/math];
  3. Вычислить [math] v_1 = \frac{r_0}{\|r_0\|_2} [/math].
[math]n[/math]-я итерация метода

Построение ортонормального базиса [math] K_n [/math]:

Для всех [math] j [/math] от 1 до n по нарастанию выполнять

  1. [math] h_{ij} := (Av_j, v_i), \quad i=1,\ldots,j [/math];
  2. [math] \hat{v}_{j+1} := Av_j - \sum_{i=1}^j h_{ij}v_{i} [/math];
  3. [math] h_{j+1j} = \|\hat{v}_{j+1}\|_2 [/math];
  4. [math] v_{j+1} = \frac{\hat{v}_{j+1}}{h_{j+1j}} [/math].

Вычисление приближённого решения [math] x_n [/math]:

[math] x_n = x_0 + V_ny_n [/math],

где [math]y_n[/math] минимизирует [math]\|r_0 - AV_ny_n\|_2[/math].