Изменения
Нет описания правки
что и требовалось доказать.
}}
== Пример ==
Посчитаем <tex>DFT</tex> для полинома степени <tex>n = 4</tex>.
<center>
<tex>
A(x) = 5 + 2x + 4x^2 - x^3
</tex>
</center>
Тогда подставляя значения <tex>k</tex> в <tex>e^{2i\frac{\pi k}{4}}</tex> получаем:
<center>
<tex>
x_0 = \ \ 1 \\
x_1 = \ \ 2 \\
x_2 = \ \ 4 \\
x_3 = -1
</tex>
</center>
Построим матрицу Вандермонда:
<center>
<tex>
\begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & i & -1 & -i \\
1 & -1 & 1 & -1 \\
1 & -i & 1 & i
\end{pmatrix}
\begin{pmatrix}
5 \\
2 \\
4 \\
-1
\end{pmatrix}
=
\begin{pmatrix}
y_0 \\
y_1 \\
y_2 \\
y_3
\end{pmatrix}
</tex>
</center>
Получаем вектор значений многочлена <tex>(y_0, y_1, y_2, y_3)</tex>:
<center>
<tex>
y_0 = 1 \cdot 5 \ + \ 1 \cdot 2 \ + \ 1 \cdot 4 \ -1 \ = \ 10 \\
y_1 = 1 \cdot 5 \ + \ 2i \ - \ 4 \ + \ i \ = \ 1 \ + \ 3i \\
y_2 = 1 \cdot 5 \ - \ 2 \ + \ 4 \ + 1 \ = \ 8 \\
y_3 = 1 \cdot 5 \ - \ 2i \ - \ 4 \ - \ i = 1 \ - \ 3i
</tex>
</center>
В итоге получаем:
<center>
<tex>
DFT(A) = (10, 1 + 3i, 8, 1 - 3i)
</tex>
</center>
== См. также ==
