Простая итерация и условие сходимости
Урок про метод простой итерации (метод неподвижной точки): как из уравнения сделать сходящийся процесс и от чего зависит сходимость.
Метод простой итерации решает $x = g(x)$, повторяя $x_{n+1} = g(x_n)$. Точка $r$ с $r = g(r)$ называется неподвижной. Процесс сходится, если $|g'(r)| \lt 1$.
Идея: превратить уравнение в подстановку
Любое уравнение $f(x)=0$ можно переписать как $x = g(x)$ — выразив $x$ через себя. Тогда корень становится неподвижной точкой отображения $g$ — тем самым $x$, который $g$ возвращает без изменений. Метод предельно прост: подставляй результат обратно в $g$ снова и снова. Если повезёт — приближения сойдутся к корню.
Но способов переписать $f(x)=0$ как $x=g(x)$ бесконечно много, и от выбора $g$ зависит всё: один даст сходимость, другой — расходимость. Решение задачи $x^3 - x - 2 = 0$ можно записать и как $x = x^3 - 2$, и как $x = (x+2)^{1/3}$. Проверим оба.
def итерация(g, x0, имя, шагов=8):
print(f"--- {имя} ---")
x = x0
for n in range(1, шагов + 1):
x_new = g(x)
print(f"шаг {n}: x = {x_new:.10f} |dx| = {abs(x_new - x):.2e}")
x = x_new
# Хорошее g: x = (x+2)^(1/3), g'(r) ≈ 0.14 -> сходится
итерация(lambda x: (x + 2) ** (1/3), 1.0, "x = (x+2)^(1/3)")
print()
# Плохое g: x = x^3 - 2, g'(r) ≈ 6.9 -> расходится (быстро взрывается)
итерация(lambda x: x**3 - 2, 1.5, "x = x^3 - 2", шагов=5)Вывод:
--- x = (x+2)^(1/3) --- шаг 1: x = 1.4422495703 |dx| = 4.42e-01 шаг 2: x = 1.5098974493 |dx| = 6.76e-02 шаг 3: x = 1.5197243050 |dx| = 9.83e-03 шаг 4: x = 1.5211412691 |dx| = 1.42e-03 шаг 5: x = 1.5213453678 |dx| = 2.04e-04 шаг 6: x = 1.5213747615 |dx| = 2.94e-05 шаг 7: x = 1.5213789946 |dx| = 4.23e-06 шаг 8: x = 1.5213796042 |dx| = 6.10e-07 --- x = x^3 - 2 --- шаг 1: x = 1.3750000000 |dx| = 1.25e-01 шаг 2: x = 0.5996093750 |dx| = 7.75e-01 шаг 3: x = -1.7844216004 |dx| = 2.38e+00 шаг 4: x = -7.6818846825 |dx| = 5.90e+00 шаг 5: x = -455.3184031398 |dx| = 4.48e+02
Условие сходимости: всё решает |g'(r)|
Различие объясняет производная $g$ в корне. Если $|g'(r)| \lt 1$, отображение сжимающее: каждый шаг уменьшает расстояние до неподвижной точки в $|g'(r)|$ раз — процесс сходится линейно. Если $|g'(r)| \gt 1$ — растягивающее, ошибка растёт, расходимость. У хорошего $g = (x+2)^{1/3}$ производная в корне $\approx 0.14$ (сжатие), у плохого $g = x^3-2$ производная $\approx 6.9$ (растяжение). Чем меньше $|g'(r)|$, тем быстрее сходимость; при $g'(r)=0$ сходимость становится квадратичной — и это, по сути, метод Ньютона в маскировке.
|g'(r)| < 1: СЖАТИЕ |g'(r)| > 1: РАСТЯЖЕНИЕ
x0 x1 x2 r r x0 x1 x2
|---|--|-| |--|----|--------|--->
шаги жмутся к корню шаги убегают от корняКак работает под капотом
Формально работает теорема о сжимающем отображении (Банаха): если на отрезке вокруг корня $|g'(x)| \le q \lt 1$, то итерации сходятся к единственной неподвижной точке, и ошибка после $n$ шагов не больше $q^n$ от начальной. Это даёт и сходимость, и оценку скорости, и способ заранее выбрать $g$. Метод Ньютона — это простая итерация с $g(x) = x - \frac{f(x)}{f'(x)}$, у которой $g'(r) = 0$: отсюда его квадратичная скорость. Так разрозненные методы укладываются в одну теорию.
Частые ошибки
- Брать первое попавшееся $g$. Проверьте $|g'(r)| \lt 1$ (хотя бы оцените численно), иначе процесс разойдётся.
- Считать расходимость багом кода. Часто это правильный диагноз: данное $g$ не сжимающее — нужно переписать уравнение иначе.
- Нет страховки от выхода за область. Расходящиеся итерации могут дать переполнение или взять корень из отрицательного — оборачивайте в проверку/лимит.
Итоги
- Простая итерация решает $x = g(x)$ подстановкой $x_{n+1} = g(x_n)$; корень — неподвижная точка.
- Сходимость определяется производной: $|g'(r)| \lt 1$ — сжатие и сходимость, $\gt 1$ — расходимость.
- Скорость линейная со знаменателем $|g'(r)|$; при $g'(r)=0$ — квадратичная (это Ньютон).
- Выбор формы $g$ критичен: одно и то же уравнение можно переписать сходяще или расходяще.