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

Материал из Алговики
Перейти к навигации Перейти к поиску
← Предыдущая правкаСледующая правка →
Нет описания правки
Нет описания правки
Строка 18: Строка 18:
Метод GMRES приближает точное решение исходной системы <math> Ax = b </math> вектором <math> x_k \in K_k </math>, минимизирующим Евклидову норму невязки <math>r_k = Ax_k-b</math>.
Метод GMRES приближает точное решение исходной системы <math> Ax = b </math> вектором <math> x_k \in K_k </math>, минимизирующим Евклидову норму невязки <math>r_k = Ax_k-b</math>.


Для решения исходной системы GMRES, используя <math> l_2 </math>-ортонормальный базис пространства <math> K_k </math>, выполняет поиск приближённого решения <math> x_k </math> в виде:  
Для решения исходной системы GMRES, используя <math> l_2 </math>-ортонормированный базис пространства <math> K_k </math>, выполняет поиск приближённого решения <math> x_k </math> в виде:  
:<math> x_k = x_0 + z_k </math>,  
:<math> x_k = x_0 + z_k </math>,  
где <math> x_0 </math> - некоторое начальное приближение, <math> z_k \in K_k </math> - поправка решения.
где <math> x_0 </math> - некоторое начальное приближение, <math> z_k \in K_k </math> - поправка решения.


Для построения ортонормального базиса <math> K_k </math> метод использует ортогонализацию Арнольди. При введении для базиса <math> K_k </math> матричного обозначения <math> V_k </math> можно записать:  
Для построения ортонормированного базиса <math> K_k </math> метод использует ортогонализацию Арнольди. При введении для базиса <math> K_k </math> матричного обозначения <math> V_k </math> можно записать:  
:<math> z_k = V_ky_k </math>,  
:<math> z_k = V_ky_k </math>,  
где <math> y_k \in \mathbb{R}^k </math> - вектор коэффициентов.
где <math> y_k \in \mathbb{R}^k </math> - вектор коэффициентов.
Строка 28: Строка 28:
В общем виде k-aя итерация алгоритма GMRES может быть записан следующим образом:
В общем виде k-aя итерация алгоритма GMRES может быть записан следующим образом:


# найти ортонормальный базис <math> V_k </math> подпространства <math> K_k </math> с помощью ортогонализации Арнольди;
# найти ортонормированный базис <math> V_k </math> подпространства <math> K_k </math> с помощью ортогонализации Арнольди;
# найти <math> y_k </math>, минимизирующий <math> \|r_k\|_2 </math>;
# найти <math> y_k </math>, минимизирующий <math> \|r_k\|_2 </math>;
# вычислить <math> x_k = x_0 + V_ky_k </math>;
# вычислить <math> x_k = x_0 + V_ky_k </math>;
Строка 36: Строка 36:


Вычислительное ядро последовательной версии метода GMRES состоит из двух частей:
Вычислительное ядро последовательной версии метода GMRES состоит из двух частей:
* Вычисление ортонормального базиса <math> K_k </math>;
* Вычисление ортонормированного базиса <math> K_k </math>;
* Формирование приближенного решения <math> x_k </math>.
* Формирование приближенного решения <math> x_k </math>.


На каждой итерации для вычисления ортонормального базиса <math> K_k </math> метод использует процесс Арнольди:
На каждой итерации для вычисления ортонормированного базиса <math> K_k </math> метод использует процесс Арнольди:
: <math> \hat{v}_{k+1} := Av_k - \sum_{i=1}^k h_{ik}v_{k} </math>, где <math> h_{ik} := (Av_k, v_i) </math>.
: <math> \hat{v}_{k+1} := Av_k - \sum_{i=1}^k h_{ik}v_{k} </math>, где <math> h_{ik} := (Av_k, v_i) </math>.
Этот процесс требует <math> k(k + 1) n + kNZ  </math> мультипликативных операций, где NZ - количество ненулевых элементов матрицы <math> A </math>.
Этот процесс требует <math> k(k + 1) n + kNZ  </math> мультипликативных операций, где NZ - количество ненулевых элементов матрицы <math> A </math>.
Строка 73: Строка 73:
# <math> v_{k+1} = \frac{\hat{v}_{k+1}}{h_{k+1k}} </math>;
# <math> v_{k+1} = \frac{\hat{v}_{k+1}}{h_{k+1k}} </math>;
# <math> x_k = x_0 + V_ky_k </math>, где <math>y_k</math> минимизирует <math>\|r_0 - AV_ky_k\|_2</math>.
# <math> x_k = x_0 + V_ky_k </math>, где <math>y_k</math> минимизирует <math>\|r_0 - AV_ky_k\|_2</math>.
=== Последовательная сложность алгоритма ===


== Литература ==
== Литература ==
<references \>
<references \>

Версия от 20:56, 15 октября 2016

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

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

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

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

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

  • система линейных алгебраических уравнений вида [math]\displaystyle{ Ax = b }[/math], где [math]\displaystyle{ A }[/math] — невырожденная матрица размера [math]\displaystyle{ n }[/math]-на-[math]\displaystyle{ n }[/math];
  • [math]\displaystyle{ x_0 }[/math] - некоторое начальное приближение.

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

  • [math]\displaystyle{ x_k }[/math] - приближённое решение исходной системы.

Подпространство Крылова размерности [math]\displaystyle{ k, k \leq n }[/math] для решения исходной системы:

[math]\displaystyle{ K_k = K_k(A,b) = \operatorname{span} \, \{ b, Ab, A^2b, \ldots, A^{k-1}b \}. \, }[/math]

Метод GMRES приближает точное решение исходной системы [math]\displaystyle{ Ax = b }[/math] вектором [math]\displaystyle{ x_k \in K_k }[/math], минимизирующим Евклидову норму невязки [math]\displaystyle{ r_k = Ax_k-b }[/math].

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

[math]\displaystyle{ x_k = x_0 + z_k }[/math],

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

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

[math]\displaystyle{ z_k = V_ky_k }[/math],

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

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

  1. найти ортонормированный базис [math]\displaystyle{ V_k }[/math] подпространства [math]\displaystyle{ K_k }[/math] с помощью ортогонализации Арнольди;
  2. найти [math]\displaystyle{ y_k }[/math], минимизирующий [math]\displaystyle{ \|r_k\|_2 }[/math];
  3. вычислить [math]\displaystyle{ x_k = x_0 + V_ky_k }[/math];
  4. вычислить [math]\displaystyle{ r_k }[/math] и остановиться,если требуемая точность была достигнута, иначе повторить для k + 1.

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

Вычислительное ядро последовательной версии метода GMRES состоит из двух частей:

  • Вычисление ортонормированного базиса [math]\displaystyle{ K_k }[/math];
  • Формирование приближенного решения [math]\displaystyle{ x_k }[/math].

На каждой итерации для вычисления ортонормированного базиса [math]\displaystyle{ K_k }[/math] метод использует процесс Арнольди:

[math]\displaystyle{ \hat{v}_{k+1} := Av_k - \sum_{i=1}^k h_{ik}v_{k} }[/math], где [math]\displaystyle{ h_{ik} := (Av_k, v_i) }[/math].

Этот процесс требует [math]\displaystyle{ k(k + 1) n + kNZ }[/math] мультипликативных операций, где NZ - количество ненулевых элементов матрицы [math]\displaystyle{ A }[/math].

Для нахождения на каждой итерации приближённого решения метод использует формулу:

[math]\displaystyle{ x_k = x_0 + V_ky_k }[/math].

Вычисление этой формулы требует [math]\displaystyle{ nk }[/math] мультипликативных операций.

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

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

  • Умножение матрицы на вектор;
  • Вычисление скалярного произведения векторов;
  • Вычисление Евклидовой нормы вектора;
  • Умножение вектора на скаляр;
  • Деление вектора на скаляр;
  • Задача минимизации функционала [math]\displaystyle{ \|r_0 - AV_ky_k\|_2 }[/math].

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

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

Подготовка перед итерационным процессом:

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

k-ая итерация:

  1. [math]\displaystyle{ h_{ik} := (Av_k, v_i), \quad i=1,\ldots,k }[/math];
  2. [math]\displaystyle{ \hat{v}_{k+1} := Av_k - \sum_{i=1}^k h_{ik}v_{i} }[/math];
  3. [math]\displaystyle{ h_{k+1k} = \|\hat{v}_{k+1}\|_2 }[/math];
  4. [math]\displaystyle{ v_{k+1} = \frac{\hat{v}_{k+1}}{h_{k+1k}} }[/math];
  5. [math]\displaystyle{ x_k = x_0 + V_ky_k }[/math], где [math]\displaystyle{ y_k }[/math] минимизирует [math]\displaystyle{ \|r_0 - AV_ky_k\|_2 }[/math].

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

Литература

<references \>

  1. ↑ 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)
  2. ↑ C. C. Paige and M. A. Saunders. Solution of sparse indefinite systems of linear equations, SIAM J. Numerical Analysis 12, 617-629 (1975)
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Участник:Alexander34396/Обобщенный_метод_минимальных_невязок&oldid=12030