Изменения
Нет описания правки
Как и с комплексными корнями, остальные <tex>n-1</tex> корней <tex>n</tex>-ой степени из единицы по модулю <tex>p</tex> можно получить как степени примитивного корня <tex>\omega_n</tex>
== Утверждения Следствия =={{Утверждение|statement= <tex>DFT(DFT(a_0, a_1, \ldots , a_{n-1})) = \dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1) </tex>|proof= '''Доказательство:''' Применим к обеим частям обратное ДПФ и получим: <center><tex>DFT(a_0, a_1, a_{n-1}) = InvDFT(\dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1))</tex></center> Заметим, что слева у нас находится вектор значений многочлена с коэффициентами <tex>(a_0, a_1, \ldots , a_{n-1})</tex> и обозначим его за <tex>(y_0, y_1, \ldots , y_{n-1})</tex>. Заметим, что: <center><tex>y_k = \sum\limits_{j=0}^{n} a_j e^{i\frac{2\pi k}{n} j}</tex></center> Теперь рассмотрим правую часть. По определению, справа у нас находится вектор коэффициентов многочлена со значениями <tex>\left( \dfrac{1}{n} a_0, \dfrac{1}{n} a_{n-1}, \ldots , \dfrac{1}{n} a_1 \right)</tex> в точках <tex>x = \omega_n^k</tex>. Обозначим его как <tex>(y_0 ', y_1 ', \ldots , y_{n-1} ')</tex>, где: <center><tex>y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n} z_j e^{-i\frac{2\pi k}{n} j},</tex></center> где <center><tex>\begin{pmatrix}z_0 \\z_1 \\z_2 \\\vdots \\z_{n-1}\end{pmatrix}=\begin{pmatrix}\dfrac{a_0}{n}\\\dfrac{a_{n-1}}{n}\\\dfrac{a_{n-2}}{n}\\\vdots \\\dfrac{a_1}{n}\end{pmatrix}</tex></center> Тогда, подставляя значения <tex>z_j</tex>, получаем: <center><tex>y_k ' = a_0 e^0 + \sum\limits_{j=1}^{n} a_j e^{-i\frac{2\pi k}{n} (n - j)} = a_0 + \sum\limits_{j=1}^{n} a_j e^{-i 2\pi k} e^{i\frac{2\pi k}{n} j}</tex></center> А так как <tex>e^{-i 2\pi k} = \left(\dfrac{1}{e^{i 2\pi}}\right)^k = 1</tex>, получаем: <center><tex>y_k ' = a_0 + \sum\limits_{j=1}^{n} a_j e^{i \frac{2\pi k}{n} j} = \sum\limits_{j=0}^{n} a_j e^{i\frac{2\pi k}{n} j} = y_k,</tex></center>что и требовалось доказать.}}
== См. также ==
*[[Быстрое преобразование Фурье]]
