\input{../preambles/preamble}

\title{36 - TRIGONOMETRISK INTERPOLASJON}

%sirkulære

\begin{document}
\pagenumbering{gobble}

\maketitle

Temaet i denne økten kalles gjerne diskret fouriertransform (DFT), 
og du får bruk for det i DIGGSIGG.
Det er et år til, 
men det passer bra å ta det nå,
siden dere nå har lært interpolasjon
og dessuten er eksperter i abstrakte indreprodukt.
Diskret fouriertransform kan angripes på litt forskjellig vis.
Hvis man allerede har fouriertransform på $[-\pi,\pi]$ i ryggraden,
er det kanskje enklest å begynne med følgende problem.
Her er et ekvidistant gitter på intervallet $[-\pi,\pi]$:
\[
t_k=\frac{\pi k}{N}, \qquad -N \leq k \leq N
\]
Vi ønsker å finne et trigonometrisk polynom 
\begin{equation*}
\sum_{n=-N}^{N-1} c_n e^{int}
\end{equation*}
som interpolerer et kontinuerlig $2\pi$-periodisk signal $x$ i gitterpunktene, altså at
\begin{equation*}
x\left(\frac{\pi k}{N}\right)=\sum_{k=-N}^{N-1} 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 kan vi se bort fra gitterpunktet $x_N=\pi$,
og det er derfor summene går til $N-1$ og ikke $N$.

\begin{oppgave}{1}
Vis at 
\[
(x,y)=\sum_{k=-N}^{N-1} 
x\left(\frac{\pi k}{N}\right)
\overline{y\left(\frac{\pi k}{N}\right)}
\]
er et komplekst indreprodukt,
og at funksjonene
\[
e^{int} \qquad \text{der} \qquad -N \leq n \leq N-1
\]
er ortogonale med hensyn på dette indreproduktet,
og bruk det du lærte om ortogonale vektorer i TMA4106 til å utlede at 
\begin{equation*}
c_n=\frac{1}{2N}\sum_{k=-N}^{N-1} 
x\left(\frac{ \pi k }{N}\right)e^{-in\frac{ \pi k }{N}}
\end{equation*}
og gå tilbake til formelen for fourierrekker 
på $[-\pi,\pi]$ og sjekk at du ser analogien.
\end{oppgave}

\begin{center}
\includegraphics[scale=.3]{../figurer/L1019135}
\end{center}

Et grunnleggende problem med å undervise fourieranalyse,
er at konvensjonene for de forskjellige typene fouriertransform
er slik at det er litt vanskelig å se at det er \say{det samme}.
Fouriertransform kommer i flere varianter, 
og dette er den tredje varianten vi har sett til nå. 
La oss oppsummere litt. 
Dersom du har et periodisk signal $x$, 
kan du stort sett skrive
\[
x(t) = \sum_{n=-\infty}^{\infty}c_n e^{2\pi i n t/T}
\qquad
\text{der}
\qquad
c_n=\frac{1}{T}\int_{-T/2}^{T/2} x(t) e^{-2\pi i n t/T}\; dt.
\]
Har du et ikkeperiodisk signal,
kan du stort sett skrive
\[
x(t) = \frac{1}{2\pi}\int_{-\infty}^{\infty}X(\omega)e^{i\omega t}d\omega
\qquad
\text{der}
\qquad
X(\omega) =\int_{-\infty}^{\infty} x(t)e^{-i\omega t}\;dt.
\]
Nå er det for eksempel litt forvirrende at normaliseringsfaktoren 
$1/T$ står på fourierkoeffisienten i det første tilfellet
mens normaliseringsfaktoren $1/2\pi$ står på 
inverstransformen i det andre tilfellet. 
Når det gjelder DFT er det enda mere forvirrende, 
for profesjonelle diggsiggere bruker ikke DFT-formler som likner på 
disse i det hele tatt. 

De gjør det slik.
La $x$ være et diskret signal med $N$ verdier $x(k)$.  
Da er det slik at dersom 
\[
X_n=\sum_{k=0}^{N-1} e^{-2\pi i nk/N}
\qquad
\text{er}
\qquad
x(k)=\frac{1}{N}\sum_{n=0}^{N-1} X_n e^{2\pi i nk/N}.
\]
Dette blir bra greier med lite griseri.
La oss gjenta oppgave 1. 

\begin{oppgave}{2}
Vis at 
\[
(x,y)=\sum_{k=0}^{N-1} 
x(k)
\overline{y(k)}
\]
er et komplekst indreprodukt,
og at funksjonene
\[
e^{2\pi i nt} \qquad \text{der} \qquad 0 \leq n \leq N-1
\]
er ortogonale med hensyn på dette indreproduktet,
og bruk det du lærte om ortogonale 
vektorer i TMA4106 til å utlede at dersom 
\[
X_n=\sum_{k=0}^{N-1} e^{-2\pi i nk/N}
\qquad
\text{er}
\qquad
x(k)=\frac{1}{N}\sum_{n=0}^{N-1} X_n e^{2\pi i nk/N}.
\]
Lykke til med å gå tilbake til formelen for 
fourierrekker på $[-\pi,\pi]$ og sjekke at du ser analogien.
\end{oppgave}

\begin{center}
\includegraphics[scale=.3]{../figurer/L1018405-HDR}
\end{center}


Beregning av fourierkoeffisientene er i bunn og grunn et matrise-vektorprodukt,
og dersom primtallsfaktoriseringen til $N$ består av 
så mange små faktorer som mulig ($N=2^m$ er det aller beste)
går det veldig fort å beregne dem:\\
\url{https://en.wikipedia.org/wiki/Fast_Fourier_transform}\\
Dette kalles FFT (Fast Fourier Transform) og regnes som en av århundrets viktigste algoritmer. 
At fourierkoeffisientene kan beregnes raskt var kjent for Carl Friedrich Gauss,
for han brukte visst DFT til å interpolere et datasett på jakt etter banene til asteroidene Pallas og Juno. 
Algoritmen har blitt gjenoppdaget mange ganger opp gjennom,
men det var Cooley og Tukey som til slutt ble kreditert i 1965:\\
\url{https://en.wikipedia.org/wiki/Cooley–Tukey_FFT_algorithm}\\


\begin{oppgave}{3}
Skriv opp matrise-vektorproduktet for $N=7$ og $N=8$. 
Se nøye på vandermondematrisene, 
og se om du ser noen forskjell. 
Hvis du ser veldig nøye etter, 
vil du kanskje skjønne hvordan Cooley og Tukey klarte å redusere antall beregninger 
fra størrelsesorden $N^2$ til $N\log N$. 
\end{oppgave}

Vi må selvfølgelig ha pytagoras, 
som sier at 
\[
\sum_{k=0}^{N-1}|x(k)|^2=
\sum_{n=0}^{N-1}|X_n|^2
\]

\begin{oppgave}{4}
Jeg kunne bedt deg utlede dette, 
men du har allerede gjort det på eksamen i TMA4106.
Derfor slipper du det nå. 
Dette er fordelen med abstrakt matematikk.
\end{oppgave}


Dette kalles ikke egentlig pytagoras, 
men derimot Plancherels teorem, 
jeg har bare kalt det pytagoras til nå siden det er 
det det er en generalisering av. 
En generalisering av Plancherel er Parsevals teorem, 
som sier at 
\[
(x,y)=\frac{1}{N}(X,Y)
\]

\begin{oppgave}{5}
Klarer du denne?
\end{oppgave}



DFT brukes selvfølgelig til filtrering av digitale signal, 
og alle signaler er digitale nå til dags. 
Derfor må vi også ha konvolusjonsteoremet. 
Diskret konvolusjon er 
\[
(x \ast y )(k)= \sum_{m=0}^{N-1} x(m)y(k-m)
\]

\begin{oppgave}{6}
Vis at den diskrete fouriertransformen  
til $x \ast y$ er 
$
(X,Y)$.
\end{oppgave}


\begin{center}
\includegraphics[scale=.28]{../figurer/L1003600}
\end{center}


%dirichletkjernen 

%spør lars om sinc



\section*{UKENS NØTTER} 

\begin{oppgave}{1}
De diskrete fourierkoeffisientene slik de 
står i oppgave 1 kan også utledes ved å ta formelen 
\[
c_n=\frac{1}{2\pi}\int_{-\pi}^\pi x(t)e^{-int}\; dt
\]
for vanlige fourierkoeffisienter og så bruke den sammensatte trapesregelen 
\[
\int_a^b x(t)\; dt \approx \frac{1}{n}\left(\frac{x(a)}{2}+
\sum_{k=1}^{n-1} x\left(a+k\frac{b-a}{n}\right) + \frac{x(b)}{2}\right).
\]
Prøv. 
\end{oppgave}

\end{document}
