Участник:Анюшева Ирина/Итерационный метод решения системы линейных алгебраических уравнений GMRES (обобщенный метод минимальных невязок): различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «Основные авторы описания: Анюшева Ирина (614 группа), Исхаков Эльдар (614 группа) == Свойства…»)
 
Строка 3: Строка 3:
 
== Свойства и структура алгоритма ==
 
== Свойства и структура алгоритма ==
  
 +
== Свойства и структура алгоритма ==
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
Обобщенный метод минимальных невязок (GMRES) для решения системы линейных алгебраических уравнений аппроксимирует решение с помощью вектора в подпространства Крылова с минимальным остатком. Метод GMRES разработан Ю.Саадом и Мартин Х. Шульцом в 1986 году.
+
Обобщенный метод минимальных невязок (GMRES) для решения системы линейных алгебраических уравнений аппроксимирует решение с помощью вектора в подпространства Крылова с минимальным остатком. Метод GMRES разработан Ю.Саадом и Мартин Х. Шульцом в 1986 году. Метод по праву считается одним из самых эффективных численных методов решения несимметричных систем. Он гарантирует неувеличение нормы невязки в ходе итерационного процесса, который строится основан на построении базиса в соответствующей системе подпространстве Крылова <math>K_j(A, r_0)</math>.
 +
Затем решение уточняется некоторой добавкой, представленной в виде разложения по этому базису.
 +
 
 +
Метод обобщенных минимальных невязок популярен из-за наличия ряда преимуществ: он ошибкоустойчив, допускает эффективное распараллеливание, не требует нахождения параметра релаксации, обладает суперлинейной скоростью сходимости. Однако в чистом виде для больших систем метод не используется из-за чрезвычайно больших затрат памяти. Зато широкое распространение получила перезапускаемая версия метода, подоразумевающая перезапуск метода каждые m итераций. Уменьшение размерности пространства может привести к стагнации метода – процессу, при котором с каждой следующей итерацией норма невязки уменьшается незначительно, либо не уменьшается вовсе.
 +
 
 +
=== Математическое описание алгоритма ===
 +
Исходные данные: система линейных алгебраических уравнений <math>Ax=b</math>
 +
 
 +
,где <math>A=(a_{ij})</math> -- вещественная матрица размера <math>n \times n</math>;
 +
 
 +
<math>b</math> и <math>x</math> вектора из <math>n</math> элементов;
 +
 
 +
<math>x^*</math> -- точное решение системы.
 +
 
 +
====Ортогонализация Арнольди====

Версия 03:44, 15 октября 2016

Основные авторы описания: Анюшева Ирина (614 группа), Исхаков Эльдар (614 группа)

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

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

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

Обобщенный метод минимальных невязок (GMRES) для решения системы линейных алгебраических уравнений аппроксимирует решение с помощью вектора в подпространства Крылова с минимальным остатком. Метод GMRES разработан Ю.Саадом и Мартин Х. Шульцом в 1986 году. Метод по праву считается одним из самых эффективных численных методов решения несимметричных систем. Он гарантирует неувеличение нормы невязки в ходе итерационного процесса, который строится основан на построении базиса в соответствующей системе подпространстве Крылова [math]K_j(A, r_0)[/math]. Затем решение уточняется некоторой добавкой, представленной в виде разложения по этому базису.

Метод обобщенных минимальных невязок популярен из-за наличия ряда преимуществ: он ошибкоустойчив, допускает эффективное распараллеливание, не требует нахождения параметра релаксации, обладает суперлинейной скоростью сходимости. Однако в чистом виде для больших систем метод не используется из-за чрезвычайно больших затрат памяти. Зато широкое распространение получила перезапускаемая версия метода, подоразумевающая перезапуск метода каждые m итераций. Уменьшение размерности пространства может привести к стагнации метода – процессу, при котором с каждой следующей итерацией норма невязки уменьшается незначительно, либо не уменьшается вовсе.

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

Исходные данные: система линейных алгебраических уравнений [math]Ax=b[/math]

,где [math]A=(a_{ij})[/math] -- вещественная матрица размера [math]n \times n[/math];

[math]b[/math] и [math]x[/math] вектора из [math]n[/math] элементов;

[math]x^*[/math] -- точное решение системы.

2.2.1 Ортогонализация Арнольди