Anvendelser

I dette kapitel ser vi på, hvordan python kan bruges til at løse matematiske problemer.

Beregninger med iteration

I matematik betyder iteration, at man gentager anvendelsen af en regel eller en beregning. Man starter med en begyndelsesværdi og bruger en formel eller funktion igen og igen, hvor hvert nyt resultat bruges som input til næste trin.

Et eksempel på en funktion, som kan beregnes ved iteration er fakultet funktionen: \[ n! = n · (n-1) · (n-2) \cdots 3 · 2 · 1\] hvor fx $5!=5·4·3·2·1=120$. Nu kan $6!$ beregnes ud fra $5!$ fordi \[ 6! = 6·5·4·3·2·1 = 6·5!\] På samme måde kan $n!$ beregnes ud fra $(n-1)!$ \[ n! = n· (n-1) \] Hver ny værdi af $n!$ kan altså beregnes ud fra den foregående $(n-1)$ ved at bruge samme metode: gang med $n$.

Hvis man starter med $0!=1$, kan alle de øvrige værdier beregnes ved at gange med $n$: \[ 1!=1·0!, \quad 2!=2·1!, \quad 3!=3·2! \quad \text{osv.}\]

Et andet eksempel på iteration er Fibonacci-tallene: \[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots \] hvor hver tal i rækken er summen af de to foregående. Dette program beregner det $n$’te Fibonacci tal:

Løs en ligning med bisektionsmetoden

Vi vil nu bruge python til at finde en numerisk løsning til en ligning. En numerisk løsning til en ligning er en tilnærmet værdi for løsningen, som findes ved hjælp af beregningsmetoder i stedet for en nøjagtig, eksakt formel. Den ligning, vi vil løse er \[x^2=2\] Vi ved godt at der et to løsninger, $x=-\sqrt 2$ og $x=\sqrt 2$, så det er muligt at sammenligne det numeriske resultat med den eksakte løsning. Den metode vi vil bruge kaldes bisektions-metoden. Det er faktisk en metode til at finde nulpunkter (rødder) i en funktion, så første trin er at lave omskrive ligningen til \[ x^2-2=0\] Hvis vi sætter $f(x)=x^2-2$ kan vores ligning altså skrives som \[ f(x)=0\] Bisektions metoden kræver at vi starter med et interval $[a,b]$, hvor $f(a)$ og $f(b)$ har forskelligt fortegn. Derfor ved vi, at må være en rod i intervallet (hvis funktionen er kontinert).

Metoden går ud på at bestemme $f(c)$, hvor $c$ ligger midt imellem $a$ og $b$. Hvis $f(a)$ og $f(c)$ har forskelligt fortegn så er der en rod i intervallet $[a;c]$ og vi fortsætter med at undersøge dette interval. Ellers må der være en rod i intervallet $[c;b]$ og vi fortsætter med at undersøge dette interval. Vi har altså et nyt interval, hvor vi finder midtpunktet og beregner funktionsværdien osv. osv.

Hver gang vi vælger et nyt interval, bliver længden af intervallet halveret. Det er derfor metoden kaldes bisektion = “dele op i to dele”. Intervallerne bliver mindre og mindre, og vi kommer derfor tættere og tættere på den rigtige værdi af roden.

Proceduren er den samme hver gang vi har valgt et interval, og metoder hvor vi gentager den samme procedure igen og igen kaldes iterative. Hver anvendelse af metoden kaldes en iteration. Med mindre man ved et tilfælde rammer et interval, hvor $f(c)=0$ kan man i princippet fortsætte metoden i det uendelige. Man angiver derfor en tolerance, og afbryder derfor metoden når $f(c)$ er tættere på 0 end tolerancen angiver. Dermed kan man betragte $c$ som en tilnærmet løsning til ligningen.

For en sikkerheds skyld sætter man også en grænse for, hvor mange iterationer programmet må foretage. Hvis der ikke er fundet en løsning inden det maksimale antal iterationen fejler metoden.

Det er metoder som disse (med lidt mere avancerede variatoner), som dit CAS-værktøj bruger, hvis det ikke kan finde en eksakt løsning til en ligning ved hjælp af en formel. Men nu til selve programmet:

Newton-Raphsons metode

Newtons-Raphsons metode (den kaldes også nogen gange blot for Newtons metode) er en metode til at finde nulpunkter for en funktion $f(x)$. Det gøres ved at starte med et gæt på hvor nulpunktet ligger. Det kalder man for $x_0$.

Nu kan beregne et nyt gæt, som kan beregnes med formlen

\[ x_1=x_0-\frac{f(x_0)}{f'(x_0)} \] Metoden kræver altså at vi kender både $f(x)$ og $f'(x)$. Metoden kan udvides til at beregne flere værdier ved iteration. Hvis man kender den $n$’te værdi, $x_n$, kan den næste værdi $x_{n+1}$ beregnes med formlen

\[ x_{n+1} = \frac{f(x_n)}{f'(x_n)} \]

Eulers metode

Eulers metode er metode til at beregne en tilnærmet løsning til en første-ordens differentialligning.

Hvis en differentialligning er givet ved

\[ y'=f(x,y) \] beregnes $y$-værdier ved hjælp iteration ud fra formlen

\[ y_{n+1} = y_n + h·f(x_n,y_n) \] og

\[ x_{n+1} = x_n +h \]

hvor $h$ kaldes skridtlængden.

Det følgende program beregner en numerisk løsning til differentialligningen

\[ y' = 1{,}1·y \] med begyndelsesbetingelsen $y(0)=3$.

I programmet er y0 betingelsen $y(x_0)=3$. x0 er startværdien af $x$, og xn er den sidste $x$-værdi, så programmet beregner en tilnærmet løsning i intervallet $[x_0; x_n]$.

Øvelse

Løs differentialligningen med dit CAS-værktøj og plot grafen for løsningen for $x=0$ til $x=5$ og sammenlign med grafen fra pythonprogrammet.
kan du få en bedre overensstemmelse ved de to grafer ved at ændre værdien af skridtlængden $h$?
lav programmet om, så det løser differentialligningen $y'=-0{,}9·y+100$, med $y(0)=300$ i intervallet $[0;10]. Vælg selv en værdi af skridtlængden, og sammenlign output med en løsning med fra CAS-program.

Feigenbaum

Det næste program plotter en figur, som er kendt som Feigenbaums træ. Plottet er baseret på iteration ud fra formlen \[ x_{n+1} = r· x_n · (1- x_n) \] hvor $r$ er en konstant. Du kan læse mere om plottet i bemærkningerne efter programmet.

Bemærkninger

Figuren er baseret på iteration ud fra ligningen illustreres oftest ud fra den logistiske ligning, som anvendes til at modellere populationsudvikling fra generation til generation: \[ x_{n+1} = r \cdot x_n (1 - x_n) \] Denne ligning kaldes den logistiske ligning og bruges indenfor biologi til at modellere udviklingen i en population af dyr. I modellen betegner $x_n$ populationsstørrelsen i den $n$’te generation, men således at størrelsen af populationen er skaleret til at være mellem $0$ og $1$, og $r$ er en vækstparameter.

Hvis man starter med en værdi $x_0$ og beregner $x_n$ for forskellige generationer (værdier af $n$), vil man kunne opleve to forskellige ting. Enten vil værdien af $x_n$ nærme sig en bestemt værdi når $n \to \infty$, eller også vil man opleve at $x_n$ veksler mellem to eller flere forskellige værdier.

Diagrammet laves ved at plotte de forskellige værdier, som $x_n$ svinger imellem, som funktion af vækstparameteren $r$, som altså er på den vandrette akse. Men for at sikre at værdien (eller værdierne) af $x_n$ har stabiliseret sig, laves først 1000 iterationer. Derefter beregnes 100 værdier af $x_n$, som plottes i grafen med værdien af $r$ på x-aksen.

Det viser sig, at grafens opførsel er meget afhængig af værdien af $r$:

For $r < 3,0$ er der det, man kan kalde en enkelt ligevægt: Populationen (værdien af $x_n$ stabiliserer sig på én fast værdi når $n\to\infty$. Diagrammet viser blot en enkelt kurve – det, der svarer til træets “stamme”.
Ved $r = 3{,}0$ optræder der en forgrening (den første af uendeligt mange).Stabilileringen bryder sammen, og systemet begynder i stedet at svinge mellem 2 faste værdier (f.eks. et højt tal det ene år og et lavt det næste). Stammen deler sig i 2 grene.
Ved $r \approx 3{,}45$ sker der det, man kalder en periodedobling: Hver gren deler sig i to nye grene. Systemet svinger nu mellem 4 værdier, og for højere værdier af $r$ svinger det mellem derefter 8 værdier, 16 værdier, 32 værdier osv. Forgreningerne sker hurtigere og hurtigere, forstået på den måde at $r$ skal ændres mindre og mindre for at få en ny periodedobling.
Ved $r \approx 3{,}57$ når vi det, man kan kalde kaos-grænsen: Forgreningerne mødes i et akkumuleringspunkt. Antallet af svingninger (forskellige værdier af $x_n$) bliver uendeligt, og træets grene opløses i et tæt, mørkt felt. Man kan sige, at systemet er trådt ind i et kaotiske område.

Mitchell Feigenbaums universelle opdagelse

Den amerikanske fysiker Mitchell Feigenbaum regnede i 1975 på afstanden mellem forgreningspunkterne (som vi kan kalde $r_1, r_2, r_3, \dots$). Han opdagede, at forholdet af afstanden mellem forgreningspunkterne $(r_k-r_{k-1})/(r_{k+1}-r_k)$ nærmer sig en konstant værdi: \[ \delta = \lim_{k \to \infty} \frac{r_k - r_{k-1}}{r_{k+1} - r_k} \approx 4,6692016... \] Dette tal kaldes Feigenbaums første konstant.

Det revolutionerende ved opdagelsen er, at den universel: Feigenbaums konstant er en naturkonstant på linje med $\pi$ og $e$.

Uanset om man studerer biologiske populationer, konvektion i væsker, svingninger i elektriske kredsløb eller turbulens, vil systemer, der går over i kaos via periodedobling, følge præcis samme forgreningsmønster og samme værdi af konstanten $\delta$.

Fraktal opbygning (Orden i kaos)

Inden i det mørke, kaotiske område øverst i træet er der “hvide vinduer”, hvor systemet pludselig vender tilbage til en stabil svingning (f.eks. en periode på 3). Zoomer man ind på et af disse vinduer, opdager man, at mønsteret gentager sig: Der opstår et nyt lille Feigenbaum-træ i miniature. Træet besidder dermed det som man kalder selvsimilaritet og har en fraktal opbygning.