Участник:Alexander34396/Обобщенный метод минимальных невязок
| Файл:Symbol wait.svg | Эта работа ждет рассмотрения преподавателем Дата последней правки страницы: 17.10.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 }[/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 может быть записан следующим образом:
- найти ортонормированный базис [math]\displaystyle{ V_k }[/math] подпространства [math]\displaystyle{ K_k }[/math] с помощью ортогонализации Арнольди;
- найти [math]\displaystyle{ y_k }[/math], минимизирующий [math]\displaystyle{ \|r_k\|_2 }[/math];
- вычислить [math]\displaystyle{ x_k = x_0 + V_ky_k }[/math];
- вычислить [math]\displaystyle{ r_k }[/math] и остановиться,если требуемая точность была достигнута, иначе повторить.
Вычислительное ядро алгоритма
Вычислительное ядро последовательной версии метода GMRES состоит из двух частей:
- Вычисление ортонормированного базиса [math]\displaystyle{ K_k }[/math];
- Формирование приближенного решения [math]\displaystyle{ x_k }[/math].
Для вычисления ортонормированного базиса [math]\displaystyle{ K_k }[/math] метод использует процесс Арнольди:
- [math]\displaystyle{ h_{j+1j}v_{j+1} = Av_j - \sum_{i=1}^j h_{ij}v_{j} }[/math], где [math]\displaystyle{ h_{ij} = (Av_j, v_i) }[/math], [math]\displaystyle{ \quad j=1,\ldots,k }[/math].
Для нахождения приближённого решения [math]\displaystyle{ x_k }[/math] метод использует формулу:
- [math]\displaystyle{ x_k = x_0 + V_ky_k }[/math].
Макроструктура алгоритма
В алгоритме можно выделить следующие макрооперации:
- Умножение матрицы на вектор;
- Вычисление скалярного произведения векторов;
- Вычисление Евклидовой нормы вектора;
- Умножение вектора на скаляр;
- Деление вектора на скаляр.
Схема реализации последовательного алгоритма
Для решения исходной системы методом GMRES можно воспользоваться следующим алгоритмом:
Подготовка перед итерационным процессом:
- Выбрать начальное приближение [math]\displaystyle{ x_0 }[/math];
- Посчитать невязку [math]\displaystyle{ r_0 = b - Ax_0 }[/math];
- Вычислить [math]\displaystyle{ v_1 = \frac{r_0}{\|r_0\|_2} }[/math].
k-ая итерация:
- [math]\displaystyle{ h_{ik} = (Av_k, v_i), \quad i=1,\ldots,k }[/math];
- [math]\displaystyle{ \hat{v}_{k+1} = Av_k - \sum_{i=1}^k h_{ik}v_{i} }[/math];
- [math]\displaystyle{ h_{k+1k} = \|\hat{v}_{k+1}\|_2 }[/math];
- [math]\displaystyle{ v_{k+1} = \frac{\hat{v}_{k+1}}{h_{k+1k}} }[/math];
- [math]\displaystyle{ x_k = x_0 + V_ky_k }[/math], где [math]\displaystyle{ y_k }[/math] минимизирует [math]\displaystyle{ \|r_0 - AV_ky_k\|_2 }[/math].
Последовательная сложность алгоритма
Если пренебречь сложностью вычисления [math]\displaystyle{ y_k }[/math], то общую сложность алгоритма GMRES можно разделить на две части:
- 1. Сложность вычисления ортонормированного базиса пространства [math]\displaystyle{ K_k }[/math]
- a) Для вычисления [math]\displaystyle{ j }[/math]-го вектора базиса [math]\displaystyle{ K_k, j \lt k }[/math] требуется:
- [math]\displaystyle{ NZ + (2j + 1)n }[/math] мультипликативных операций, где [math]\displaystyle{ NZ }[/math] - количество ненулевых элементов матрицы [math]\displaystyle{ A }[/math].
- b) Вычисление последнего вектора базиса требует:
- [math]\displaystyle{ n(k + 1) }[/math] мультипликативных операций.
- c) Общая мультипликативная сложность вычисления ортонормированного базиса [math]\displaystyle{ K_k }[/math]:
- [math]\displaystyle{ nk(k + 1) + kNZ }[/math].
- 2. Сложность вычисления приближённого решения [math]\displaystyle{ x_k }[/math]
- Вычисление этой формулы требует [math]\displaystyle{ nk }[/math] мультипликативных операций.
Информационный граф
Литература
<references \>
- ↑ 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)
- ↑ C. C. Paige and M. A. Saunders. Solution of sparse indefinite systems of linear equations, SIAM J. Numerical Analysis 12, 617-629 (1975)