Инструменты сайта


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

$$ 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

algebra2/fourier.txt · Последние изменения: 2020/03/11 23:18 (внешнее изменение)