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

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

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

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

Содержание

1 Дискретное преобразование Фурье
2 Пример использования
- 2.1 1. Тригонометрическая функция с шумом
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]$ , точки по умолчанию расположены равномерно на промежутке. Как будет показано ниже, это соответсвует наилучшей аппроксимации.

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

Рис.1

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