УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу ТРИГОНОМЕТРИЧЕСКАЯ ИНТЕРПОЛЯЦИЯ


Матрица дискретного преобразования Фурье (ДПФ)

F=\left[ \varepsilon_j^{k} \right]_{j,k=0}^{n-1}= \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_1 & \varepsilon_1^2 & \dots & \varepsilon_1^{n-1} \\ 1 & \varepsilon_2 & \varepsilon_2^2 & \dots & \varepsilon_2^{n-1} \\ 1 & \varepsilon_3 & \varepsilon_3^2 & \dots & \varepsilon_3^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{n-1} & \varepsilon_{n-1}^{2} & \dots & \varepsilon_{n-1}^{n-1} \end{array} \right)_{n\times n} \quad npu \quad \varepsilon_j = \cos \frac{2 \pi j}{n} + {\mathbf i} \, \sin \frac{2 \pi j}{n}

корне n-й степени из 1. Основываясь на свойстве \varepsilon_j=\varepsilon_1^j, матрицу часто записывают в эквивалентном виде

F= \left[ \varepsilon^{jk} \right]_{j,k=0}^{n-1}= \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon & \varepsilon^2 & \dots & \varepsilon^{n-1} \\ 1 & \varepsilon^2 & \varepsilon^4 & \dots & \varepsilon^{2(n-1)} \\ 1 & \varepsilon^3 & \varepsilon^6 & \dots & \varepsilon^{3(n-1)} \\ \vdots & & & & \vdots \\ 1 & \varepsilon^{n-1} & \varepsilon^{2(n-1)} & \dots & \varepsilon^{(n-1)^2} \end{array} \right)_{n\times n} \quad npu \quad \varepsilon = \cos \frac{2 \pi}{n} + {\mathbf i} \, \sin \frac{2 \pi}{n} \ .
П

Пример. При n=4 матрица ДПФ:

F= \left( \begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 & \mathbf i & -1 & - \mathbf i \\ 1 & -1 & 1 & -1 \\ 1 & -\mathbf i & -1 & \mathbf i \end{array} \right) \ .

При n=8 ЗДЕСЬ.

Матрица ДПФ является симметричной: F=F^{\top}; она является частным случаем матрицы Вандермонда.

Т

Теорема 1. \det F = n^{n/2} {\mathbf i}^{n(n-1)/2+1} при n_{}четном, \det F = n^{n/2} {\mathbf i}^{n(n-1)/2} при n_{}нечетном.

Доказательство. С одной стороны, возведем матрицу F_{} в квадрат, результатом будет ганкелева матрица

F^2= \left(\begin{array}{lllll} h_0 & h_1 & h_2 & \dots & h_{n-1} \\ h_1 & h_2 & h_3 & \dots & h_n \\ h_2 & h_3 & h_4 & \dots & h_{n+1} \\ \vdots & & & & \vdots \\ h_{n-1} & h_{n} & h_{n+1} & \dots & h_{2n-2} \end{array} \right) \ npu \ h_j=1+\varepsilon_1^j+\varepsilon_2^j+\dots+\varepsilon_{n-1}^j=1+\varepsilon_j^1+\varepsilon_j^2+\dots+\varepsilon_j^{n-1}\ .

Теперь воспользуемся результатом, полученным ЗДЕСЬ:

h_j= \left\{ \begin{array}{ccc} n & npu & \varepsilon_j=1 , \\ 0 & npu & \varepsilon_j\ne 1 . \end{array} \right.

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

F^2= \left(\begin{array}{cccccc} n & 0 & 0 & \dots & 0 & 0 \\ 0 & 0 & 0 & \dots & 0 & n \\ 0 & 0 & 0 & \dots & n & 0 \\ \vdots & & & & & \vdots \\ 0 & n & 0 & \dots & 0 & 0 \end{array} \right)

и, на основании определения определителя, имеем

\det F^2 =(-1)^{(n-1)(n-2)/2}n^n \quad \Rightarrow \quad \det F \in \{\pm \mathbf i ^{(n-1)(n-2)/2} n^{n/2} \} .

Осталось только выбрать из двух полученных чисел одно истинное. Для этого рассмотрим \det F как определитель Вандермонда:

\det F = \prod_{0\le j <k \le n-1} ( \varepsilon^k-\varepsilon^j ) \ .

Положим

\varepsilon= \alpha^2 \quad npu \quad \alpha = \cos \frac{\pi}{n} + \mathbf i \sin \frac{\pi}{n} \ ,

получим

\det F =\prod_{0\le j <k \le n-1} \alpha^{k+j} ( \alpha^{k-j}-\alpha^{-(k-j)} ) = \prod_{0\le j <k \le n-1} \alpha^{k+j} \prod_{0\le j <k \le n-1} 2\mathbf i \sin \frac{(k-j)\pi}{n} \ .

Для рассматриваемых значений j и k имеем: 0 < k-j < n и, следовательно, \displaystyle \sin \frac{(k-j)\pi}{n} > 0. Поэтому

| \det F | = \prod_{0\le j <k \le n-1} 2 \sin \frac{(k-j)\pi}{n} = n^{n/2} \ .

Для определения аргумента комплексного числа \det F имеем соотношение

\det F = \mathbf i^{n(n-1)/2} \prod_{0\le j <k \le n-1} \alpha^{k+j} \cdot | \det F | \ .

Теперь определим величину произведения

\prod_{0\le j <k \le n-1} \alpha^{k+j} = \alpha^{\displaystyle \sum_{0\le j <k \le n-1}(k+j)} \ .

Распишем сумму из показателя

\begin{array}{crrrrrr} \sum_{0\le j <k \le n-1}(k+j) & = & (0+1)+ &(0+2)+ & (0+3)+ & \dots + & 0+ (n-1) + \\ & & & (1+2) + & (1+3)+ & \dots + & 1+ (n-1)+ \\ & & & & (2+3)+ & \dots + & 2+ (n-1) + \\ & & & & & +& \dots+ \\ & & & & & +& (n-2)+ (n-1)= \end{array}

пересуммируем по столбцам:

=\left(1^2+2^2+3^2+\dots+(n-1)^2 \right) + 1 + (1+2)+(1+2+3)+\dots+(1+2+\dots+(n-2)) =
=\left(1^2+2^2+3^2+\dots+(n-1)^2 \right)+\left(C_2^2+C_3^2+\dots+C_{n-1}^2 \right) =

и воспользуемся формулами суммы степеней целых чисел и суммы биномиальных коэффициентов:

= \frac{n(n-1)(2n-1)}{6}+\frac{n(n-1)(n-2)}{6} = \frac{n(n-1)^2}2 \ .

Если предположить n_{} четным: n=2m, то

\alpha^{\displaystyle \sum_{0\le j <k \le n-1}(k+j)}=\alpha^{m(2m-1)^2}=\alpha^{4m(m^2-m)}\alpha^m ,

и, поскольку

\alpha^{4m}=\left( \cos \frac{\pi}{2m} + \mathbf i \sin \frac{\pi}{2m} \right)^{4m}= 1 \quad u \quad \alpha^{m}=\mathbf i ,

то получаем справедливость одной части теоремы. Вторая часть доказывается аналогично.

Т

Теорема 2. Матрица обратная к матрице ДПФ вычисляется по формуле:

F^{-1}=\frac{1}{n}\left[ \varepsilon_{-j}^{k} \right]_{j,k=0}^{n-1}= \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_{-1} & \varepsilon_{-1}^2 & \dots & \varepsilon_{-1}^{n-1} \\ 1 & \varepsilon_{-2} & \varepsilon_{-2}^2 & \dots & \varepsilon_{-2}^{n-1} \\ 1 & \varepsilon_{-3} & \varepsilon_{-3}^2 & \dots & \varepsilon_{-3}^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{-(n-1)} & \varepsilon_{-(n-1)}^{2} & \dots & \varepsilon_{-(n-1)}^{n-1} \end{array} \right) \quad npu \quad \varepsilon_{-j} = \cos \frac{2 \pi j}{n} - {\mathbf i} \, \sin \frac{2 \pi j}{n}

Основываясь на свойстве \varepsilon_{-j}=\varepsilon_{-1}^j=\overline{\varepsilon_1}^j (см. ЗДЕСЬ ), матрицу часто записывают в эквивалентном виде

F= \frac{1}{n}\left[ \overline{\varepsilon}^{jk} \right]_{j,k=0}^{n-1}=\frac{1}{n} \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \overline{\varepsilon} & \overline{\varepsilon}^2 & \dots & \overline{\varepsilon}^{n-1} \\ 1 & \overline{\varepsilon}^2 & \overline{\varepsilon}^4 & \dots & \overline{\varepsilon}^{2(n-1)} \\ 1 & \overline{\varepsilon}^3 & \overline{\varepsilon}^6 & \dots & \overline{\varepsilon}^{3(n-1)} \\ \vdots & & & & \vdots \\ 1 & \overline{\varepsilon}^{n-1} & \overline{\varepsilon}^{2(n-1)} & \dots & \overline{\varepsilon}^{(n-1)^2} \end{array} \right) \quad npu \quad \overline{\varepsilon} = \cos \frac{2 \pi}{n} - {\mathbf i} \, \sin \frac{2 \pi}{n} \ .

§

Образно говоря: обращение матрицы F_{} сводится к сопряжению каждого ее элемента и делению его на порядок матрицы.

Доказательство сводится к проверке умножением:

\left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_{-1} & \varepsilon_{-1}^2 & \dots & \varepsilon_{-1}^{n-1} \\ 1 & \varepsilon_{-2} & \varepsilon_{-2}^2 & \dots & \varepsilon_{-2}^{n-1} \\ 1 & \varepsilon_{-3} & \varepsilon_{-3}^2 & \dots & \varepsilon_{-3}^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{-(n-1)} & \varepsilon_{-(n-1)}^{2} & \dots & \varepsilon_{-(n-1)}^{n-1} \end{array} \right)\cdot \left( \begin{array}{lllll} 1 & 1 & 1 & \dots & 1 \\ 1 & \varepsilon_1 & \varepsilon_1^2 & \dots & \varepsilon_1^{n-1} \\ 1 & \varepsilon_2 & \varepsilon_2^2 & \dots & \varepsilon_2^{n-1} \\ 1 & \varepsilon_3 & \varepsilon_3^2 & \dots & \varepsilon_3^{n-1} \\ \vdots & & & & \vdots \\ 1 & \varepsilon_{n-1} & \varepsilon_{n-1}^{2} & \dots & \varepsilon_{n-1}^{n-1} \end{array} \right)=

(в следующей матрице везде суммирование идет по j \in \{0,1,\dots,n-1\}, и все эти суммы равны нулю (см. ЗДЕСЬ ):

=\left( \begin{array}{lllll} n & \sum \varepsilon_j & \sum \varepsilon_j^2 & \dots & \sum \varepsilon_j^{n-1} \\ \sum \varepsilon_{-j} & n & \sum \varepsilon_j & \dots & \sum \varepsilon_j^{n-2} \\ \sum \varepsilon_{-j}^2 & \sum \varepsilon_{-j} & n & \dots & \sum \varepsilon_j^{n-3} \\ \sum \varepsilon_{-j}^3 & \sum \varepsilon_{-j}^2 & \sum \varepsilon_{-j} & \dots & \sum \varepsilon_j^{n-4} \\ \vdots & & & & \vdots \\ \sum \varepsilon_{-j}^{n-1} & \sum \varepsilon_{-j}^{n-2} & \sum \varepsilon_{-j}^{n-3} & \dots & n \end{array} \right) = \left( \begin{array}{lllll} n & 0 & 0 & \dots & 0 \\ 0 & n & 0 & \dots & 0 \\ 0 & 0 & n & \dots & 0 \\ \vdots & & & \ddots & \vdots \\ 0 & 0 & 0 & \dots & n \end{array} \right) \ .

П

Пример. При n=4:

F^{-1}=\frac{1}{4} \left( \begin{array}{rrrr} 1 & 1 & 1 & 1\\ 1 & -\mathbf i & -1 & \mathbf i \\ 1 & -1 & 1 & -1 \\ 1 & \mathbf i & -1 & -\mathbf i \end{array} \right) \ ;

при n=8ЗДЕСЬ.

§

Видим, что обращение матрицы F_{} фактически сводится к перестановке ее строк; это хорошо заметно на матрице 8-го порядка. Подозрение, что матрица F^{-1} должна быть очень похожа на матрицу F_{} следовало из первого этапа доказательства теоремы 1: фактически F^2 уже была близка к диагональной матрице. Алгоритм перестановки строк матрицы F_{}, приводящий к ее обращению, следует из правила \overline{\varepsilon_j}=\varepsilon_{-j}=\varepsilon_{n-j}: вторая строка переставляется местами с последней, третья — с предпоследней, и т.д.

Т

Теорема 3. Собственные числа матрицы F_{} находятся во множестве \{\pm\sqrt{n}, \pm\mathbf i\sqrt{n} \}. Кратности определяются из следующей таблицы:

\begin{array}{c|c|c|c|c} n & \lambda= \sqrt{n} & \lambda= - \sqrt{n} & \lambda= -\mathbf i \sqrt{n} & \lambda= \mathbf i \sqrt{n} \\ \hline 4m & m+1 & m & m & m-1 \\ 4m+1 & m+1 & m & m & m \\ 4m+2 & m+1 & m+1 & m & m \\ 4m+3 & m+1 & m+1 & m+1 & m \\ \end{array}

П

Пример. Характеристический полином матрицы F_{} при n_{}=4:

\det (F-\lambda E) \equiv (\lambda - 2\, \mathbf i)(\lambda+2)(\lambda-2)^2 \ ;

при n_{}=8ЗДЕСЬ.




Статья не закончена!







Источник

С небольшими модификациями взято из:

Проскуряков И.В. Сборник задач по линейной алгебре. М.Наука. 1974


2017/03/06 09:20 редактировал au