Численные решатели ОДУ

Зачем это в ветке про диффузию

Забегая вперёд: сэмплирование диффузионной модели — это решение дифференциального уравнения численно. Урок 060 покажет, откуда оно берётся; здесь нужен аппарат.

Задача Коши: известна производная и начальное условие, нужно значение в конце.

$$\frac{dx}{dt} = \htmlData{k=field}{f(t, x)}, \quad x(0) = x_0 \qquad\Longrightarrow\qquad x_{n+1} = x_n + \htmlData{k=step}{h}\,\Phi(t_n, x_n, h)$$

Поле $f$ в диффузии — это и есть выход нейросети. Значит любое утверждение о численных методах здесь превращается в утверждение о том, сколько раз нужно вызвать сеть, — и вот почему эта тема практически важна, а не формальна.

Три метода

Эйлер — двигаться по производной в текущей точке:

$x_{n+1} = x_n + h f(t_n, x_n)$

Хойн (он же метод трапеций, он же RK2) — сделать пробный шаг, посмотреть производную там и усреднить:

$\tilde{x} = x_n + h f(t_n, x_n), \qquad x_{n+1} = x_n + \frac{h}{2}\big[f(t_n, x_n) + f(t_{n+1}, \tilde{x})\big]$

Рунге–Кутта 4 — четыре пробных вычисления с известными весами:

$x_{n+1} = x_n + \frac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4)$

Ключевая цифра, которую стоит держать в голове: число вызовов $f$ на шаг — один, два и четыре соответственно. В диффузии это буквально число прогонов сети.

Что такое порядок и как его измерить

Метод имеет порядок $p$, если ошибка на конце ведёт себя как $O(h^p)$. Проверяется это без всякой теории: удвоить число шагов и посмотреть, во сколько раз упала ошибка. Отношение $2^p$, значит

$p \approx \log_2 \frac{e(h)}{e(h/2)}$

Виджет считает именно это. Возьмите $dx/dt = x$, где точный ответ $e$, и пройдитесь по методам.

dx/dt = xdx/dt = −2x + sin 3tdx/dt = −12x

ЭйлерХойнRK4

время x

шагов

8

шум σ

0

x в конце

2.56578

ошибка

1.52e-1

измеренный порядок

0.92

разброс траекторий

—

разница методов

0.1525

Классический тест: точный ответ равен e = 2.718281828…, поэтому ошибку видно до последнего знака.

Шум выключен: столбец «измеренный порядок» осмыслен, и его стоит сравнить с 1, 2 и 4.

Измерено на $dx/dt = x$, $T = 1$:

метод	вызовов $f$	ошибка при $N=8$	ошибка при $N=64$	измеренный порядок
Эйлер	$1$	$1.5\cdot10^{-1}$	$2.1\cdot10^{-2}$	$0.98$
Хойн	$2$	$6.4\cdot10^{-3}$	$1.1\cdot10^{-4}$	$1.98$
RK4	$4$	$5.0\cdot10^{-6}$	$1.3\cdot10^{-9}$	$3.98$

Обратите внимание, что порядок измеряется как $0.98$, а не ровно $1$: он асимптотический, и на крупном шаге проявляется не полностью. Это сам по себе полезный факт — «второй порядок» не означает, что при четырёх шагах ошибка будет квадратично мала.

Как правильно сравнивать методы

Здесь стоит поправить типичное сравнение «RK4 точнее Эйлера». Точнее при равном числе шагов, но каждый шаг стоит вчетверо больше. Честное сравнение — при равном числе вызовов $f$:

бюджет: 32 вызова	шагов	ошибка
Эйлер	$32$	$4.1\cdot10^{-2}$
Хойн	$16$	$1.7\cdot10^{-3}$
RK4	$8$	$5.0\cdot10^{-6}$

RK4 всё равно выигрывает, и с большим запасом. Но вывод не универсален: выигрыш высокого порядка пропадает, когда либо поле $f$ негладко, либо в задаче есть шум (урок 030), либо бюджет вызовов настолько мал, что асимптотика не наступила. Все три случая встречаются в диффузии, и поэтому DDIM с Эйлером остаётся конкурентоспособным.

Устойчивость — не то же самое, что точность

Возьмите в виджете жёсткое уравнение $dx/dt = -12x$ с четырьмя шагами. Точный ответ убывает до $e^{-12} \approx 6\cdot10^{-6}$; Эйлер даёт $(1 - 12h)^4 = (1-3)^4 = 16$ — на семь порядков не туда, да ещё с чередованием знака.

Причина не в порядке метода. Эйлер устойчив только при $|1 + h\lambda| < 1$, то есть при $h < 2/|\lambda|$ для отрицательного вещественного $\lambda$. Это в точности то же условие $\alpha < 2/L$, которое ограничивало шаг градиентного спуска в блоке 5, урок 040 — и не случайно: градиентный спуск и есть метод Эйлера для $\dot{x} = -\nabla f(x)$.

	точность	устойчивость
про что	как быстро ошибка падает с $h$	расходится ли метод вовсе
лечится	методом выше порядка	только уменьшением шага (или неявной схемой)
проявляется	лишними знаками	взрывом или колебаниями

Различать их обязательно: увидев расходимость, повышать порядок метода бессмысленно.

Что из этого понадобится дальше

• Сэмплирование диффузии — численное интегрирование, и число вызовов сети равно числу вычислений $f$. Отсюда все разговоры про «сколько шагов нужно».
• Порядок метода — измеримая величина, и на крупных шагах он проявляется частично.
• Сравнивать методы нужно по бюджету вызовов, а не по числу шагов.
• Устойчивость ограничивает шаг независимо от точности, и её ограничение — то же, что у градиентного спуска.