Введение

Несходимость при интерполяции

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

Введение

Теорема Вейерштрасса об аппроксимации утверждает, что для каждой непрерывной функции f(x), определенной на интервале [a, b], существует множество полиномиальных функций Pn(x) для n = 0, 1, 2, …, каждая из которых имеет степень не выше n, приближающих f(x) с равномерной сходимостью на [a, b] при n, стремящемся к бесконечности, то есть,

Рассмотрим случай, когда требуется интерполировать функцию f(x) через n+1 равноотстоящих точек, используя полином степени n, Pn(x), проходящий через эти точки. Естественно, можно было бы ожидать, что согласно теореме Вейерштрасса, использование большего числа точек приведет к более точной реконструкции f(x). Однако данный конкретный набор полиномиальных функций Pn(x) не гарантированно обладает свойством равномерной сходимости; теорема лишь утверждает о существовании такого набора функций, не предоставляя общего метода его нахождения. Полиномы Pn(x), построенные таким образом, могут фактически расходиться от f(x) с ростом n; это обычно проявляется в виде колебаний, усиливающихся вблизи концов интервала интерполяции. Открытие этого явления приписывается Рунге.

Изменение точек интерполяции

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

S-Runge алгоритм без переотборки

Когда необходимо использовать равноотстоящие выборки, поскольку передискретизация на хорошо организованных наборах узлов невозможна, можно рассмотреть алгоритм S Runge. В этом подходе исходный набор узлов отображается на набор узлов Чебышёва, обеспечивая стабильную полиномиальную реконструкцию. Особенность этого метода заключается в том, что нет необходимости в передискретизации в отображенных узлах, которые также называют фиктивными узлами. Реализация этой процедуры на Python доступна здесь.

Использование кусочных многочленов

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

Ограниченная минимизация

Можно также использовать полином более высокой степени (например, при использовании точек – полином порядка вместо ). Также можно подобрать интерполирующий полином, первая (или вторая) производная которого имеет минимальную норму. Аналогичный подход заключается в минимизации ограниченной версии расстояния между -й производной полинома и средним значением его -й производной. Явно, минимизируется выражение

где и , относительно коэффициентов полинома и множителей Лагранжа. При , уравнения ограничений, порожденные множителями Лагранжа, сводятся к полиному наименьшей степени, проходящему через все точки. В противоположном случае, при больших значениях , результат будет приближаться к кусочно-полиномиальной аппроксимации. В частности, при , аппроксимация приближается к линейным кусочным полиномам, то есть к соединению точек интерполяции прямыми линиями. Параметр играет роль контроля важности отклонений от среднего значения. Чем больше , тем сильнее штрафуются большие отклонения по сравнению с малыми. Главное преимущество евклидовой нормы, , заключается в возможности получения аналитических решений и гарантии единственности минимума. При , в может быть несколько минимумов, что затрудняет определение, является ли найденный минимум глобальным или локальным.

Пример минимальных квадратов

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

Полином Бернштейна

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

Интерполяция внешних ложных ограничений

Этот метод предлагает оптимально наложить плотное распределение ограничений вида 1 = P″(x) = 0 на узлы, расположенные внешне, вблизи конечных точек каждой стороны интерполяционного интервала, где P″(x) – вторая производная интерполяционного полинома. Эти ограничения называются внешними фиктивными ограничениями, поскольку они не принадлежат интерполяционному интервалу и не соответствуют поведению функции Рунге. Метод продемонстрировал более высокую точность интерполяции по сравнению с кусочно-полиномиальной интерполяцией (сплайнами) для уменьшения эффекта феномена Рунге.

Связанные утверждения из теории приближения

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