Тригонометрическая интерполяция
Материал из 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> уже вычислены). Если N не является простым числом, то количество операций можно значительно сократить, используя быстрое преобразование Фурье. | ||
==Постановка задачи== | ==Постановка задачи== | ||
Версия 18:47, 18 октября 2008
Содержание |
Дискретное преобразование Фурье
В прикладных задачах часто используются различные преобразования Фурье функций непрерывного аргументся, а также представлений функций с помощью сходящихся тригонометрических рядов.
Всякую непрерывно дифференцируемую фцнкцию можно разложить в ряд Фурье:
коэффициенты находятся по следущим формулам
Но как правила функция задана только в некоторых точках или у нас есть возможность узнать ее значения только в некотором конечном числе точек. Допустим, .В этом случае аналогом функции непрервной интерполяции функции будет дискретный вариант:
Разложение имеет место когда функцию можно приблизить тригонометрическим многочленом следущего вида в заданных нам точках
Система функций является ортогональной, на множестве точек
при том что
, таким образом разложение имеет место и коэффициенты
представляются в виде:
Далее для удобства записи будем использовать
Часто используется следущий вид формул:
и это соответсвует интерполяции тригонометрическим многочленом
, где коэффициенты
считаются по тем же формулам.
Быстрое преобразование Фурье
Если вычисления проводить по вышеприведенноым формулам, то на выполнения каждого из преобразований потребуется арифметических операций (считаем, что
уже вычислены). Если N не является простым числом, то количество операций можно значительно сократить, используя быстрое преобразование Фурье.
Постановка задачи
Интерполирование функции — приближенное или нахождение точной величины по известным значениям функции в конечном числе точек. В случае тригонометрической интерполяции аппроксимирующая функция ищется в виде
Таким образом, ищется приближение функции тригонометрическими полиномами в смысле Фурье.
Потребность в подобной интерполяции возникает в случае, когда приближаемая функция по своей природе предполагается периодической с известным периодом, например 2π.
