Материал: Фарфоровская Ю. Б. Математика. Дискретное и быстрое преобразование Фурье

Доказательство. Пусть α – вещественное число. Рассмотрим скалярное произведение вектора z + αw самого на себя:

A(α) = (z + αw, z + αw) = (z, z) + (αw, z) + (z, αw) + (αw, αw).

Так как α вещественно, его можно выносить из любого сомножителя. Поэтому

A( ) z 2 (w, z) (z, w) 2 w 2 . Но (w, z) (z, w) и (w, z) (z, w) 2 Re(z, w).

Значит, A(α) = |z|2 + 2α Re(z, w) + α2|w|2 ≥ 0. Так как квадратный трехчлен А(α) ≥ 0 при всех α, то его дискриминант ≤ 0, и поэтому [Re(z, w)]2 –

|z|2|w|2 ≤ 0,

Re(z1, w) = Re(ze–iφ, w)) = Re(e–iφ(z, w)) = Re(e–iφ reiφ) = Re(r) = r = |(z, w)|.

Получаем из (1.2):

|z||w|=|z1||w| ≥ |Re(z1, w)|=|(z, w)|,

и неравенство (1.1) доказано.

Два вектора в Сп называются ортогональными, если их скалярное произведение равно 0:

z w (z, w) 0 .

Базисом в Сп называется набор из п векторов, через которые можно выразить все остальные векторы, т. е. таких векторов, что любой другой вектор пространства является линейной комбинацией базисных векторов (векторы базиса обязательно линейно независимы). Коэффициенты этой линейной комбинации и называются координатами этого вектора в данном базисе. Базис – максимальный (по числу элементов) набор линейно независимых векторов. Базис называется ортогональным, если любые 2 вектора базиса ортогональны между собой (в этом случае линейная независимость базисных векторов выполняется автоматически). Базис называется ортонормальным (или декартовым), если он ортогонален и нормы всех его векторов равны 1. Число векторов в базисе равно п и это число п называется

6

размерностью пространства Сп. Стандартный базис в Сп – (скользящая единица):

е1 = {1, 0, …, 0},

е2 = {0, 1, …, 0},

………………

еn = {0, 0, …, 1}.

Заметим, что в пространстве последовательностей длины п элементы каждой последовательности являются соответствующими координатами в стандартном базисе.

Любой набор из п линейно независимых векторов пространства также образует базис. Если в пространстве есть 2 базиса: новый { e1 , e2 ,...,en } и

старый {е1, е2, …, еn}, то матрицей перехода от старого базиса к новому называется матрица п-го порядка, в столбцах которой стоят координаты новых базисных векторов в старом базисе. Если А – такая матрица, то обяза-

тельно detA ≠ 0, и следовательно, существует А–1 – матрица перехода от нового базиса к старому; поэтому в ее столбцах стоят координаты старых базисных векторов в новом базисе.

Если z = {z1, z2, …, zn} – координаты вектора z в старом базисе, а w – в новом, w = {w1, w2, …, wn}, то w = Az, z = A–1 w (в обоих равенствах и сле-

ва, и справа записаны столбцы).

Наряду со стандартным базисом (из скользящих единиц) рассмотрим новый базис (что он действительно базис, будет доказано позднее):

Таким образом,

Z0 = {1, 1,…,1},

…………………………………

7

Тогда матрица перехода F= fij in, j 1 от стандартного базиса к базису

Очевидно, что эта матрица симметрична, т. е. fij = fji. Кроме того, все элементы этой матрицы являются корнями п-ой степени из единицы, поэтому число различных элементов этой матрицы равно п и все эти числа находятся в ее второй строчке (кроме того, сумма элементов каждой строчки (кроме первой) равна нулю, что следует из доказанной далее леммы).

Докажем теперь что векторы Zj образуют ортогональный базис. Это доказательство основано на достаточно очевидном утверждении, которое мы оформим в виде леммы (оно нам понадобится и в дальнейшем).

Лемма. Пусть n, j, s натуральные числа. Рассмотрим сумму

только тогда, когда j – s делится на п. Поэтому при j s 0 и значит, q 1, по формуле для суммы членов геометрической прогрессии получаем

n 1

L 1 n .

k 0

Лемма доказана.

8

Следствие. Базис Zj, (j = 0, 1, 2, …, n – 1) ортогонален и длина каждого

его вектора равна n .

Действительно, вычислим скалярное произведение

По лемме при j ≠ s это скалярное произведение равно 0, и значит, базисные векторы попарно ортогональны. При j = s это скалярное произведе-

ние равно квадрату длины вектора Zj и, по лемме, равно п. Следствие доказано.

Отсюда следует, что этот базис можно сделать ортонормальным (разделив все координаты каждого вектора на n ). Такая процедура часто осуществляется в математических исследованиях, но в многочисленных приложениях ДПФ обычно этого не делают.

Докажем, что обратной матрицей к F является матрица F*, состоящая из комплексносопряженныхэлементовматрицыF, поделенныхнап, т. е.

В силу ортогональности все недиагональные элементы этой матрицы равны нулю, а на главной диагонали стоит число п, поэтому

9

где Е – единичная матрица. Это и значит, что матрица F* является обратной к матрице F.

Замечание. Напомним, что матрицей, сопряженной к матрице А, называется матрица A* для которой при любых элементах х и у справедливо ра-

венство (Ах, у) = (х, A*y). Легко доказать, что элементы a*ij сопряженной матрицы задаются формулой a*ij = a ji . Так как F симметрична, а матрица

nF* состоит из элементов, комплексно сопряженных к элементам матрицы F, то матрица nF* и является сопряженной к матрице F, и значит, для всех х и у справедливо равенство (Fx, y) = n(x, F*y).

Заметим, что F* равна 1n , умноженной на матрицу, у которой в показа-

телях степеней экспонент нет минусов. Кроме того, все элементы этой матрицы, как и у матрицы F, являются корнями п-ой степени из единицы, поэтому число различных элементов этой матрицы равно п. Теперь мы можем дать определения прямого и обратного преобразования Фурье.

Определение. Прямым дискретным преобразованием Фурье (ДПФ) вектора z = (z0, z1, z2, …, zn – 1) в п-мерном пространстве называется новый

вектор w = (w0, w1, w2,…,wn – 1) этого пространства, определяемый формулой w = Fz, т. е.

Таким образом, координаты вектора прямого преобразования Фурье определяются формулой

Это и есть общепринятые формулы прямого дискретного преобразования Фурье (прямого ДПФ). Вектор w = (w0, w1, …, wn) называют дискрет-

10