\input{preamble}

\title{1 - 11 - LIKNINGER - LF}

%tvilling

\begin{document}
\pagenumbering{gobble}

\maketitle

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

\begin{oppgave}{3-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}{5-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=.7]{../figurer/xlnx-1}
\end{center}
\end{oppgave}

\clearpage

\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}{10-13}
    Det er lett å modifisere koden fra oppgave 6 til å løse alle disse. 
\end{oppgave}

\begin{oppgave}{16}
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}{18}
    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=.35]{../figurer/xlnx-2}\\
        $g(x)=1/\ln x$
\end{center}
\end{minipage}
\begin{minipage}{80mm}
    \begin{center}
\includegraphics[scale=.35]{../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}

\begin{oppgave}{19}
    Denne hadde vi på konten i august, se oppgave 5:\\
    \url{https://mortano.folk.ntnu.no/eksamen/tma4101-23k-lf.pdf}
\end{oppgave}

\begin{oppgave}{20}
    Dersom
    \[
    \lim_{n\to \infty} x_n=L_1
    \quad \text{og} \quad
    \lim_{n\to \infty} y_n=L_2
    \]
    er 
    \begin{align*}
    \lim_{n\to \infty} x_n+y_n&=L_1+L_2.
    \end{align*}
    Velg $\epsilon$. 
    Vi må vise at det går an å velge $N$ slik at $n>N$ impliserer
    \[
    |x_n+y_n-L_1-L_2|< \epsilon 
    \]
    Merk først at 
    \begin{align*}
    |x_n+y_n-L_1-&L_2|=  \\[2pt]
    |x_n-L_1+&y_n-L_2|\leq  \\[2pt]
    |x_n-&L_1|+|y_n-L_2|
    \end{align*}
    Siden $z$ konvergerer mot $L_1$, og $w$ mot $L_2$, 
    kan vi velge  $N$ slik at $n > N$ impliserer 
    \[
    |x_n-L_1|< \epsilon/2
    \]
    og 
    \[
    |y_n-L_2|< \epsilon/2.
    \]
    Men i så fall impliserer $n<N$ at 
    \begin{align*}
    |x_n-L_1+y_n-L_2|< \epsilon/2+\epsilon/2=\epsilon,
    \end{align*}
    som var det vi skulle vise. 
\end{oppgave}

\begin{oppgave}{21}
    Siden 
    \begin{align*}
        \frac{2(n+1)}{n} = 
        \frac{n+1}{n} + 
        \frac{n+1}{n} 
    \end{align*}
    følger det fra forrige oppgave at denne grenseverdien må være 2.
\end{oppgave}

\begin{oppgave}{22}
    Velg $\epsilon$. 
    Vi må vise at det går an å velge $N$ slik at $n>N$ impliserer
    \[
    |ax_n-aL|< \epsilon.
    \]
    Men dette er trivielt siden 
    \[
    |ax_n-aL| = |a| \cdot |x_n - L|, 
    \]
    så vi kan velge $N$ slik at $n>N$ impliserer $|x_n-L|< \epsilon/|a|$ 
    og så har vi at $|ax_n-aL|< \epsilon$ dersom $n>N$. 
\end{oppgave}

\begin{oppgave}{23}
    Jepsi pepsi. 
    Bytt ut alle absoluttverditegn med kompleks modulus og så er du gudd. 
\end{oppgave}


\begin{comment}
\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{comment}


\end{document}
