В математической области численного анализа , явление Рунга ( немецкое: [ʁʊŋə] ) является проблемой колебаний на краях интервала , который происходит при использовании полиномиальной интерполяции с полиномами высокой степени над набором эквидистантен расположенными точки интерполяции. Он был открыт Карлом Дэвидом Толме Рунге (1901) при исследовании поведения ошибок при использовании полиномиальной интерполяции для аппроксимации определенных функций. [1] Это открытие было важным, потому что оно показывает, что получение более высоких степеней не всегда улучшает точность. Это явление аналогично явлению Гиббса в приближении ряда Фурье.
Вступление
В теореме Вейерштрасса приближение гласит , что для каждой непрерывной функции F ( х ) , определенной на интервале [ , Ь ], существует набор полиномиальных функций Р п ( х ) при п = 0, 1, 2, ..., каждый из степени не более n , что приближает f ( x ) с равномерной сходимостью по [ a , b ], когда n стремится к бесконечности, то есть
Рассмотрим случай , когда кто -то желает интерполировать через п + 1 эквидистантно расположенных точек функции F ( х ) с помощью п - градусный многочлен Р п ( х ) , который проходит через эти точки. Естественно, из теоремы Вейерштрасса можно было ожидать, что использование большего количества точек приведет к более точному восстановлению f ( x ). Однако не гарантируется , что этот конкретный набор полиномиальных функций P n ( x ) обладает свойством равномерной сходимости; теорема только утверждает, что существует набор полиномиальных функций, не предоставляя общего метода их нахождения .
Р п ( х ) , полученный таким образом , может в действительности расходятся от F ( х ) , как п возрастает; обычно это происходит в виде колеблющегося рисунка, который увеличивается ближе к концам точек интерполяции. Это явление приписывают Рунге. [2]
Проблема
Рассмотрим функцию Рунге
(масштабированная версия Ведьмы Агнеси ). Рунге обнаружил, что если эта функция интерполирована в эквидистантных точках x i между -1 и 1 таким образом, что:
с полиномом P n ( x ) степени ≤ n , результирующая интерполяция колеблется к концу интервала, то есть близко к -1 и 1. Можно даже доказать, что ошибка интерполяции увеличивается (без ограничений), когда степень полином увеличивается:
Это показывает, что полиномиальная интерполяция высокой степени в равноотстоящих точках может быть проблематичной.
Причина
Феномен Рунге является следствием двух свойств этой проблемы.
- Величина производных n-го порядка этой конкретной функции быстро растет с увеличением n .
- Эквидистантность между точками приводит к постоянной Лебега, которая быстро увеличивается с увеличением n .
Это явление графически очевидно, потому что оба свойства в совокупности увеличивают величину колебаний.
Ошибка между производящей функцией и интерполяционным полиномом порядка n определяется выражением
для некоторых в (−1, 1). Таким образом,
- .
Обозначим через узловая функция
и разреши быть максимумом величины функция:
- .
Элементарно доказать, что при равноудаленных узлах
где размер шага.
Кроме того, предположим, что ( n +1) -я производная от ограничен, т. е.
- .
Следовательно,
- .
Но величина ( n + 1) -й производной функции Рунге увеличивается с увеличением n , поскольку. Следствием этого является то, что полученная верхняя оценка, стремится к бесконечности, когда n стремится к бесконечности.
Хотя это часто используется для объяснения феномена Рунге, тот факт, что верхняя граница ошибки стремится к бесконечности, конечно, не обязательно означает, что сама ошибка также расходится с n.
Смягчение проблемы
Изменение точек интерполяции
Колебание можно минимизировать, используя узлы, которые более плотно распределены по краям интервала, в частности, с асимптотической плотностью (на интервале [−1,1]), задаваемой формулой [3]. Стандартный пример такого набора узлов - узлы Чебышева , для которых максимальная ошибка аппроксимации функции Рунге гарантированно уменьшается с увеличением полиномиального порядка. Это явление демонстрирует, что многочлены высокой степени обычно не подходят для интерполяции с равноудаленными узлами.
Алгоритм S-Рунге без передискретизации
Когда необходимо использовать эквидистантные выборки, поскольку повторная выборка на наборах узлов с хорошим поведением невозможна, можно рассмотреть алгоритм S-Рунге. [4] В этом подходе исходный набор узлов отображается на набор узлов Чебышева , обеспечивая стабильную полиномиальную реконструкцию. Особенность этого метода заключается в том, что нет необходимости в передискретизации сопоставленных узлов, которые также называются фальшивыми узлами . Python выполнение этой процедуры можно найти здесь .
Использование кусочно-полиномов
Этой проблемы можно избежать, используя сплайновые кривые, которые являются кусочно-полиномами. При попытке уменьшить ошибку интерполяции можно увеличить количество частей полинома, которые используются для построения сплайна, вместо увеличения степени используемых полиномов.
Ограниченная минимизация
Можно также подобрать полином более высокой степени (например, с точки используют полином порядка вместо ), и подобрать интерполяционный многочлен, первая (или вторая) производная которого имеет минимальную норма .
Аналогичный подход заключается в минимизации ограниченной версии расстояние между полиномами производная и среднее значение ее производная. Явно, чтобы минимизировать
где а также , относительно коэффициентов полинома и множителей Лагранжа ,. Когда, уравнения связи, порождаемые множителями Лагранжа, уменьшают к минимальному многочлену, проходящему через все точки. На противоположном концеприблизится к форме, очень похожей на приближение кусочно-полиномов. Когда, в частности, приближается к линейным кусочно-полиномам, т.е. соединяет точки интерполяции прямыми линиями.
Роль, которую играет в процессе минимизации состоит в том, чтобы контролировать важность размера отклонений от среднего значения. Чем большето есть более сильные колебания наказываются по сравнению с небольшими. Наибольшее преимущество евклидовой нормы,, заключается в том, что он допускает аналитические решения и гарантирует, что будет только один минимум. Когда может быть несколько минимумов в , что затрудняет обеспечение того, чтобы конкретный найденный минимум был глобальным минимумом, а не локальным.
Подгонка наименьших квадратов
Другой метод - подгонка полинома меньшей степени с использованием метода наименьших квадратов . Обычно при использовании равноудаленные точки, если тогда приближение наименьших квадратов хорошо кондиционирован. [5]
Многочлен Бернштейна
Используя многочлены Бернштейна , можно равномерно аппроксимировать каждую непрерывную функцию в отрезке, хотя этот метод довольно затратен в вычислительном отношении. [ необходима цитата ]
Связанные утверждения из теории приближений
Для каждой предопределенной таблицы узлов интерполяции существует непрерывная функция, для которой последовательность полиномов интерполяции на этих узлах расходится. [6] Для каждой непрерывной функции существует таблица узлов, на которых сходится процесс интерполяции. [ необходимая цитата ] Чебышёвская интерполяция (т.е. на чебышёвских узлах ) сходится равномерно для любой абсолютно непрерывной функции.
Смотрите также
- Сравните с явлением Гиббса для синусоидальных базисных функций
- Серия Тейлора
- Чебышевские узлы
- Теорема Стоуна – Вейерштрасса
Рекомендации
- ^ Рунге, Карл (1901), "Über empirische Funktionen und die Interpolation zwischen äquidistanten Ordinaten", Zeitschrift für Mathematik und Physik , 46 : 224–243.доступно на www.archive.org
- ^ Эпперсон, Джеймс (1987). «На примере Рунге» . Амер. Математика. Ежемесячно . 94 : 329–341. DOI : 10.2307 / 2323093 .
- ^ Беррут, Жан-Поль; Trefethen, Ллойд Н. (2004), "Барицентрическое Лагранжа интерполяции", SIAM Обзор , 46 (3): 501-517, CiteSeerX 10.1.1.15.5097 , DOI : 10,1137 / S0036144502417715 , ISSN 1095-7200
- ^ Де Марчи, Стефано; Маркетти, Франческо; Перраккионе, Эмма; Поджиали, Давиде (2020), «Полиномиальная интерполяция с помощью отображенных баз без повторной выборки», J. Comput. Прил. Математика. , 364 , DOI : 10.1016 / j.cam.2019.112347 , ISSN 0377-0427
- ^ Дальквист, Гермунд ; Бьорк, Оке (1974), «4.3.4. Эквидистантная интерполяция и феномен Рунге», Численные методы , стр. 101–103 , ISBN 0-13-627315-7
- ^ Чейни, Уорд; Свет, Уилл (2000), Курс теории приближений , Брукс / Коул, стр. 19, ISBN 0-534-36224-9