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

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

Напротив, прямые методы пытаются решить проблему с помощью конечной последовательности операций. При отсутствии ошибок округления прямые методы дадут точное решение (например, решение линейной системы уравнений методом исключения Гаусса ). Итерационные методы часто являются единственным выбором для нелинейных уравнений . Однако итерационные методы часто полезны даже для линейных задач, включающих множество переменных (иногда порядка миллионов), где прямые методы были бы чрезмерно дорогими (а в некоторых случаях невозможными) даже при наилучшей доступной вычислительной мощности. ^[1]${\ 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 {x} ^{*}}$

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

Итерационный метод называется линейным, если существует матрица такая, что${\displaystyle C\in \mathbb {R} ^{n\times n}}$

${\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=M-N}$

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

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

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

${\displaystyle C=I-M^{-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:={\frac {1}{\omega }}I\quad (\omega \neq 0)}$
• Метод Якоби :${\displaystyle M:=D}$
• Демпфированный метод Якоби :${\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}$
• Метод Гаусса – Зейделя :${\displaystyle M:=D+L}$
• Метод последовательной избыточной релаксации (SOR):${\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}$
• Симметричное последовательное избыточное расслабление (SSOR):${\displaystyle M:={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \neq \{0,2\})}$

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

Методы подпространства Крылова [ править ]

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

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

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

Предварительные кондиционеры [ править ]

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

История [ править ]

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

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

См. Также [ править ]

• Выражение в закрытой форме
• Нелинейный метод наименьших квадратов
• Числовой анализ
• Алгоритм поиска корней

Ссылки [ править ]

Внешние ссылки [ править ]

Викискладе есть медиафайлы по итерационным методам .

• Шаблоны для решения линейных систем
• Ю. Саад: Итерационные методы для разреженных линейных систем , 1-е издание, PWS 1996