Простая итерация и условие сходимости

Урок про метод простой итерации (метод неподвижной точки): как из уравнения сделать сходящийся процесс и от чего зависит сходимость.

Метод простой итерации решает x = g(x), повторяя x_{n+1} = g(x_n). Точка r с r = g(r) называется неподвижной. Процесс сходится, если |g'(r)| < 1.

Идея: превратить уравнение в подстановку

Любое уравнение f(x)=0 можно переписать как x = g(x) — выразив x через себя. Тогда корень становится неподвижной точкой отображения g — тем самым x, который g возвращает без изменений. Метод предельно прост: подставляй результат обратно в g снова и снова. Если повезёт — приближения сойдутся к корню.

Но способов переписать f(x)=0 как x=g(x) бесконечно много, и от выбора g зависит всё: один даст сходимость, другой — расходимость. Решение задачи x³ − x − 2 = 0 можно записать и как x = x³ − 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)| < 1, отображение сжимающее: каждый шаг уменьшает расстояние до неподвижной точки в |g'(r)| раз — процесс сходится линейно. Если |g'(r)| > 1 — растягивающее, ошибка растёт, расходимость. У хорошего g = (x+2)^(1/3) производная в корне ≈ 0.14 (сжатие), у плохого g = x³−2 производная ≈ 6.9 (растяжение). Чем меньше |g'(r)|, тем быстрее сходимость; при g'(r)=0 сходимость становится квадратичной — и это, по сути, метод Ньютона в маскировке.

|g'(r)| < 1: СЖАТИЕ            |g'(r)| > 1: РАСТЯЖЕНИЕ
   x0  x1 x2 r                     r  x0   x1      x2
   |---|--|-|                      |--|----|--------|--->
   шаги жмутся к корню             шаги убегают от корня

Как работает под капотом

Формально работает теорема о сжимающем отображении (Банаха): если на отрезке вокруг корня |g'(x)| ≤ q < 1, то итерации сходятся к единственной неподвижной точке, и ошибка после n шагов не больше q^n от начальной. Это даёт и сходимость, и оценку скорости, и способ заранее выбрать g. Метод Ньютона — это простая итерация с g(x) = x − f(x)/f'(x), у которой g'(r) = 0: отсюда его квадратичная скорость. Так разрозненные методы укладываются в одну теорию.

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

Брать первое попавшееся g. Проверьте |g'(r)| < 1 (хотя бы оцените численно), иначе процесс разойдётся.
Считать расходимость багом кода. Часто это правильный диагноз: данное g не сжимающее — нужно переписать уравнение иначе.
Нет страховки от выхода за область. Расходящиеся итерации могут дать переполнение или взять корень из отрицательного — оборачивайте в проверку/лимит.

Итоги

Простая итерация решает x = g(x) подстановкой x_{n+1} = g(x_n); корень — неподвижная точка.
Сходимость определяется производной: |g'(r)| < 1 — сжатие и сходимость, > 1 — расходимость.
Скорость линейная со знаменателем |g'(r)|; при g'(r)=0 — квадратичная (это Ньютон).
Выбор формы g критичен: одно и то же уравнение можно переписать сходяще или расходяще.