Метод средней точки и метод Хойна: порядок 2

Главная беда метода Эйлера — он судит о наклоне на всём шаге по одной-единственной точке в его начале. А что если заглянуть вперёд, оценить наклон ещё и в конце шага, и пойти по усреднённому направлению? Два вычисления правой части вместо одного — и порядок точности подскакивает с первого до второго. Так устроены методы средней точки и Хойна, прямые предки знаменитой Рунге-Кутты.

Метод Хойна (улучшенный Эйлер, предиктор-корректор) — схема второго порядка: сначала предиктором (явным шагом Эйлера) грубо оценивают конец шага, затем корректором делают настоящий шаг по среднему из наклонов в начале и в предсказанном конце.

Откуда берётся точность

Вернёмся к корню проблемы. Метод Эйлера идёт по касательной, взятой в начале шага. Если решение на шаге изгибается, этот наклон уже устарел к концу шага — отсюда систематическая ошибка O(h). Естественная идея: наклон на шаге не постоянен, так давайте использовать не одно его значение, а несколько, и скомбинировать их поумнее.

Метод средней точки предлагает шагнуть сначала на половину шага вперёд, посмотреть наклон там, в серединке, и уже этим серединным наклоном пройти весь шаг целиком. Середина — хорошая «представительная» точка отрезка, наклон в ней ближе к среднему по шагу, чем наклон с краю. Формально:

Metod sredney tochki:
  k1   = f(t_n, y_n)                # naklon v nachale
  y_mid = y_n + (h/2) * k1          # shag na polovinu - v seredinu
  k2   = f(t_n + h/2, y_mid)        # naklon v seredine
  y_{n+1} = y_n + h * k2            # ves shag seredinnym naklonom

Метод Хойна идёт другим путём — усредняет наклоны на краях. Сначала предиктор: обычным Эйлером грубо прыгаем в конец шага и получаем черновое значение. Там вычисляем наклон. Теперь у нас два наклона — в начале и в (предсказанном) конце. Корректор делает настоящий шаг по их среднему арифметическому:

Metod Hoyna (prediktor-korrektor):
  k1 = f(t_n, y_n)                  # naklon v nachale
  y_pred = y_n + h * k1             # PREDIKTOR: grubyy konec (shag Eylera)
  k2 = f(t_n + h, y_pred)           # naklon v predskazannom konce
  y_{n+1} = y_n + h * (k1 + k2) / 2 # KORREKTOR: shag po srednemu naklonu

Обе схемы стоят два вычисления f на шаг вместо одного у Эйлера — вдвое дороже за шаг. Но за эти деньги мы покупаем второй порядок: глобальная ошибка теперь O(h²), а не O(h). Это огромная разница: уменьшили шаг вдвое — ошибка упала вчетверо, а не вдвое.

Как работает под капотом: почему именно второй порядок

Секрет — в ряде Тейлора. Точное приращение решения за шаг раскладывается так:

y(t_n + h) = y_n + h·y'_n + (h²/2)·y''_n + (h³/6)·y'''_n + ...

Метод Эйлера воспроизводит только два первых члена (до h·y'), а член (h²/2)·y'' отбрасывает — вот его локальная ошибка O(h²) и глобальная O(h). Хитрость методов Хойна и средней точки в том, что комбинация двух наклонов k1 и k2 подобрана так, что её разложение в ряд совпадает с точным вплоть до члена h² включительно. Первый «лишний» отброшенный член теперь — порядка h³. Локальная ошибка стала O(h³), а глобальная (после деления на число шагов N = L/h, как мы разбирали) — O(h²). Второй порядок.

Можно сказать проще: усреднение наклонов «ловит» кривизну решения (вторую производную), которую одиночная касательная Эйлера игнорирует. Именно кривизна — главный источник ошибки Эйлера, и методы второго порядка её учитывают.

Сравнение в эксперименте

Проверим на нашем эталоне y' = y, y(0) = 1 на [0, 1], точное значение в конце — e ≈ 2.71828. Прогоним Эйлера и Хойна при одинаковых шагах и сравним ошибки. Заодно для Хойна посмотрим, как ошибка падает при делении шага вдвое — отношение должно стремиться к 4, а не к 2.

import math

f = lambda t, y: y

def euler(h, n):
    t, y = 0.0, 1.0
    for _ in range(n):
        y = y + h * f(t, y)
        t = t + h
    return y

def heun(h, n):
    t, y = 0.0, 1.0
    for _ in range(n):
        k1 = f(t, y)
        y_pred = y + h * k1          # prediktor
        k2 = f(t + h, y_pred)        # naklon v konce
        y = y + h * (k1 + k2) / 2    # korrektor
        t = t + h
    return y

exact = math.exp(1.0)

print("Eyler protiv Hoyna pri odinakovom shage:")
print(f"{'h':>8} {'osh Eylera':>15} {'osh Hoyna':>15}")
for h in [0.1, 0.05, 0.025]:
    n = round(1.0 / h)
    print(f"{h:8.4f} {abs(exact - euler(h, n)):15.6f} {abs(exact - heun(h, n)):15.6f}")

print()
print("Shodimost Hoyna (otnoshenie -> 4 = vtoroy poryadok):")
print(f"{'h':>8} {'oshibka':>12} {'otnosh':>10}")
prev = None
for h in [0.1, 0.05, 0.025]:
    n = round(1.0 / h)
    err = abs(exact - heun(h, n))
    ratio = '-' if prev is None else f"{prev / err:.2f}"
    print(f"{h:8.4f} {err:12.7f} {ratio:>10}")
    prev = err

Вывод:

Eyler protiv Hoyna pri odinakovom shage:
       h      osh Eylera       osh Hoyna
  0.1000        0.124539        0.004201
  0.0500        0.064984        0.001091
  0.0250        0.033218        0.000278

Shodimost Hoyna (otnoshenie -> 4 = vtoroy poryadok):
       h      oshibka     otnosh
  0.1000    0.0042010          -
  0.0500    0.0010908       3.85
  0.0250    0.0002779       3.93

Цифры говорят сами за себя. При одном и том же шаге h = 0.1 ошибка Эйлера — 0.125, а Хойна — 0.0042, в тридцать раз меньше. И падает она быстрее: смотрите на столбец отношений во второй таблице — 3.85, 3.93, всё ближе к четырём. Делим шаг вдвое — ошибка падает вчетверо. Это и есть второй порядок в действии (вспомните: у Эйлера отношение стремилось к 2). Чтобы выбить лишний десятичный знак точности, Хойну достаточно уменьшить шаг примерно в √10 ≈ 3.2 раза, а не в 10 — он куда экономнее.

Оба метода — частные случаи семейства Рунге-Кутты второго порядка (они отличаются лишь тем, в какой точке и с какими весами берут наклоны). Сделав ещё шаг по этой дороге — взяв четыре оценки наклона на шаг с хитрыми весами — получают классический метод Рунге-Кутты 4-го порядка, рабочую лошадку всех инженерных расчётов. Но идея одна и та же, и вы её уже поняли: чем в большем числе точек шага мы спрашиваем наклон и чем умнее усредняем, тем выше порядок.

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

Используют предиктор как ответ. В методе Хойна y_pred — черновик, нужный только чтобы вычислить k2. Настоящий ответ даёт корректор y_n + h·(k1+k2)/2. Если по ошибке вернуть y_pred, вы получите обычного Эйлера первого порядка.

Берут наклон k2 в t_n вместо t_n + h. Для автономного f = y разницы нет, но для неавтономных уравнений второй наклон обязан вычисляться в конце шага: f(t_n + h, y_pred). Перепутаете точку времени — потеряете второй порядок.

Путают среднюю точку с Хойном. Это разные схемы: средняя точка берёт один наклон в середине отрезка, Хойн — среднее из двух наклонов на краях. Обе второго порядка, но формулы разные; не смешивайте их части.

Ждут отношение ровно 4. Как и у первого порядка, оценка O(h²) асимптотическая. При конечных h отношение приближается к 4 снизу (3.85, 3.93...) — это нормально.

• Источник ошибки Эйлера — наклон берётся в одной точке; методы 2-го порядка спрашивают наклон в нескольких точках шага и усредняют.
• Средняя точка: шаг на полшага, наклон в середине, им — весь шаг. Хойн: предиктор Эйлером, корректор по среднему наклонов начала и конца.
• Цена — два вычисления f на шаг; выигрыш — глобальная ошибка O(h²) вместо O(h).
• Комбинация наклонов воспроизводит ряд Тейлора до члена h², поэтому метод «видит» кривизну решения.
• Эксперимент: при равном шаге Хойн точнее Эйлера в десятки раз, а отношение ошибок при делении шага стремится к 4 (подпись 2-го порядка).
• Эти схемы — ступенька к методам Рунге-Кутты высших порядков: больше точек оценки наклона — выше порядок.