Эффект Рунге

Материал из MachineLearning.

Статья написана с использованием LLM Qwen3.7-Plus и проверена участником Участник:Iurii Zhuravlev 21:29, 19 июля 2026 (MSD)

Промпт приводится полностью в Обсуждение:Эффект Рунге

Содержание

1 Историческая справка
2 Математическая формулировка
- 2.1 Интерполяционный полином Лагранжа
- 2.2 Функция Рунге и расходимость
3 Причины возникновения эффекта
- 3.1 Комплексно-аналитическое объяснение
- 3.2 Константа Лебега
4 Связь с машинным обучением и статистикой
5 Методы борьбы
6 Практическое руководство для инженера
7 См. также
8 Примечания
9 Литература

Эффект Рунге (англ. Runge's phenomenon) — явление в численном анализе и теории приближений, при котором интерполяция функции полиномом высокой степени в равномерно распределённых узлах приводит к сильным осцилляциям приближения, особенно вблизи границ интервала. При увеличении числа узлов (и, соответственно, степени полинома) максимальная ошибка интерполяции не уменьшается, а растёт неограниченно, стремясь к бесконечности.

Эффект Рунге имеет фундаментальное значение для машинного обучения и статистики, поскольку является классическим примером того, как увеличение сложности модели (степени полинома) приводит к катастрофическому переобучению. Это явление напрямую связано с проблемой неустойчивости полиномиальной регрессии высокой степени и объясняет, почему на практике почти всегда используются сплайны или базисы Чебышёва вместо стандартных степенных базисов.

Историческая справка

Открытие эффекта

Эффект был описан немецким математиком Карлом Рунге в 1901 году в его работе, посвящённой интерполяции функций^[1]. Рунге исследовал, насколько хорошо интерполяционный полином Лагранжа приближает различные функции при увеличении числа равноотстоящих узлов.

Он показал, что для функции, которую он позже назвал «контрпримером»:

$f(x) = \frac{1}{1 + 25x^2}, \quad x \in [-1, 1],$

интерполяционный полином $P_n(x)$ степени $n$ , построенный по $n+1$ равномерно распределённым узлам, расходится при $n \to \infty$ вблизи концов отрезка. Максимальное отклонение $\max_{x \in [-1,1]} |f(x) - P_n(x)|$ неограниченно растёт, хотя в центре интервала приближение остаётся хорошим.

Теоретическое осмысление

Полное теоретическое объяснение эффекта было дано позже, в 1930-х годах, в работах Гезы Фабера и Сергея Натановича Бернштейна. Фабёр доказал, что для любой заранее заданной таблицы узлов существует непрерывная функция, для которой интерполяционный процесс расходится^[1].

Джеймс Лагранж (James L. Walsh) и позднее Вальтер Гаутсчи систематизировали теорию, связав эффект Рунге с поведением функции в комплексной плоскости^[1].

Связь с машинным обучением

В 1970-х годах эффект Рунге стал рассматриваться как математический аналог проблемы переобучения в статистике. Корнелиус Ланцош в своей книге 1956 года «Applied Analysis» популяризировал использование узлов Чебышёва для борьбы с эффектом в вычислительной практике^[1]. В современном машинном обучении эффект Рунге изучается в контексте компромисса смещения и дисперсии и является одним из нагляднейших примеров того, почему сложные модели не всегда лучше простых.

Математическая формулировка

Интерполяционный полином Лагранжа

Пусть задана функция $f(x)$ на отрезке $[-1, 1]$ и набор из $n+1$ равномерно распределённых узлов:

$x_i = -1 + \frac{2i}{n}, \quad i = 0, 1, \dots, n.$

Интерполяционный полином Лагранжа $P_n(x)$ степени $n$ , проходящий через все точки $(x_i, f(x_i))$ , имеет вид:

$P_n(x) = \sum_{i=0}^{n} f(x_i) L_i(x),$

где $L_i(x)$ — базисные полиномы Лагранжа:

$L_i(x) = \prod_{\substack{j=0 \\ j \ne i}}^{n} \frac{x - x_j}{x_i - x_j}.$

Ошибку интерполяции можно записать как:

$f(x) - P_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n} (x - x_i),$

где $\xi \in (-1, 1)$ . Казалось бы, при $n \to \infty$ факториал в знаменателе должен обеспечить сходимость. Однако произведение $\omega_n(x) = \prod_{i=0}^{n} (x - x_i)$ растёт экспоненциально вблизи концов отрезка, и этот рост перевешивает убывание факториала.

Функция Рунге и расходимость

Для классической функции Рунге $f(x) = \frac{1}{1 + 25x^2}$ можно показать, что:

$\lim_{n \to \infty} \max_{x \in [-1, 1]} |f(x) - P_n(x)| = \infty.$

Более того, расходимость наблюдается на любых подынтервалах $[-1, -a] \cup [a, 1]$ , где $a \approx 0.726$ . Только на центральном интервале $[-0.726, 0.726]$ интерполяционный полином сходится к функции.

Причины возникновения эффекта

Комплексно-аналитическое объяснение

Наиболее глубокое объяснение эффекта Рунге даёт теория функций комплексного переменного. Функция $f(x) = \frac{1}{1+25x^2}$ , будучи гладкой на вещественной оси, имеет особые точки (полюсы) в комплексной плоскости:

$z = \pm \frac{i}{5}.$

Радиус сходимости ряда Тейлора $f(z)$ вокруг любой точки вещественной оси определяется расстоянием до ближайшего полюса. Для интерполяции полиномом Лагранжа по равномерным узлам область сходимости ограничена так называемой областью Бернштейна — эллипсом в комплексной плоскости с фокусами в $\pm 1$ и суммой полуосей, равной $1 + \sqrt{2}$ . Если полюсы функции лежат вне этого эллипса, интерполяция сходится; если внутри — расходится^[1].

Для функции Рунге полюсы $\pm i/5$ лежат внутри области Бернштейна, что и объясняет расходимость.

Константа Лебега

Количественно неустойчивость интерполяции описывается константой Лебега $\Lambda_n$ :

$\Lambda_n = \max_{x \in [-1, 1]} \sum_{i=0}^{n} |L_i(x)|.$

Константа Лебега оценивает, во сколько раз ошибка интерполяции может превышать ошибку наилучшего полиномиального приближения той же степени. Для равномерных узлов:

$\Lambda_n \sim \frac{2^{n+1}}{e \, n \ln n} \quad n \to \infty.$

Экспоненциальный рост $\Lambda_n$ означает, что даже малая ошибка в значениях функции (например, шум в данных) усиливается в $\Lambda_n$ раз, что делает интерполяцию численно неустойчивой.

Связь с машинным обучением и статистикой

Полиномиальная регрессия и переобучение

В машинном обучении эффект Рунге проявляется в полиномиальной регрессии высокой степени. Рассмотрим задачу регрессии:

$y = \beta_0 + \beta_1 x + \beta_2 x^2 + \dots + \beta_d x^d + \varepsilon.$

Если обучающие точки $x_i$ распределены равномерно на отрезке, а степень $d$ велика, то модель начинает демонстрировать поведение, полностью аналогичное эффекту Рунге:

В центре диапазона признаков модель хорошо аппроксимирует истинную зависимость.
Вблизи границ — появляются сильные осцилляции, предсказания становятся бессмысленными.

С точки зрения теории смещения и дисперсии, увеличение степени полинома снижает смещение, но экспоненциально увеличивает дисперсию модели. Эффект Рунге — это наглядная демонстрация того, что сложная модель не всегда лучше простой.

Мультиколлинеарность и численная неустойчивость

Ещё одно проявление эффекта — мультиколлинеарность признаков. В полиномиальной регрессии признаки $x, x^2, x^3, \dots, x^d$ становятся практически линейно зависимыми при больших $d$ . Матрица Грама $\mathbf{X}^T \mathbf{X}$ становится плохо обусловленной, её число обусловленности растёт экспоненциально с $d$ . Это приводит к тому, что малые возмущения в данных (шум) вызывают огромные изменения в оценках коэффициентов $\beta_i$ .

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

Аналогия с нейронными сетями

Хотя эффект Рунге строго доказан для полиномиальных моделей, его идеи переносятся и на глубокое обучение. Спектральное смещение (spectral bias) нейронных сетей — явление, при котором сети в первую очередь изучают низкочастотные компоненты функции и медленно — высокочастотные — можно рассматривать как регуляризованную версию эффекта Рунге, где архитектура сети сама по себе ограничивает осцилляции.

Методы борьбы

Существует несколько эффективных способов устранения эффекта Рунге:

Узлы Чебышёва

Наиболее известный метод — замена равномерных узлов на узлы Чебышёва:

$x_k = \cos\left(\frac{(2k - 1)\pi}{2n}\right), \quad k = 1, 2, \dots, n.$

Узлы сгущаются к краям отрезка, что компенсирует рост осцилляций. Для узлов Чебышёва константа Лебега растёт лишь логарифмически:

$\Lambda_n \sim \frac{2}{\pi} \ln n.$

Это гарантирует сходимость интерполяции для любой непрерывной функции, допускающей аналитическое продолжение в эллипс Бернштейна. На практике использование узлов Чебышёва полностью устраняет эффект Рунге^[1].

Кусочно-полиномиальная интерполяция (сплайны)

Вместо одного полинома высокой степени на всём отрезке используются сплайны — кусочно-полиномиальные функции низкой степени (обычно кубические), соединённые в узлах с заданной гладкостью. Поскольку каждый кусок имеет малую степень, осцилляции не возникают. Сплайны обеспечивают локальность: изменение данных в одной точке влияет только на соседние куски.

В машинном обучении сплайны лежат в основе обобщённых аддитивных моделей (GAM) и современных архитектур KAN^[1].

Регуляризация

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

$\min_{f} \sum_{i=1}^n (y_i - f(x_i))^2 + \lambda \int [f''(x)]^2 dx.$

Параметр $\lambda$ контролирует компромисс между близостью к данным и гладкостью, предотвращая осцилляции.

Замена базиса

Вместо степенного базиса $\{1, x, x^2, \dots, x^d\}$ используется ортогональный базис — полиномы Чебышёва или Лежандра. Ортогональность устраняет мультиколлинеарность и стабилизирует численные расчёты.

Практическое руководство для инженера

Как избежать эффекта Рунге в задачах анализа данных:

Избегайте полиномиальной регрессии высокой степени: Если вам нужна нелинейная модель, используйте сплайны (библиотеки `patsy`, `pyGAM`) или градиентный бустинг (XGBoost, LightGBM).
Используйте узлы Чебышёва: При интерполяции или построении базисных функций располагайте узлы по формуле $x_k = \cos\left(\frac{(2k-1)\pi}{2n}\right)$ . В Python — `numpy.polynomial.chebyshev.chebpts`.
Регуляризуйте: Если вы вынуждены использовать полиномы высокой степени, применяйте гребневую регрессию (Ridge) с большим параметром $\alpha$ .
Нормализуйте признаки: Полиномиальные признаки крайне чувствительны к масштабу. Всегда применяйте стандартизацию перед построением полиномов.
Проверяйте поведение на краях: После обучения модели визуализируйте предсказания на всём диапазоне признаков, особенно в хвостах распределения. Осцилляции — верный признак эффекта Рунге.
Используйте KAN: Современные сети Колмогорова-Арнольда используют сплайны на рёбрах, что по конструкции устраняет эффект Рунге и обеспечивает гладкую интерполяцию.

См. также

Примечания

Литература

Runge C. Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten // Zeitschrift für Mathematik und Physik. — 1901. — Vol. 46. — P. 224-243.
Faber G. Über die interpolatorische Darstellung stetiger Funktionen durch algebraische Polynome beschränkten Grades // Jahresbericht der Deutschen Mathematiker-Vereinigung. — 1914. — Vol. 23. — P. 192-210.
Lanczos C. Applied Analysis. — Prentice-Hall, 1956. — 528 p.
Mason J. C., Handscomb D. C. Chebyshev Polynomials. — CRC Press, 2003. — 368 p.
Trefethen L. N. Approximation Theory and Approximation Practice. — SIAM, 2013. — 294 p.
Boyd J. P. Chebyshev and Fourier Spectral Methods. — 2nd ed. — Dover Publications, 2001. — 688 p.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed. — Springer, 2009. — 745 p. (Раздел 5.2: Basis Expansions and Regularization).
Liu Z., Wang Y., Vaidya S., Ruehle F., Halbleib A., Chen Y., ... & Tegmark M. KAN: Kolmogorov-Arnold Networks // Advances in Neural Information Processing Systems (NeurIPS). — 2024. — arXiv:2404.19756.

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%AD%D1%84%D1%84%D0%B5%D0%BA%D1%82_%D0%A0%D1%83%D0%BD%D0%B3%D0%B5»