Сходимость метода простой итерации: условие и оценка

Сходимость метода простой итерации - центральный вопрос при численном решении нелинейного уравнения, сведённого к виду $x = \varphi(x)$. Сам метод тривиален: берём начальное приближение $x_0$ и строим последовательность $x_{n+1} = \varphi(x_n)$. Но эта последовательность вовсе не обязана приближаться к корню - она может расходиться, зацикливаться или хаотично прыгать. Сходимость метода простой итерации полностью определяется поведением функции $\varphi$ вблизи неподвижной точки, и есть точный критерий, который позволяет заранее сказать, сработает метод или нет. Разберём этот критерий, скорость сходимости, оценку погрешности и то, как переписать исходное уравнение, чтобы итерации сошлись.

Постановка: уравнение в форме x = φ(x)

Пусть нужно решить уравнение $f(x) = 0$. Метод простой итерации (его ещё называют методом последовательных приближений) требует сначала переписать его в эквивалентной форме $x = \varphi(x)$, где корень исходного уравнения становится неподвижной точкой функции $\varphi$: $x^{*} = \varphi(x^{*})$. Например, $x^3 + x - 1 = 0$ можно переписать как $x = 1 - x^3$, или как $x = \frac{1}{1 + x^2}$, или как $x = \sqrt[3]{1 - x}$ - все три формы имеют тот же корень, но ведут себя по-разному.

Дальше выбираем $x_0$ и итерируем: $x_1 = \varphi(x_0)$, $x_2 = \varphi(x_1)$ и так далее. Если последовательность $\{x_n\}$ сходится к некоторому пределу $x^{*}$, и $\varphi$ непрерывна, то предел автоматически является корнем: переход к пределу в равенстве $x_{n+1} = \varphi(x_n)$ даёт $x^{*} = \varphi(x^{*})$. Вся проблема - гарантировать, что сходимость метода простой итерации вообще имеет место.

Проверка сходимости перед запуском итераций

Прежде чем вручную считать десяток итераций и гадать, сходятся они или нет, разумно проверить достаточное условие на выбранной форме $\varphi$ и оценить, сколько шагов понадобится для нужной точности. Ниже - небольшая форма: задаёшь функцию $\varphi(x)$, отрезок локализации корня, начальное приближение и точность - получаешь проверку условия сжатия $|\varphi'(x)| \le q < 1$, оценку числа итераций и пошаговый расчёт.

После того как условие проверено, остаётся понять, почему именно производная $\varphi'$ управляет сходимостью.

Принцип сжимающих отображений

Теоретический фундамент - теорема о неподвижной точке Банаха (принцип сжимающих отображений). Отображение $\varphi$ называется сжимающим на отрезке $[a, b]$, если оно переводит этот отрезок в себя ($\varphi([a,b]) \subseteq [a,b]$) и существует константа $q < 1$ такая, что для любых двух точек

$|\varphi(x) - \varphi(y)| \le q\, |x - y|.$

Эта константа $q$ называется коэффициентом сжатия. Теорема утверждает: сжимающее отображение имеет на $[a, b]$ единственную неподвижную точку $x^{*}$, и метод простой итерации сходится к ней из любого начального приближения $x_0 \in [a, b]$. То есть сходимость метода простой итерации в этом случае гарантирована глобально на отрезке - выбор $x_0$ влияет лишь на число шагов, но не на сам факт сходимости.

Условие сходимости через производную

Проверять неравенство $|\varphi(x) - \varphi(y)| \le q|x-y|$ напрямую неудобно. Если $\varphi$ дифференцируема, по теореме Лагранжа $\varphi(x) - \varphi(y) = \varphi'(\xi)(x - y)$ для некоторой точки $\xi$ между $x$ и $y$. Отсюда удобный рабочий критерий: достаточно, чтобы на отрезке $[a, b]$, содержащем корень, выполнялось

$q = \max_{x \in [a, b]} |\varphi'(x)| < 1.$

Это и есть основное достаточное условие сходимости метода простой итерации. Смысл прозрачен: если $|\varphi'| < 1$, функция вблизи корня «сжимает» расстояния, и каждая итерация приближает нас к $x^{*}$. Если же $|\varphi'(x^{*})| > 1$, неподвижная точка отталкивающая - итерации убегают от неё, как бы близко мы ни стартовали. Случай $|\varphi'(x^{*})| = 1$ - пограничный, метод может сходиться сколь угодно медленно или не сходиться вовсе.

Вернёмся к примеру $x^3 + x - 1 = 0$ с корнем около $x^{*} \approx 0{,}682$. Форма $x = 1 - x^3$ даёт $\varphi'(x) = -3x^2$, и $|\varphi'(x^{*})| \approx 1{,}4 > 1$ - расходится. Форма $x = \frac{1}{1 + x^2}$ даёт $\varphi'(x) = \frac{-2x}{(1+x^2)^2}$, и $|\varphi'(x^{*})| \approx 0{,}57 < 1$ - сходится. Уравнение одно, а сходимость метода простой итерации противоположная: всё решает выбор $\varphi$.

Скорость сходимости

Метод простой итерации обладает линейной скоростью сходимости. Из неравенства сжатия следует, что ошибка $e_n = |x_n - x^{*}|$ убывает геометрически:

$|x_{n+1} - x^{*}| \le q\, |x_n - x^{*}|, \qquad |x_n - x^{*}| \le q^{n}\, |x_0 - x^{*}|.$

Каждая итерация уменьшает погрешность примерно в $q$ раз, поэтому число верных знаков растёт линейно по $n$. Чем меньше $q$, тем быстрее: при $q = 0{,}1$ за один шаг прибавляется около одного десятичного знака, при $q = 0{,}9$ для того же эффекта нужно более двадцати шагов. Это принципиально медленнее квадратичной сходимости метода Ньютона, где число верных знаков удваивается за шаг - поэтому метод простой итерации ценят за простоту и устойчивость, а не за скорость. Особый случай: если удаётся подобрать $\varphi$ так, что $\varphi'(x^{*}) = 0$, сходимость становится квадратичной (именно так устроен метод Ньютона как частный случай простой итерации).

Оценка погрешности и критерий остановки

На практике корень $x^{*}$ неизвестен, поэтому погрешность оценивают через соседние приближения. Из неравенства сжатия выводятся две оценки. Апостериорная (по уже вычисленным шагам):

$|x_n - x^{*}| \le \frac{q}{1 - q}\, |x_n - x_{n-1}|.$

Она удобна как критерий остановки: считаем, пока разность $|x_n - x_{n-1}|$ не станет достаточно малой. Важная тонкость: при $q$, близком к единице, множитель $\frac{q}{1-q}$ велик, и малость разности $|x_n - x_{n-1}|$ ещё не означает малость самой ошибки - наивный критерий «остановиться, когда $|x_n - x_{n-1}| < \varepsilon$» здесь обманчив. Априорная оценка позволяет заранее предсказать число шагов:

$|x_n - x^{*}| \le \frac{q^{n}}{1 - q}\, |x_1 - x_0|.$

Приравняв правую часть к требуемой точности $\varepsilon$ и взяв логарифм, получаем минимальное $n$, гарантирующее нужную точность. Темы устойчивости и числа итераций тесно связаны с понятием числа обусловленности матрицы в линейных задачах и с методом Гаусса-Зейделя, который и есть простая итерация для систем линейных уравнений.

Частые ошибки

• Запуск метода без проверки $|\varphi'| < 1$. Самая частая причина «метод не работает» - выбрана расходящаяся форма $\varphi$. Сначала оцените производную на отрезке, потом итерируйте.
• Проверка производной только в одной точке. Условие $q < 1$ должно выполняться на всём отрезке локализации, а не только в корне или в $x_0$. Берите $\max |\varphi'|$ по отрезку.
• Игнорирование условия $\varphi([a,b]) \subseteq [a,b]$. Даже при $|\varphi'| < 1$ итерации могут вылететь за пределы отрезка, где условие сжатия уже не гарантировано.
• Критерий остановки $|x_n - x_{n-1}| < \varepsilon$ при $q$ около единицы. При медленной сходимости фактическая ошибка может быть в $\frac{q}{1-q}$ раз больше разности приближений.
• Путаница неподвижной точки и нуля функции. Метод ищет корень $x = \varphi(x)$, а не $\varphi(x) = 0$; забытое преобразование $f(x)=0 \to x=\varphi(x)$ ведёт к неверной постановке.

FAQ

Чем метод простой итерации отличается от метода Ньютона? Метод Ньютона - частный случай простой итерации с $\varphi(x) = x - \frac{f(x)}{f'(x)}$, специально подобранным так, что $\varphi'(x^{*}) = 0$. Поэтому он сходится квадратично, а общий метод простой итерации - линейно. Зато простая итерация не требует вычислять производную $f'$ и устойчивее.

Что делать, если $|\varphi'(x)| > 1$ и метод расходится? Переписать уравнение в другой форме $x = \varphi(x)$. Универсальный приём - релаксация: взять $\varphi(x) = x - \lambda f(x)$ и подобрать параметр $\lambda$ так, чтобы $|\varphi'(x^{*})| = |1 - \lambda f'(x^{*})| < 1$.

Гарантирует ли $|\varphi'(x^{*})| < 1$ сходимость из любой точки? Только локальную - из достаточно близкой к корню $x_0$. Глобальная сходимость на отрезке требует, чтобы $|\varphi'| < 1$ и $\varphi([a,b]) \subseteq [a,b]$ выполнялись на всём $[a, b]$ (условия принципа сжатия).

Коротко

Сходимость метода простой итерации $x_{n+1} = \varphi(x_n)$ определяется коэффициентом сжатия: достаточное условие - $q = \max |\varphi'(x)| < 1$ на отрезке, содержащем корень и переходящем в себя. При выполнении этого условия по принципу сжимающих отображений итерации сходятся к единственной неподвижной точке с линейной скоростью $|x_n - x^{*}| \le q^n |x_0 - x^{*}|$, а априорная и апостериорная оценки позволяют заранее посчитать число шагов и корректно остановиться. Одно уравнение можно записать в нескольких формах $\varphi$ - и именно выбор формы решает, сойдётся метод или разойдётся.