Участник:Alexander34396/Обобщенный метод минимальных невязок: различия между версиями
Строка 7: | Строка 7: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
− | Исходные данные: | + | '''Исходные данные:''' |
− | * система линейных алгебраических уравнений вида <math> Ax = b </math>, где <math> A </math> — невырожденная матрица размера <math> | + | * система линейных алгебраических уравнений вида <math> Ax = b </math>, где <math> A </math> — невырожденная матрица размера <math>n</math>-на-<math> n </math>; |
− | * подпространство Крылова размерности <math> n </math>, порождённое вектором <math> b </math> и матрицей <math> A </math>: | + | * подпространство Крылова размерности <math> m, m <= n </math>, порождённое вектором <math> b </math> и матрицей <math> A </math>: |
− | :<math> | + | :<math> K_m = K_m(A,b) = \operatorname{span} \, \{ b, Ab, A^2b, \ldots, A^{m-1}b \}. \, </math> |
− | Вычисляемые данные: | + | '''Вычисляемые данные:''' |
− | * <math> | + | * <math> x_m \in K_m </math> - приближённое решение исходной системы. |
− | Метод GMRES приближает точное решение исходной системы <math> Ax = b </math> вектором <math> | + | Метод GMRES приближает точное решение исходной системы <math> Ax = b </math> вектором <math> x_m \in K_m </math>, минимизирующим Евклидову норму невязки <math>r_m = Ax_m-b</math>. |
− | Для решения исходной системы GMRES, используя <math> l_2 </math>-ортонормальный базис пространства <math> | + | Для решения исходной системы GMRES, используя <math> l_2 </math>-ортонормальный базис пространства <math> K_m </math>, выполняет поиск приближённого решения <math> x_m </math> в виде: |
− | :<math> | + | :<math> x_m = x_0 + z_m </math>, |
− | где <math> x_0 </math> - некоторое начальное приближение, <math> | + | где <math> x_0 </math> - некоторое начальное приближение, <math> z_m \in K_m </math> - поправка решения. |
− | Для построения ортонормального базиса <math> | + | Для построения ортонормального базиса <math> K_m </math> метод использует ортогонализацию Арнольди. При введении для базиса <math> K_m </math> матричного обозначения <math> V_m </math> можно записать: |
− | :<math> | + | :<math> z_m = V_my_m </math>, |
− | где <math> | + | где <math> y_m \in \mathbb{R}^m </math> - вектор коэффициентов. |
В общем виде алгоритм метода GMRES может быть записан следующим образом: | В общем виде алгоритм метода GMRES может быть записан следующим образом: | ||
− | # найти ортонормальный базис <math> | + | # найти ортонормальный базис <math> V_m </math> подпространства <math> K_m </math> с помощью ортогонализации Арнольди; |
− | # найти <math> | + | # найти <math> y_m </math>, минимизирующий <math> \|r_m\|_2 </math>; |
− | # посчитать <math> | + | # посчитать <math> x_m = x_0 + V_my_m </math>; |
− | # | + | # посчитать <math> r_m </math> и остановиться,если требуемая точность была достигнута, иначе повторить. |
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
Вычислительное ядро последовательной версии метода GMRES состоит из двух частей: | Вычислительное ядро последовательной версии метода GMRES состоит из двух частей: | ||
− | * Вычисление ортонормального базиса <math> | + | * Вычисление ортонормального базиса <math> K_m </math> с помощью ортогонализации Арнольди: |
− | : | + | : на одной итерации алгоритма <math> m(m + 1) n + mNZ </math> мультипликативных операций, где NZ - количество ненулевых элементов матрицы <math> A </math>; |
− | + | * Формирование приближенного решения <math> x_0 + V_mY_m </math>: | |
− | + | : <math>nm</math> мультипликативных операций. | |
− | + | ||
+ | === Макроструктура алгоритма === | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
Строка 44: | Строка 45: | ||
Для решения исходной системы методом GMRES можно воспользоваться следующим алгоритмом: | Для решения исходной системы методом GMRES можно воспользоваться следующим алгоритмом: | ||
− | + | 1 Подготовка перед итерационным процессом: | |
+ | :1.1 Выбрать начальное приближение <math> x_0 </math>; | ||
+ | :1.2 Посчитать невязку <math> r_0 = b - Ax_0 </math>; | ||
+ | :1.3 Вычислить <math> v_1 = \frac{r_0}{\|r_0\|_2} </math>. | ||
− | + | 2 Построение ортонормального базиса <math> K_m </math>: | |
− | |||
− | |||
− | ;<math> | + | :Для всех <math> j </math> от 1 до m по нарастанию выполнять: |
+ | :2.1 <math> h_{ij} := (Av_j, v_i), \quad i=1,\ldots,j </math>; | ||
+ | :2.2 <math> \hat{v}_{j+1} := Av_j - \sum_{i=1}^j h_{ij}v_{i} </math>; | ||
+ | :2.3 <math> h_{j+1j} = \|\hat{v}_{j+1}\|_2 </math>; | ||
+ | :2.4 <math> v_{j+1} = \frac{\hat{v}_{j+1}}{h_{j+1j}} </math>. | ||
− | + | 3 Вычисление приближённого решения <math> x_m </math>: | |
+ | :3.1 <math> x_m = x_0 + V_my_m </math>, где <math>y_m</math> минимизирует <math>\|r_0 - AV_my_m\|_2</math>; | ||
+ | :3.2 Вычислить <math> r_m </math>; | ||
+ | :3.3 Если требуемая точность достигнута, остановиться. | ||
− | + | 4 Рестарт: | |
− | + | :4.1 <math>x_0 = x_m</math>; | |
− | + | :4.2 <math>v_1 = \frac{r_m}{\|r_m\|_2}</math>; | |
− | + | :4.3 Перейти к шагу 2. | |
− | |||
− | |||
− | |||
− |
Версия 21:08, 15 октября 2016
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Обобщённый метод минимальных невязок (англ. Generalized minimal residual method, GMRES) - итерационный метод численного решения системы линейных алгебраических уравнений с невырожденной матрицей. Метод основан на минимизации квадратичного функционала невязки на подпространствах Крылова. Разработан Юсефом Саадом и Мартином Шульцем в 1986 году как обобщение метода MINRES на случай систем с несимметричными матрицами.
1.2 Математическое описание алгоритма
Исходные данные:
- система линейных алгебраических уравнений вида [math] Ax = b [/math], где [math] A [/math] — невырожденная матрица размера [math]n[/math]-на-[math] n [/math];
- подпространство Крылова размерности [math] m, m \lt = n [/math], порождённое вектором [math] b [/math] и матрицей [math] A [/math]:
- [math] K_m = K_m(A,b) = \operatorname{span} \, \{ b, Ab, A^2b, \ldots, A^{m-1}b \}. \, [/math]
Вычисляемые данные:
- [math] x_m \in K_m [/math] - приближённое решение исходной системы.
Метод GMRES приближает точное решение исходной системы [math] Ax = b [/math] вектором [math] x_m \in K_m [/math], минимизирующим Евклидову норму невязки [math]r_m = Ax_m-b[/math].
Для решения исходной системы GMRES, используя [math] l_2 [/math]-ортонормальный базис пространства [math] K_m [/math], выполняет поиск приближённого решения [math] x_m [/math] в виде:
- [math] x_m = x_0 + z_m [/math],
где [math] x_0 [/math] - некоторое начальное приближение, [math] z_m \in K_m [/math] - поправка решения.
Для построения ортонормального базиса [math] K_m [/math] метод использует ортогонализацию Арнольди. При введении для базиса [math] K_m [/math] матричного обозначения [math] V_m [/math] можно записать:
- [math] z_m = V_my_m [/math],
где [math] y_m \in \mathbb{R}^m [/math] - вектор коэффициентов.
В общем виде алгоритм метода GMRES может быть записан следующим образом:
- найти ортонормальный базис [math] V_m [/math] подпространства [math] K_m [/math] с помощью ортогонализации Арнольди;
- найти [math] y_m [/math], минимизирующий [math] \|r_m\|_2 [/math];
- посчитать [math] x_m = x_0 + V_my_m [/math];
- посчитать [math] r_m [/math] и остановиться,если требуемая точность была достигнута, иначе повторить.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро последовательной версии метода GMRES состоит из двух частей:
- Вычисление ортонормального базиса [math] K_m [/math] с помощью ортогонализации Арнольди:
- на одной итерации алгоритма [math] m(m + 1) n + mNZ [/math] мультипликативных операций, где NZ - количество ненулевых элементов матрицы [math] A [/math];
- Формирование приближенного решения [math] x_0 + V_mY_m [/math]:
- [math]nm[/math] мультипликативных операций.
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
Для решения исходной системы методом GMRES можно воспользоваться следующим алгоритмом:
1 Подготовка перед итерационным процессом:
- 1.1 Выбрать начальное приближение [math] x_0 [/math];
- 1.2 Посчитать невязку [math] r_0 = b - Ax_0 [/math];
- 1.3 Вычислить [math] v_1 = \frac{r_0}{\|r_0\|_2} [/math].
2 Построение ортонормального базиса [math] K_m [/math]:
- Для всех [math] j [/math] от 1 до m по нарастанию выполнять:
- 2.1 [math] h_{ij} := (Av_j, v_i), \quad i=1,\ldots,j [/math];
- 2.2 [math] \hat{v}_{j+1} := Av_j - \sum_{i=1}^j h_{ij}v_{i} [/math];
- 2.3 [math] h_{j+1j} = \|\hat{v}_{j+1}\|_2 [/math];
- 2.4 [math] v_{j+1} = \frac{\hat{v}_{j+1}}{h_{j+1j}} [/math].
3 Вычисление приближённого решения [math] x_m [/math]:
- 3.1 [math] x_m = x_0 + V_my_m [/math], где [math]y_m[/math] минимизирует [math]\|r_0 - AV_my_m\|_2[/math];
- 3.2 Вычислить [math] r_m [/math];
- 3.3 Если требуемая точность достигнута, остановиться.
4 Рестарт:
- 4.1 [math]x_0 = x_m[/math];
- 4.2 [math]v_1 = \frac{r_m}{\|r_m\|_2}[/math];
- 4.3 Перейти к шагу 2.