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

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

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

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

Содержание

1 Дискретное преобразование Фурье
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 не является простым числом, то количество операций можно значительно сократить, используя быстрое преобразование Фурье.