Численные методы решения нелинейных уравнений

Отделение корней, метод половинного деления, метод хорд, метод Ньютона и простых итераций — условия сходимости, оценка погрешности, код на Python.

Большинство уравнений не решается аналитически, поэтому корень ищут численно. Любой метод состоит из двух этапов: сначала отделяют корень — находят отрезок, где он единственный, затем уточняют его до нужной точности.

Этап 1: отделение корней

Корень находится на отрезке [a; b], если функция непрерывна и меняет знак: f(a)·f(b) < 0. Если при этом производная не меняет знак, корень единственный.

Условие существования корня:  f(a) · f(b) < 0
Условие единственности:       f'(x) сохраняет знак на [a; b]

Практически отрезки находят табулированием: считают функцию с шагом и смотрят, между какими точками меняется знак. Для отчёта этого достаточно, но график тоже стоит приложить.

Метод половинного деления (бисекции)

c = (a + b) / 2
Если f(a)·f(c) < 0  →  b = c,  иначе  a = c
Повторять, пока (b − a) > 2ε

Число итераций известно заранее:  n ≥ log₂((b−a)/ε)

• Плюс: сходится всегда, если корень отделён. Отказаться не может.
• Минус: медленный — точность растёт линейно, на каждый знак требуется около 3,3 итерации.
• Производная не нужна — годится для функций, заданных таблично или численно.

Метод Ньютона (касательных)

x_(n+1) = x_n − f(x_n) / f'(x_n)

Условие выбора начального приближения:  f(x₀) · f''(x₀) > 0
Сходимость квадратичная: число верных знаков удваивается за итерацию

Метод хорд (секущих)

x_(n+1) = x_n − f(x_n)·(x_n − x_(n−1)) / (f(x_n) − f(x_(n−1)))

Производная не нужна, скорость сходимости ≈ 1,6 — между бисекцией и Ньютоном

Метод простых итераций

Уравнение приводят к виду x = φ(x), затем:  x_(n+1) = φ(x_n)

Условие сходимости:  |φ'(x)| < 1 на всём отрезке
Оценка погрешности:  |x_n − x*| ≤ q/(1−q) · |x_n − x_(n−1)|,  q = max|φ'(x)|

Приведение к виду x = φ(x) неоднозначно, и от выбора зависит, сойдётся ли метод. Универсальный приём: φ(x) = x − f(x)/M, где M выбирают так, чтобы условие сходимости выполнялось.

Сравнение

def bisection(f, a, b, eps=1e-6):
    if f(a) * f(b) > 0:
        raise ValueError('На отрезке нет отделённого корня')
    steps = 0
    while (b - a) / 2 > eps:
        c = (a + b) / 2
        if f(a) * f(c) <= 0:
            b = c
        else:
            a = c
        steps += 1
    return (a + b) / 2, steps


def newton(f, df, x0, eps=1e-6, max_iter=100):
    x, steps = x0, 0
    for _ in range(max_iter):
        fx, dfx = f(x), df(x)
        if abs(dfx) < 1e-12:
            raise ValueError('Производная близка к нулю — метод неприменим')
        x_new = x - fx / dfx
        steps += 1
        if abs(x_new - x) < eps:
            return x_new, steps
        x = x_new
    raise ValueError('Метод не сошёлся за отведённое число итераций')


f  = lambda x: x**3 - x - 2
df = lambda x: 3*x**2 - 1
print(bisection(f, 1, 2))   # (1.5213797, ~20 итераций)
print(newton(f, df, 1.5))   # (1.5213797, ~4 итерации)

Разница в числе итераций — 20 против 4 — и есть тот результат, который просят показать в отчёте по лабораторной работе. Таблицу итераций с приближениями и погрешностью выводят для каждого метода.