Временные ряды. Обработка данных и теория. - Бриллинджер Д.Р.
Скачать (прямая ссылка):
к sin—(X-(O^
и у этого преобразования большая амплитуда при Х = о)Л±2я/, / = 0, ±1, ... .
Пример 4 (моном). Допустим X(t) = tk, ^ = 0, ±1, ... , где k — натуральное число. Тогда (3.4.10) примет вид
2 **ехр{— Ш} = (0~*
t=-n
ах*"
sin(*+?)
sin у X
(3.4.14)
Это выражение ведет себя подобно производной преобразования, рассмотренного в примере 1. Заметим, что при больших п наше преобразование сконцентрировано в окрестности Х = 0, ±2я,
Полином 2*а^Л будет вести себя как линейная комбинация функций вида (3.4.14).
Пример 5 (колебание с мономиальной амплитудой). Положим X(t) = tkехр тогда (3.4.10) обращается в
? ^ ехр {-i (X-(O) 0 = ї-*-^
sin
sin -^-(Я —со)
, (3.4.15)
т. е. в рассмотренную выше функцию примера 4, сдвинутую по частоте на величину оз.
Общее содержание этих примеров таково: в случае, когда X(O — постоянная или медленно меняющаяся по t функция, амплитуда ее преобразования Фурье сосредоточена вблизи точек X = O, ±2я, .... Если X (0— гармоническое колебание частоты со или гармоническое колебание частоты (со), умноженное на поли-
ном ио tу то ее преобразование Фурье сосредоточено в окрестности X = со, со ± 2я, ....
Преобразование (3.4.2) можно обратить с помощью интегрирования:
X(O = (2Ji)-1JeXp(MJd^ (l)dK *=0.....Г—1. (3.4.16)
о
С другой стороны, обратное преобразование получается и суммированием:
X(O = ^-1S , * = 0, ... , Г-1. (3.4.17)
Набор T векторов dlP(2ns/T), s==0, \.. ,Г—1, размерности г иногда называют дискретным преобразованием Фурье функции Х(/)> / = 0, . ..,Т—1. В следующих двух параграфах мы рассмотрим способы его вычисления, а также ряд его свойств.
Дискретное преобразование Фурье можно представить в матричной форме. Пусть Ж обозначает гх'Т-матрицу со столбцами X (0), ..., X (T- 1), расположенными в таком порядке, и пусть SD обозначает г X Т-матрицу со столбцами d(P(2ns/T), s=0, ..., T—1. Пусть также $ есть Tx Т-матрица с элементами ехр {—і (2nst/T)\ в (s+ 1)-й строке и (t+l)-M столбце при sy t = Q, ..., Г— 1. Тогда нетрудно видеть, что
= (3.4.18)
В случаях 7==1,2,3,4 получаются соответственно следующие матрицы:
[
¦¦і і
"1 1 1 —і 1 -1
.1 і
[1].
1
2
1
—1 1
—1
і
-T-i
1" і
-1 -і J
2 V3
(3.4.19) (3.4.20)
(3.4.21)
Общее исследование дискретного и конечного преобразований Фурье проводится в работах: Stumpff (1937), Whittaker, Robinson (1944), Schoenberg (1950), Cooley, Lewis, Welch (1967). Дальнейшие сведения даны в упражнениях к этой главе.
3.5. Быстрое преобразование Фурье
Для построения интересующих нас статистик в этой книге применяется, главным образом, дискретное преобразование Фурье. Поэтому важно уметь быстро вычислять дискретное преобразование Фурье данного набора чисел X(t), O^ t<!Т—1.
Заметим, что если вычислять это преобразование по формуле
йТ(Щ=Т?ехр{-{Щх(», i = 0, ...,T-I1 (3.5.1)
т. е. по определению, то требуется произвести Т? операций умножения комплексных чисел. В случае когда Т —составное число (произведение нескольких целых чисел), был предложен ряд простых процедур, сокращающих необходимое число умножений [Cooley и др. (1967)]. Недавно появились формальные алгоритмы, сокращающие число умножений почти до минимума [Good (1958), Cooley, Tukey (1965), Gentleman, Sande (1966), Cooley и др. (1967), Bergland (1967), Bingham и др. (1967), Brigham, Morrow (1967)]. О формулировках в терминах композиционных рядов конечной группы см. Posner (1968), Cairns (1971).
Укажем вначале вид алгоритма быстрого преобразования Фурье в двух элементарных случаях. "Идея этих алгоритмов — сократить число операций при преобразовании длинного ряда наблюдений, сводя задачу к последовательному вычислению преобразований Фурье более коротких наборов данных.
Теорема 3.5.1. Пусть T = T1T2, где T1 и T2-целые числа; тогда
7*1-1
d$> (2JiT-1 [J1T2 + /2]) = S ехР {- Я*ТГ1Ш ехр {- 12JiT-1Ut1)
Z1 = O T —\
X S ехр {—12XTi1UU) X & +
*2=0
(3.5.2)
0</і<7\-1, 0</2<T2 — 1.
Заметим, что J1T2-^j2 пробегает все целые значения /, /«S T-I при 0< Z1 < T1 — 1 и 0 < Z2S^r2-I. Заметим так-
же, что требуется (T1+ T2) T1T2 умножений комплексных чисел для вычисления дискретных преобразований Фурье порядков T1 и T2B формуле (3.5.2). Некоторое определенное число дополнительных операций будет затрачено на введение множителей ехр{—12JtJr-1JVi}.
Другой алгоритм дается следующей теоремой, в которой X(t) обозначает периодическое продолжение ^ X (0), ..., X (T — 1), с периодом Т.
Теорема 3.5.2. Пусть T = T1T2, где T1 и T2 взаимно простые числа. Тогда для J = J1 (HiOdT1), /=/2(modT2), 0 ^ Z1^T1-I, О ^ j2 ^ T2 —-1, имеем
T — 1 T — 1
dT (2UT-1J)= S ? ехр {-12Ti(T1-H1J1 + ТД,-)}
X X (tj2 + I2T1). (3.5.3)
Отметим, что необходимое число умножений комплексных чисел опять равно (T1 + T2) T1T2. Здесь для каждого / мы должны определить Z1 и /2, фигурирующие выше, и подсчитать соответствующий коэффициент Фурье. При этом отсутствуют члены вида ехр{—/2JtT-1Z2^1}, входящие в (3.5.2), и результирующее выражение симметрично по T1 и T2. Good (1971) сравнил эти два алгоритма быстрого преобразования Фурье.
