# Følger og iterative metoder ## Del 0 · Hva en følge er En følge er en funksjon med de naturlige tallene som definisjonsmengde. I stedet for $f(n)$ skriver vi vanligvis $a_n$: $$ a:\mathbb N\to\mathbb R, \qquad n\mapsto a_n. $$ Følgen $a_n=1/n$ gir leddene $$ 1,\frac12,\frac13,\frac14,\ldots $$ Indekseringen må alltid kontrolleres. Noen følger starter med $a_0$, andre med $a_1$. Startindeksen påvirker startverdiene i rekursive formler. ### Eksplisitt og rekursiv form En eksplisitt formel gir $a_n$ direkte fra $n$. Eksempel: $$ a_n=2^n. $$ En rekursiv formel lager neste ledd fra tidligere ledd. Den samme følgen kan skrives $$ a_{n+1}=2a_n,\qquad a_0=1. $$ Startverdien er en del av definisjonen. Uten $a_0$ finnes uendelig mange følger som oppfyller $a_{n+1}=2a_n$. ## Del 1 · Begrensning, monotoni og oscillasjon En følge er begrenset oppover hvis det finnes et tall $M$ slik at $a_n\le M$ for alle $n$. Den er begrenset nedover hvis det finnes et tall $m$ slik at $m\le a_n$ for alle $n$. En følge er monoton voksende når $a_{n+1}\ge a_n$ for alle relevante $n$. Den er monoton avtakende når $a_{n+1}\le a_n$. ![Punktene viser en voksende følge, en avtakende følge og en følge som oscillerer.](/guide-img/matte1/sequence-behaviors.svg) Den vanligste testen for monotoni er å undersøke $$ a_{n+1}-a_n. $$ Hvis alle differansene er positive, er følgen voksende. Hvis alle er negative, er den avtakende. For positive følger kan det noen ganger være enklere å undersøke forholdet $a_{n+1}/a_n$. ::: oppgave **Oppgave.** Vis at $a_n=n/(n+1)$ er voksende og begrenset oppover. ::: losning Vi sammenligner to naboledd: $$ a_{n+1}-a_n =\frac{n+1}{n+2}-\frac n{n+1} =\frac{(n+1)^2-n(n+2)}{(n+1)(n+2)} =\frac1{(n+1)(n+2)}>0. $$ Følgen er derfor voksende. Videre er $n0$ finnes et naturlig tall $N$ slik at $$ n>N\quad\Longrightarrow\quad |a_n-L|<\varepsilon. $$ ::: $\varepsilon$ er en feilmargin som kan velges så liten vi ønsker. $N$ forteller hvor langt ut i følgen vi må gå før alle senere ledd ligger innenfor feilmarginen. ![Etter indeksen N ligger alle leddene i epsilonbåndet rundt L og blir værende der.](/guide-img/matte1/epsilon-band.svg) Det holder ikke at følgen kommer nær $L$ noen ganger. Den må bli værende nær $L$ etter et bestemt punkt. ::: oppgave **Oppgave.** Vis fra definisjonen at $a_n=1/n$ konvergerer mot $0$. ::: losning Vi tar det baklengs. Målet er at avstanden fra $a_n$ til $0$ skal bli mindre enn den feilmarginen $\varepsilon$ som noen velger: $$ \left|\frac1n-0\right|=\frac1n<\varepsilon. $$ Spørsmålet er derfor: **Hvor stor må $n$ være for at $1/n<\varepsilon$?** Siden $n$ og $\varepsilon$ er positive, kan vi snu ulikheten: $$ \frac1n<\varepsilon \quad\Longleftrightarrow\quad n>\frac1\varepsilon. $$ Velg et heltall som ligger minst så langt ute, for eksempel $$ N=\left\lceil\frac1\varepsilon\right\rceil. $$ Symbolet $\lceil\cdot\rceil$ betyr «rund opp til nærmeste heltall». Hvis $\varepsilon=0.1$, kan vi velge $N=10$; alle $n>10$ gir $1/n<0.1$. Hvis $\varepsilon=0.001$, kan vi velge $N=1000$. For en hvilken som helst positiv $\varepsilon$ vil altså $n>N$ gi $$ \left|\frac1n-0\right|<\varepsilon. $$ Det er akkurat definisjonen på at $1/n$ konvergerer mot $0$. ::: ### Regneregler for grenser Hvis $a_n\to A$ og $b_n\to B$, gjelder $$ a_n+b_n\to A+B, $$ $$ a_nb_n\to AB, $$ $$ \frac{a_n}{b_n}\to\frac AB $$ så lenge $B\ne0$ og nevnerne ikke er null fra et punkt og videre. En konvergent følge er alltid begrenset. Det motsatte er ikke sant, som $(-1)^n$ viser. ## Del 4 · Monoton konvergens ::: definisjon Teoremet om monotone og begrensede følger En monoton voksende følge som er begrenset oppover, konvergerer. En monoton avtakende følge som er begrenset nedover, konvergerer. ::: Teoremet kobler monotoni til kompletthet. En voksende følge har ingen lov til å gå nedover. Hvis den samtidig har et tak, må leddene samle seg ved den minste øvre skranken. ::: bevis Hvorfor en voksende og begrenset følge konvergerer La $M=\{a_1,a_2,\ldots\}$. Mengden er ikke tom og begrenset oppover. Kompletthet gir et tall $$ L=\sup M. $$ La $\varepsilon>0$. Tallet $L-\varepsilon$ kan ikke være en øvre skranke, for $L$ er den minste øvre skranken. Derfor finnes en indeks $N$ slik at $$ a_N>L-\varepsilon. $$ Følgen er voksende, så for alle $n\ge N$ er $$ a_n\ge a_N>L-\varepsilon. $$ Samtidig er $L$ en øvre skranke, så $a_n\le L1$, vokser den. Ti prosent vekst per steg betyr $q=1.10$; ti prosent nedgang betyr $q=0.90$. ::: funfact Newtons avkjølingslov som differenslikning En varm kopp kaffe mister vanligvis varme omtrent i takt med temperaturforskjellen til rommet. Måler vi temperaturen hvert minutt, kan vi bruke modellen $$ T_{n+1}=T_n-k(T_n-T_{\text{rom}}), \qquad 0\sum_{j\ne i}|a_{ij}| $$ for hver rad. Den presise matrisetesten er at spektralradien til iterasjonsmatrisen $-D^{-1}R$ er mindre enn $1$. ## Del 10 · Newtons metode og konvergensorden Newtons metode finner nullpunkter til $f(x)$: $$ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}. $$ Metoden bruker tangentlinjen ved $x_n$. Der tangenten treffer $x$ aksen, får vi $x_{n+1}$. ::: visualpair ![Newtons metode på x i andre minus 2. Tangenten i x null treffer x aksen i x en, som blir den neste tilnærmingen.](/guide-img/matte1/newton-method.svg) ::: side Én Newton-runde Ved punktet $(x_n,f(x_n))$ har tangenten stigning $f'(x_n)$. Tangentligningen er $$ y-f(x_n)=f'(x_n)(x-x_n). $$ Sett $y=0$ for å finne hvor tangenten treffer $x$-aksen. Løsningen er $$ x=x_n-\frac{f(x_n)}{f'(x_n)}=x_{n+1}. $$ ::: ::: oppgave **Oppgave 1.** Bruk to Newton-steg på $f(x)=x^2-2$ med $x_0=1.5$. ::: losning Her er $f'(x)=2x$, så $$ x_{n+1}=x_n-\frac{x_n^2-2}{2x_n} =\frac12\left(x_n+\frac2{x_n}\right). $$ Første steg gir $$ x_1=\frac12\left(1.5+\frac2{1.5}\right) \approx1.4166667. $$ Andre steg gir $$ x_2=\frac12\left(1.4166667+\frac2{1.4166667}\right) \approx1.4142157. $$ Allerede etter to steg har vi fem riktige desimaler av $\sqrt2\approx1.4142136$. ::: ::: oppgave **Oppgave 2.** Finn nullpunktet til $f(x)=\cos x-x$ med $x_0=1$ og tre Newton-steg. ::: losning Den deriverte er $$ f'(x)=-\sin x-1. $$ Newton-formelen blir $$ x_{n+1}=x_n-\frac{\cos x_n-x_n}{-\sin x_n-1}. $$ Med radianer på kalkulatoren får vi $$ x_1\approx0.7503639, \qquad x_2\approx0.7391129, \qquad x_3\approx0.7390851. $$ Kontroll: $\cos(0.7390851)\approx0.7390851$, så tallet er både et nullpunkt for $\cos x-x$ og et fikspunkt for $\cos x$. ::: ### Feil og konvergensorden Hvis den eksakte løsningen er $r$, definerer vi feilen $$ e_n=|r-x_n|. $$ Feilen er den faktiske avstanden fra tilnærmingen til svaret. Hvis $r=\sqrt2$ og $x_n=1.4$, er $$ e_n=|\sqrt2-1.4|\approx0.0142. $$ Vi kjenner vanligvis ikke $r$ når vi regner. I praktiske stoppkriterier ser vi derfor ofte i stedet på $|x_{n+1}-x_n|$ eller $|f(x_n)|$. En metode har konvergensorden $q$ når $$ \frac{e_{n+1}}{e_n^q}\longrightarrow C $$ for en konstant $C>0$. Tallet $q$ forteller hvor dramatisk en liten feil krymper når vi tar ett nytt steg: | Orden | Omtrentlig regel nær løsningen | Hva du merker | |---|---|---| | $q=1$ | $e_{n+1}\approx Ce_n$, $02$ | $e_{n+1}\approx Ce_n^q$ | enda raskere lokal konvergens | Eksempel: Dersom en lineær metode har $C=0.1$ og feilen er $10^{-2}$, blir neste feil omtrent $10^{-3}$. En kvadratisk metode med $C\approx1$ ville fra samme feil gi omtrent $(10^{-2})^2=10^{-4}$. Ved lineær konvergens er $q=1$. Feilen reduseres omtrent med en fast faktor. Ved kvadratisk konvergens er $q=2$. Feilen blir omtrent proporsjonal med kvadratet av forrige feil. Vanlig fikspunktiterasjon har ofte lineær konvergens når $0<|g'(r)|<1$. Hvis $g'(r)=0$, kan ordenen bli høyere. Newtons metode har vanligvis kvadratisk konvergens nær en enkel rot når $f'(r)\ne0$ og funksjonen er tilstrekkelig glatt. For iterasjonen $$ g(x)=\frac12\left(x+\frac2x\right) $$ som finner $\sqrt2$, er $g'(\sqrt2)=0$. En Taylor-analyse gir $$ \frac{e_{n+1}}{e_n^2} \longrightarrow \frac12|g''(\sqrt2)| =\frac1{2\sqrt2} \approx0.3536. $$ Det er den presise betydningen av kvadratisk konvergens her: når vi er nær nok roten, er neste feil omtrent $0.3536$ ganger kvadratet av den forrige. ## Det viktigste å ta med seg - En følge kan være begrenset, monoton, konvergent eller oscillerende. - Epsilondefinisjonen krever at alle ledd etter en indeks blir værende nær grensen. - Kompletthet gir supremum og infimum og driver teoremet om monoton konvergens. - En rekursjon trenger startverdier og kan modellere vekst, bærekapasitet og dynamikk. - Lineære differensligninger løses med det karakteristiske polynomet. - Et fikspunkt oppfyller $g(r)=r$. - Betingelsen $|g'|<1$ betyr at iterasjonen trekker avstander sammen. - For matriseiterasjoner bestemmer egenverdiene om gjentatt multiplikasjon krymper. - Jacobimetoden er en fikspunktiterasjon for lineære systemer. - Newtons metode bruker tangenter og har vanligvis kvadratisk konvergens nær en enkel rot.

Komplekse tall