В вычислительной математике итерационный метод — это математическая процедура , использующая начальное значение для генерации последовательности улучшения приближенных решений класса задач, в которой n -е приближение выводится из предыдущих.
Конкретная реализация с критериями завершения для данного итерационного метода, такого как градиентный спуск , восхождение на холм , метод Ньютона или квазиньютоновские методы , такие как BFGS , является алгоритмом итерационного метода. Итерационный метод называется сходящимся, если соответствующая последовательность сходится при заданных начальных приближениях. Обычно проводится математически строгий анализ сходимости итерационного метода; однако также распространены итеративные методы, основанные на эвристике .
Напротив, прямые методы пытаются решить проблему с помощью конечной последовательности операций. При отсутствии ошибок округления прямые методы дадут точное решение (например, решение линейной системы уравнений методом исключения Гаусса ). Итерационные методы часто являются единственным выбором для нелинейных уравнений . Однако итерационные методы часто полезны даже для линейных задач, включающих множество переменных (иногда порядка миллионов), где прямые методы были бы непомерно дорогими (а в некоторых случаях невозможными) даже при максимальной доступной вычислительной мощности. [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 . С другой стороны, в числовых методах часто используются верхние индексы в круглых скобках, чтобы не мешать нижним индексам, имеющим другие значения. (Например, x ( n +1) = f ( x ( n ) ).) Если функция f непрерывно дифференцируема , то достаточным условием сходимости является то, что спектральный радиус производной строго ограничен единицей в окрестности фиксированная точка. Если это условие выполняется в фиксированной точке, то должна существовать достаточно малая окрестность (бассейн притяжения).
В случае системы линейных уравнений двумя основными классами итерационных методов являются стационарные итерационные методы и более общие методы подпространств Крылова .
Стационарные итерационные методы решают линейную систему с оператором , аппроксимирующим исходную; и на основе измерения ошибки результата ( остатка ) сформировать «уравнение коррекции», для которого этот процесс повторяется. Хотя эти методы просты в разработке, реализации и анализе, сходимость гарантируется только для ограниченного класса матриц.
Итерационный метод определяется формулой
а для данной линейной системы с точным решением ошибка на
Итерационный метод называется линейным, если существует матрица такая, что
и эта матрица называется матрицей итераций . Итерационный метод с заданной итерационной матрицей называется сходящимся , если выполняется следующее
Важная теорема утверждает, что для данного итерационного метода и его итерационной матрицы он сходится тогда и только тогда, когда его спектральный радиус меньше единицы, то есть
Основные итерационные методы работают путем разделения матрицы на
и здесь матрица должна быть легко обратимой . Итерационные методы теперь определяются как
Отсюда следует, что итерационная матрица имеет вид
Основные примеры стационарных итерационных методов используют разделение матрицы, например:
где – только диагональная часть , а – строгая нижняя треугольная часть . Соответственно – строгая верхняя треугольная часть .
Линейные стационарные итерационные методы также называют методами релаксации .
Методы подпространств Крылова работают путем формирования основы последовательности последовательных степеней матрицы, умноженной на начальный остаток ( последовательность Крылова ). Затем аппроксимации решения формируются путем минимизации невязки по сформированному подпространству. Прототипическим методом в этом классе является метод сопряженных градиентов (CG), который предполагает, что матрица системы является симметричной положительно определенной . Для симметричного (и, возможно, неопределенного) используется метод минимальной невязки (MINRES). В случае несимметричных матриц были выведены такие методы, как обобщенный метод минимальной невязки (GMRES) и метод двусопряженного градиента (BiCG).
Поскольку эти методы составляют основу, очевидно, что метод сходится за N итераций, где N — размер системы. Однако при наличии ошибок округления это утверждение не выполняется; более того, на практике N может быть очень большим, и итерационный процесс достигает достаточной точности уже гораздо раньше. Анализ этих методов сложен, поскольку зависит от сложной функции спектра оператора .
Аппроксимирующий оператор, который появляется в стационарных итерационных методах, также может быть включен в методы подпространства Крылова, такие как GMRES (альтернативно предобусловленные методы Крылова можно рассматривать как ускорения стационарных итерационных методов), где они становятся преобразованиями исходного оператора в предположительно лучше обусловленный один. Создание прекондиционеров представляет собой обширную область исследований.
Джамшид аль-Каши использовал итерационные методы для расчета синуса 1 ° и π в «Трактате об хорде и синусе» с высокой точностью. Первый итерационный метод решения линейной системы появился в письме Гаусса своему ученику. Он предложил решать систему уравнений 4х4 путем многократного решения той компоненты, в которой невязка была самой большой .
Теория стационарных итерационных методов прочно утвердилась в работах Д.М. Янга, начиная с 1950-х годов. Метод сопряженных градиентов также был изобретен в 1950-х годах независимыми разработками Корнелиуса Ланцоша , Магнуса Хестенеса и Эдуарда Штифеля , но его природа и применимость в то время были неправильно поняты. Только в 1970-х годах стало понятно, что методы, основанные на сопряжении, очень хорошо работают для уравнений в частных производных , особенно эллиптического типа.
