Итерационный метод
англ. Iterative method
Последовательные приближения $x_{k+1}=\varphi(x_k)$, сходящиеся при $|\varphi'|<1$: так численно решают уравнения с точностью $\varepsilon$.
Итерационный метод — метод, в котором решение строится как предел последовательности приближений: выбирают начальное , затем вычисляют , пока не станет меньше заданной точности . Для скалярного уравнения достаточное условие сходимости — в окрестности корня; тогда погрешность убывает как , то есть геометрически.
Так работают метод простой итерации, методы Якоби и Гаусса–Зейделя для СЛАУ, метод Ньютона, градиентный спуск. В отличие от прямых методов итерации дают лишь приближённый ответ, зато терпимы к разреженным матрицам и огромным системам, где прямые методы дороги по памяти. Квадратичная сходимость Ньютона удваивает число верных знаков за шаг; оценка трудоёмкости — тема сложности алгоритмов.
Частые вопросы
Чем итерационный метод отличается от прямого?
Прямой метод (например, метод Гаусса) за конечное число операций выдаёт ответ, точный при идеальной арифметике. Итерационный метод генерирует бесконечную последовательность приближений и останавливается по достижении заданной точности. Прямые методы хороши для плотных матриц умеренного размера, итерации — для огромных разреженных систем, где экономия памяти и времени решает всё.
Что делать, если итерации не сходятся?
Проверить условие : если оно нарушено, переписать уравнение в другой итерационной форме — у одного уравнения таких форм бесконечно много, и сходимость сильно зависит от выбора. Помогают релаксация (смешивание старого и нового приближений), переход к методу Ньютона с лучшей локальной сходимостью и более удачное начальное приближение.