Зачем нам новые методы, если бисекция уже работает?

Справедливый вопрос. Метод бисекции гарантированно находит корень. Зачем что-то ещё? Ответ простой: скорость.

Сравните на пальцах

Представьте, что вам нужно найти корень уравнения с точностью до 15 знаков после запятой (это стандартная точность double, с которой работают реальные программы).

Где это критично в IT

• Физический движок игры. 60 кадров в секунду × 1000 объектов = 60 000 вычислений в секунду. Каждый лишний шаг — это просадка FPS.
• Машинное обучение. Обучение нейросети — это миллионы итераций поиска минимума. Метод Ньютона здесь — стандарт (его обобщение называется методом Ньютона — Рафсона).
• 3D-графика. Трассировка лучей и нахождение пересечений поверхностей. Каждый пиксель — уравнение.
• Финансовые системы. Расчёт доходности облигаций (IRR) для тысяч инструментов одновременно.

Короткое напоминание: что такое корень и где мы его ищем

Прежде чем двинуться дальше, освежим базу из Лекции №2.

Задача

Найти такое значение x, при котором функция обращается в ноль:

f(x) = 0

Геометрически это точка, где график функции пересекает горизонтальную ось Ox.

Что у нас уже есть

Мы умеем локализовать корень — найти отрезок [a, b], на концах которого функция имеет разные знаки:

f(a) · f(b) < 0

По теореме Больцано — Коши это гарантирует, что внутри отрезка есть хотя бы один корень.

Чем новые методы отличаются от бисекции

Бисекция смотрит только на знаки функции (плюс или минус). Ей безразлично, насколько круто график идёт вверх или вниз. А методы хорд и Ньютона используют саму форму графика — они «прицеливаются» в корень точнее.

Метод хорд: идея «на пальцах»

Слово «хорда» знакомо из геометрии: это отрезок, соединяющий две точки кривой. Именно эту идею мы и используем.

Аналогия из жизни

Представьте, что вы стоите на двух холмах и натянули между ними верёвку. Верёвка — это прямая. Там, где верёвка пересекает уровень земли (ноль), — примерно и находится корень. Потом вы переезжаете на один из холмов, ближе к этому месту, и снова натягиваете верёвку. И так несколько раз.

Геометрический смысл

У нас есть точки A(a, f(a)) и B(b, f(b)). Мы проводим через них прямую (хорду). Эта прямая пересекает ось Ox в некоторой точке c. Это и есть наше новое приближение корня.

Рисунок 1. Метод хорд: прямая через точки A и B пересекает ось Ox в точке c — новом приближении корня

Затем мы смотрим: знак f(c) совпадает со знаком f(a) или f(b)? Тот конец отрезка, с которым совпал знак, «отбрасываем» и заменяем на c. Отрезок сужается, и мы повторяем.

Формула метода хорд

Откуда берётся формула? Это уравнение прямой, проходящей через две точки.

Вывод по шагам

Прямая через точки A(a, f(a)) и B(b, f(b)) задаётся уравнением:

y − f(a) = (f(b) − f(a)) / (b − a) · (x − a)

Нам нужна точка, где эта прямая пересекает ось Ox, то есть где y = 0. Подставляем y = 0 и выражаем x:

c = a − f(a) · (b − a) / (f(b) − f(a))

Это и есть рабочая формула метода хорд. Она даёт новое приближение корня c.

Алгоритм пошагово

1. Заданы отрезок [a, b] и точность ε. Проверяем: f(a) · f(b) < 0.
2. Вычисляем c по формуле.
3. Если |f(c)| < ε или |b − a| < ε — корень найден, возвращаем c.
4. Если f(a) · f(c) < 0 — корень в левой части: b = c.
5. Иначе — корень в правой части: a = c.
6. Повторяем шаги 2–5.

Разбираем пример вручную

Найдём корень уравнения x³ − x − 1 = 0 на отрезке [1, 2]. Это классическое уравнение, у которого нет красивой формулы решения.

Шаг 0. Проверяем локализацию

• f(1) = 1³ − 1 − 1 = −1 (отрицательно)
• f(2) = 8 − 2 − 1 = 5 (положительно)
• f(1) · f(2) = −5 < 0 — корень есть, идём дальше.

Шаг 1. Первое приближение

c = a − f(a) · (b − a) / (f(b) − f(a))

c = 1 − (−1) · (2 − 1) / (5 − (−1)) = 1 + 1/6 ≈ 1.1667

Считаем f(c) = f(1.1667) ≈ 1.588 − 1.1667 − 1 = −0.5787 (отрицательно).

Шаг 2. Сужаем отрезок

f(a) = −1 и f(c) = −0.579 — оба отрицательны. Значит, корень в правой части, делаем a = c = 1.1667.

Новый отрезок: [1.1667, 2].

Шаг 3. Второе приближение

c = 1.1667 − (−0.5787) · (2 − 1.1667) / (5 − (−0.5787)) ≈ 1.2531

Считаем f(c) ≈ −0.285 (отрицательно). Снова a = c.

Шаг 4. Третье приближение

c ≈ 1.2531 − (−0.285) · (2 − 1.2531) / (5 − (−0.285)) ≈ 1.2934

Считаем f(c) ≈ −0.128. И так далее.

Когда метод хорд работает, а когда — нет

Как и любой численный метод, метод хорд имеет условия сходимости. Хорошая новость: они не очень строгие.

Условия сходимости

• Функция f(x) непрерывна на отрезке [a, b].
• На концах отрезка значения разных знаков: f(a) · f(b) < 0.
• Производная f'(x) не обращается в ноль на отрезке (функция монотонна — не «разворачивается»).
• Вторая производная f''(x) сохраняет знак на отрезке (график не имеет перегибов внутри).

Порядок сходимости

Метод хорд имеет линейную (почти суперлинейную) сходимость. Это значит, что число верных знаков растёт примерно на 1 за итерацию. Быстрее бисекции, но медленнее Ньютона.

Реализация метода хорд на Python

Сравните с бисекцией: код почти такой же, но формула середины заменена на формулу хорды.

def f(x):
    """Наша функция: x^3 - x - 1"""
    return x**3 - x - 1

def chord_method(a, b, epsilon, max_iter=100):
    """Метод хорд для поиска корня на отрезке [a, b]"""
    # Проверяем, что на концах разные знаки
    if f(a) * f(b) >= 0:
        print("Ошибка: f(a) и f(b) одного знака!")
        return None

    step = 0
    print(f"{'Шаг':<5} {'a':<12} {'b':<12} {'c':<12} {'f(c)':<15}")
    print("-" * 60)

    while step < max_iter:
        # Формула хорды
        c = a - f(a) * (b - a) / (f(b) - f(a))
        fc = f(c)
        step += 1
        print(f"{step:<5} {a:<12.8f} {b:<12.8f} {c:<12.8f} {fc:<15.2e}")

        # Проверка на сходимость
        if abs(fc) < epsilon or abs(b - a) < epsilon:
            return c

        # Сужаем отрезок
        if f(a) * fc < 0:
            b = c
        else:
            a = c

    print("Достигнут лимит итераций!")
    return (a + b) / 2

# Запуск
root = chord_method(1, 2, 1e-6)
print(f"\n🎯 Корень найден: x ≈ {root:.8f}")
print(f"Проверка: f(x) = {f(root):.2e}")

Ожидаемый вывод

Шаг 1:  a=1.00000000  b=2.00000000  c=1.16666667  f(c)=-5.79e-01
Шаг 2:  a=1.16666667  b=2.00000000  c=1.25311203  f(c)=-2.85e-01
Шаг 3:  a=1.25311203  b=2.00000000  c=1.29339903  f(c)=-1.28e-01
...
Шаг 10: a=1.32471795  b=2.00000000  c=1.32471796  f(c)=1.11e-16

🎯 Корень найден: x ≈ 1.32471796
Проверка: f(x) = 1.11e-16

А можно ещё быстрее? Метод касательных (Ньютона)

Метод хорд использует прямую, проходящую через две точки графика. А что если мы возьмём касательную к графику в одной точке? Интуиция подсказывает: касательная точнее «прилипает» к кривой, чем хорда.

Аналогия из жизни

Представьте, что вы спускаетесь с горы в тумане. Вы не видите всю гору, но чувствуете наклон под ногами. Логично идти в ту сторону, куда «скатывается» склон. Касательная — это именно направление склона в текущей точке.

Идея метода

У нас есть начальное приближение x₀. Проводим касательную к графику f(x) в точке (x₀, f(x₀)). Смотрим, где эта касательная пересекает ось Ox. Это точка x₁. Повторяем: касательная в x₁ даёт x₂, и так далее.

Рисунок 2. Метод Ньютона: касательная в точке x₀ пересекает ось Ox в точке x₁ — более точном приближении корня

Формула метода Ньютона

Выведем формулу из геометрии. Касательная к графику f(x) в точке xₙ задаётся уравнением:

y − f(xₙ) = f'(xₙ) · (x − xₙ)

где f'(xₙ) — производная функции в точке xₙ (это и есть наклон касательной).

Нам нужна точка пересечения с осью Ox: подставляем y = 0 и выражаем x:

xₙ₊₁ = xₙ − f(xₙ) / f'(xₙ)

Это и есть итерационная формула метода Ньютона. Она также называется методом касательных или методом Ньютона — Рафсона.

Алгоритм пошагово

1. Выбираем начальное приближение x₀ (обычно берём один из концов отрезка локализации).
2. Вычисляем xₙ₊₁ = xₙ − f(xₙ) / f'(xₙ).
3. Если |xₙ₊₁ − xₙ| < ε — корень найден, возвращаем xₙ₊₁.
4. Иначе xₙ = xₙ₊₁ и повторяем.

Разбираем пример вручную: уравнение x³ − x − 1 = 0

То же уравнение, что и для метода хорд. Сравним скорость.

Подготовка

• f(x) = x³ − x − 1
• Производная: f'(x) = 3x² − 1
• Начальное приближение: x₀ = 1 (левый конец отрезка [1, 2], где f(1) = −1).

Шаг 1

x₁ = 1 − f(1) / f'(1) = 1 − (−1) / (3·1² − 1) = 1 + 1/2 = 1.5

Проверяем f(1.5) = 3.375 − 1.5 − 1 = 0.875. Уже ближе к нулю!

Шаг 2

f(1.5) = 0.875, f'(1.5) = 3·2.25 − 1 = 5.75

x₂ = 1.5 − 0.875 / 5.75 ≈ 1.5 − 0.1522 = 1.3478

f(1.3478) ≈ 2.449 − 1.3478 − 1 = 0.1012.

Шаг 3

f'(1.3478) ≈ 3·1.8165 − 1 ≈ 4.4496

x₃ = 1.3478 − 0.1012 / 4.4496 ≈ 1.3251

f(1.3251) ≈ 0.00188. Уже почти ноль!

Шаг 4

x₄ ≈ 1.3247 — совпадает с точным корнем до 4 знаков!

Почему метод Ньютона такой быстрый: квадратичная сходимость

Это самое важное теоретическое понятие лекции. Разберёмся, что такое «квадратичная сходимость» и почему это круто.

Что такое порядок сходимости

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

• p = 1 (линейная сходимость): ошибка уменьшается в постоянное число раз. Так работают бисекция и метод хорд.
• p = 2 (квадратичная сходимость): число верных знаков удваивается на каждом шаге. Так работает метод Ньютона.

Что это значит на практике

Пусть текущая ошибка равна 0.1 (1 верный знак после запятой).

Когда метод Ньютона может «взорваться»

Метод Ньютона — это мощный инструмент, но у него есть опасные режимы. Разберём, когда он работает, а когда ломается.

Условия сходимости

• f(x) непрерывна и дифференцируема на отрезке.
• f'(x) ≠ 0 на отрезке (нет горизонтальных касательных).
• Вторая производная f''(x) не меняет знак на отрезке (нет точек перегиба).
• Начальное приближение x₀ выбрано достаточно близко к корню.

Когда метод «взрывается»

Как выбрать начальное приближение

Практическое правило (условие Фурье): если f''(x) и f(a) имеют один знак, то берём x₀ = a, иначе берём x₀ = b. Проще: выбираем тот конец отрезка, где функция и её вторая производная имеют одинаковый знак.

Реализация метода Ньютона на Python

Понадобится не только сама функция, но и её производная. Есть три способа её задать.

Способ 1: задать производную вручную (самый быстрый)

def f(x):
    return x**3 - x - 1

def df(x):
    """Производная: 3x^2 - 1"""
    return 3 * x**2 - 1

def newton_method(x0, epsilon, max_iter=50):
    """Метод Ньютона (касательных)"""
    x = x0
    print(f"{'Итерация':<10} {'x':<15} {'f(x)':<15} {'|dx|':<15}")
    print("-" * 55)

    for n in range(max_iter):
        fx = f(x)
        dfx = df(x)

        # Проверка, что производная не близка к нулю
        if abs(dfx) < 1e-12:
            print("⚠️ Производная близка к нулю! Метод может разойтись.")
            return None

        x_new = x - fx / dfx
        diff = abs(x_new - x)

        print(f"{n+1:<10} {x_new:<15.10f} {f(x_new):<15.2e} {diff:<15.2e}")

        if diff < epsilon:
            return x_new

        x = x_new

    print("⚠️ Метод не сошёлся за заданное число итераций!")
    return None

# Запуск
root = newton_method(1.0, 1e-10)
print(f"\n🎯 Корень найден: x ≈ {root:.12f}")

Ожидаемый вывод

Итерация   x               f(x)            |dx|
-------------------------------------------------------
1          1.5000000000    8.75e-01        5.00e-01
2          1.3478260870    1.01e-01        1.52e-01
3          1.3252003989    2.06e-03        2.26e-02
4          1.3247181739    8.31e-07        4.82e-04
5          1.3247179572    1.33e-13        2.17e-07
6          1.3247179572    0.00e+00        1.51e-14

🎯 Корень найден: x ≈ 1.324717957245

Что делать, если производную сложно найти?

Иногда функция задана сложной формулой или вообще таблично. Символьно брать производную трудно. На помощь приходит численная производная.

Идея

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

f'(x) ≈ (f(x + h) − f(x − h)) / (2h)

где h — маленький шаг (например, 1e-7). Это центральная разность — она точнее, чем обычная.

Код с численной производной

def f(x):
    return x**3 - x - 1

def df_numeric(x, h=1e-7):
    """Численная производная (центральная разность)"""
    return (f(x + h) - f(x - h)) / (2 * h)

def newton_numeric(x0, epsilon, max_iter=50):
    x = x0
    for n in range(max_iter):
        fx = f(x)
        dfx = df_numeric(x)
        if abs(dfx) < 1e-12:
            return None
        x_new = x - fx / dfx
        if abs(x_new - x) < epsilon:
            return x_new
        x = x_new
    return None

root = newton_numeric(1.0, 1e-10)
print(f"Корень: x ≈ {root:.12f}")

Сравниваем три метода: бисекция, хорды, Ньютон

У нас теперь полный арсенал. Пора расставить всё по местам.

Сравнение на одном графике: куда «прыгает» каждый метод

Один и тот же корень, одни и те же стартовые точки — но разные стратегии поиска. Смотрите, как по-разному методы приближаются к цели.

Рисунок 3. Три метода идут к одному корню разными путями. Бисекция — «шаг за шагом». Хорда — «прицельно-прямолинейно». Ньютон — «сразу почти в цель»

Прикладной пример: физика в игре

Представьте, что вы пишете игру, где мяч летит с начальной скоростью под углом и нужно рассчитать, когда он упадёт на землю (или где пересечёт стену).

Задача

Мяч брошен с начальной скоростью v₀ = 20 м/с под углом 45°. Есть сопротивление воздуха, пропорциональное квадрату скорости. Уравнение высоты:

y(t) = v₀·sin(α)·t − (g/2)·t² − k·t³ = 0

где g = 9.81 м/с², k = 0.05 — коэффициент сопротивления.

Почему нельзя решить формулой?

Это кубическое уравнение. Формула Кардано существует, но она огромна и содержит комплексные числа даже при вещественных корнях. Проще — численно.

import math

def y(t):
    v0, alpha, g, k = 20, math.radians(45), 9.81, 0.05
    return v0 * math.sin(alpha) * t - (g/2) * t**2 - k * t**3

def dy(t):
    v0, alpha, g, k = 20, math.radians(45), 9.81, 0.05
    return v0 * math.sin(alpha) - g * t - 3 * k * t**2

# Локализация: где y меняет знак?
for t in [0, 1, 2, 3]:
    print(f"t={t}: y={y(t):.3f}")

# y(2)>0, y(3)<0 → корень на [2, 3]
# Метод Ньютона, старт с t=2.5
t = 2.5
for _ in range(10):
    t = t - y(t) / dy(t)

print(f"\nМяч упадёт через t ≈ {t:.4f} секунды")

Прикладной пример: оптимизация в машинном обучении

Обучение нейросети — это поиск минимума функции потерь (error). А минимум функции — это точка, где её производная равна нулю.

Связь с методом Ньютона

Чтобы найти минимум функции L(w) (потери), нужно решить уравнение:

L'(w) = 0

Именно к этому уравнению и применяют метод Ньютона! В многомерном случае это обобщается: wₙ₊₁ = wₙ − H⁻¹·∇L(wₙ), где H — матрица вторых производных (гессиан).

Что это значит для вас

• Градиентный спуск (который вы будете изучать) — это «упрощённый Ньютон», который использует только первую производную.
• Оптимизатор Adam (стандарт в TensorFlow и PyTorch) — это гибрид, который адаптивно меняет шаг, вдохновлённый квадратичной сходимостью Ньютона.
• Newton-CG — метод оптимизации в scipy и TensorFlow, использующий производные второго порядка.

Прикладной пример: финансы и IRR

В финансах есть понятие IRR (Internal Rate of Return — внутренняя норма доходности). Это ставка, при которой инвестиционный проект выходит в ноль (чистая приведённая стоимость равна нулю).

Формула

NPV(r) = Σ Cᵢ / (1 + r)ⁱ − C₀ = 0

где Cᵢ — денежные потоки, C₀ — начальные инвестиции, r — искомая ставка.

Это уравнение относительно r. Если платежей больше двух, оно превращается в полином высокой степени — аналитически решить невозможно.

Как это делают в Excel и банковских системах

Функция IRR() в Excel использует именно метод Ньютона (или его аналог). Когда вы вводите =IRR(A1:A20), Excel решает уравнение методом касательных за доли миллисекунды.

# Упрощённый расчёт IRR методом Ньютона
def npv(r, flows):
    """Чистая приведённая стоимость"""
    return sum(cf / (1 + r)**i for i, cf in enumerate(flows))

def dnpv(r, flows):
    """Производная NPV по r"""
    return sum(-i * cf / (1 + r)**(i+1) for i, cf in enumerate(flows))

def irr(flows, guess=0.1, eps=1e-9):
    r = guess
    for _ in range(100):
        dr = npv(r, flows) / dnpv(r, flows)
        r -= dr
        if abs(dr) < eps:
            return r
    return None

# Пример: инвестиция -1000, возвраты 300, 400, 500
flows = [-1000, 300, 400, 500]
print(f"IRR ≈ {irr(flows)*100:.2f}%")

«Золотой стандарт»: гибрид бисекции и Ньютона

В промышленном коде не используют «чистый» Ньютон. Слишком опасно — при плохом старте он разлетится. Делают так:

Стратегия

1. Делаем 3–5 шагов бисекции — получаем надёжное приближение и гарантированно узкий отрезок.
2. Переключаемся на Ньютона — быстро дожимаем до высокой точности.
3. Если Ньютон «срывается» (производная мала или точка вылетела за пределы отрезка), откатываемся к бисекции.

Реализация

def hybrid_root(f, df, a, b, epsilon):
    """Гибрид: бисекция + Ньютон"""
    # Шаг 1: несколько итераций бисекции
    for _ in range(5):
        c = (a + b) / 2
        if f(a) * f(c) < 0:
            b = c
        else:
            a = c

    # Шаг 2: Ньютон из середины суженного отрезка
    x = (a + b) / 2
    for _ in range(50):
        fx = f(x)
        dfx = df(x)
        if abs(dfx) < 1e-12:
            break
        x_new = x - fx / dfx
        # Защита: если Ньютон вылетел за [a,b] — откат к середине
        if not (a <= x_new <= b):
            x_new = (a + x_new) / 2
        if abs(x_new - x) < epsilon:
            return x_new
        x = x_new
    return x

Готовые инструменты Python

В реальной работе не пишут методы с нуля — используют scipy. Но знать, что внутри, необходимо, чтобы правильно выбирать инструмент.

from scipy.optimize import newton, root_scalar
import math

def f(x):
    return x**3 - x - 1

def df(x):
    return 3*x**2 - 1

# Метод Ньютона (нужна производная)
root1 = newton(f, x0=1.0, fprime=df, tol=1e-10)
print(f"newton:      x = {root1:.12f}")

# Метод Ньютона с численной производной (без df)
root2 = newton(f, x0=1.0, tol=1e-10)
print(f"newton(num): x = {root2:.12f}")

# Гибридный метод Брента — золотой стандарт
result = root_scalar(f, bracket=[1, 2], method='brentq', xtol=1e-10)
print(f"brentq:      x = {result.root:.12f}, шагов: {result.iterations}")

# Метод секущих (без производной, но с суперлинейной сходимостью)
result = root_scalar(f, x0=1.0, x1=2.0, method='secant', xtol=1e-10)
print(f"secant:      x = {result.root:.12f}, шагов: {result.iterations}")

Вывод

newton:      x = 1.324717957245
newton(num): x = 1.324717957245
brentq:      x = 1.324717957245, шагов: 8
secant:      x = 1.324717957245, шагов: 9

Типичные ошибки: как не сломать программу

Ошибка 1. Делить на ноль

В методе Ньютона f'(xₙ) может оказаться нулём (или очень близким к нулю числом). Программа либо упадёт, либо получит бесконечность.

# ❌ Плохо
x = x - f(x) / df(x)

# ✅ Хорошо
if abs(df(x)) < 1e-12:
    print("Производная близка к нулю! Переключаюсь на бисекцию.")
    # ... код бисекции ...
else:
    x = x - f(x) / df(x)

Ошибка 2. Бесконечный цикл

Без ограничения на число итераций метод может крутиться вечно.

# ✅ Всегда ставьте лимит
for i in range(max_iter):
    ...
else:
    print("Не сошлось за", max_iter, "итераций")

Ошибка 3. Плохое начальное приближение

Если x₀ далеко от корня, Ньютон может «улететь». Всегда проверяйте, что x₀ лежит в пределах отрезка локализации.

Ошибка 4. Забыть про точность

Сравнивать f(x) == 0 — плохо. Используйте abs(f(x)) < eps.

Вопросы для самопроверки (часть 1)

Проверьте себя — сможете ли ответить без подсказки?

1. Чем метод хорд отличается от метода бисекции? Что он использует «дополнительно»?
2. Запишите формулу метода хорд. Объясните, откуда она берётся (какая геометрическая идея).
3. Какие условия должны выполняться, чтобы метод хорд сходился?
4. Почему метод Ньютона называется также методом касательных?
5. Выведите формулу метода Ньютона xₙ₊₁ = xₙ − f(xₙ) / f'(xₙ) из уравнения касательной.
6. Что такое порядок сходимости? Каков он у бисекции, метода хорд и метода Ньютона?

Вопросы для самопроверки (часть 2)

7. Почему метод Ньютона в 5–10 раз быстрее бисекции? В чём причина?
8. Что такое «квадратичная сходимость»? Объясните на числовом примере.
9. При каких условиях метод Ньютона может «взорваться»?
10. Как выбрать начальное приближение для метода Ньютона? Какое правило (условие Фурье) существует?
11. Что делать, если производную сложно найти? Какой численный приём используют?
12. Почему в реальных проектах используют гибрид бисекции и Ньютона, а не «чистый» Ньютон?

Вопросы для самопроверки (часть 3)

13. Приведите 3 примера из IT и реальной жизни, где применяется метод Ньютона.
14. Как связан метод Ньютона с обучением нейросетей?
15. Как связан метод Ньютона с расчётом IRR в финансах?
16. Что такое метод секущих и как он относится к методу хорд и методу Ньютона?
17. Какие готовые функции Python используют методы Ньютона и хорд?
18. Назовите 4 типичные ошибки при программировании методов хорд и Ньютона.

Что должен уметь студент после этой лекции

Домашнее задание

1. Вручную (на бумаге): решить уравнение x³ − 2x − 5 = 0 на отрезке [2, 3] методом хорд с точностью 0.01. Сделать 3 шага, записать промежуточные значения.
2. Вручную: решить то же уравнение методом Ньютона. Производная: 3x² − 2. Начать с x₀ = 2. Сделать 3 шага. Сравнить скорость с заданием 1.
3. Творческое (со звёздочкой): написать на Python программу, которая для функции f(x) = e^x − 3x находит корень на отрезке [0, 1] тремя способами (бисекция, хорды, Ньютон) и выводит таблицу сравнения: метод, число итераций, найденный корень, время работы.
4. Прочитать в учебнике Лапчика М.П. «Элементы численных методов» главу 2 (раздел о методе касательных).
5. Подготовиться к практической работе №3: установить scipy, проверить работу scipy.optimize.newton.

Для любопытных: почему Ньютон сходится квадратично

Вы уже знаете, что метод Ньютона даёт квадратичную сходимость. Но почему? Вот красивое объяснение.

Разложение в ряд Тейлора

Пусть x* — точный корень, eₙ = xₙ − x* — текущая ошибка. Разложим f(x*) в ряд Тейлора в окрестности xₙ:

f(x*) = f(xₙ) + f'(xₙ)·(x* − xₙ) + (1/2)·f''(ξ)·(x* − xₙ)²

Но f(x*) = 0, а x* − xₙ = −eₙ. После преобразований (для тех, кто любит математику) получаем:

eₙ₊₁ ≈ (f''(x*) / (2·f'(x*))) · eₙ²

Что это значит

Новая ошибка eₙ₊₁ пропорциональна квадрату старой ошибки eₙ². Если ошибка была 10⁻³, следующая будет порядка 10⁻⁶, потом 10⁻¹², потом 10⁻²⁴ (уже за пределами точности компьютера).

Ещё один разбор: уравнение cos(x) − x = 0

Это уравнение из Лекции №2. Тогда мы решали его бисекцией. Теперь сравним с Ньютоном.

Подготовка

• f(x) = cos(x) − x
• Производная: f'(x) = −sin(x) − 1
• Начальное приближение: x₀ = 0.5 (внутри отрезка [0, 1]).

Итерации

Обратите внимание на магию: ошибка на шаге 0 была 0.2391, на шаге 1 — 0.0161 (стала в 15 раз меньше), на шаге 2 — 0.0001 (в 160 раз меньше), на шаге 3 — < 10⁻¹⁰ (в миллион раз меньше). Это и есть квадратичная сходимость в действии.

Итоги лекции

Мы освоили два «гоночных» метода поиска корней.

Краткое резюме

• Метод хорд использует прямую через две точки графика. Не нужна производная, работает надёжнее Ньютона, но медленнее.
• Метод Ньютона использует касательную. Нужна производная, но даёт квадратичную сходимость — в 5–10 раз быстрее.
• Оба метода требуют, чтобы корень был локализован (найден отрезок, где функция меняет знак).
• Метод Ньютона может «взорваться» при плохом старте или при f'(x) ≈ 0. В реальном коде его комбинируют с бисекцией.
• В Python есть готовые инструменты: scipy.optimize.newton и root_scalar.

Что нас ждёт дальше

Численные методы решения уравнений — это только начало. В курсе нас ждут:

• Раздел 3: Решение систем линейных уравнений (метод Гаусса, метод Зейделя).
• Раздел 4: Интерполяция (Лагранж, Ньютон, сплайны) — как восстановить данные по точкам.
• Раздел 5: Численное интегрирование — как найти площадь под кривой.
• Раздел 6: Дифференциальные уравнения — как моделировать физику.

Все эти темы опираются на то, что мы сегодня изучили: методы, сходимость, оценка точности. Так что не расслабляйтесь — впереди ещё много интересного!