Участник:Анюшева Ирина/Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок)
Основные авторы описания: Анюшева Ирина (614 группа), Исхаков Эльдар (614 группа)
Свойства и структура алгоритма
Общее описание алгоритма
Обобщенный метод минимальных невязок (GMRES) для решения системы линейных алгебраических уравнений аппроксимирует решение с помощью вектора в подпространства Крылова с минимальным остатком. Метод GMRES разработан Ю.Саадом и Мартин Х. Шульцом в 1986 году. Метод по праву считается одним из самых эффективных численных методов решения несимметричных систем. Он гарантирует неувеличение нормы невязки в ходе итерационного процесса, который строится основан на построении базиса в соответствующей системе подпространстве Крылова [math]\displaystyle{ K_j(A, r_0) }[/math]. Затем решение уточняется некоторой добавкой, представленной в виде разложения по этому базису.
Метод обобщенных минимальных невязок популярен из-за наличия ряда преимуществ: он ошибкоустойчив, допускает эффективное распараллеливание, не требует нахождения параметра релаксации, обладает суперлинейной скоростью сходимости. Однако в чистом виде для больших систем метод не используется из-за чрезвычайно больших затрат памяти. Зато широкое распространение получила перезапускаемая версия метода, подоразумевающая перезапуск метода каждые m итераций. Уменьшение размерности пространства может привести к стагнации метода – процессу, при котором с каждой следующей итерацией норма невязки уменьшается незначительно, либо не уменьшается вовсе.
Математическое описание алгоритма
Исходные данные: система линейных алгебраических уравнений [math]\displaystyle{ Ax=b }[/math], где:
[math]\displaystyle{ A=(a_{ij}) }[/math] [math]\displaystyle{ - }[/math] вещественная матрица размера [math]\displaystyle{ n \times n }[/math];
[math]\displaystyle{ b }[/math] и [math]\displaystyle{ x }[/math] вектора из [math]\displaystyle{ n }[/math] элементов;
[math]\displaystyle{ x^* }[/math] [math]\displaystyle{ - }[/math] точное решение системы.
Вычисляемые данные: [math]\displaystyle{ x^{(s)} - }[/math]приближенное решение системы.
Ортогонализация Арнольди
Для построения базиса в подпространстве Крылова в методе GMRES применяется ортогонализация Арнольди.
Формулы метода:
- [math]\displaystyle{ \begin{align} (h_{i+1,i}v_{i+1}) & = Av_i - \sum_{j = 1}^{i} h_{j,i}v_j, \\ v_1 &= \frac{r_0}{\parallel r_0 \parallel}, \end{align} }[/math]
В матрично-векторных обозначениях соотношение может быть записано как
- [math]\displaystyle{ \begin{align} AV_i &= V_i H_i + h_{i+1,i}v_{i+1} e^T &=V_{i+1}\overline{H_i}, \end{align} }[/math]
V_i &= верхняя матрица Хессенберга [math]\displaystyle{ \overline{H} \in R }[/math]
Схема реализации последовательного алгоритма
[math]\displaystyle{ 1. \text{Выбрать } }[/math]