2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Аппроксимация многочленами Чебышёва
Сообщение21.07.2011, 05:12 
Аватара пользователя
Здравствуйте!

Пытаюсь разобраться с сабжем на примере разложения $e^x$ на [-1;1], до многочлена 2 степени.
Нахожу коэффициенты разложение $y=a_2T_2 + a_1T_1+a_0T_0$ по формулам:
$$a_0 = \frac{1}{\pi}\int_{{-}1}^1 e^x\,\frac{dx}{\sqrt{1-x^2}},\quad a_n = \frac{2}{\pi}\int_{{-}1}^1 e^xT_n(x)\,\frac{dx}{\sqrt{1-x^2}}$$
И получаю
$$y = 0.2715T_2(x) + 1.1303T_1(x) + 1.2661T_0(x) = 0.5430\,x^2+1.1303\,x+0.9946$$
По графику абсолютной разницы между многочленом и экспонентой максимальное отклонение находится в точке x=1 и равно 0.0504. Но график выглядит как-то не так.

Потом беру алгоритм Ремеза и через несколько шагов нахожу такую параболу: $y = 0.5540\,x^2+1.1302\,x+0.9890$, и максимальное отклонение равно 0.0450. И график модуля разницы выглядит уже более убедительно (пики одной высоты).

Почему же результат по формулам Фурье даёт более плохое приближение?

 
 
 
 Re: Аппроксимация многочленами Чебышёва
Сообщение21.07.2011, 09:42 
Потому что разложение Фурье и наилучшее равномерное приближение - это две разные задачи с разными целями и ответами. И первые несколько членов ряда Фурье не обязаны давать наилучш. равномерное приближение.

 
 
 
 Re: Аппроксимация многочленами Чебышёва
Сообщение21.07.2011, 11:34 
Аватара пользователя
Я думал, что в этом случае ситуация такая же, как когда мы ищем лучшую аппроксимацию в смысле квадратичного отклонения. Если составить интеграл этого отклонения $\int\left(f(x)-P_n(x)\right)^2\,dx$ и найти при каких коэффициентах $P_n(x)$ он достигает экстремума, то результат будет такой же, как если по формулам Фурье находить разложение по многочленам Лежандра. :roll:

 
 
 
 Re: Аппроксимация многочленами Чебышёва
Сообщение21.07.2011, 14:24 
Если Вас интересует квадратиченое отклонение - зачем Вы смотрите на максимум модуля разности отклонения? Разные нормы дают разные аппроксимации. В общем - определитесь, что Вы хотите получить - и все получится.

 
 
 
 Re: Аппроксимация многочленами Чебышёва
Сообщение21.07.2011, 14:57 
kirasole в сообщении #470111 писал(а):
Почему же результат по формулам Фурье даёт более плохое приближение?

Ряд Фурье действительно не предназначен для получения наилучшего равномерного приближения. Но если этот ряд -- по многочленам Чебышёва, то он даёт приближение, близкое к наилучшему. Конкретно у Вас: даже для параболы значения погрешности в точках "квазиальтернанса" -- это

Код:
       -0.039363
        0.041762
       -0.047271
        0.050402


Качество приближения (отношение максимального выброса к минимальному): $ 0.050402 / 0.039363 = 1.280432$. Согласно теореме Валле-Пуссена это означает, что уменьшить погрешность (уточнением альтернанса, скажем, по методу Ремеза) более чем на 28% уж точно невозможно; скорее же всего, не улучшишь даже более чем на 14%. А, скажем, для многочлена 10-й степени, для которого аналогичное отношение равно $1.08675$, идеальный альтернанс даст уточнение не более чем на 4 - 5 процентов, что вряд ли имеет практическое значение.

Причина подобного поведения в том, что коэффициенты ряда Фурье очень быстро убывают (как геометрическая прогрессия или даже быстрее):

Код:
  k     c_k

0   1.26606
1   1.13031
2   2.71495 e-1
3   4.43368 e-2
4   5.47424 e-3
5   5.42926 e-4
6   4.49773 e-5
7   3.19843 e-6
8   1.99212 e-7
9   1.10367 e-8
10   5.50589 e-10
11   2.49795 e-11
12   1.03900 e-12
13   3.98175 e-14
14   1.40708 e-15

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

 
 
 
 Re: Аппроксимация многочленами Чебышёва
Сообщение21.07.2011, 15:18 
Аватара пользователя
alex1910
я довольно подробно описал, чтó хочу получить, боюсь, Вы невнимательно прочитали.

ewert
я имел в виду, конечно, обобщённый ряд Фурье — по многочленам Чебышёва.
Но Вы ответили на мой вопрос! Большое спасибо :)

(Оффтоп)

Как Вы так ловко посчитали коэффициенты Фурье? :)

 
 
 
 Re: Аппроксимация многочленами Чебышёва
Сообщение21.07.2011, 15:34 

(Оффтоп)

kirasole в сообщении #470250 писал(а):
Как Вы так ловко посчитали коэффициенты Фурье? :)

Тупо: $c_k=\frac{2}{\pi}\int\limits_0^{\pi}f\big(\frac{a+b}{2}+\frac{b-a}{2}\,\cos t\big)\,\cos(kt)\,dt,$ запрограммировал на коленке формулу Симпсона для этого интеграла и проитерировал её до сходимости.

 
 
 
 Re: Аппроксимация многочленами Чебышёва
Сообщение21.07.2011, 19:58 
Аватара пользователя
kirasole в сообщении #470154 писал(а):
Я думал, что в этом случае ситуация такая же, как когда мы ищем лучшую аппроксимацию в смысле квадратичного отклонения. Если составить интеграл этого отклонения $\int\left(f(x)-P_n(x)\right)^2\,dx$ и найти при каких коэффициентах $P_n(x)$ он достигает экстремума, то результат будет такой же, как если по формулам Фурье находить разложение по многочленам Лежандра. :roll:

Тут дело в том, что Чебышевское приближение (точнее равномерная норма) не определяется никаким скалярным произведением, и это можно доказать с помощью равенства параллелограмма (точнее, его невыполнимостью). Отсюда невозможность применения рядов Фурье.

 
 
 
 Re: Аппроксимация многочленами Чебышёва
Сообщение21.07.2011, 20:30 

(Оффтоп)

мат-ламер в сообщении #470334 писал(а):
Отсюда невозможность применения рядов Фурье.

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

 
 
 
 Re: Аппроксимация многочленами Чебышёва
Сообщение22.07.2011, 01:21 
Аватара пользователя
мат-ламер
О, спасибо, это очень интересная деталь!

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group