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

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

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

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

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

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

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