Изменения

A \times B = \mathrm{InvDFT}(\mathrm{DFT}(A) \times \mathrm{DTFDFT}(B)).

|statement= <tex>\mathrm{DFT}(\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1})) = \dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1) </tex>

\mathrm{DFT}(a_0, a_1, \ldots , a_{n-1}) = \mathrm{InvDFT}\left(\dfrac{1}{n} (a_0, a_{n-1}, \ldots , a_1)\right)

y_k = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j}

Теперь рассмотрим правую часть. По определению, справа у нас находится вектор коэффициентов многочлена со значениями <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>, где:

y_k '= \dfrac{1}{n} \sum\limits_{j=0}^{n-1} z_j e^{-i\frac{2\pi k}{n} j},

\dfracn{a_0}{n}\\\dfracn{a_{n-1}}{n}\\\dfracn{a_{n-2}}{n}\\

\dfracn{a_1}{n}

y_k ' = a_0 e^0 + \sum\limits_{j=1}^{n-1} a_j e^{-i\frac{2\pi k}{n} (n - j)} = a_0 + \sum\limits_{j=1}^{n-1} a_j e^{-i 2\pi k} e^{i\frac{2\pi k}{n} j}

y_k ' = a_0 + \sum\limits_{j=1}^{n-1} a_j e^{i \frac{2\pi k}{n} j} = \sum\limits_{j=0}^{n-1} a_j e^{i\frac{2\pi k}{n} j} = y_k.

x_0 = \ \ 1 5 \\

1 & -i & -1 & i

[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]