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

В вычислительной математике итерационный метод — это математическая процедура , которая использует начальное значение для генерации последовательности улучшения приближенных решений для класса задач, в которой i -е приближение (называемое «итерацией») выводится из предыдущих. .

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

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

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

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

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

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

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

Введение

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

Определение

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

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

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

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

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

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

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

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

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

\rho (C)<1\,.

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

A=M-N

а здесь матрица $M$ должно быть легко обратимым . Итерационные методы теперь определяются как

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

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

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

Примеры

Базовые примеры стационарных итерационных методов используют расщепление матрицы $A$ такой как

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

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

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

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

Krylov subspace methods

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

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

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

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

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

История

Джамшид аль-Каши использовал итерационные методы для расчета синуса 1 ° и $π$ в «Трактате об хорде и синусе» с высокой точностью. Первый итерационный метод решения линейной системы появился в письме Гаусса своему ученику. Он предложил решать систему уравнений 4х4, многократно решая ту компоненту, в которой невязка была наибольшей. ^{[ нужна ссылка ]}.

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

См. также

Ссылки

^ Амриткар, Амит; де Стерлер, Эрик; Свиридович, Катажина; Тафти, Данеш; Ахуджа, Капил (2015). «Переработка подпространств Крылова для приложений CFD и новый гибридный решатель переработки». Журнал вычислительной физики . 303 : 222. arXiv : 1501.03358 . Бибкод : 2015JCoPh.303..222A . дои : 10.1016/j.jcp.2015.09.040 .

Внешние ссылки

[1] Амриткар, Амит; де Стерлер, Эрик; Свиридович, Катажина; Тафти, Данеш; Ахуджа, Капил (2015). «Переработка подпространств Крылова для приложений CFD и новый гибридный решатель переработки». Журнал вычислительной физики . 303 : 222. arXiv : 1501.03358 . Бибкод : 2015JCoPh.303..222A . дои : 10.1016/j.jcp.2015.09.040 .

[1]