Феномен Рунге: почему высокая степень опасна

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

Феномен Рунге — расходящиеся осцилляции интерполяционного полинома высокой степени у концов отрезка при равномерном расположении узлов.

Интуиция против реальности

Логика подсказывает: больше узлов → выше степень полинома → точнее приближение. Для многих функций это так. Но Карл Рунге в 1901 году нашёл функцию, на которой всё наоборот: f(x) = 1/(1 + 25x²) на отрезке [−1, 1]. Интерполируя её полиномом по равномерно расставленным узлам и повышая степень, мы получаем не сходимость, а всё более бешеные колебания у краёв отрезка — с амплитудой, растущей до бесконечности.

def runge(x):
    return 1.0 / (1.0 + 25.0 * x * x)

def лагранж(xs, ys, x):
    s = 0.0
    for i in range(len(xs)):
        t = ys[i]
        for j in range(len(xs)):
            if j != i:
                t *= (x - xs[j]) / (xs[i] - xs[j])
        s += t
    return s

def равномерные_узлы(n):
    return [-1.0 + 2.0 * i / n for i in range(n + 1)]

# Чем выше степень, тем ХУЖЕ у края (точка 0.9)
print("оценим ошибку интерполяции в точке x = 0.9")
for n in [4, 8, 12, 16]:
    узлы = равномерные_узлы(n)
    значения = [runge(x) for x in узлы]
    приближение = лагранж(узлы, значения, 0.9)
    истина = runge(0.9)
    print(f"степень {n:2}: P(0.9) = {приближение:8.3f}  истина = {истина:.3f}  ошибка = {abs(приближение - истина):.3f}")

Вывод:

оценим ошибку интерполяции в точке x = 0.9
степень  4: P(0.9) =   -0.289  истина = 0.047  ошибка = 0.336
степень  8: P(0.9) =   -0.960  истина = 0.047  ошибка = 1.007
степень 12: P(0.9) =   -2.083  истина = 0.047  ошибка = 2.130
степень 16: P(0.9) =   -2.812  истина = 0.047  ошибка = 2.859

Ошибка не падает, а растёт с ростом степени: от 0.34 до 2.86. Истинное значение функции в этой точке — скромные 0.047, а полином 16-й степени выдаёт −2.81. У краёв отрезка он «идёт вразнос», и чем выше степень, тем сильнее. Это и есть феномен Рунге.

  истинная f (плавный колокол)      полином высокой степени
        ___                          \  /\      /\  /
       /   \                          \/  \    /  \/
  ____/     \____               . . . узлы . . .     ← дикие осцилляции
                                  у краёв амплитуда растёт с n

Почему так происходит

Дело не в функции и не в методе, а в равномерном расположении узлов. Ошибка интерполяции содержит множитель — произведение (x−x₀)(x−x₁)...(x−x_n). На равномерной сетке этот множитель у концов отрезка достигает огромных значений, и именно туда «выплёскивается» ошибка. Высокая степень лишь усиливает эффект.

Как победить Рунге

Есть два классических лекарства:

Узлы Чебышёва. Если расставить узлы не равномерно, а сгущая их к краям (по корням многочленов Чебышёва), произведение-множитель ошибки выравнивается, и полиномиальная интерполяция снова сходится. На тех же степенях ошибка падает на порядки.
Сплайны. Не строить один полином высокой степени, а склеить много низких — кусочные кубические сплайны (следующий урок). Они вообще не страдают от Рунге, потому что степень фиксирована и мала.

Как работает под капотом

Формально ошибка интерполяции равна f^{(n+1)}(ξ)/(n+1)! · Π(x−x_i). Два сомножителя борются: факториал в знаменателе тянет ошибку вниз, но для функции Рунге производные f^{(n+1)} растут так быстро (комплексные полюса ±i/5 близко к отрезку), что перевешивают. А множитель Π(x−x_i) на равномерной сетке у краёв велик. Узлы Чебышёва минимизируют именно max|Π(x−x_i)| — поэтому и спасают. Вывод-предупреждение: «больше узлов» ≠ «точнее»; расположение узлов и выбор схемы важнее количества.

Частые ошибки

Повышать степень ради точности на равномерной сетке. Это прямой путь в Рунге; для гладких функций берите узлы Чебышёва, иначе — сплайны.
Винить функцию. Рунге проявляется у вполне гладких функций; виновата схема узлов, а не «плохая» функция.
Доверять полиному у краёв отрезка. Даже без явного Рунге края — самое ненадёжное место интерполяции.

Итоги

Феномен Рунге: на равномерной сетке полином высокой степени дико осциллирует у краёв, ошибка растёт со степенью.
Причина — множитель Π(x−x_i), огромный у концов равномерной сетки.
Лекарства: узлы Чебышёва (сгущение к краям) или кубические сплайны.
Главный урок: качество интерполяции определяется расположением узлов и схемой, а не их числом.