שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה - התמרת פורייה מהירה

מהו הפלט של טרנספורם פורייה הדיסקרטי $\text{DFT}_n$ מסדר $n$, כאשר הקלט הוא $(1,1,\dots,1)$ — כלומר וקטור המקדמים של הפולינום $p(x)=1+x+x^2+\cdots+x^{n-1}$?

רמז: $\text{DFT}_n$ מעריך את הפולינום בשורשי היחידה. מהו סכום הסדרה ההנדסית $1+\omega+\cdots+\omega^{n-1}$ עבור שורש יחידה $\omega\neq 1$, ומה מתקבל עבור $\omega=1$?

פתרון: **הפלט הוא $(n,0,0,\dots,0)$.** $\text{DFT}_n$ מעריך את $p$ בשורשי היחידה מסדר $n$, $\;\omega_n^k=e^{2\pi i k/n}$ עבור $k=0,\dots,n-1$: - **עבור שורש היחידה הראשון** $x=1=\omega_n^0$: $\;p(1)=1+1+\cdots+1=n$. - **עבור $k\neq 0$:** לפי סכום סדרה הנדסית $p(\omega_n^k)=\dfrac{(\omega_n^k)^n-1}{\omega_n^k-1}=\dfrac{1-1}{\omega_n^k-1}=0$ (שכן $(\omega_n^k)^n=1$ ו-$\omega_n^k\neq 1$). לכן $\text{DFT}_n(1,\dots,1)=(n,0,\dots,0)$. $\blacksquare$