Тригонометрическая интерполяция

Материал из MachineLearning.

Версия от 19:15, 20 октября 2008; Alina (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Дискретное преобразование Фурье
2 Пример использования
- 2.1 Тригонометрическая функция с шумом
- 2.2 Кусочно-заданная функция, не тригонометрическая
3 Погрешность вычислений
4 Список литературы
5 См. также

Дискретное преобразование Фурье

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

$f(x)=\sum_{k=-\infty}^{\infty} \alpha_k exp{2\pi i k x}$

коэффициенты $\alpha_k$ находятся по следующим формулам

$\alpha_k=\int \limits_{0}^{1} f(x) exp {-2 \pi i k x} dx$

Но как правила функция задана только в некоторых точках или у нас есть возможность узнать её значения только в некотором конечном числе точек. Допустим, $x_j=j/N, j=0,1,\dots,N-1$ .В этом случае аналогом функции непрерывной интерполяции функции будет дискретный вариант:

$f(x_j)=\sum_{k=0}^{N-1} \alpha_k exp{2\pi ikx_j}, 0\le j<N$

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

$S_N(x)=\sum_{k=0}^{N-1}a_k exp{2 \pi ikx}$

Система функций $\phi (x)=2\pi kx, 0\le k <N$ является ортогональной, на множестве точек $x_j=j/N, 0\le j<N$ при том что $(\phi_k,\phi_k)=N$ , таким образом разложение имеет место и коэффициенты $a_k$ представляются в виде:

$a_k=\frac{1}{N} \sum_{l=0}^{N-1} f(x_l)exp{-2\pi ikx_l}, 0\le k<N$

Далее для удобства записи будем использовать $\omega=exp{2\pi i/N}$

Часто используется следующий вид формул:

$f(x_j)=\sum_{-N/2<k\le N/2} a_k exp{2\pi ikx_j},$ и это соответствует интерполяции тригонометрическим многочленом

$S_N=\sum_{-N/2<k\le N/2}a_k exp{2\pi i kx}$ ,

где коэффициенты $a_k$ считаются по тем же формулам.

Если вычисления проводить по вышеприведённым формулам, то на выполнения каждого из преобразований потребуется $N^2$ арифметических операций (считаем, что $\omega=exp{2\pi i/N}$ уже вычислены). Если N не является простым числом, то количество операций можно значительно сократить, используя быстрое преобразование Фурье.

Пример использования

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

$\begin{matrix} F_n(x)=a_0 & + & a_1 \cos x + a_2 \cos 2x+\dots + a_n \cos nx + \\ \ &+&b_1 \sin x + b_2 \sin 2x+\dots + b_n \sin nx . \end{matrix}$

Будем искать приближение функции f(x). Пусть известно значения $f(\frac{2\pi j}{2n+1})=y_i$ при $j\in \{-n,-n+1,\dots,0,1,\dots n\}$

Тогда по формулам изложенным выше можно получить $a_m= \frac{2}{2n+1} \sum_{j=-n}^n y_j \cos \left( \frac{2\pi jm}{2n+1} \right),\quad b_m= \frac{2}{2n+1} \sum_{j=-n}^n y_j \sin \left(\frac{2\pi jm}{2n+1} \right)$

Если интерполировать тригонометические функции и выбирать правильное число узлов, то погрешность приближается к нулю. Интересно рассмотреть функции, не являющиеся тригонометрическими, но обладающие периодом. Рассмотрим ряд вычислений приближенных функций с помощью программы, использующей выше изложенный алгоритм апроксимации. На вход подается функция и количество точек на промежутке $[-\pi;\pi]$ , точки по умолчанию расположены равномерно на промежутке. Как будет показано ниже, это соответсвует наилучшей аппроксимации.

Тригонометрическая функция с шумом

На вход подавалась функция $sin(5*x)+cos(x)+rand()$ , (пусть под 'rand()' понимается некоторая шумовая функция). Вычислияем значение функции в 5 точках. По графику ('Рис.1')видно, что аппроксимация произвендена достаточно точно.

Рис.1

Выход : коэффициенты $a_n, b_n$ , чтоб можно было восстановить многочлен с помощью других вычислительных инструментов. Также ряд значений функции на промежутке $[-\pi,\pi]$ . Количество точек запрашивается у пользователя.

Кусочно-заданная функция, не тригонометрическая

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

Рис.2

На вход программе подавалась кусочно-заданная функция $\pi<x<-1.5 y=1, -1.5<x<1.6 y=0, 1.6<x<\pi <tex>, функция подразумевается периодической с периодом <tex>\pi$ . Для вычисления полинома бралось 25 точек. На Рис.2 приведен график функциии и график интерполирующего полинома. На Рис.4 приведен график ошибки интерполяции.