Тригонометрическая интерполяция
Материал из MachineLearning.
(→Дискретное преобразование Фурье) |
|||
| Строка 20: | Строка 20: | ||
<tex>a_k=\frac{1}{N} \sum_{l=0}^{N-1} f(x_l)exp{-2\pi ikx_l}, 0\le k<N</tex> | <tex>a_k=\frac{1}{N} \sum_{l=0}^{N-1} f(x_l)exp{-2\pi ikx_l}, 0\le k<N</tex> | ||
| + | |||
| + | Далее для удобства записи будем использовать <tex>\omega=exp{2\pi i/N}</tex> | ||
| + | |||
| + | Часто используется следущий вид формул: | ||
| + | |||
| + | <tex> f(x_j)=\sum_{-N/2<k\le N/2} | ||
| + | |||
| + | |||
| + | |||
| + | ==Быстрое преобразование Фурье== | ||
| + | |||
| + | Если вычисления проводить по вышеприведенноым формулам, то на выполнения каждого из преобразований потребуется <tex>N^2</tex> арифметических операций (считаем, что <tex>\omega=exp{2\pi i/N}</tex> уже вычислены). | ||
| + | |||
==Постановка задачи== | ==Постановка задачи== | ||
Версия 18:10, 18 октября 2008
Содержание |
Дискретное преобразование Фурье
В прикладных задачах часто используются различные преобразования Фурье функций непрерывного аргументся, а также представлений функций с помощью сходящихся тригонометрических рядов.
Всякую непрерывно дифференцируемую фцнкцию можно разложить в ряд Фурье:
коэффициенты находятся по следущим формулам
Но как правила функция задана только в некоторых точках или у нас есть возможность узнать ее значения только в некотором конечном числе точек. Допустим, .В этом случае аналогом функции непрервной интерполяции функции будет дискретный вариант:
Разложение имеет место когда функцию можно приблизить тригонометрическим многочленом следущего вида в заданных нам точках
Система функций является ортогональной, на множестве точек
при том что
, таким образом разложение имеет место и коэффициенты
представляются в виде:
Далее для удобства записи будем использовать
Часто используется следущий вид формул:
арифметических операций (считаем, что
уже вычислены).
Постановка задачи
Интерполирование функции — приближенное или нахождение точной величины по известным значениям функции в конечном числе точек. В случае тригонометрической интерполяции аппроксимирующая функция ищется в виде
Таким образом, ищется приближение функции тригонометрическими полиномами в смысле Фурье.
Потребность в подобной интерполяции возникает в случае, когда приближаемая функция по своей природе предполагается периодической с известным периодом, например 2π.
