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

§

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

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

$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