Тригонометрическая интерполяция
Материал из MachineLearning.
(→Дискретное преобразование Фурье) |
|||
Строка 26: | Строка 26: | ||
<tex> f(x_j)=\sum_{-N/2<k\le N/2} a_k exp{2\pi ikx_j}, </tex> и это соответсвует интерполяции тригонометрическим многочленом | <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>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 не является простым числом, то количество операций можно значительно сократить, используя [[быстрое преобразование Фурье]]. | Если вычисления проводить по вышеприведенноым формулам, то на выполнения каждого из преобразований потребуется <tex>N^2</tex> арифметических операций (считаем, что <tex>\omega=exp{2\pi i/N}</tex> уже вычислены). Если N не является простым числом, то количество операций можно значительно сократить, используя [[быстрое преобразование Фурье]]. | ||
Строка 36: | Строка 39: | ||
<tex>\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}</tex> | <tex>\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}</tex> | ||
- | Будем искать приближение функции f(x). Пусть известно значения <tex>(\frac{2\pi j}{2n+1})=y_i</tex> при <tex>j\in \{-n,-n+1,\dots,0,1,\dots n\}</tex> | + | Будем искать приближение функции f(x). Пусть известно значения <tex>f(\frac{2\pi j}{2n+1})=y_i</tex> при <tex>j\in \{-n,-n+1,\dots,0,1,\dots n\}</tex> |
Тогда по формулам изложенным выше можно получить | Тогда по формулам изложенным выше можно получить | ||
Строка 43: | Строка 46: | ||
==Погрешность вычислений== | ==Погрешность вычислений== | ||
- | |||
- | |||
==Список литературы== | ==Список литературы== |
Версия 10:17, 19 октября 2008
Содержание |
Дискретное преобразование Фурье
В прикладных задачах часто используются различные преобразования Фурье функций непрерывного аргументся, а также представлений функций с помощью сходящихся тригонометрических рядов. Всякую непрерывно дифференцируемую фцнкцию можно разложить в ряд Фурье:
коэффициенты находятся по следущим формулам
Но как правила функция задана только в некоторых точках или у нас есть возможность узнать ее значения только в некотором конечном числе точек. Допустим, .В этом случае аналогом функции непрервной интерполяции функции будет дискретный вариант:
Разложение имеет место когда функцию можно приблизить тригонометрическим многочленом следущего вида в заданных нам точках
Система функций является ортогональной, на множестве точек при том что , таким образом разложение имеет место и коэффициенты представляются в виде:
Далее для удобства записи будем использовать
Часто используется следущий вид формул:
и это соответсвует интерполяции тригонометрическим многочленом
,
где коэффициенты считаются по тем же формулам.
Если вычисления проводить по вышеприведенноым формулам, то на выполнения каждого из преобразований потребуется арифметических операций (считаем, что уже вычислены). Если N не является простым числом, то количество операций можно значительно сократить, используя быстрое преобразование Фурье.
Пример использования
Рассмотрим применение тригонметрической интерполяции. Будем использовать для приблежения следущий тригонометрический полином:
Будем искать приближение функции f(x). Пусть известно значения при
Тогда по формулам изложенным выше можно получить