\input{../preambles/preamble}

\title{35 - INTERPOLASJON OG REGRESJON}

%sirkulære

\begin{document}
\pagenumbering{gobble}

\maketitle

Dersom du har skjønt alt i forrige økt, 
blir det litt enklere å huske og forstå hvordan lineærregresjon funker.
I sannsynlighetsregning pakkes dette inn i mye komplisert notasjon,
og statistikerne må gjøre det slik for å bygge opp alt systematisk.
Men selve matematikken er ikke så komplisert.

La oss begynne med noe som kalles \textbf{interpolasjon}. 
Hvis du har $n+1$ punkter $(x_i,y_i)$ i $\mathbb R^2$, 
der $x_i\neq x_j$ for alle $i\neq j$,
vil det alltid være mulig å finne et reelt polynom 
\[
p(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0
\]
hvis graf går gjennom alle disse punktene, 
altså at
\[
p(x_i)=y_i
\]
for alle $1\leq i \leq n+1$. 
DIsse likningene utgjør et $(n+1)\times (n+1)$-likningssystem for koeffisientene $a_i$ med totalmatrise
\[
\begin{amatrix}{5}
x_{1}^{n} & x_{1}^{n-1} & \hdots  & x_{1} & 1 & y_1\\
x_{2}^{n} & x_{2}^{n-1} & \hdots  & x_{2} & 1 & y_2\\
\vdots  & \vdots & \ddots  & \vdots & \vdots & \vdots\\
x_{n+1}^{n} & x_{n+1}^{n-1} & \hdots  & x_{n+1} & 1 & y_{n+1}\\
\end{amatrix}
\]
Dette systemet kalles vandermondesystemet,
og vi slipper faktisk å plages med det,
for vi kan heller gjøre slik:
For hvert punkt $x_{i}$, definerer vi et polynom
\begin{equation}\notag
l_{i}(x)= \prod_{\begin{matrix}
k=0\\
k \neq i
\end{matrix}}^{\begin{matrix}
n
\end{matrix}} \frac{(x-x_{k})}{(x_{i}-x_{k})}. 
\end{equation}

\begin{oppgave}{1}
Sjekk at polynomet $l_{i}(x)$ har orden $n$, og at det tilfredsstiller
\begin{equation}\notag
l_{i}(x_{k})= \begin{cases}
      1  & \text{for } i = k \\
      0 & \text{for } i \neq k
    \end{cases} .
\end{equation}
Hvordan tror du vi skal få bruk for disse polynomene?
\end{oppgave}

\begin{center}
\includegraphics[scale=.2]{../figurer/L1019584}
\end{center}

Det er lett å se at 
\begin{equation}\notag
p_n(x)= \sum_{i=0}^ny_{i}l_{i}(x). 
\end{equation}
tilfredsstiller $p_n(x_i)=y_i$ for alle  $i$. 
Polynomene $l_i$ kalles lagrangepolynomer,
og alt dette kalles Lagranges interpolasjonsmetode.
Det er også klart at vi alltid kan finne et entydig interpolasjonspolynom dersom $x_i\neq x_j$ for alle $i\neq j$.
\footnote{
Hvis vi antar at det finnes to forskjellige polynomer $p_n$ og $q_n$ av grad $n$ som interpolerer den samme tabellen, og evaluerer differansen $p_n-q_n$ i punktene $x_{i}$, ser vi at 
\begin{equation}\notag
p_n(x_{i})-q_n(x_{i})=0  \qquad 0\leq i \leq n.
\end{equation}
Polynomet $p-q$ har maksimal grad $n$, og kan maksimalt ha $n$ nullpunkter, så derfor må $p=q$.}

\begin{oppgave}{2}
Finn et annengradspolyom som går gjennom punktene
\[
\begin{bmatrix}
1 \\ 4
\end{bmatrix}, \;
\begin{bmatrix}
2 \\ 5
\end{bmatrix} \;
\quad \text{og} \quad
\begin{bmatrix}
3 \\ 6
\end{bmatrix}.
\]
\end{oppgave}
%Vi setter opp
%\begin{align*}
%l_0(x)&=\frac{(x-2)(x-3)}{(1-2)(1-3)}=\frac{1}{2}(x-2)(x-3) \\ 
%l_1(x)&=\frac{(x-1)(x-3)}{(2-1)(2-3)}=-(x-1)(x-3) \\
%&\text{og} \\
%l_2(x)&=\frac{(x-1)(x-2)}{(3-1)(3-2)}=\frac{1}{2}(x-1)(x-2).
%\end{align*}
%Det andre ordens polynomet som interpolerer denne tabellen er:
%\begin{align*}
%p(x)&=4l_0(x)+5l_1(x)+6l_2(x) \\[3pt] &= 2(x-2)(x-3) -5(x-1)(x-3)\\ &\qquad +3(x-1)(x-2).
%\end{align*}

Polynominterpolasjon ligger til grunn for veldig mye forskjellig. 
En klassiker er numerisk integrasjon. 
Den enkleste formen for numerisk integrasjon er å beregne riemannsummer. 
Men med polynominterpolasjon kan vi gjøre det mye bedre. 
La oss si at vi ønsker å finne en approksimasjon til 
\[
\int_a^b f(x)\; dx.
\]
Dette kan gjøres ved å dele inn $[a,b]$ i et ekvidistant gitter med $a=x_0$ og $b=x_n$, 
skrive
\[
\int_a^b f(x)\; dx \approx \int_a^b p(x)\; dx = f(x_i) \sum_{i=0}^n \int_a^b l_i(x)\; dx
\]
og så beregne 
\[
\int_a^b l_i(x)\; dx
\]
for alle $i$. 
For $n=1$ får man trapesregelen
\[
\int_a^b f(x)\; dx \approx \frac{b-a}{2}\left(f(a)+f(b)\right)
\]
\url{https://en.wikipedia.org/wiki/Trapezoidal_rule}\\
og for $n=2$ får man noe som kalles Simpsons metode:
\[
\int_a^b f(x)\; dx \approx \frac{b-a}{6}\left(f(a)+4f\left(\frac{b+a}{2}\right)+f(b)\right)
\]
\url{https://en.wikipedia.org/wiki/Simpson%27s_rule}\\
og så videre.
Dersom gitteret ikke er ekvidistant, 
kan man lage andre numeriske integrasjonsrutiner, 
for eksempel gausskvadratur:\\
\url{https://en.wikipedia.org/wiki/Gaussian_quadrature}\\
eller clenshawcurtiskvadratur:\\
\url{https://en.wikipedia.org/wiki/Clenshaw–Curtis_quadrature}

\begin{oppgave}{3}
Bruk Simpson på punktene i oppgave 2.
\end{oppgave}


Dersom man prøver å interpolere et datasett med et polynom som har for lav orden, 
vil man få det overbestemte $(n+1)\times (m+1)$-systemet 
\[
\begin{amatrix}{5}
x_{1}^{m} & x_{1}^{n-1} & \hdots  & x_{1} & 1 & y_1\\
x_{2}^{m} & x_{2}^{n-1} & \hdots  & x_{2} & 1 & y_2\\
\vdots  & \vdots & \ddots  & \vdots & \vdots & \vdots\\
x_{n+1}^{m} & x_{n+1}^{n-1} & \hdots  & x_{n+1} & 1 & y_{n+1}\\
\end{amatrix}
\]
Dette kalles \textbf{regresjon}.

\begin{oppgave}{4}
Prøv å finne et annengradspolyom som går gjennom punktene
\[
\begin{bmatrix}
0 \\ 1
\end{bmatrix}, \;
\begin{bmatrix}
1 \\ 0
\end{bmatrix}, \;
\begin{bmatrix}
2 \\ 1
\end{bmatrix} \;
\quad \text{og} \quad
\begin{bmatrix}
3 \\ 2
\end{bmatrix} .
\]
\end{oppgave}

\begin{center}
\includegraphics[scale=.5]{../figurer/img1690}
\end{center}


Likningssystemet i oppgaven over ble
\begin{align*}
                   c =& 1\\
    a + b + c  =& 0 \\
    4a + 2b + c =& 1\\
    9a + 3b + c =& 2
\end{align*}
Hvordan fikse dette?
Nå trenger vi noe som kalles minste kvadraters metode.
Dette er en teknikk for å finne tilnærmede løsninger til lineære systemer med flere likninger enn ukjente.
La oss si at $A$ er en $m \times n$-matrise, 
at $\V x$ og $\V y$ er kolonnevektorer i $\mathbb{C}^n$, 
og at vi ønsker å betrakte systemet
\[
A\V x=\V y
\]
for $m>n$. 
Dette systemet vil ikke ha noen løsning med mindre $\V y$ tilfeldigvis ligger i kolonnerommet til $A$, 
så vi ønsker istedet å finne den $\V x$ som minimerer avstanden fra $A\V x$ til $\V y$.
Det gjør vi ved å kreve
\[
A^*(A\V x-\V b)=\V 0
\]
altså at
\[
A^*A\V x=A^*\V y.
\]

\begin{oppgave}{5}
Hvorfor det?
\end{oppgave}

Dette er et $n \times n$-system som kalles \textbf{normallikningene},
og systemet har entydig løsning om kolonnene til $A$ er lineært uavhengige: 
Løsningen av systemet gir den $\V x$ som minimerer avstanden fra $A\V x$ til $\V y$.

\begin{oppgave}{6}
Bli ferdig med oppgave 4.
\end{oppgave}

Når statistikere snakker om regresjonslinje, 
mener de alt dette og at man bruker et førsteordens polynom $ax+b$ og at man 
bruker minste kvadraters metode for å finne koeffisientene $a$ og $b$.
Økonomer kaller det trendlinje.

\begin{oppgave}{7}
Finn regresjonslinjen til punktene
\[
\begin{bmatrix}
0 \\ 1
\end{bmatrix}, \;
\begin{bmatrix}
1 \\ 0
\end{bmatrix}, \;
\begin{bmatrix}
2 \\ 1
\end{bmatrix} \;
\quad \text{og} \quad
\begin{bmatrix}
3 \\ 2
\end{bmatrix} .
\]
\end{oppgave}

\begin{oppgave}{8}
Skriv en rutine som tar inn et datasett og produserer trendlinjen. 
\end{oppgave}

\begin{center}
\includegraphics[scale=.35]{../figurer/img20220425_06500107}
\end{center}

\section*{UKENS NØTTER}

\begin{minipage}{14cm}
Jeg var på en hytte i Kragerø i helgen og badet i en sirkulær badestamp med et sirkulært høl i bånn. 
Når jeg skulle tømme den, 
målte jeg vannstanden etterhvert som stampen tømtes,
og fikk tabellen i margen.
\end{minipage}
\begin{minipage}{4cm}
\begin{center}
\begin{tabular}{c | c}
$t$\; (s) & $h$\; (cm)\\
\hline
0 & 48\\
10 & 38\\
20 & 28\\
30 & 20\\
40 & 14\\
50 & 8 
\end{tabular}
\end{center}
\end{minipage}

I følge boken skal vannstanden følge Torricellis lov, 
som sier at 
$
\dot h = a \sqrt{h}.
$

\begin{oppgave}{9}
Estimer $a$. 
\end{oppgave}

Det går også an å modellere tømming av tank med modellen 
$
\dot h = a h+b.
$

\begin{oppgave}{10}
Estimer $a$. Hvilken modell passer best?
\end{oppgave}

Ifølge boken skal egentlig
\[
\dot h = - \sqrt{\frac{2g}{b^2-1}h} 
\]
der $g$ er tyngdeakselerasjonen og $b$ er forholdet mellom arealet til badestampen og arealet til hølet:\\
\url{https://en.wikipedia.org/wiki/Torricelli%27s_law}

\begin{oppgave}{11}
Stampen hadde radius på ca en meter,
men jeg glemte å måle radien på hølet. 
Hva var den?
\end{oppgave}



\begin{figure}[H]
\begin{center}
\includegraphics[scale=.25]{../figurer/L1019713}
\caption{Elsys Torjus koser seg i badestampen}
\end{center}
\end{figure}
\vspace{-5mm}
\begin{figure}[H]
\begin{center}
\includegraphics[scale=.25]{../figurer/L1019719}
\caption{Elsys Torjus hopper i havet}
\end{center}
\end{figure}



\end{document}
