Dynamiska system

Ett dynamiskt system består av en eller flera variabler som förändras över tiden. Ett kontinuerligt dynamiskt system kan matematiskt modelleras av differentialekvationer. I ett diskret dynamiskt system mäts tiden i diskreta steg. Diskreta dynamiska system modelleras matematiskt med hjälp av rekursion.

Rekursivt definierade talföljder

En rekursivt definierad talföljd definieras av

  1. Ett eller flera initialvärden
  2. En rekursionsekvation som beskriver hur ett tal beror på föregående tal i följden

Ett exempel på en rekursivt definierad talföljd är Fibonacci talen $0, 1, 1, 2, 3, 5, 8, 13, \ldots$.

$$ \left\{ \begin{align*} f_0 & = 0 \\ f_1 & = 1 \\ f_n & = f_{n-1}+f_{n-2}, n \gt 1 \end{align*} \right. $$

En rekursivt definierad talföljd där rekursionsekvationen bara beror på föregående tal kallas homogen.

Låt den homogena talföljden $\{a_n\}$ definieras av

$$ \left\{ \begin{align*} a_0 & = A \\ a_n & = f(a_{n-1}), n \gt 0 \end{align*} \right. $$

Om $a_n$ har ett gränsvärde då $n\to \infty$, kallas detta gränsvärde för en fixpunkt till rekursionsekvationen. Om funktionen $f$ appliceras på en fixpunkt kommer resultatet att bli samma tal igen. Låt $x^*$ beteckna en fixpunkt, då gäller det att $f(x^*) =x^*$.

För att bestämma fixpunkter till en rekursionsekvation löser du alltså ekvationen $f(x) = x$.

Då man itererar en rekursiv ekvationen applicerar man samma funktion på sig själv, om och om igen.

$$ x, f(x), f\left(f\left(x\right)\right), f\left(f\left(f\left(x\right)\right)\right), f\left(f\left(f\left(f\left(x\right)\right)\right)\right) \ldots$$

Övning 1

Ett exempel på en funktion applicerad på sig själv, om och om igen, är kedjebråket nedan. $$ 1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cdots}}} $$

Formulera kedjebråket som en rekursivt definierad talföld $\{x_n\}$. Använd initialvärdet $x = 1$ och beräkna $x_n$ för $n = 1000$.

In [ ]:

Övning 2

Man kan bestämma fixpunkterna till rekursionsekvationen i Övning 1 genom att lösa ekvationen

$$ x^2-x-1 = 0 $$

De två rötterna till andragradsekvationen är $x_1 = \frac{1+\sqrt{5}}{2}$ och $x_2 = \frac{1-\sqrt{5}}{2}$

Provkör programmet du gjorde i Övning 1 med olika initialvärden, testa speciellt att låta $x = \frac{1+\sqrt{5}}{2}$ och $x = \frac{1-\sqrt{5}}{2}$. Vad blir resultaten? Vilken av fixpunkterna är attraherande/repellerande? Utgå från spindelvävsdiagrammen på sidan Spindelvävsdiagram och förklara varför punkterna är attraherande/repellerande!

Övning 3

Ett annat exempel på en funktion applicerad på sig själv är kedjerotuttrycket nedan.

$$ \sqrt{1+\sqrt{1+\sqrt{1+\sqrt{1+\cdots}}}} $$

Formulera kedjerotuttrycket som en rekursivt definierad talföld $\{x_n\}$. Beräkna $x_n$ för $n = 1000$ och olika initialvärden.

Denna rekursion har samma fixpunkter som kedjebråket i Övning 1. Vad blir resultaten för olika initialvärden?

In [ ]:

Övning 4

Ekvationer på formen $f(x) = x$ kan ibland lösas approximativt enligt principen:

  1. Definiera en rekursivt definerad talföljd $\{x_n\}$ vars fixpunkt bestäms genom att lösa ekvationen $f(x) = x$.
  2. Iterera för att numeriskt bestämma fixpunkten.

Ekvationen $\cos(x)=x$ har exakt en lösning men ekvationen kan inte lösas algebraiskt. Bestäm en approximativ lösning till denna ekvation genom att iterera. Spelar det någon roll vilket startvärde du använder?

In [ ]:

Newtons metod

Newtons metod (eller Newton-Raphson) är en algorithm som används för att approximera rötter till ekvationer.

Låt $f(x) = 0$ vara en ekvation och $(x_0, f(x_0))$ en startpunkt på funktionens graf. Följ tangenten genom startpunkten $(x_0, f(x_0))$ till $x$-axeln. Antag att tangenten skär $x$-axeln i punkten $(x_1, 0)$. Tangentens lutning ges av $f'(x_0)$ och dessutom gäller det att lutningen är $\frac{\Delta y}{\Delta x}$ där skillnaderna tas mellan punkterna $(x_0, f(x_0))$ och $(x_1, 0)$. Därför gäller följande:

$$ f'(x_0) = \frac{f(x_0)}{x_0-x_1} $$

Det nya approximationen $x_1$ kan skrivas som

$$ x_1 = x_0 - \frac{f(x_0)}{f(x_0)} $$

Om processen upprepas får man en rekursionsekvation

$$ x_{n+1} = x_n - \frac{f(x_n)}{f(x_n)} $$

Övning 5

Definera funktionen $f(x) = x^3-2x^2 +1$ som en Python-funktion. Låt $g(x)=f'(x)$ och definiera Python-funktionen $g(x)$. Implementera kod som utför Newtons metod. Provkör koden med olika initialvärden och olika värden på $n$.

In [ ]:

Kommentar till Övning 5

Om man använder Newtons metod på komplexa tal kan man skapa fraktaler. Ett interaktivt exempel visas här: Newton Fractals.

Grafen till funktionen $f(x) = x^3-2x^2 +1$ plottas nedan.

In [1]:
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np

fig = plt.figure(figsize = (8, 6))
fig.suptitle("$f(x) = x^3-2x^2 +1$", fontsize = 15)

#Visa koordinataxlar istället för en ram runt bilden
axes = plt.gca()
axes.spines['right'].set_color('none')
axes.spines['top'].set_color('none')
axes.xaxis.set_ticks_position('bottom')
axes.spines['bottom'].set_position(('data',0))
axes.yaxis.set_ticks_position('left')
axes.spines['left'].set_position(('data',0))

X = np.linspace(-1, 2, 300)
Y = X**3-2*X**2 + 1
plt.xlim(-1, 2)
plt.ylim(-1.9, 1.1)
plt.plot(X, Y, linewidth = 2, color = (0.7, 0, 1))

plt.show()

Logistisk avbildning

Om man i en populationsmodell antar att förändringshastigheten är proportionell mot populationen, kan detta skrivas som

$$ \frac{dN}{dt} = rN $$

där $N(t)$ är antalet individer vid tidpunkten $t$ och $r$ är en proportionalitetskonstant. Denna modell ger upphov till exponentiell tillväxt, ett faktum som uppmärksammades i slutet av 1700-talet av Thomas Malthus som sedermera skrev essän An Essay on the Principle of Population vilken hade ett mycket stort inflytande på den tidens samhällsdebatt.

I början av 1800-talet argumenterade Pierre Verhulst emot Malthus populationsmodell och föreslog en ny populationsmodell. I Verhulsts modell antas en population ha ett maximalt antal individer. Om det maximala antalet individer beteckas $K$, kan Verhulst modell skrivas som

$$ \frac{dN}{dt} = rN\left(1-\frac{N}{K} \right) $$

Lösningen till differentialekvationen kallade Verhulst för den logistiska funktionen.

En diskret version av Verhulst differentialekvation, är den så kallade logistiska avbildningen:

$$ x_{n+1} = rx_n(1-x_n) $$

Här antas $x_n$ vara en andel av den maximala populationen. Talen $x_n$ antar därför bara värden mellan $0$ och $1$. Eftersom funktionen $f(x) = x(1-x)$ har maximum i punkten $(1/2, 1/4)$ får $r$ bara anta värden mellan $0$ och $4$.

Genom att lösa ekvationen $x = rx(1-x)$ finner man att rekursionen har två fixpunkter $x_1 = 0$ och $x_2 = \frac{r-1}{r}$. Som vi tidigare sett, är det dock inte säkert att en talföljden konvergerar mot en fixpunkt.

Övning 6

Beräkna $x_{150}$, definierad av den logistiska avbildningen, för olika värden på $r$.

Modulen random innehåller en funktion random som genererar ett slumptal mellan 0 och 1. Använd denna funktion för initialvärdet.

För varje $r$ bör du göra flera beräkningar med slumpmässiga initialvärden.

Vad kan du säga om konvergensen då $r \leq 1$?

Vad kan du säga om konvergensen då $1\lt r \lt 3$?

Vad kan du säga om konvergensen då $r$ är $3.2, 3.5$ och $3.8$?

In [ ]:
from random import random

x = random()

# Fyll i kod

Kommentar till Övning 6

Några nyckelor i form av länkar till Wikipedia:

Logistisk avbildning är ett exempel på deterministiskt kaos. Nedan plottas $x_n$ mot $r$ i ett så kallat bifurkationsdiagram.

In [2]:
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
from random import random

fig = plt.figure(figsize = (9,6))
fig.suptitle("Logistisk avbildning - Bifurkationsdiagram", fontsize = 15)

axes = plt.gca()
axes.set_xlabel('$r$', fontsize = 15)
axes.set_ylabel('$x_{\infty}$', fontsize = 15)
axes.set_xlim(2.5, 4)
axes.set_ylim(0, 1)

rN = 500
rValues = [2.5 + 1.5/rN*i for i in range(rN+1)]
for r in rValues:
    x = random()
    xList = []
    for i in range(150):
        x = r*x*(1-x)
    for i in range(150):
        x = r*x*(1-x)
        xList.append(x)
    plt.scatter([r]*len(xList),xList, 1, color =(1, 0.3, 0, 0.2))
    
plt.show()
In [ ]: