\input{preamble}

\title{1 - 3 - LIKNINGER}

%tvilling

\begin{document}
\pagenumbering{gobble}

\maketitle

%RUST
%husk ustabil balanse under dykk, s 385 ancestors tale, man synker under og stiger opp over

Fysiske modeller formuleres stort sett som likninger som involverer fysiske størrelser. 
I de enkleste tilfellene er modellen en algebraisk likning, 
slik som 
$
s=s_0+vt
$
eller
$
\frac{1}{2}mv^2=mgh,
$
og løsningen et tall.
Dersom man kun påvirket av tyngden og i vakuum hopper ut av et tre
og vil regne ut hvor man lander, 
består dette problemet i bunn og grunn av å løse en annengradslikning.

\begin{center}
\includegraphics[scale=.17]{../figurer/tre}
\end{center}

På skolen trente du derfor veldig mye på å løse algebraiske likninger som
$
x^2+2x+1=0.
$
Men denne tolv år lange løsningstreningsleiren gir av ymse grunner et litt skjevt bilde av virkeligheten.
Det mange likninger som ikke har noen løsning
(slik som $x^2=2$ der $x$ er et rasjonalt tall),
og de du på skolen lærte ikke har løsning,
har gjerne det allikevel
(slik som
$
x^2 + 2 x + 2 = 0
$).
Likninger kan ha uendelig mange løsninger
(ikke bare to slik som annengradslikningene),
og det kan tenkes at likningens løsninger eksisterer,
men at det er håpløst å regne dem ut.

Vi skal denne uken studere det siste tilfellet,
flesker defor til med en ganske vanskelig oppgave.

\begin{oppgave}{1}
Prøv å løse likningen
$
x=\cos x
$.
\end{oppgave}

\begin{center}
\includegraphics[scale=.19]{../figurer/L1016462-Pano}
\end{center}

\begin{minipage}{100mm}
Her er et plot av funksjonene $f(x)=x$ og $g(x)=\cos x$.
Det er lett å se at de to funksjonene krysser hverandre,
så løsningen til likningen eksisterer,
men den er ikke så lett å finne uten en kalkulator eller en datamaskin.\\
Løsningen kalles \textit{dottietallet} og er oppkalt etter en professor i fransk.
Professor Dottie var gift med en matematiker, 
og oppdaget at hvis hun skrev inn et tilfeldig tall på kalkulatoren hans
og trykket gjentatte ganger på cosinusknappen,
endte hun alltid opp på omtrent $0.739085$.
%\\[-3mm]
\end{minipage}
\begin{minipage}{8cm}
\hspace{5mm}
\includegraphics[scale=.42]{../figurer/dottie.png}
\end{minipage}

\begin{oppgave}{2}
Gjenta Dotties eksperiment i Python. (Nå er det antagelig på tide å lære seg for-løkke.)
\end{oppgave}

Før vi går videre kan vi ta et sitat av en stor matematiker:


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

Konseptet \say{datamaskin som kan generere prediksjon} er ganske gammelt,\footnote{\url{https://en.wikipedia.org/wiki/Antikythera_mechanism}}
og et helt uunværlig verktøy for å løse små og store matematiske problemer.
En av de klassiske teknikkene for å løse uløselige likninger
kalles \textbf{fikspunktiterasjonen},
og det var denne Professor Dottie snublet over ved å trykke på cosinusknappen gjentatte ganger.
Hun oppdaget at rekursjonen
\[
x_{n+1}=\cos{x_n}
\]
lager en følge som 
sakte men sikkert konvergerer mot den korrekte løsningen $L\approx 0.739085$.
Fikspunktiterasjonen har vært i bruk i tusener av år,\footnote{\url{https://en.wikipedia.org/wiki/Fixed-point_iteration}}
og er et eksempel noe som kalles en
\textbf{numerisk likningsløser}.
Dette er noe som produserer en følge $\{x_n\}$ som sakte men sikkert
jobber seg inn mot løsningen til en likning. 
Det er nyttig å kjenne til numeriske likningsløsere, 
slik at man ikke blir stående fast bare fordi man støter på en likning som er umulig å løse med penn og papir.


\begin{oppgave}{3}
Gjenta professor Dotties eksperiment i Python,
men legg inn noe som teller hvor mange iterasjoner 
det tar før det stabiliserer seg på $L\approx 0.739085133215161$. 
\end{oppgave}

\begin{center}
\includegraphics[scale=.27]{../figurer/L1016490}
\end{center}

Nå er det antagelig på tide å innføre en ny type funksjon
som kalles en \textbf{følge}.
Dette er en funksjon fra $\mathbb{N}$ til $\mathbb{R}$ eller $\mathbb{C}$.
Vanligvis er følgen gitt ved en \textbf{rekursjon}:
\[
    x_{n+1} = f\left( x_n \right)
\]
og en initialverdi $x_0$.
Spørsmålet
er nesten alltid hva følgen konvergerer til.
Vi sier at en følge $\{x_n\}$ er \textbf{konvergent} dersom det finnes en $L$ slik
at det for enhver $\epsilon>0$ finnes $N$ slik at $n>N$ impliserer
\[
|x_n-L|<\epsilon.
\]
\begin{minipage}{9cm}
Dette er en definisjon som får mange studenter til å fryse på ryggen.
Men det er dessverre den eneste måten å gjøre det på slik at alt blir presist.
Tenk på $L$ som løsningen til $x=\cos x$,
og på $\epsilon$ som vilkårlig valgt bitte lite tall.
Konvergens betyr at alle ledd etter ledd nummer $N$  ligger nærmere $L$ enn $\epsilon$,
og at du kan finne en slik $N$ uansett hvor liten $\epsilon$ velges.
\end{minipage}
\begin{minipage}{8cm}
\begin{center}
\includegraphics[scale=.4]{../figurer/konvergens-1}
\end{center}
\end{minipage}

Fikspunktiterasjonen er gitt ved rekursjonen
\[
x_{n+1}=g\left(x_n\right),
\]
og den produserer en følge som av og til konvergerer mot en løsning av likningen
\[
x=g(x).
\]
Om fikspunktiterasjonen konvergerer til noe fornuftig,
kommer an på $g$ og på $x_0$.
Nøyaktig når den konvergerer,
skal vi komme tilbake til.
Nå tar vi noen flere eksempler.

\begin{oppgave}{4}
Likningen
\[
x\ln x=1
\]
kan skrives om til formen
\[
x=g(x)
\]
på minst to forskjellige måter.
Finn de to åpenbare,
og prøv fikspunktiterasjonen
\[
x_{n+1}=g(x_n)
\]
på begge. 
Hvor mange iterasjoner før du når \textbf{maskinpresisjon}, altså $\epsilon \approx 10^{-16}$?\footnote{\url{https://en.wikipedia.org/wiki/Double-precision_floating-point_format}}
\end{oppgave}


\begin{center}
\includegraphics[scale=.2]{../figurer/M-5-2}
\end{center}

Det finnes mange numeriske likningsløsere.
En annen klassiker er \textbf{Newtons metode}.
Denne baserer seg på at likningen som skal løses er skrevet på formen
\[
f(x)=0.
\]
Den leter altså etter nullpunkter til funksjoner,
og er gitt ved
\[
x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}.
\]

\begin{oppgave}{5}
Løs likningen $x=\cos x$ med Newtons metode og tell antall iterasjoner slik som i oppgave 3. 
(Du må skrive om likningen litt.)
Hva ser du?
\end{oppgave}

Det første elementet $x_0$  i følgen kalles \textbf{initialgjetningen}.
Alle numeriske likningsløsere trenger en slik for å komme igang. 
Noen numeriske likningsløsere er mer sensitive på initialgjetningen enn andre,
og forskjellige numeriske likningsløsere oppfører ganske ulikt.

\begin{oppgave}{6}
Løs likningen $x=\cos x$ med både Newtons metode og fikspunktiterasjonen og eksperimenter med forskjellige initialgjetninger.
Hva skjer om $x_0=4$ eller større?
\end{oppgave}

\begin{oppgave}{7}
Gjenta for $x=\ln x$.
\end{oppgave}


Nå tar vi en oppgave fra den virkelige verden. 
Denne er visst en klassiker borte på maskin.

\begin{oppgave}{8}
  La $h$ være vannstanden i et kloakkrør med radius $1$ m, og la $h =
  \cos \theta$.
  
  \begin{minipage}{7cm}
Når vannet fyller $75$ \% av rørets tverrsnitt, 
løser $\theta$  ligningen
  \[
    2\sin 2\theta + \pi - 4\theta = 0.
  \]
  Finn vannstanden $h$ med fikspunktiterasjonen og Newtons metode.
  \end{minipage}
\begin{minipage}{9cm}
  \begin{center}
    \begin{tikzpicture}[thick]
      \draw[->] (-1.5,0) -- (1.5,0) node[right]{$x$};
      \draw[->] (0,-1.5) -- (0,1.5) node[above]{$y$};
      \filldraw[fill=blue!75!white,fill opacity=0.55] (-0.866,0.5)
        [snake=coil,segment aspect=0,segment amplitude=1pt] --
        (0.866,0.5) arc(30:-210:1cm);
      \draw (0,0) circle (1cm);
      \node[below right] at (1,0){$1$};
      \node[below left] at (-1,0){$-1$};
      \node[above left] at (0,1){$1$};
      \node[below left] at (0,-1){$-1$};
      \node[draw,fill=white,align=center] at (0,0){$75$ \%};

      \begin{scope}[xshift=3cm,yshift=-1cm]
          \draw[->] (-0.5,0) -- (2.5,0) node[right]{$x$};
          \draw[->] (0,-0.25) -- (0,2.5) node[above]{$y$};
          \draw (2,0) arc(0:90:2cm);
          \draw (0,0) -- (2*0.866,1);
          \draw[snake=coil,segment aspect=0,segment amplitude=1pt]
            (0,1) -- (2*0.866,1);
          \draw (0,0.35) arc(90:30:0.35cm)
            node[above,xshift=-0.05cm,yshift=0.05cm]{$\theta$};
          \draw[snake=brace] (-0.05,0) --
            node[left,xshift=-0.05cm]{$h$} (-0.05,1);
          \node[below] at (2,0){$1$};
          \node[left] at (0,2){$1$};
      \end{scope}
    \end{tikzpicture}
  \end{center}
  \end{minipage}
(Figur: Marius Thaule.)
\end{oppgave}

\begin{oppgave}{9}
Likningen 
$
x^3+x^2+x+1=0
$
har en reell og to komplekse røtter.
Du kan finne disse numerisk,
men du må fortelle Python at du har til hensikt å jobbe 
med komplekse tall og skrive initialgjetningen som $1+0*1j$.
Prøv å finne alle.
\end{oppgave}


\begin{center}
\includegraphics[scale=.2]{../figurer/L1008001-Pano}
\end{center}

Når vi først er inne på det:
Det finnes en klasse av funksjoner som er spesielt gunstige.
De heter \textbf{polynomer},\footnote{Studenter har flere ganger foreslått at jeg bytter fornavn til Poly.}
og er funksjoner på formen
\[
p(x)=a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+\cdots+a_2x^2+a_1x+a_0.
\]
Dersom $a_n\neq 0$ sier vi at polynomet har orden $n$.
Det var Rene Descartes som introduserte denne notasjonen på 1600-tallet en gang.
Fordelen med polynomer er at de er enkle å analysere.
Tallene $a_n,\, a_{n-1},\cdots, a_0$ kalles \textbf{koeffisientene}.

Vi sier at en tallmengde er algebraisk lukket dersom alle 
polynomer med koeffisienter fra tallmengden har et nullpunkt.
Dette er ikke sant for $\mathbb R$,
for eksempel finnes det ingen $x\in \mathbb R$ slik at
\[
x^2+2x+2=0,
\]
men den neste tallmengden i matryosjkaen vår, 
$\mathbb C$, er derimot algebraisk lukket.
Jean-Robert Argand (en amatørmatematiker!)\footnote{\url{https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra}}
beviste i 1806 at vi alltid kan faktorisere slik:
\[
z^n+a_{n-1}z^{n-1}+\cdots+a_1 z+a_0=\prod_{i=1}^n (z-z_i)
\]
der $z_i \in \mathbb C$ er løsninger av likningen
\[
z^n+a_{n-1}z^{n-1}+...+a_1 z+a_0=0.
\]

Dette er altfor vanskelig å bevise for oss,
men kan være artig å kjenne til fra tid til annen.


\begin{oppgave}{10}
Vi vet jo at det kan være vanskelig å finne nullpunktene til et polyom, 
men nå vet vi ihvertfall at de finnes.
Her kan numeriske likningsløsere være til hjelp.
Faktoriser polynomet
\[
x^3+x^2-3x-3=0.
\]
\end{oppgave}

\begin{oppgave}{11}
Her er en oppgave som slenger ut noen spørsmål vi kan svare på mot slutten av semesteret.
Polynomene 
\[
p(x)=x^4-10x^3+35x^2-50x+24
\]
og 
\[
q(x)=x^4-9x^3+27x^2-31x+12
\]
har begge nullpunkt i $x=1$. 
Prøv å finne nullpunktene med Newtons metode med startverdi $x_0=1/2$, 
og noter deg hvor mange iterasjoner som trengs for både $p$ og $q$. 
\end{oppgave}

\begin{center}
\includegraphics[scale=.11]{../figurer/L1008023-Pano}
\end{center}

Her kommer en utledning av Newtons metode.
Newtons metode baserer seg på at likningen er skrevet på formen
\[
f(x)=0.
\]

\begin{minipage}{100mm}
Den leter etter nullpunkter til funksjoner. 
La oss si at nullpunktet vi leter etter kalles $r$
og at vi har en tilnærming $x_0$ til $r$,
og så slår vi tangenten til $f$ i $x_0$.
Punktet der tangenten skjærer $x$-aksen,
kaller vi $x_1$. 
Dette punktet kan vi finne ved å sette opp likningen for tangenten til $f$ i $x_0$:
\[
y-f(x_0)=f'(x_0)(x-x_0)
\]
og så kreve at $y=0$ i denne likningen:
\[
-f(x_0)=f'(x_0)(x_1-x_0)
\]
Løser vi denne likningen for $x_1$, får vi at
\[
x_1=x_0-\frac{f(x_0)}{f'(x_0)}.
\]
%\begin{center}
%\begin{tikzpicture}[scale=2]
%      \draw[->] (0,0) -- (3.2,0) node[right] {$x$};
%      \node[anchor=west] at (.5,-.4) {$r$};
%      \node[anchor=west] at (1.6,1.7) {$f$};
%      \draw[scale=0.5,domain=0:5,smooth,variable=\x,blue] plot ({\x},{.2*(\x*\x-2)});
%%      \draw[scale=0.5,domain=-3:3,smooth,variable=\y,red]  plot ({\y},{\y});
%\end{tikzpicture}
%\end{center}       
\end{minipage}
\begin{minipage}{50mm}
\begin{center}
\begin{tikzpicture}[scale=2]
      \draw[->] (0,0) -- (3.2,0) node[right] {$x$};
      \node[anchor=west] at (.5,-.4) {$r$};
      \node[above right] at (.6,-.11){$\circ$};      
      \node[anchor=west] at (1.8,-.4) {$x_0$};
      \node[above right] at (1.8,-.11){$\circ$};      
      \node[anchor=west] at (1,-.4) {$x_{1}$};      
      \node[above right] at (1.02,-.11){$\circ$};      
      \node[above right] at (1.86,1.24){$\circ$};      
      \node[anchor=west] at (1.6,1.7) {$f$};
      \node[anchor=west] at (2,1.35) {$(x_0,f(x_0))$};
      \draw[scale=0.5,domain=0:5,smooth,variable=\x,blue] plot ({\x},{.2*(\x*\x-2)});
      \draw[scale=0.5,domain=1:5,smooth,variable=\y,red]  plot ({\y},{1.6*(\y-4)+14/5});
\end{tikzpicture}
\end{center}
\end{minipage}

Dersom $f$ og $x_0$ ser ut slik som i figuren, 
vil $x_1$ ligge nærmere nullpunktet enn $x_0$,
og det trengs ikke så stor fantasi for å se at $x_2$ vil legge seg nærmere nullpunktet enn $x_1$.
Newtons metode er definert som den rekursive følgen
\[
x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}.
\]
Denne utledningen er litt for vanskelig til at du og jeg ville klart å komme på det selv som nittenåringer. 
Derfor lager jeg heller en oppgave som heter

\begin{oppgave}{12}
Denne utledningen kan du bli spurt om på eksamen og da må du kunne den. 
\end{oppgave}

\begin{center}
\includegraphics[scale=.4]{../figurer/img20220809_10524150}
\end{center}

\clearpage


Hvis du husker \textbf{sekantsetningen},
som sier at dersom en funksjon $f$ er deriverbar på et intervall som inneholder $a$ og $b$,
finnes en $c$ mellom $a$ og $b$ slik at
\[
    f'(c) = \frac{f(b) - f(a)}{b-a}
\]
er det mulig for deg å forstå slike ting som hvorfor fikspunktiterasjonen noen ganger konvergerer fort,
noen ganger sakte,
og noen ganger ikke i det hele tatt.

 \begin{center}
    \begin{tikzpicture}[thick]
     % \draw[blue] (-2,0) circle (2cm) ;
   %   \draw[red] (0,-1) circle (1.5cm);

 \draw[thick] (0,.7) sin (7,4);
  \draw[thick] (7,4) sin (8,3);
 \node[above] at (7,3){$f$};

\draw[thick,red] (0,1.2) -- (7,4.1) node[right]{sekant};
\draw[thick,blue] (0,1.65) -- (7,4.55) node[right]{tangent};

   %   \begin{scope}[xshift=5cm,yshift=-1cm]
\node[below] at (1.6,.7){$a$};
\node at (1.6,.98){$\circ$};

\node[below] at (4.4,.7){$c$};
\node at (4.4,.98){$\circ$};


\node[below] at (6.7,.7){$b$};
\node at (6.7,.98){$\circ$};

\node[left] at (0,1.87){$f(a)$};
\node at (0.005,1.87){$\circ$};


\node[left] at (0,4){$f(b)$};
\node at (0.005,4){$\circ$};

%\draw[-] (0,4) -- (8,4);

%\draw[-] (2.4,0) -- (2.4,5);
          \draw[->] (0,1) -- (8,1);
%                    \draw[->] (3.45,0) -- (3.45,4);
          \draw[->] (0,1) -- (0,4.5) ;
    \end{tikzpicture}
  \end{center}



Dersom $g$ er deriverbar på et intervall som inneholder
både $x_n$ og $r$,
sier sekantsetningen at det må finnes en $s$ mellom disse to slik at
\[
g'(s)=\frac{g(x_n)-g(r)}{(x_n-r)}=\frac{x_{n+1}-r}{(x_n-r)}
\]
som gir at
\[
x_{n+1}-r=g'(s)(x_n-r).
\]
Denne likningen forteller oss noe om avstanden mellom iterasjonene og løsningen $r$,
og vi ser nå at det kan være lurt å ha peiling på hvorvidt
$|g'| < 1$ før vi programmerer opp og trykker på kjør.
Hvis $|g'| > 1$ kan det være det ikke konvergerer i det hele tatt.


\begin{oppgave}{13}
	I oppgave 4 over,
    var de to åpenbare omskrivningene $x=1/\ln x$ og $x = e^{1/x}$.
    Bruk din nye kunnskap til å spå på forhånd (1) hvilken av disse omskrivningene som kommer til å funke og
    (2) hvilke startverdier som funker for den omskrivningen som funker.\\
\end{oppgave}

En liknende analyse av Newtons metode vil forklare hvorfor denne som regel konvergerer fortere.
Men denne analysen må vi vente med,
for vi trenger litt mere maskineri først.
Dette maskineriet kalles Taylors teorem og kommer mot slutten av semesteret.

\reversemarginpar\marginnote{\includegraphics[scale=.08]{../figurer/herrdummefjes-2}}[7mm]

\begin{oppgave}{Nøtt}
I forrige uke var vi innom kurvene
\[
    C =  x + y - \ln|x| - \ln|y|
\]
Du kan plotte disse selv fra scratch ved å skrive en rutine med en for-løkke som løper gjennom  forskjellige verdier av $x$,
og så en løkke innafor der som leter etter korresponderende $y$-verdier med Newtons metode.
Kjører du denne for forskjellige verdier av $C$,
kan du reprodusere figuren som matplotlib.pyplot.contour lager.

	Prøv dette. Det holder å styre på i første kvadrant.
\end{oppgave}

\clearpage

\begin{comment}

\section*{HVA SKAL DU MED DETTE?}

\subsubsection*{LIKEVEKTSKONSENTRASJONER}


\begin{oppgave}{1}
Dersom man skal finne likevektskonsentrasjoner, 
ender man ofte opp med å måtte løse en ikkelineær likning. 
For eksempel må man løse likningen 
\[
K_c=\frac{16x^3}{\left(1-4x\right)^2}
\]
dersom man skal finne likevektskonsentrasjonene i 
\[
\ce{2NOCl(g) <=> 2NO(g) + Cl_2(g)} 
\]
Nå er det på påpiret mulig å regne ut løsningen av en tredjegradslikning for hånd, 
men det er enklere å kjøre en numerisk likningsløser.
\end{oppgave}

\begin{oppgave}{2}
Les eksempel 4.5 i Sveins notat om vandige likevekter, 
og betrakt likningen
\[
x=\left[\ce{HA}\right]_T\frac{K_a}{x+K_a}+\frac{K_w}{x}
\]
der $K_w=10^{-14}$ er dissosiasjonskonstanten til vann. 
Sett $\left[\ce{HA}\right]_T=10^{-2}$, velg din enprotiske favorittsyre, finn $K_a$ i tabellboken, og finn $x$ ved Newtons metode eller fikspunktiterasjon.
\end{oppgave}

\subsubsection*{MER OM DIODER}

Det er lett å finne frem til en krets der det vi må ty til numeriske likningsløsere. 
Du har allerede koblet den opp i ADE:
\begin{center}
	\begin{circuitikz}
		\draw  (0,3) to [V=1$V$] (0,1);
		\draw (0,3)to [R=1$\Omega$ ] (4,3) to [D] (4,1) to  (0,1);
	\end{circuitikz}
\end{center}

Vi er mest interesserte i den matematiske oppførselen til likningen, 
og derfor setter vi både
$
\frac{q}{nkT}=1
$
og $I_0=1$ slik at likningen blir 
\[
i(v)=e^v-1
\]
for det blir så greit.
Lars kan ta seg av griseriet med alle de fysiske konstantene.


\begin{oppgave}{1}
Gjør ovennevnte antagelser på dioden,
og bruk Kirchhoffs spenningslov til å utlede likningen 
\[
1=i+\ln(i+1).
\]
for strømmen i kretsen.
Denne kan ikke løses analytisk.
Bruk en numerisk likningsløser til å finne strømmen,
og noter deg hvor mange iterasjoner som trengs. 
\end{oppgave}

Kirchhoff var forresten temmelig barsk i knolten.
Han har funnet opp mye greier:\\
\url{https://no.wikipedia.org/wiki/Gustav_Kirchhoff}






\subsection*{NOEN PROBLEMER FRA KVANTEMEKANIKK}


\begin{oppgave}{1}
Når man løser partikkel i boks med ikke helt tette vegger,\footnote{\url{https://en.wikipedia.org/wiki/Finite_potential_well}}
støter man gjerne på likningen
\[
\tan \sqrt{x}=\frac{2\sqrt{x(1-x)}}{2x-1}.
\]
Finn $x$.
\end{oppgave}

\begin{minipage}{120mm}
\begin{oppgave}{2}
Når man jobber med den kvantemekaniske harmoniske oscillatoren, 
støter man visst på en situasjon der man må finne skjæringspunktet mellom kurvene gitt ved $y=\exp(-ax^2)$ og $y=bx^2$, 
der $a>0$ og $b>0$ er konstanter. 
Lag en funksjon som tar inn $a$ og $b$, 
plotter disse to funksjonene i samme plot, 
og finner skjæringspunktene med en numerisk likningsløser.
Hvorfor er det kun nødvendig å beregne det ene skjæringspunktet?
\end{oppgave}
\end{minipage}
\begin{minipage}{50mm}
\begin{center}
    \begin{tikzpicture}[thick]
      \begin{scope}[xshift=5cm,yshift=-1cm]
%\filldraw[orange, thick] (0,0) -- (.2,.01) -- (.5,.06) -- (.7,.16) -- (1,.3) -- (1.5,.71) -- (2,1.3)  -- (2,0) -- cycle;
          \draw[->] (-2,0) -- (2,0) node[right]{$x$};
         \draw[->] (0,0) -- (0,2);% node[above]{$t$};

%           \node[above] at (.5,1.7){$f(x)=x$};
%           \node[above] at (2,-.7){$x$};
      \draw[scale=1,domain=-1.3:1.3,smooth,variable=\x,black,thick] plot ({\x},{1-(\x*\x)+.5*(\x*\x*\x*\x)-0.16666666666666666*(\x*\x*\x*\x*\x*\x)+0.0416666666666666666*(\x*\x*\x*\x*\x*\x*\x*\x)-0.008333333333333333*(\x*\x*\x*\x*\x*\x*\x*\x*\x*\x)+0.001388888888888889*(\x*\x*\x*\x*\x*\x*\x*\x*\x*\x*\x*\x)});
      \draw[scale=1,domain=-1.3:1.3,smooth,variable=\x,black,thick] plot ({\x},{(\x*\x)});
       \end{scope}
    \end{tikzpicture}
 \end{center}
\end{minipage}


\subsection*{UKENS NØTTER}

\begin{oppgave}{1}
Utled likningen 
  \[
    2\sin 2\theta + \pi - 4\theta = 0
  \]
  i kloakkrøroppgaven over.
\end{oppgave}


\begin{oppgave}{2}
Følgende oppgave illustrerer Georg Cantors konstruksjon av $\mathbb R$,
nemlig ved å lage ekvivalensklasser av cauchyfølger.\footnote{\url{https://en.wikipedia.org/wiki/Construction_of_the_real_numbers}}
Løs likningen 
\[
x^2-2=0
\]
med Newtons metode, 
og svar på følgende to spørsmål:
\begin{itemize}
\item Er det sant at $x_n\in \mathbb Q$ for alle $n$ dersom $x_0\in \mathbb Q$?
\item Dersom $\{x_n\}$ konvergerer, 
konvergeres det mot et rasjonalt tall?
\end{itemize}
\end{oppgave}


%\section*{MVT}
\begin{oppgave}{3}
Følgende er en modell for matauk,
og kalles marginalverditeoremet (marginal value theorem).\footnote{\url{https://en.wikipedia.org/wiki/Marginal_value_theorem}}
En stær noe slikt mater ungene sine ved å plukke mark fra et sted i nærheten. 
La $x=x_0$ være tidspunktet den forlater redet, 
og $x=0$ tiden den ankommer stedet der den plukker mark.
Funksjonen $f$ beskriver hvor mye mat den får med seg. 
Denne kurven flater ut når tiden øker, 
for etterhvert som stæren fyller nebbet med mark, 
blir det vanskeligere og vanskeligere å fange nye mark. 


\begin{minipage}{90mm}
Stæren ønsker å maksimere forholdet mellom total tid borte fra redet og mengde hjembrakt mat. 
Tidspunktet $x=x_1$ når den setter nebbet hjemover, 
er tidspunktet når dette forholdet er maksimert. 
Vis at tangenten til $f$ i $x_1$ skjærer $x$-aksen i $x_0$.
\end{minipage}
\begin{minipage}{50mm}
 \begin{center}
    \begin{tikzpicture}[thick]

\draw[thick,blue] (-2,1) -- (2.8,2.65) node[right]{tangent};

   %   \begin{scope}[xshift=5cm,yshift=-1cm]
\node[below] at (1.3,.7){$x_1$};
\node at (1.3,.98){$\circ$};

\node[below] at (-2,.7){$x_0$};
\node at (-2,.98){$\circ$};

\draw[smooth, domain=0.1:2.3, color=black, thick] 
    plot (\x,{.3*log2(\x)+2}) node [right] {\footnotesize $f$};
 

          \draw[->] (-3,1) -- (3,1) node [right] {tid};
          \draw[->] (0,1) -- (0,2.7) node [above] {mat};
    \end{tikzpicture}
  \end{center}
\end{minipage}
\end{oppgave}

\end{comment}

\section*{LØSNINGSFORSLAG}

\begin{oppgave}{2}
Se oppgave 6.
\end{oppgave}

\begin{oppgave}{4}
Du kan modifisere koden under til å løse dette problemet.
    Det som er interessant med oppgaven er at likningen $x\ln x=1$ kan skrives om til formen
    $x=g(x)$ på minst to forskjellige måter.
    De to åpenbare er $x=e^{1/x}$ og $x = 1/\ln x$.
    For den første formen stabiliserer fikspunktiterasjonen seg på $r \approx 1.7632228343518968$ etter
    om lag 73 iterasjoner med $x_0=0.1$,
    mens for den andre formen konvergerer det ikke for noen startverdier.
\end{oppgave}

\begin{oppgave}{6}
    Her er min kode for å beregne iterasjoner for å finne dottietallet med fikspunktiterasjon (x) og Newtons metode (y):
        \begin{lstlisting}
            import numpy as np
            x=1
            y=1

            for i in range(15):
                x=np.cos(x)
                y=y-(y-np.cos(y))/(1+np.sin(y))
                print(x,y)
        \end{lstlisting}
    Newton går bra mye fortere,
    men feiler når $x_0$ er for langt unna den korrekte løsningen.
\end{oppgave}

\begin{oppgave}{7}
Et plott av $y=x$ og $y=\ln x$ avslører at dette problemet ikke har noen løsning.
Ikke let etter løsningen før du vet at den eksisterer!
MEN: Setter du $1+1j$ som startverdi og kjører $x_{n+1} = \ln x_n$,
vil du få tak i den komplekse løsningen $r \approx 0.3181315052047577+1.3372357014306768i$
\begin{center}
\includegraphics[scale=.8]{../figurer/xlnx-1}
\end{center}

\clearpage

\end{oppgave}

\begin{oppgave}{9}
Kjører du Newtons metode med startverdi $x_0=1$ får du den reelle roten $r_1=-1$ til maskinpresisjon på om lag ti iterasjoner.
    Kjører du med startverdi $x_0 = 1 + 0i$ får du den andre roten $r_2 = i$ på rundt fem iterasjoner,
    og har du gjort oppgave 21 fra økt 1 - 1,
    vet du at reelle polynomer alltid har komplekse røtter i komplekskonjugerte par,
    så den siste må være $r_3 = -i$.
    Vi kan dermed faktorisere polynomet som
    \[
        x^3+x^2+x+1 = \left( x+1 \right)\left( x+i \right)\left( x-i \right).
    \]
\end{oppgave}

\begin{oppgave}{11}
Kjører du Newton $x_0=0$
på det første polynomet får du den reelle roten $r=1$ til maskinpresisjon på om lag ti iterasjoner.\footnote{jeg vet det sto $x_0=1/2$ i oppgaven, men det er ikke så viktig}
Men kjører du den samme startverdien på det andre polynomet,
    stabiliserer det seg på $r=0.9999999851925497$ etter om lag tredve iterasjoner.\\
    Hva skjer?
Følg med senere i semesteret.\\
(Hvis du evaluerer polynomene litt smartere i newtoniterasjonen,
får du en desimal eller to til. Google "Horner method polynomial evaluation".)
\end{oppgave}


\begin{oppgave}{13}
    Likningen
    \[
x_{n+1}-r=g'(s)(x_n-r)
\]
indikerer at det er en god ide å sjekke om $|g'|<1$.
    Hvis $x_n$ og $r$ ligger i et intervall der  $|g'|<1$,
    vil
     $x_{n+1}$ ligge nærmere $r$ enn $x_n$.
    Som erfart av oppgave 7 er det alltid en god ide å plotte de involverte funksjonene før man går igang med å lete etter løsninger,
    så la oss gjøre dette.

\begin{minipage}{75mm}
    \begin{center}
\includegraphics[scale=.4]{../figurer/xlnx-2}\\
        $g(x)=1/\ln x$
\end{center}
\end{minipage}
\begin{minipage}{80mm}
    \begin{center}
\includegraphics[scale=.4]{../figurer/xlnx-3}\\
        $g(x)=e^{1/x}$
\end{center}
\end{minipage}

På det venstre plottet er  $|g'(r)|>1$ og på det høyre er $|g'(r)|<1$.
    Med andre ord kommer $x_{n+1}=e^{1/x_n}$ til å konvergere og $x_{n+1}=1/\ln x_n$ ikke til å konvergere.
    Merk ellers at $e^{1/x}$ og $1/\ln x$ er hverandres inversfunksjoner.
    Dette gir oss et et klassisk triks;
    siden inversderivasjonsformelen er gitt ved
    \[
    \frac{d}{dx}f^{-1}(x)=\frac{1}{f'(f^{-1}(x))}
    \]
    og $r=g(r)$,
    kan du som regel finne $r$ med iterasjonen $x_{n+1}=f^{-1}\left( x_n \right)$ dersom
    $x_{n+1}=f\left( x_n \right)$ ikke funker.

    Merk ellers at $x_{0}$ ikke nødvendigvis må ligge i et intervall der $|g'|<1$ for at fikspunktiterasjonen skal konvergere.
    Iterasjonen $x_{n+1}=e^{1/x_n}$ konvergerer selv om du starter med $x_0$ mellom 0 og 1,
    for den sender $x_1$ opp i et område der $|g'|<1$.
    Starter du med $x_0<0$,
    tar det to iterasjoner.
    Hvis du er teknisk anlagt,
    kan du finne et fullstendig konvergensbevis for fikspunktiterasjonen på side 44 her:\\
    \url{https://folk.ntnu.no/mortano/notater/sivingmatte.pdf}
\end{oppgave}

\clearpage

\section*{GAMLE EKSAMENSOPPGAVER MED LØSNING}

\begin{oppgave}{1}
Gjør rede for at følgen
\[
f(n)=\frac{2+n^2}{1+n^2}
\]
konvergerer.\\[5mm]
\textbf{Løsning:}
Dersom vi ganger brøken oppe og nede med $1/n^2$,
ser vi at
\[
\lim_{n\to \infty}\frac{2+n^2}{1+n^2}=\lim_{n\to \infty}\frac{2+n^2}{1+n^2}\cdot\frac{1/n^2}{1/n^2}=\lim_{n\to \infty}\frac{2/n^2+1}{1/n^2+1}=1.
\]
Jeg tar $\epsilon$ også for å illustrere hvordan det kan gjøres.
Intuisjon og lang erfaring forteller oss at grenseverdien antagelig er $1$.
Vi velger $\epsilon>0$, og ser at
\[
\left|\frac{2+n^2}{1+n^2}-1\right|=\left|\frac{2+n^2}{1+n^2}-\frac{1+n^2}{1+n^2}\right|=\frac{1}{1+n^2} < \epsilon
\]
dersom $n > \sqrt{\frac{1}{\epsilon}-1}$.
\end{oppgave}

\begin{oppgave}{2}
Skriv et pythonscript for å løse likningen
  \begin{equation*}
    2\sin 2\theta + \pi - 4\theta = 0
  \end{equation*}
  med fikspunktiterasjonen,
  og gjør rede for hvorfor du kan forvente konvergens.

    \textbf{Løsning:}
    Fikspunktiterasjonen er
\[
x_{n+1}=g(x_n)
\]
og leter etter løsninger til likningen
\[
x=g(x).
\]
Vi må derfor begynne med å skrive om likningen til
  \[
\theta =    \frac{\sin 2\theta}{2} + \frac{\pi}{4}.
  \]
  og fikspunktiterasjonen blir
  \[
\theta_{n+1} =  \frac{1}{4} \left( 2\sin 2\theta_n+\pi\right)
  \]
Dette kan selvfølgelig gjøres på andre måter,
men vi skal se at dette her går fint.
På eksamen må du nesten skrive ned noe sånt:

\begin{center}
    \includegraphics[scale=.16]{../figurer/kode}
\end{center}

Dette føles nok litt rart,
men jeg vet ikke om noen annen effektiv måte for å sjekke hvem som har programmert og hvem som ikke har programmert.
Hvis noen har gode ideer,
er jeg åpen for diskusjon,
men i år blir det slik.
Programmering er en viktig komponent i jobben med å forstå numeriske metoder.

La oss nå se på hvorfor vi kan forvente at iterasjonen konvergerer.
For det første vil en rask sketsj av situasjonen:

\includegraphics[scale=.2]{../figurer/fikspkt}

fortelle oss at likningen bør ha en løsning et sted $\theta=0$ og $\theta=\frac{3\pi}{2}$.
Vi vet at vi kan forvente konvergens dersom $|g'|<1$ i området rundt løsningen,
og siden
\[
g'(\theta)=\cos 2\theta
\]
ser vi at $|g'(\theta)|<1$ dersom $0<\theta <\frac{3\pi}{2}$.
Hvis initialgjetningen (magefølelsen for omtrent hvor roten ligger) ligger i dette intervallet,
bør fikspunktiterasjonen konvergere.

\textbf{Kommentar:}
Det å vite at to funksjoner som skjærer hverandre faktisk skjærer hverandre,
er ikke egentlig så innlysende som det kan se ut ved første øyekast.
Skjæringssetningen sier at dersom $f:\mathbb R \to \mathbb R$ er en kontinuerlig funksjon på $[a,b]$, og at $f(a)<f(b)$
og $f(a)<c<f(b)$, finnes en $x \in [a,b]$ slik at $f(x)=c$.
Men her er det særdeles viktig at definisjonsmengden til $f$ er $\mathbb R$ og ikke for eksempel $\mathbb Q$.
Funksjonen $f:\mathbb Q \to \mathbb Q$ gitt ved $f(x)=x^2$ vil for eksempel aldri ta verdien 2,
for det finnes jo ingen rasjonale tall $x$ slik at $x^2=2$.

Når det gjelder fikspunkiterasjonens konvergens,
har vi et teorem som sier at
dersom $g$ er en kontinuerlig deriverbar funksjon med
både  $a<g(x)<b$ og $|g'(x)| \leq L < 1$ på på $[a,b]$,
konvergerer fikspunktiterasjonen
\[
x_{n+1}=g(x_n)
\]
mot $r$ dersom $x_0 \in [a,b]$.

Dette følger av Taylors teorem.
La oss anta at $x_n \in (a,b)$.
Vi bruker taylors teorem på $g$ i $r$, og skriver
\[
g(x_n)= g(r)+g'(s)(x_n-r)
\]
for en $s$ mellom $x_n$ og $r$. Hvis vi bruker at $r=g(r)$ og $x_{n+1}=g(x_n)$, kan vi skrive
\[
x_{n+1}-r=g(x_{n})-g(r)=g'(s)(x_n-r).
\]
Vi tar absoluttverdi på begge sider,
og bruker at $|g'(s)| \leq L < 1$, siden $s \in (a,b)$:
\[
|x_{n+1}-r|=|g'(s)(x_n-r)| \leq L|x_n-r| \leq L^{n+1} |x_0-r|
\]
Lar vi så $n\to \infty$, får vi
\[
\lim_{x \to \infty}|x_{n+1}-r| \leq  |x_0-r|\lim_{x \to \infty} L^{n+1}=0,
\]
siden $L < 1$.

\end{oppgave}

\end{document}
