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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Дискретное преобразование Фурье)
Строка 15: Строка 15:
Разложение имеет место когда функцию можно приблизить тригонометрическим многочленом следущего вида в заданных нам точках
Разложение имеет место когда функцию можно приблизить тригонометрическим многочленом следущего вида в заданных нам точках
-
<tex>S_N(x)=\sum_{k=0}^{N-1}a_k exp{2 \pi ikx}</tex>
+
<tex>S_N(x)=\sum_{k=0}^{N-1}a_k exp{2 \pi ikx} </tex>
Система функций <tex>\phi (x)=2\pi kx, 0\le k <N</tex> является ортогональной, на множестве точек <tex>x_j=j/N, 0\le j<N </tex> при том что <tex>(\phi_k,\phi_k)=N</tex>, таким образом разложение имеет место и коэффициенты <tex>a_k</tex> представляются в виде:
Система функций <tex>\phi (x)=2\pi kx, 0\le k <N</tex> является ортогональной, на множестве точек <tex>x_j=j/N, 0\le j<N </tex> при том что <tex>(\phi_k,\phi_k)=N</tex>, таким образом разложение имеет место и коэффициенты <tex>a_k</tex> представляются в виде:
Строка 25: Строка 25:
Часто используется следущий вид формул:
Часто используется следущий вид формул:
-
<tex> f(x_j)=\sum_{-N/2<k\le N/2}
+
<tex> f(x_j)=\sum_{-N/2<k\le N/2} a_k exp{2\pi ikx_j}, </tex> и это соответсвует интерполяции тригонометрическим многочленом
 +
<tex>S_N=\sum{-N/2<k\le N/2}a_k exp{2\pi i kx}</tex>, где коэффициенты <tex>a_k</tex> считаются по тем же формулам.
-
==Быстрое преобразование Фурье==
+
===Быстрое преобразование Фурье===
-
 
+
-
Если вычисления проводить по вышеприведенноым формулам, то на выполнения каждого из преобразований потребуется <tex>N^2</tex> арифметических операций (считаем, что <tex>\omega=exp{2\pi i/N}</tex> уже вычислены).
+
 +
Если вычисления проводить по вышеприведенноым формулам, то на выполнения каждого из преобразований потребуется <tex>N^2</tex> арифметических операций (считаем, что <tex>\omega=exp{2\pi i/N}</tex> уже вычислены). Если N не является простым числом, то количество операций можно значительно сократить, используя быстрое преобразование Фурье.
==Постановка задачи==
==Постановка задачи==

Версия 18:47, 18 октября 2008

Содержание

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

В прикладных задачах часто используются различные преобразования Фурье функций непрерывного аргументся, а также представлений функций с помощью сходящихся тригонометрических рядов. Всякую непрерывно дифференцируемую фцнкцию 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}

Таким образом, ищется приближение функции тригонометрическими полиномами в смысле Фурье.

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

Погрешность вычислений

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

Список литературы