В области вычислительной математики , А.Н. итерационный метод является математической процедурой , которая использует начальное значение для генерации последовательности улучшения приближенных решений для класса задач, в которых п -е приближение является производным от предыдущих. Конкретная реализация итерационного метода, включая критерии завершения , представляет собой алгоритм итерационного метода. Итерационный метод называется сходящимся, если соответствующая последовательность сходится при заданных начальных приближениях. Обычно выполняется математически строгий анализ сходимости итерационного метода; однако эвристический-основанные итерационные методы также распространены.
Напротив, прямые методы пытаются решить проблему с помощью конечной последовательности операций. При отсутствии ошибок округления прямые методы дадут точное решение (например, решение линейной системы уравненийметодом исключения Гаусса ). Итерационные методы часто являются единственным выбором для нелинейных уравнений . Однако итерационные методы часто полезны даже для линейных задач, включающих множество переменных (иногда порядка миллионов), где прямые методы были бы чрезмерно дорогими (а в некоторых случаях невозможными) даже при наилучшей доступной вычислительной мощности. [1]
Привлекательные фиксированные точки
Если уравнение может быть введено в виде F ( х ) = х , а решение х является привлекательной неподвижной точкой функции F , то можно начать с точкой х 1 в бассейне притяжения от х , и пусть х 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 является непрерывно дифференцируемой , достаточным условием сходимости является то , что спектральный радиус производной строго ограничена одной в окрестности фиксированная точка. Если это условие выполняется в неподвижной точке, то должна существовать достаточно малая окрестность (область притяжения).
Линейные системы
В случае системы линейных уравнений двумя основными классами итерационных методов являются стационарные итерационные методы и более общие методы подпространства Крылова .
Стационарные итерационные методы
Вступление
Стационарные итерационные методы решают линейную систему с оператором, аппроксимирующим исходную; и на основе измерения ошибки в результате ( остатка ) формируют «уравнение коррекции», для которого этот процесс повторяется. Хотя эти методы просты в получении, реализации и анализе, сходимость гарантируется только для ограниченного класса матриц.
Определение
Итерационный метод определяется
и для данной линейной системы с точным решением ошибка по
Итерационный метод называется линейным, если существует матрица такой, что
и эта матрица называется итерационной матрицей . Итерационный метод с заданной матрицей итерацийназывается сходящимся, если выполняется
Важная теорема утверждает, что для данного итерационного метода и его итерационной матрицы он сходится тогда и только тогда, когда его спектральный радиус меньше единицы, то есть
Основные итерационные методы работают путем разбиения матрицы в
и здесь матрица должно быть легко обратимым . Итерационные методы теперь определены как
Отсюда следует, что итерационная матрица имеет вид
Примеры
Базовые примеры стационарных итерационных методов используют разбиение матрицы такой как
где это только диагональная часть , а также является строго нижняя треугольная часть из. Соответственно, - строгая верхнетреугольная часть .
- Метод Ричардсона :
- Метод Якоби :
- Затухающий метод Якоби :
- Метод Гаусса – Зейделя :
- Метод последовательной избыточной релаксации (SOR):
- Симметричное последовательное избыточное расслабление (SSOR):
Линейные стационарные итерационные методы также называют методами релаксации .
Методы подпространства Крылова
Методы подпространства Крылова работают, формируя основу из последовательности последовательных степеней матрицы, умноженных на начальную невязку ( последовательность Крылова ). Затем формируются приближения к решению путем минимизации невязки по сформированному подпространству. Прототипным методом в этом классе является метод сопряженных градиентов (CG), который предполагает, что матрица системыявляется симметричной положительно определенной . Для симметричных (и, возможно, неопределенных)один работает с методом минимальной невязки (MINRES). В случае несимметричных матриц были получены такие методы, как обобщенный метод минимальной невязки (GMRES) и метод двусопряженных градиентов (BiCG).
Сходимость методов подпространства Крылова
Поскольку эти методы составляют основу, очевидно, что метод сходится за N итераций, где N - размер системы. Однако при наличии ошибок округления это утверждение не выполняется; более того, на практике N может быть очень большим, и итерационный процесс достигает достаточной точности уже намного раньше. Анализ этих методов сложен и зависит от сложной функции спектра оператора.
Прекондиционеры
Аппроксимирующий оператор, который появляется в стационарных итерационных методах, также может быть включен в методы подпространства Крылова, такие как GMRES (альтернативно, предобусловленные методы Крылова можно рассматривать как ускорение стационарных итерационных методов), где они становятся преобразованиями исходного оператора в предположительно более обусловленный один. Строительство прекондиционеров - большая область исследований.
История
Вероятно, первый итерационный метод решения линейной системы появился в письме Гаусса к его ученику. Он предложил решить систему уравнений 4 на 4, многократно решая компонент, в котором невязка была наибольшей [ необходима цитата ] .
Теория стационарных итерационных методов была прочно обоснована работами Д.М. Юнга, начиная с 1950-х годов. Метод сопряженного градиента также был изобретен в 1950-х годах независимыми разработками Корнелиуса Ланцоса , Магнуса Хестенеса и Эдуарда Штифеля , но его природа и применимость были неправильно поняты в то время. Только в 1970-х годах стало понятно, что методы, основанные на сопряженности, очень хорошо работают для уравнений в частных производных , особенно для эллиптических уравнений .
Смотрите также
- Выражение в закрытой форме
- Нелинейный метод наименьших квадратов
- Численный анализ
- Алгоритм поиска корней
Рекомендации
- ^ Амриткар, Амит; де Стерлер, Эрик; Свиридович, Катажина; Тафти, Данеш; Ахуджа, Капил (2015). «Переработка подпространств Крылова для приложений CFD и новый гибридный решатель рециклинга». Журнал вычислительной физики . 303 : 222. arXiv : 1501.03358 . Bibcode : 2015JCoPh.303..222A . DOI : 10.1016 / j.jcp.2015.09.040 .
Внешние ссылки
- Шаблоны для решения линейных систем
- Ю. Саад: Итерационные методы для разреженных линейных систем , 1-е издание, PWS 1996