Феномен Рунге

Феномен (явление) Рунге — в численном анализе эффект нежелательных осцилляций, возникающий при интерполяции полиномами высоких степеней. Был открыт Карлом Рунге при изучении ошибок полиномиальной интерполяции для приближения некоторых функций[1].

Функция Рунге (плотность вероятности распределения Коши) и интерполяционный полином 5-й степени

Функция типа Рунге ${\displaystyle f(x)={\frac {1}{1+x^{2}}}}$ и интерполяционный полином 10-й степени

Рассмотрим функцию ${\displaystyle f(x)={\frac {1}{1+x^{2}}}.}$ Если интерполировать её по равноотстоящим узлам ${\displaystyle x_{i}}$ между −5 и 5. ${\displaystyle x_{i}=-5+(i-1){\frac {10}{n}},\quad i\in \left\{1,2,\dots ,n+1\right\}}$ полиномом ${\displaystyle P_{n}(x)}$ со степенью меньше или равной ${\displaystyle n}$, то полученный интерполянт будет осциллировать ближе к концам интервала. С возрастанием степени полинома погрешность интерполяции стремится к бесконечности: ${\displaystyle \lim _{n\rightarrow \infty }\left(\max _{-5\leq x\leq 5}|f(x)-P_{n}(x)|\right)=\infty .}$

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

Компромиссом можно считать узлы Чебышёва, погрешность интерполяции по ним равномерно убывает для любой абсолютно непрерывной функции.