Пример непрерывной функции, которую трудно аппроксимировать полиномами

16

В учебных целях мне понадобится непрерывная функция от одной переменной, которую «трудно» аппроксимировать полиномами, то есть, для степенного ряда достаточно сильных степеней, чтобы «соответствовать» этой функции. Я намерен показать своим ученикам «пределы» того, что может быть достигнуто с помощью степенных рядов.

Я думал о том, чтобы придумать что-то «шумное», но вместо того, чтобы катиться по своему усмотрению, мне просто интересно, существует ли какая-то стандартная «сложная функция», которую люди используют для тестирования алгоритмов аппроксимации / интерполяции, в некоторой степени аналогично тем функциям тестирования оптимизации, которые имеют многочисленные локальные минимумы, где наивные алгоритмы легко застревают.

Извиняюсь, если этот вопрос не правильно сформулирован; пожалуйста, помилуй нематематика.

Ларикс Децидуа
источник

Ответы:

14

Почему бы просто не показать функцию абсолютного значения?

Аппроксимация, например, с использованием полиномиального расширения Лежандра, работает довольно плохо :

Последовательное приближение функции абсолютного значения полиномами

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

leftaroundabout
источник
Вы можете интерполировать | x | используя чебышевскую интерполяцию, см. nbviewer.jupyter.org/github/cpraveen/na/blob/master/…, которая сходится довольно быстро. Например, вы можете изменить N = 2 * i в коде на N = 15 + i и проверить большую степень. Это не метод расширения, но все еще основанный на полиномах.
cpraveen
@PraveenChandrashekar Чебышев работает «лучше», потому что он придает больший вес внешним частям интервала, где функция гладкая. Таким образом, чрезмерное колебание избегается, но говорить, что оно лучше приближает функцию, сомнительно - оно, в частности, фиксирует резкий поворот при даже хуже, чем равномерно-дискретные точки или минимизация L 2 . Если ваша цель - избежать высокочастотных компонентов, лучше использовать интегральное преобразование, которое должным образом демпфирует эти компоненты. x=0L2
оставлено около
Хорошо иметь неоднородные точки, как в чебышевской интерполяции. Со степенью около 20 это дает гораздо более точное приближение, чем Legendre, которое вы показываете в своем посте. Измерьте ошибки, чтобы быть более количественным. Также можно сделать аппроксимацию чебышевского ряда для | x | что точнее, чем расширение Лежандра.
cpraveen
@PraveenChandrashekar, суть в том, что полиномы в принципе не способны аппроксимировать такую ​​функцию, как должным образом. Существуют различные методы, каждый из которых дает более или менее впечатляющий результат, но ни один из них не работает хорошо в том смысле, что «только несколько терминов дают то, что можно принять за исходную функцию». Если вы должны использовать полиномы, вам нужно подумать, какие виды ошибок более проблематичны, у Legendre и Chebyshev есть свои варианты использования, но нет серебряной пули. В конечном счете, подход, например, со сплайнами, обычно более эффективен. x|x|
оставлено около
Мы знаем, что не существует идеального метода. Вопрос в том, какие функции трудно аппроксимировать полиномам. Таким образом, нужно увидеть все возможные методы с использованием полиномов, чтобы сделать вывод, что ни один из них не делает хорошую работу. Лежандр не лучший способ приблизить | x | и, следовательно, создается довольно ложное впечатление, что многочлены слишком плохи для | x |. С Чебышевым у вас есть сходимость и гораздо лучшие приближения, чем у Лежандра, они колеблются не так сильно, как у Лежандра, хотя и сходятся медленно около x = 0, где функция недостаточно гладкая.
cpraveen
10

|x|

Вольфганг Бангерт
источник
Спасибо, это именно то, что я имел в виду под «я думал о чем-то« шумном »». Очень хороший пример ИМО.
Ларикс Децидуа
6

Аппроксимация усложняется не только аппроксимируемой функцией, но и интервалом, в котором аппроксимация должна быть «подходящей». И вы должны определить меру для «хорошего соответствия», то есть, какую максимальную (абсолютную или относительную) ошибку вы хотите допустить?

exp(x)[0,10]sin(x)[0,2π]введите описание изображения здесьвведите описание изображения здесь

GertVdE
источник
Я показываю такие примеры в своем курсе, чтобы подчеркнуть, что разложение Тейлора не является хорошим методом для приближения функций.
cpraveen
6

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

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

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

|x|x=0

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

[1] https://people.maths.ox.ac.uk/trefethen/mythspaper.pdf

[2] http://www.chebfun.org

cpraveen
источник
+1 за ссылку на «статью о мифах» Ллойда Трефетена, очень хороший обзор темы IMO, спасибо.
Ларикс Децидуа
2

е(Икс)знак равно1Икс2+1

1Икс2+1знак равно1-Икс2+Икс4-Икс6+Икс8-Икс10+Икс12-...

Это сходится для -1<Икс<1, но это расходится повсюду. Полиномиальное приближение вокругИксзнак равно0 никогда не даст вам правильного ответа Иксзнак равно2,

Кристофер Уэллс
источник
0

Yзнак равноsяN(Икс)? Периодические функции должны быть трудно аппроксимировать с использованием полиномов, если только нет возможности ограничить полиномы конечными интервалами.

Анируддха Ачарья
источник
Или даже Yзнак равногрех(1Икс)если вы хотите разозлиться вокруг происхождения.
sfmiller940