\title{Diskret fouriertransform}

\input{preamble}




\begin{document}
\pagenumbering{gobble}

\maketitle


Her er et ekvidistant gitter på intervallet $[-\pi,\pi]$:
\begin{equation*}
x_k=\frac{\pi k}{N} \quad \text{der} \quad -N \leq k \leq N
\end{equation*}
Vi ønsker å finne et trigonometrisk polynom 
\begin{equation*}
\sum_{n=-N}^{N} c_n e^{inx}
\end{equation*}
som interpolerer en $2\pi$-periodisk funksjon $f$ i gitterpunktene, altså at
\begin{equation*}
f\left(\frac{\pi k}{N}\right)=\sum_{n=-N}^{N} c_n e^{in\frac{\pi k}{N}}.
\end{equation*}

Det trigonometriske polynomet vi skal interpolere med, 
har fundamentalperiode $2\pi$, 
så hvis vi bestemmer hva polynomet skal være i $x=-\pi$, 
bestemmer vi samtidig hva det skal være i $x=\pi$. 
Derfor er ikke gitterpunktet $x_N=\pi$ med i beregningene under.


La oss gange først gange likningen over med $e^{-im\frac{\pi k}{N}}$ og summere over alle gitterpunkter:
\begin{equation*}
\sum_{k=-N}^{N-1} f\left(\frac{\pi k}{N}\right)e^{-im\frac{\pi k}{N}}=\sum_{k=-N}^{N-1}\sum_{n=-N}^{N} c_n e^{i\frac{ \pi k }{N}(n-m)}
\end{equation*}
Nå bytter vi summasjonsrekkefølgen på høyre side:
\begin{equation*}
\sum_{k=-N}^{N-1} f\left(\frac{ \pi k }{N}\right)e^{-im\frac{ \pi k }{N}}=\sum_{n=-N}^{N} c_n \sum_{k=-N}^{N-1}  e^{i\frac{\pi k}{N}(n-m)}
\end{equation*}
Den innerste summen er en endelig geometrisk rekke med multiplikasjonsfaktor $e^{i\frac{\pi}{N}(n-m)}$. Siden 
\begin{align*}
\sum_{k=-N}^{N-1}  e^{i\frac{\pi k}{N}(n-m)}=
\begin{cases}
2N\quad &m= n \\
0 \quad &m\neq n
\end{cases}
%&=e^{i\frac{\pi k}{N}(-N-m)}\sum_{k=0}^{2N-1} e^{i\frac{\pi k}{N}(n-m)}\\
%&=e^{i\frac{\pi k}{N}(-N-m)}\sum_{k=0}^{2N-1}  \left(e^{i\frac{\pi }{N}(n-m)}\right)^k \\
%&=e^{i\frac{\pi k}{N}(-N-m)} \frac{1-\left(e^{\frac{\pi i}{N}(n-m)}\right)^{2N}}{1-e^{\frac{\pi i}{N}(n-m)}} \\[3pt]
%& =e^{i\frac{\pi k}{N}(-N-m)}  \frac{1-e^{2\pi i(n-m)}}{1-e^{\frac{2\pi i}{N}(n-m)}}=0, 
\end{align*}
%\begin{equation*}
%\sum_{k=-N}^{N-1}  e^{\frac{\pi i}{N}k(n-m)}=\sum_{k=-N}^{N-1}  1=2N,
%\end{equation*}
blir
\begin{equation*}
\sum_{n=-N}^{N} c_n \sum_{k=-N}^{N-1}  e^{\frac{2\pi i}{N}k(n-m)}=2N c_m.
\end{equation*}
Med andre ord er
\begin{align*}
\sum_{k=-N}^{N-1} f\left(\frac{ \pi k }{N}\right)e^{-imx}& =\sum_{n=-N}^{N} c_n \sum_{k=-N}^{N-1}  e^{\frac{2\pi i}{N}k(n-m)} \\
&=2Nc_n. 
\end{align*}
 eller
\begin{equation*}
c_n=\frac{1}{2N}\sum_{k=-N}^{N-1} f\left(\frac{ \pi k }{N}\right)e^{-in\frac{ \pi k }{N}}.
\end{equation*}



\end{document}
