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

Алгоритм, в котором каждое приближение решения выводится из предыдущих приближений

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

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

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

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

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

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

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

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

Введение

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

Определение

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

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

и для данной линейной системы с точным решением ошибка на ${\displaystyle A\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 \not \in \{0,2\})}$

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

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

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

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

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

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

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

Методы последовательного приближения

Математические методы, относящиеся к последовательному приближению, включают:

• Вавилонский метод нахождения квадратных корней чисел ^[2]
• Итерация с фиксированной точкой ^[3]
• Способы нахождения нулей функций:
  • Метод Галлея
  • Метод Ньютона
• Вопросы дифференциальных уравнений:
  • Теорема Пикара–Линделёфа о существовании решений дифференциальных уравнений
  • Методы Рунге–Кутты для численного решения дифференциальных уравнений

История

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

Теория стационарных итерационных методов была прочно установлена ​​с работой DM Young, начавшейся в 1950-х годах. Метод сопряженных градиентов также был изобретен в 1950-х годах с независимыми разработками Cornelius Lanczos , Magnus Hestenes и Eduard Stiefel , но его природа и применимость были неправильно поняты в то время. Только в 1970-х годах стало ясно, что методы, основанные на сопряжении, очень хорошо работают для уравнений с частными производными , особенно эллиптического типа.

Смотрите также

• Математический портал

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

Ссылки

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

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

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