Итерационный метод - Iterative method

В области вычислительной математики , А.Н. итерационный метод является математической процедурой , которая использует начальное значение для генерации последовательности улучшения приближенных решений для класса задач, в которых п -е приближение является производным от предыдущих. Конкретная реализация итерационного метода, включая критерии завершения , представляет собой алгоритм итерационного метода. Итерационный метод называется сходящимся, если соответствующая последовательность сходится при заданных начальных приближениях. Обычно выполняется математически строгий анализ сходимости итерационного метода; однако итерационные методы , основанные на эвристике , также широко распространены.

Напротив, прямые методы пытаются решить проблему с помощью конечной последовательности операций. При отсутствии ошибок округления прямые методы дадут точное решение (например, решение линейной системы уравнений методом исключения Гаусса ). Итерационные методы часто являются единственным выбором для нелинейных уравнений . Однако итерационные методы часто полезны даже для линейных задач, включающих множество переменных (иногда порядка миллионов), где прямые методы были бы чрезмерно дорогими (а в некоторых случаях невозможными) даже при наилучшей доступной вычислительной мощности. ${\ Displaystyle А \ mathbf {x} = \ mathbf {b}}$

Привлекательные фиксированные точки

Если уравнение может быть введено в виде F ( х ) = х , а решение х является привлекательной неподвижной точкой функции F , то можно начать с точкой х ₁ в бассейне притяжения от х , и пусть х _{n +1} = f ( x _n ) для n ≥ 1, и последовательность { x _n } _{n ≥ 1} сходится к решению x . Здесь x _n - это n- е приближение или итерация x, а x _{n +1} - следующая или n + 1 итерация x . В качестве альтернативы, верхние индексы в круглых скобках часто используются в числовых методах, чтобы не мешать нижним индексам с другими значениями. (Например, х ^{( п + 1)} = F ( х ^{( п )} ).) Если функция F является непрерывно дифференцируемой , достаточным условием сходимости является то , что спектральный радиус производной строго ограничена одной в окрестности фиксированная точка. Если это условие выполняется в неподвижной точке, то должна существовать достаточно малая окрестность (область притяжения).

Линейные системы

В случае системы линейных уравнений двумя основными классами итерационных методов являются стационарные итерационные методы и более общие методы подпространства Крылова .

Стационарные итерационные методы

Вступление

Стационарные итерационные методы решают линейную систему с оператором, аппроксимирующим исходную; и на основе измерения ошибки в результате ( остатка ) формируют «уравнение коррекции», для которого этот процесс повторяется. Хотя эти методы просты в получении, реализации и анализе, сходимость гарантируется только для ограниченного класса матриц.

Определение

Итерационный метод определяется

{\ Displaystyle \ mathbf {x} ^ {k + 1}: = \ Psi (\ mathbf {x} ^ {k}) \ ,, \ quad k \ geq 0}

и для заданной линейной системы с точным решением ошибки при ${\ Displaystyle А \ mathbf {x} = \ mathbf {b}}$ ${\ Displaystyle \ mathbf {х} ^ {*}}$

{\ displaystyle \ mathbf {e} ^ {k}: = \ mathbf {x} ^ {k} - \ mathbf {x} ^ {*} \ ,, \ quad k \ geq 0 \ ,.}

Итерационный метод называется линейным, если существует матрица такая, что ${\ Displaystyle С \ ин \ mathbb {R} ^ {п \ раз п}}$

{\ displaystyle \ mathbf {e} ^ {k + 1} = C \ mathbf {e} ^ {k} \ quad \ forall \, k \ geq 0}

и эта матрица называется итерационной матрицей . Итерационный метод с заданной матрицей итераций называется сходящимся, если выполняется следующее: ${\ displaystyle C}$

{\ displaystyle \ lim _ {k \ rightarrow \ infty} C ^ {k} = 0 \ ,.}

Важная теорема утверждает, что для данного итерационного метода и его итерационной матрицы он сходится тогда и только тогда, когда его спектральный радиус меньше единицы, то есть ${\ displaystyle C}$ ${\ displaystyle \ rho (C)}$

{\ Displaystyle \ rho (C) <1 \ ,.}

Основные итерационные методы работают путем разбиения матрицы на ${\ displaystyle A}$

{\ displaystyle A = MN}

и здесь матрица должна быть легко обратимой . Итерационные методы теперь определены как ${\ displaystyle M}$

{\ Displaystyle M \ mathbf {x} ^ {k + 1} = N \ mathbf {x} ^ {k} + b \ ,, \ quad k \ geq 0 \ ,.}

Отсюда следует, что итерационная матрица имеет вид

{\ Displaystyle C = IM ^ {- 1} A = M ^ {- 1} N \ ,.}

Примеры

Основные примеры стационарных итерационных методов используют разбиение матрицы, например ${\ displaystyle A}$

{\ Displaystyle A = D + L + U \ ,, \ quad D: = {\ text {diag}} ((a_ {ii}) _ {i})}

где только диагональная часть , и это строго нижняя треугольная часть из . Соответственно, является строгая верхняя треугольная часть . ${\ displaystyle D}$ ${\ displaystyle A}$ ${\ displaystyle L}$ ${\ displaystyle A}$ ${\ displaystyle U}$ ${\ displaystyle A}$

Метод Ричардсона : ${\ Displaystyle M: = {\ гидроразрыва {1} {\ omega}} I \ quad (\ omega \ neq 0)}$
Метод Якоби : ${\ Displaystyle M: = D}$
Затухающий метод Якоби : ${\ Displaystyle M: = {\ гидроразрыва {1} {\ omega}} D \ quad (\ omega \ neq 0)}$
Метод Гаусса – Зейделя : ${\ displaystyle M: = D + L}$
Метод последовательной избыточной релаксации (SOR): ${\ Displaystyle M: = {\ гидроразрыва {1} {\ omega}} D + L \ quad (\ omega \ neq 0)}$
Симметричное последовательное избыточное расслабление (SSOR): ${\ Displaystyle M: = {\ гидроразрыва {1} {\ omega (2- \ omega)}} (D + \ omega L) D ^ {- 1} (D + \ omega U) \ quad (\ omega \ neq \ { 0,2 \})}$

Линейные стационарные итерационные методы также называют методами релаксации .

Методы подпространства Крылова

Методы подпространства Крылова работают, формируя основу из последовательности последовательных степеней матрицы, умноженных на начальную невязку ( последовательность Крылова ). Затем формируются приближения к решению путем минимизации невязки по сформированному подпространству. Прототипным методом в этом классе является метод сопряженных градиентов (CG), который предполагает, что матрица системы является симметричной положительно определенной . Для симметричных (и, возможно, неопределенных) работает метод минимальной невязки (MINRES). В случае несимметричных матриц были получены такие методы, как метод обобщенных минимальных невязок (GMRES) и метод двусопряженных градиентов (BiCG). ${\ displaystyle A}$ ${\ displaystyle A}$

Сходимость методов подпространства Крылова

Поскольку эти методы составляют основу, очевидно, что метод сходится за N итераций, где N - размер системы. Однако при наличии ошибок округления это утверждение не выполняется; более того, на практике N может быть очень большим, и итерационный процесс достигает достаточной точности уже намного раньше. Анализ этих методов сложен и зависит от сложной функции спектра оператора.

Прекондиционеры

Аппроксимирующий оператор, который появляется в стационарных итерационных методах, также может быть включен в методы подпространства Крылова, такие как GMRES (альтернативно, предобусловленные методы Крылова можно рассматривать как ускорение стационарных итерационных методов), где они становятся преобразованиями исходного оператора в предположительно более обусловленный один. Строительство прекондиционеров - большая область исследований.

История

Вероятно, первый итерационный метод решения линейной системы появился в письме Гаусса к его ученику. Он предложил решить систему уравнений 4 на 4, многократно решая компонент, в котором невязка была наибольшей.

Теория стационарных итерационных методов была прочно обоснована работами Д.М. Юнга, начиная с 1950-х годов. Метод сопряженных градиентов также был изобретен в 1950-х годах независимыми разработками Корнелиуса Ланцоша , Магнуса Хестенеса и Эдуарда Штифеля , но его природа и применимость были неправильно поняты в то время. Только в 1970-х годах стало понятно, что методы, основанные на сопряженности, очень хорошо работают для уравнений в частных производных , особенно для эллиптических уравнений .

Languages

In other projects