Почему равноотстоящие точки ведут себя плохо?

24

Описание эксперимента:

При интерполяции Лагранжа точное уравнение выбирается в точках (порядок полиномов ) и интерполируется в 101 точке. Здесь изменяется от 2 до 64. Каждый раз , когда готовятся графики ошибок , и . Видно , что, когда функция дискретизируются на равноразнесенные точках, ошибка изначально падает (это происходит до меньше , чем примерно 15 или около того ) , а затем ошибки идет вверх при дальнейшем увеличении .NN1NL1L2LNN

Принимая во внимание, что если первоначальная выборка выполняется в точках Лежандра-Гаусса (LG) (корни полиномов Лежандра) или в точках Лежандра-Гаусса-Лобатто (LGL) (корни полиномов Лобатто), ошибка падает до уровня машины и не увеличивается, когда еще больше увеличивается.N

Мои вопросы

Что именно происходит в случае равноотстоящих точек?

Почему увеличение в полиномиальном порядке приводит к увеличению ошибки после определенной точки?

Означает ли это также, что если я буду использовать равные точки для реконструкции WENO / ENO (используя многочлены Лагранжа), то в гладкой области я получу ошибки? (ну, это только гипотетические вопросы (для моего понимания), на самом деле не разумно восстанавливать полином порядка 15 или выше для схемы WENO)

Дополнительные детали:

Функция приблизительная:

x[-1,1]f(x)=cos(π2 x) ,x[1,1]

x делится на равнораспределенных (и позже LG) точек. Функция интерполируется каждый раз по 101 точке.N

Полученные результаты:

  1. а) равноотстоящие точки (интерполяция для ): N=65

введите описание изображения здесь

  1. б) равноотстоящие точки (график ошибок, логарифмическая шкала):

введите описание изображения здесь

  1. а) Точки LG (интерполяция для ): N=65введите описание изображения здесь

  2. б) Точки LG (график ошибок, логарифмическая шкала):

введите описание изображения здесь

Subodh
источник

Ответы:

26

Проблема с равноотстоящими точками состоит в том, что ошибка интерполяции является полиномом, т.е.

f(x)Pn(x)=f(n+1)(ξ)(n+1)!i=0n(xxi),ξ[x0,xn]

ведет себя по-разному для разных наборов узлов . В случае равноотстоящих точек этот многочлен взрывается по краям.xi

Если вы используете точки Гаусса-Лежандра, многочлен ошибки ведет себя значительно лучше, то есть он не взрывается по краям. Если вы используете чебышевские узлы , это полиномиальное равноосцилляция, и ошибка интерполяции минимальна.

Pedro
источник
6
Существует довольно подробное объяснение в книге Джона П. Бойда Чебышева и «Спектральные методы Фурье», где полиномиальная ошибка интерполяции Педро также легко объяснена (Глава 4.2, стр. 85).
Борт
Спасибо. Также константа Лебега для вышеупомянутых выборов ведет себя по-разному. Для равноотстоящих точек постоянная Лебега экспоненциально возрастает, тогда как для LG, LGL, Чебышева она как бы насыщается с ростом n. en.wikipedia.org/wiki/Lebesgue_constant_(interpolation) , ami.ektf.hu/uploads/papers/finalpdf/AMI_33_from109to123.pdf , но вопрос относительно численной реализации по-прежнему остается ...
Subodh
Извините, я мало что знаю о ENO / WENO. Но я не ожидаю проблем в гладкой области для интерполяции низкого порядка, хотя квадратурные узлы, безусловно, являются лучшим выбором по понятным причинам.
Борт
22

Это действительно интересный вопрос, и есть много возможных объяснений. Если мы пытаемся использовать полиномиальную интерполяцию, то обратите внимание, что полином удовлетворяет следующему раздражающему неравенству

Учитывая полином степени, не превосходящей N, имеемPN

|P(x)|N1x2maxx|P(x)|

за каждый . Это известно как неравенство Бернштейна , обратите внимание на особенность в этом неравенстве. Это может быть ограничено неравенством Марковаx(1,1)

maxx|P(x)|N2maxx|P(x)|

и обратите внимание , что это острый в том смысле , что Chebysehv полиномы сделать это уравнение. Другими словами, у нас есть следующая объединенная граница.

|P(x)|min(N1x2,N2)maxx|P(x)|

Что это означает: градиенты многочленов растут линейно в своем порядке везде, кроме небольших окрестностей границ интервалов. На границах они становятся больше похожими на . Не случайно все стабильные интерполяционные узлы имеют кластеризацию вблизи границ. Кластеризация необходима для управления градиентами базиса, в то время как вблизи средней точки можно быть немного более расслабленным. 1 / N 2N21/N2

Однако оказывается, что это не обязательно явление полинома, я предлагаю следующую статью:

http://math.la.asu.edu/~platte/pub/prevised.pdf

Он говорит свободно: если у вас одинаковая степень аппроксимации полиномиального базиса, то вы не можете использовать одинаково расположенные точки стабильно.

Reid.Atcheson
источник
1

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

user14717
источник
конечно, но тогда ваш интерполант не будет глобально гладким (только для вашего примера)C2
GoHokies
@ GoHokies: компактно поддерживаемые сплайны могут быть сделаны настолько гладкими, насколько это необходимо с помощью итеративной свертки. Какой вариант использования для интерполяции? C
user14717
Честная оценка. («положение-скорость-ускорение») достаточно для большинства приложений. Вы можете захотеть для некоторых краевых задач, но не можете придумать ни одного общего случая использования выше этого. C2C4
GoHokies
1

Что именно происходит в случае равноотстоящих точек?

Почему увеличение в полиномиальном порядке приводит к увеличению ошибки после определенной точки?

Это похоже на феномен Рунге, когда с равноотстоящими узлами ошибка интерполяции стремится к бесконечности с увеличением степени полинома, то есть количества точек.

Один из корней этой проблемы можно найти в константе Лебега, как отмечено в комментарии @ Subodh к ответу @Pedro. Эта константа связывает интерполяцию с наилучшим приближением.


Некоторые обозначения

У нас есть функция для интерполяции по узлам . В лагранжевой интерполяции определены полиномы Лагранжа :fC([a,b])xk

Lk(x)=i=0,ijnxxixkxi

при этом определяется полином интерполяции по парам для легкой записиpnPn(xk,f(xk))(xk,fk)

pn(x)=k=0nfkLk(x)

Теперь рассмотрим возмущение данных, это может быть, например, округление, поэтому мы получили . При этом новый полином :f~kp~n

p~n(x)=k=0nf~kLk(x)

Оценки ошибок:

pn(x)p~n(x)=k=0n(fkf~k)Lk(x)

|pn(x)p~n(x)|k=0n|fkf~k||Lk(x)|(maxk|fkf~k|)k=0n|Lk(x)|

Теперь можно определить константу Лебега как:Λn

Λn=maxx[a,b]k=0n|Lk(x)|

При этом окончательные оценки:

||pnp~n||(maxk|fkf~k|)Λn

(примечание на полях, мы смотрим только norm также потому, что мы находимся над пространством конечной меры, поэтому )LL1

Из приведенного выше расчета мы получили, что :Λn

  • независимо от даты:
  • зависит только от распределения узлов;
  • показатель стабильности (чем он меньше, тем лучше).

Это также норма оператора интерполяции относительно норма.||||

Используя следующую теорему, мы получили оценку погрешности интерполяции с постоянной Лебега:

Пусть и как указано выше, имеем где - ошибка по полиному с наилучшим равномерным приближениемfpn

||fpn||(1+Λn)dn(f)
dn(f)=infqnPn||fqn||

Т.е., если мало, ошибка интерполяции находится недалеко от ошибки наилучшего равномерного приближения, и в теореме сравнивается ошибка интерполяции с наименьшей возможной ошибкой, которая является ошибкой наилучшего равномерного приближения.Λn

Для этого поведение интерполяции зависит от распределения узлов. Нижний предел для состоит в том, что при заданном распределении узлов существует константа такая, что: поэтому константа растет, но как она растет importan.Λnc

Λn2πlog(n)c

Для равноотстоящих узлов я пропустил некоторые детали, но мы видим, что рост экспоненциальный.

Λn2n+1enlog(n)

Для чебышевских узлов также здесь я опустил некоторые детали, есть более точные и сложные оценки. Смотрите [1] для более подробной информации. Обратите внимание, что узлы семейства Чебышевских имеют логарифмический рост, и, исходя из предыдущих оценок, это почти лучшее, что вы можете получить.

Λn2πlog(n)+4

Для других распределений узлов см., Например, таблицу 1 этой статьи .


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

Также эта открытая статья ([1])

Численное интерполяционное сравнение семи сеток для полинома на интервале для различных сравнений.

Мауро Ванзетто
источник
1

Хорошо знать о интерполантах Флоатера-Хормана, когда вам нужно (или вы хотите) работать с равноотстоящими точками .{xi}i=1n

Учитывая целое число с , пусть будет полиномиальным интерполантом . Тогда FH-интерполант функции в имеет видd0dnpi{xi,xi+d}f{xi}i=1n

rn(x):=i=0ndλi(x)pi(x)i=0ndλi(x)

с "функциями смешивания"

λi(x)=(1)i(xxi)(xxi+d)

Некоторые свойства этих интерполантов:

  • они являются барицентрическими рациональными интерполантами без реальных полюсов ;
  • достичь произвольных порядков аппроксимации для , независимо от распределения точек;f C d + 2 [ a , b ]O(hd+1)fCd+2[a,b]
  • чем-то похожи на сплайны тем, что они смешивают (локальные) полиномиальные интерполанты с , действующими как функции смешивания; λp0,pndλ
  • они воспроизводят многочлены степени не более (или если нечетно);д + 1 н - дdd+1nd
  • может быть написано в барицентрической форме (см. раздел 4 статьи Флоатера и Хорманна).

Предостережение emptor : Как и ожидалось (см. Статью, на которую ссылается @ Reid.Atcheson), увеличение быстро ухудшает условия процесса аппроксимации.d

Кляйн проделал довольно недавнюю работу по решению этой проблемы. Он изменил исходный подход Флоатера-Хормана, добавив новых значений данных, соответствующих точкам за пределами исходного интервала интерполяции построенного из плавного расширения вне используя только заданные данные . Этот «глобальный» набор данных затем интерполируется новой рациональной функцией FH и оценивается только внутри .[ a , b ] f [ a , b ] f 0 , f n r n + 2 d [ a , b ]2d [a,b]f[a,b]f0,fnrn+2d[a,b]

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

Библиотека Chebfun использует интерполяции FH при построении chebfunsиз равноотстоящих данных, как описано здесь .

Ссылки:

М. С. Флоатер и К. Хорманн, Барицентрическая рациональная интерполяция без полюсов и высоких скоростей аппроксимации, Numerische Mathematik 107 (2007).

Г. Клейн, Расширение семейства блоцентрических рациональных интерполантов Флоатера – Хормана, Математика вычислений , 82 (2011) - препринт

Л. Бос, С. Де Марчи, К. Хорманн, Г. Кляйн, О константе Лебега барицентрической рациональной интерполяции в равноотстоящих узлах, Нумер. Математика 121 (2012)

GoHokies
источник