\input /home/pasky/school/fastex/lib.tex

\subchapter{Diskr�tn� Fourierova transformace}{

	$$ f(x) = c + \sum_{k=1}^{n/2-1} a_k \sin kx + \sum_{k=1}^{n/2-1} b_k \cos kx $$

	Jsme {\bf diskr�tn�}: $x_j = 2\pi/n \cdot j$,
	pak vezmeme $x_0,x_1,x_2,\ldots,x_{n-1}$.

	Ps�t $f(x)$ tak rozvl��n� je otrava, tak�e p�ejdeme do $\cmplx$,
	i kdy� n�s vlastn� zaj�m� $\real$:
	$$ e^{2x} = \cos x + i\sin x $$
	$$ \cos x = {e^{ix} + e^{-ix} \over 2} $$
	$$ \sin x = {e^{ix} - e^{-ix} \over 2i} $$

	Nyn� m��eme pou��t z�pis
	$$ f(x_j) = \sum_{k=0}^{n-1} \alpha_k e^{ikx_j} = \sum_{k=0}^{n-1} \alpha_k e^{i{2\pi kj \over n}} =: A_j $$
	a p�itom st�le plat� periodicita, nebo�
	$$ e^{ikx_j} = e^{i(k+n)x_j} = e^{ikx_j} \cdot \undernote{e^{inx_j}}{1} $$

	Diskr�tn� FT je te� vpodstat� zobrazen�
	$(A_0,\ldots,A_{n-1}) \to (\alpha_0,\ldots,\alpha_{n-1})$.

	Zkusme n�co alespo� zd�nliv� jednodu���ho:
	$(\alpha_0,\ldots,\alpha_{n-1}) \to (A_0,\ldots,A_{n-1})$.

	Zamysleme se nad $\omega = e^{2\pi i \over n}$.
	Pro r�zn� $n$ je v�dy vzd�lenost od nuly $1$,
	jde tedy o r�zn� body na jednotkov� kru�nici.
	M�me navz�jem t�m�� r�zn�
	$$\omega^0,\omega^1,\omega^2,\ldots,\omega^{n-1},\ \omega^n = \omega^0 = 1$$

	M��eme tedy je�t� zjednodu�it z�pis na
	$$ A_j = \sum_{k=0}^{n-1} \alpha_k \omega^{kj} $$

	Ale kdybychom tohle po��tali, bude to $O(n^2)$.
	My to v�ak um�me rychleji, v $O(n\log n)$.

	$$ \matrix{A_0=&a_0\omega^{0\cdot0}&+&a_1\omega^{1\cdot0}&+&a_2\omega^{2\cdot0}&+&a_3\omega^{3\cdot0} \cr
	           A_1=&a_0\omega^{0\cdot1}&+&a_1\omega^{1\cdot1}&+&a_2\omega^{2\cdot1}&+&a_3\omega^{3\cdot1} \cr
	           A_2=&a_0\omega^{0\cdot2}&+&a_1\omega^{1\cdot2}&+&a_2\omega^{2\cdot2}&+&a_3\omega^{3\cdot2} \cr
	           A_3=&a_0\omega^{0\cdot3}&+&a_1\omega^{1\cdot3}&+&a_2\omega^{2\cdot3}&+&a_3\omega^{3\cdot3}} $$

	Rozd�l�m na lich� a sud� sloupe�ky, d�m je k sob�,
	v $A_k$ vytknu lich� skupiny $\omega^k$.

	$$ \matrix{A_0=&a_0\omega^{0\cdot0}&+&a_2\omega^{2\cdot0}&+&\omega^0 & (a_1\omega^{0\cdot0}&+&a_3\omega^{2\cdot0}) \cr
	           A_1=&a_0\omega^{0\cdot1}&+&a_2\omega^{2\cdot1}&+&\omega^1 & (a_1\omega^{0\cdot1}&+&a_3\omega^{2\cdot1}) \cr
	           A_2=&a_0\omega^{0\cdot2}&+&a_2\omega^{2\cdot2}&+&\omega^2 & (a_1\omega^{0\cdot2}&+&a_3\omega^{2\cdot2}) \cr
	           A_3=&a_0\omega^{0\cdot3}&+&a_2\omega^{2\cdot3}&+&\omega^3 & (a_1\omega^{0\cdot3}&+&a_3\omega^{2\cdot3})} $$

	Te� si v�imn�me, �e $\omega^4 = 1$.
	D�ky n�soben� v exponentu o sud� ��slo lze tedy v $A_2$ a $A_3$
	zm�nit $\omega^{2\cdot2}$ na $\omega^{2\cdot0}$ apod.

	$$ \matrix{A_0=&a_0\omega^{0\cdot0}&+&a_2\omega^{2\cdot0}&+&\omega^0 & (a_1\omega^{0\cdot0}&+&a_3\omega^{2\cdot0}) \cr
	           A_1=&a_0\omega^{0\cdot1}&+&a_2\omega^{2\cdot1}&+&\omega^1 & (a_1\omega^{0\cdot1}&+&a_3\omega^{2\cdot1}) \cr
	           A_2=&a_0\omega^{0\cdot0}&+&a_2\omega^{2\cdot0}&+&\omega^2 & (a_1\omega^{0\cdot0}&+&a_3\omega^{2\cdot0}) \cr
	           A_3=&a_0\omega^{0\cdot1}&+&a_2\omega^{2\cdot1}&+&\omega^3 & (a_1\omega^{0\cdot1}&+&a_3\omega^{2\cdot1})} $$

	Te� u� je vid�t, �e tam m�me p�lku redundantn�.
	{\it Nav�c} tohle ale m��eme d�lat rekurzivn� s ka�dou �tvrtinou!
	(Resp. s ka�dou polovinou, proto�e dv� �tvrtiny jsou redundantn�.)
	Bl��e viz hezk� algovisionov� applet.

	Hop a m�me $\log n$.
	Tomuhle postupu ��k�me FFT, neboli Fast Fourier Transform.

\penalty-1000

	Dob�e, ale co spektr�ln� anal�za, tedy
	$(A_0,\ldots,A_{n-1}) \to (\alpha_0,\ldots,\alpha_{n-1})$?

	N� p�edchoz� v�po�et m��eme tak� popsat jako:
	$$ W_{p,q} = \omega^{p\cdot q} \qquad A = Wa $$
	N�s tud�� zaj�m� $W^{-1}$ (proto�e $a = W^{-1} A$),
	a za okam�ik si dok�eme:
	$$ (W^{-1})_{pq} = 1/n\cdot \omega^{-pq} $$
	To je vpodstat� stejn� �loha jako p�edt�m,
	jen m�sto $\omega$ vezmeme $\omega^{-1}$
	(a nakonci mus�me v�e vyd�lit $n$).
	Periodicita i v�e ostatn� je zachov�no,
	slun��ko sv�t�, pt��ci zp�vaj�\dots

	\proof{
		$$ (W)_{pq} = \omega^{pq} $$
		$$ (\overline{W})_{pq} = \omega^{-pq} $$

		$$ (W\cdot\overline{W})_{pq} = \sum_{s=0}^{n-1} W_{ps}\cdot\overline{W}_{sq}
			= \omega^{p0}\omega^{-0q} + \omega^{p1}\omega^{-1q} + \cdots + \omega^{ps}\omega^{-sq} + \cdots
			= \Gamma
			\opupon{?}{=} \cases{n & $p = q$ \cr 0 & $p \ne q$} $$

		Rozvoj p�es $\omega$ m��eme tak� popsat jako
		$$ \Gamma = \omega^{0(p-q)} + \omega^{1(p-q)} + \omega^{2(p-q)} + \cdots $$
		$$ p \ne q,\ 0 \le p,q < n: Q = \omega^{p-q} \ne 1 $$
		$$ \Gamma = Q^0 + Q^1 + Q^2 + \cdots + Q^{n-1} $$
		a to si m��eme p�edstavit jako body rovnom�rn� rozlo�en� po jednotkov� kru�nici, tedy se n�m vyru��.
		Form�ln� si to ale dok�eme p�es sou�et geometrick� �ady
		$$ \Gamma = {Q^{(n-1)+1} - 1 \over Q-1}Q^0 $$
		a z definice $Q$:
		$$ \Gamma = 1 $$
	}

}

\bend
