Численное интегрирование

Stanislaw Ulam, 1946 год, болезнь - и пасьянс. Он считает вероятность выигрыша комбинаторно, потом думает: а что если просто разыграть тысячу партий и посчитать? Так родился метод Монте-Карло - и через год он уже считал нейтронный транспорт для ядерной бомбы. Сегодня тот же принцип: байесовские нормализующие константы, AUC под ROC - численный интеграл, где размерность убивает классику.

• **scipy.integrate.quad:** вычисление нормализующих констант в вероятностных моделях; площадь под PR-кривой через трапеции
• **Монте-Карло в ML:** оценка ELBO в вариационных автоэнкодерах (VAE); Монте-Карло Dropout; MCMC-сэмплирование
• **AUC-ROC:** sklearn.metrics.auc использует правило трапеций по точкам ROC-кривой - численный интеграл

Предварительные знания

• Numerical Eigenvalue Computation

Формулы Ньютона-Котеса

Численное интегрирование - вычисление ∫ᵃᵇ f(x) dx, когда аналитическая первообразная недоступна. Формулы Ньютона-Котеса аппроксимируют f(x) полиномом через равноотстоящие узлы. Метод трапеций: O(h²), Симпсон 1/3: O(h⁴).

**Формулы Ньютона-Котеса:** **Трапеций (степень 1):** ∫ᵃᵇ f dx ≈ h/2·(f₀ + 2f₁ + ... + 2fₙ₋₁ + fₙ), h = (b−a)/n Погрешность: O(h²) - при h → 0 ошибка уменьшается как h² **Симпсон 1/3 (степень 2):** ∫ᵃᵇ f dx ≈ h/3·(f₀ + 4f₁ + 2f₂ + 4f₃ + ... + fₙ) Погрешность: O(h⁴) - гораздо точнее при малом h! **Симпсон 3/8 (степень 3):** O(h⁴)

Квадратуры Гаусса

Квадратуры Гаусса - оптимальное интегрирование: выбирают не только веса, но и **узлы**. n узлов Гаусса-Лежандра точно интегрируют полиномы степени до 2n−1. Это вдвое лучше любой формулы с n равноотстоящими узлами!

**Гаусс-Лежандр квадратура:** ∫₋₁¹ f(x) dx ≈ Σᵢ wᵢ f(xᵢ) Узлы xᵢ = корни полинома Лежандра Pₙ(x) Веса wᵢ = 2 / ((1−xᵢ²)[Pₙ'(xᵢ)]²) **n = 5 точек точно интегрируют полиномы степени ≤ 9!** Перевод с [a,b]: x = (b−a)/2·t + (a+b)/2, t ∈ [−1,1]. `scipy.integrate.fixed_quad(f, a, b, n=5)` - квадратура Гаусса

Квадратуры Гаусса оптимальны для **гладких** функций. Для функций с особенностями (разрыв производной, сингулярность) используйте адаптивное интегрирование `scipy.integrate.quad` или специальные формулы.

Адаптивное интегрирование и Монте-Карло

Адаптивное интегрирование автоматически делит [a,b] на подотрезки там, где функция быстро меняется. `scipy.integrate.quad` - адаптивное Гаусс-Kronrod правило. Монте-Карло интегрирование случайными выборками масштабируется намного лучше в высоких размерностях.

**Монте-Карло интегрирование:** ∫_Ω f(x) dx ≈ Vol(Ω) · (1/N) Σᵢ f(xᵢ), xᵢ ~ Uniform(Ω) **Скорость сходимости:** O(1/√N) - независимо от размерности! Для d-мерного интеграла: - Ньютон-Котес: O(h^p) = O(N^{-p/d}) - плохо при больших d - Монте-Карло: O(N^{-1/2}) - всегда! При d = 10 и p = 4: нужно N^{2/5} = N^{0.4} узлов квадратуры для той же точности что √N Монте-Карло.

Ключевые идеи

• **Трапеции/Симпсон:** O(h²)/O(h⁴) точность; простые; scipy.integrate.trapezoid, simpson
• **Гаусс-Лежандр:** оптимальные узлы; n точек точны для полиномов степени 2n−1; scipy.integrate.fixed_quad
• **scipy.integrate.quad:** адаптивное Гаусс-Kronrod; автоматический контроль ошибки; стандарт для 1D
• **Монте-Карло:** O(N^{-1/2}) независимо от размерности; единственный реалистичный выбор для d > 5

Связанные темы

Численное интегрирование связано с ОДУ и вероятностными методами:

• Численные методы для ОДУ — Численное интегрирование - основа методов Рунге-Кутты: каждый шаг интегрирует f(t, y) по малому интервалу
• Numerical Methods в ML — Монте-Карло интегрирование лежит в основе VAE, MCMC, Dropout - все используют случайную аппроксимацию интегралов

Вопросы для размышления

• Почему формула Симпсона имеет погрешность O(h⁴), хотя она аппроксимирует f параболой (степень 2)?
• Как оценить необходимое число выборок N в методе Монте-Карло для достижения ошибки ε?
• Когда квазислучайные последовательности (quasi-MC, Sobol, Halton) лучше псевдослучайных для интегрирования?

Связанные уроки

• calc-11-definite