Введение

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

В вычислительной математике итеративный метод — это математическая процедура, использующая начальное значение для генерации последовательности улучшающихся приближенных решений для класса задач, в которой n-е приближение выводится из предыдущих. Конкретная реализация с критериями останова для заданного итеративного метода, такого как градиентный спуск, метод подъема по склону, метод Ньютона или квазиньютоновские методы, такие как BFGS, является алгоритмом итеративного метода. Итеративный метод называется сходящимся, если соответствующая последовательность сходится для заданных начальных приближений. Обычно проводится математически строгий анализ сходимости итеративного метода, однако также распространены итеративные методы, основанные на эвристиках. В отличие от них, прямые методы стремятся решить задачу с помощью конечной последовательности операций. При отсутствии ошибок округления прямые методы должны дать точное решение (например, решение системы линейных уравнений методом Гаусса). Итеративные методы часто являются единственным выбором для нелинейных уравнений. Однако итеративные методы часто полезны даже для линейных задач, включающих большое количество переменных (иногда порядка миллионов), где прямые методы были бы чрезмерно затратными (и в некоторых случаях невозможными) даже при использовании наилучших доступных вычислительных ресурсов.

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

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

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

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

Введение

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

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

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

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

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

Предварительные условия

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

История

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