Toepassingen op differentievergelijkingen We beschouwen lineaire differentievergelijkingen of lineaire recurrente betrekkingen van de vorm a0 yk+n + a1 yk+n−1 + . . . + an−1 yk+1 + an yk = zk ,
k = 0, 1, 2, . . . .
Hierbij zijn de co¨effici¨enten a0 , . . . , an re¨ele getallen, is de rij getallen {zk }∞ k=0 gegeven en is de rij getallen {yk }∞ onbekend. Het gaat hierbij is dus om het vinden van deze rij getallen k=0 {yk }∞ . Als a = 6 0 en a = 6 0 dan spreekt men van een differentievergelijking van de orde 0 n k=0 n. Als zk = 0 voor alle k = 0, 1, 2 . . ., dan noemt men de differentievergelijking homogeen en anders inhomogeen. Voorbeeld 1. Beschouw de lineaire differentievergelijking van de orde 2 gegeven door yk+2 − 3yk+1 + 2yk = 0,
k = 0, 1, 2, . . . .
Stel dat yk = rk , dan volgt : rk+2 − 3rk+1 + 2rk = 0 ⇐⇒ rk (r2 − 3r + 2) = 0. Hieruit volgt dat r2 − 3r + 2 = 0 oftewel (r − 1)(r − 2) = 0. Dus : yk = 1k = 1 en yk = 2k met k = 0, 1, 2, . . . zijn oplossingen. Dus : yk = c1 + c2 2k , k = 0, 1, 2, . . . . Voorbeeld 2. Beschouw de lineaire differentievergelijking van de orde 3 gegeven door yk+3 − 5yk+2 − 4yk+1 + 20yk = 0,
k = 0, 1, 2, . . . .
Stel dat yk = rk , dan volgt : rk+3 − 5rk+2 − 4rk+1 + 20rk = 0 ⇐⇒ rk (r3 − 5r2 − 4r + 20) = 0. Hieruit volgt dat r3 − 5r2 − 4r + 20 = 0. Enkele waarden van r proberen leert dat r = 2 voldoet. Dus : r3 − 5r2 − 4r + 20 = (r − 2)(r2 − 3r − 10) en r2 − 3r − 10 = (r − 5)(r + 2). Dus : r3 − 5r2 − 4r + 20 = (r − 5)(r − 2)(r + 2). Hieruit volgt dat : yk = c1 5k + c2 2k + c3 (−2)k ,
k = 0, 1, 2, . . . .
Net als bij differentiaalvergelijkingen proberen we op deze manier n lineair onafhankelijke oplossingen te vinden voor zo’n differentievergelijking van de orde n. Hierbij kunnen zich allerlei problemen voordoen. Wat te doen in het geval van meervoudige nulpunten ? En wat als er niet-re¨ele nulpunten optreden ? Deze problemen zullen we hier buiten beschouwing laten. Voorbeeld 3. Ga na dat yk = k(k + 1) een oplossing is van de inhomogene differentievergelijking yk+2 − 5yk+1 + 4yk = −6k − 4, k = 0, 1, 2, . . . van de orde 2 en bepaal vervolgens de algemene oplossing. Door invullen van yk = k(k + 1) vinden we yk+2 − 5yk+1 + 4yk = (k + 2)(k + 3) − 5(k + 1)(k + 2) + 4k(k + 1) = k 2 + 5k + 6 − 5k 2 − 15k − 10 + 4k 2 + 4k = −6k − 4. Dus : yk = k(k + 1) is inderdaad een oplossing. 1
Vervolgens beschouwen we homogene differentievergelijking yk+2 − 5yk+1 + 4yk = 0,
k = 0, 1, 2, . . .
en bepalen hiervan de algemene oplossing. Invullen van rk leidt tot r2 − 5r + 4 = 0 oftewel (r − 1)(r − 4) = 0. Dus : yk = c1 + c2 4k , k = 0, 1, 2, . . .. De algemene oplossing van de inhomogene differentievergelijking is dan yk = k(k + 1) + c1 + c2 4k ,
k = 0, 1, 2, . . . .
Een homogene lineaire differentievergelijking kunnen we altijd schrijven in de vorm van een stelsel van eerste orde lineaire differentievergelijkingen. Voorbeeld 4. Beschouw de lineaire differentievergelijking van de orde 2 uit voorbeeld 1. Definieer nu yk xk = . yk+1 Uit de differentievergelijking volgt dat yk+2 = −2yk + 3yk+1 en dus : yk+1 yk+1 0 1 yk xk+1 = = = = Axk yk+2 −2yk + 3yk+1 −2 3 yk+1 met A =
0 1 −2 3
.
Voorbeeld 5. Beschouw de lineaire differentievergelijking van de orde 3 uit voorbeeld 2. Definieer nu yk xk = yk+1 . yk+2 Uit de differentievergelijking volgt dat yk+3 = −20yk + 4yk+1 + 5yk+2 en dus : yk+1 yk+1 0 1 0 yk = 0 yk+2 0 1 yk+1 = Axk xk+1 = yk+2 = yk+3 −20yk + 4yk+1 + 5yk+2 −20 4 5 yk+2
0 1 0 0 1 . met A = 0 −20 4 5 Het oplossen van een homogene lineaire differentievergelijking van de orde n is dus equivalent met het oplossen van een differentievergelijking van de vorm xk+1 = Axk , k = 0, 1, 2, . . . met A een (n × n)-matrix. Als A een diagonaliseerbare matrix is, dan kunnen we zo’n differentievergelijking van de vorm xk+1 = Axk , k = 0, 1, 2, . . . eenvoudig oplossen. Merk op, dat x1 = Ax0 , x2 = Ax1 = A2 x0 , enzovoorts. De oplossing kan dus geschreven worden in de vorm xk = Ak x0 , k = 0, 1, 2, . . .. 2
Nu is A = P DP −1 voor zekere inverteerbare matrix P = v 1 . . . v n en diagonaalmatrix D = diag(λ1 , . . . , λn ) en dus is Ak = P Dk P −1 met Dk = diag(λk1 , . . . , λkn ) voor k = 0, 1, 2, . . .. Als A diagonaliseerbaar is dan bestaat er dus een basis {v 1 , . . . , v n } van Rn bestaande uit eigenvectoren van A, zeg : Av i = λi v i , i = 1, 2, . . . , n. Elke beginvector x0 ∈ Rn kan dus geschreven worden als x0 = c1 v 1 + . . . + cn v n . Dan volgt : x1 = Ax0 = c1 Av 1 + . . . + cn Av n = c1 λ1 v 1 + . . . + cn λn v n , x2 = Ax1 = c1 λ1 Av 1 + . . . + cn λn Av n = c1 λ21 v 1 + . . . + cn λ2n v n , enzovoorts. Dus : xk = c1 λk1 v 1 + . . . + cn λkn v n , waarbij de co¨effici¨enten c1 , . . . , cn uniek bepaald kunnen worden uit x0 = c1 v 1 + . . . + cn v n .
Voorbeeld 6. In voorbeeld 4 vonden we : xk+1 = Axk ,
k = 0, 1, 2, . . . met A =
0 1 −2 3
.
Nu volgt :
Verder volgt :
−λ 1 |A − λI| = −2 3 − λ
= λ2 − 3λ + 2 = (λ − 1)(λ − 2).
λ1 = 1 :
−1 1 −2 2
λ2 = 2 :
−2 1 −2 1
en
=⇒
=⇒
k = 0, 1, 2, . . . is dus 1 k k k xk = c1 λ1 v 1 + c2 λ2 v 2 = c1 + c2 2 1 yk Uit de twee co¨ordinaten van xk = volgt nu yk+1 c1 + c2 2k+1 voor k = 0, 1, 2, . . .. Vergelijk met voorbeeld
v1 =
1 1
v2 =
1 2
,
k = 0, 1, 2, . . . .
.
De oplossing van xk+1 = Axk ,
De oplossing kan ook geschreven worden als 1 0 k xk = A x0 = P P −1 x0 0 2k
1 2
dat yk = c1 + c2 2k en dat yk+1 = 1.
met
P =
1 1 1 2
.
Uitgeschreven is dat 1 0 2 −1 1 1 2 −1 1 1 xk = x0 = x0 1 2 −1 1 1 2 0 2k −2k 2k 2 − 2k −1 + 2k = x0 , k = 0, 1, 2, . . . . 2 − 2k+1 −1 + 2k+1 3
Voorbeeld 7. In voorbeeld 5 vonden we : xk+1
0 1 0 0 1 . Dan = Axk met A = 0 −20 4 5
volgt : −λ −λ 1 −λ 1 0 0 1 0 0 −λ 1 = 4 −λ 1 −λ 1 = |A − λI| = 0 −20 4 5 − λ −20 + 4λ 0 5 − λ 0 0 5−λ −λ 1 = (5 − λ)(λ2 − 4) = (5 − λ)(λ − 2)(λ + 2). = (5 − λ) 4 −λ
Verder volgt :
λ1 = 5 :
λ2 = 2 :
−5 1 0 −5 1 0 0 −5 1 ∼ 0 −5 1 −20 4 0 0 0 0 −2 1 0 −2 1 0 0 −2 1 ∼ 0 −2 1 −20 4 3 0 0 0
en λ3 = −2 :
2 1 0 2 1 0 0 2 1 ∼ 0 2 1 −20 4 7 0 0 0
1 v1 = 5 , 25 1 v2 = 2 . 4
=⇒
=⇒
=⇒
1 v 3 = −2 . 4
De oplossing van xk+1 = Axk , k = 0, 1, 2, . . . is dus 1 1 1 xk = c1 5k 5 + c2 2k 2 + c3 (−2)k −2 , k = 0, 1, 2, . . . . 25 4 4 yk Uit de eerste co¨ordinaat van xk = yk+1 volgt nu dat yk = c1 5k + c2 2k + c3 (−2)k voor yk+2 k = 0, 1, 2, . . .. Vergelijk met voorbeeld 2. Merk op dat uit de tweede en derde co¨ordinaat van xk volgt dat yk+1 = c1 5k+1 + c2 2k+1 + c3 (−2)k+1
en
yk+2 = c1 5k+2 + c2 2k+2 + c3 (−2)k+2 .
De oplossing kan ook weer geschreven worden als k 5 0 0 0 P −1 x0 xk = Ak x0 = P 0 2k 0 0 (−2)k
met
1 1 1 P = 5 2 −2 . 25 4 4
Een differentievergelijking van de vorm xk+1 = Axk , k = 0, 1, 2, . . . wordt ook wel een discreet dynamisch systeem genoemd. Een differentiaalvergelijking van de vorm x0 (t) = Ax(t) noemt men ook wel een continu dynamisch systeem. 4
Aan de hand van de eigenwaarden van de (2 × 2)-matrix A konden we de banen van een continu dynamisch systeem in R2 classificeren. In het geval van een discreet dynamisch systeem xk+1 = Axk , k = 0, 1, 2, . . . met A een (2 × 2)-matrix kan dit ook. De oplossing kan immers geschreven worden in de vorm xk = c1 λk1 v 1 + c2 λk2 v 2 , k = 0, 1, 2, . . ., waarbij λ1 en λ2 de twee eigenwaarden van A zijn. De oplossing is in dit geval een rij punten (vectoren) in R2 : x0 , x1 , x2 , . . .. De grafiek van deze punten (vectoren) noemt men ook een baan van het (discrete) dynamische systeem. Als de eigenwaarden λ1 en λ2 re¨eel zijn en |λ1 | < 1 en |λ2 | < 1, dan heet de oorsprong O een aantrekker of attractor van het (discrete) dynamische systeem. Alle banen worden dan immers naar de oorsprong O toe getrokken. Als de eigenwaarden λ1 en λ2 re¨eel zijn en |λ1 | > 1 en |λ2 | > 1, dan heet de oorsprong O een afstoter van het (discrete) dynamische systeem. Alle oplossingen gaan dan immers naar oneindig (van de oorsprong O af). Als de eigenwaarden λ1 en λ2 re¨eel zijn en |λ1 | > 1 en |λ2 | < 1, dan heet de oorsprong O een zadelpunt van het (discrete) dynamische systeem. In dat geval worden sommige oplossingen naar de oorsprong toe getrokken, terwijl andere naar oneindig (van de oorsprong af) gaan. In het geval van niet-re¨ele eigenwaarden zijn de banen weer spiraalvormig rond de oorsprong. Als de absolute waarde van de beide (complex geconjugeerde) eigenwaarden kleiner is dan 1, dan worden alle banen naar de oorsprong O toe getrokken en als de absolute waarde groter dan 1 is dan draaien de banen in zo’n spiraalvorm van de oorsprong O af.
Toepassingen op Markov ketens Een Markov keten is een rij vectoren x0 , x1 , x2 , . . . die voldoet aan een differentievergelijking van de vorm xk+1 = P xk , k = 0, 1, 2, . . ., waarbij P een zogenaamde Markov matrix of stochastische matrix is : Definitie 1. Een vector in Rn heet een kansvector of stochastische vector als alle co¨ ordinaten groter dan of gelijk aan nul zijn en de som van alle co¨ ordinaten gelijk aan 1 is. Een vierkante matrix P heet een Markov matrix of stochastische matrix als alle kolommen van P kansvectoren (of stochastische vectoren) zijn. Een voorbeeld van een Markov matrix is de migratiematrix in voorbeeld 1 van § 4.9 in Lay. Een vector xk in een Markov keten heet ook wel een toestand(svector). Een typische eigenschap is dat de som van de co¨ordinaten van elke toestand(svector) steeds gelijk is. Zo blijft in voorbeeld 1 van § 4.9 het totaal aantal inwoners (1.000.000) constant. Stelling 1. Elke Markov matrix of stochastische matrix P heeft een eigenwaarde λ = 1. Een bijbehorende eigenvector x, die bovendien een kansvector of stochastische vector is, heet wel een evenwichtstoestand(svector). Bewijs. Als P een Markov matrix is, dan is de som van alle elementen in elke kolom gelijk aan 1. Beschouw nu |P − λI|, het karakteristieke polynoom van P . Als we in die determinant 5
|P −λI| alle rijen onder de eerste optellen bij de eerste rij, dan zijn alle elementen in die eerste rij gelijk aan 1 − λ. De determinant is dus deelbaar door 1 − λ. Daaruit volgt dat de matrix P een eigenwaarde λ = 1 heeft. Uit de bijbehorende eigenruimte E1 kan men natuurlijk altijd een vector kiezen waarvan de som van alle co¨ordinaten 1 is. Dat alle co¨ordinaten van die eigenvector dan ook groter dan of gelijk aan nul zijn is wat lastiger te beredeneren. Dat laten we buiten beschouwing. Definitie 2. Een Markov matrix of stochastische matrix P heet regulier als een zekere macht van P alleen positieve elementen heeft (dus geen nullen).
Stelling 2. Als P een reguliere Markov matrix is, dan heeft P een unieke evenwichtstoestand(svector) x. Verder geldt dat voor iedere kansvector x0 de Markov keten bepaald door xk+1 = P xk , k = 0, 1, 2, . . . convergeert naar die evenwichtstoestand(svector) x. Merk op dat als het proces convergeert, dus als de limiet lim xk = x bestaat, dan geldt dat k→∞
x = P x. Het bewijs dat het proces ook daadwerkelijk convergeert als P regulier is, laten we buiten beschouwing. Voorbeeld 8. Stel dat P =
0, 3 0, 2 0, 7 0, 8
, dan is P een reguliere Markov matrix. We
vinden nu : 0, 3 − λ 1−λ 1−λ 0, 2 = |P − λI| = 0, 7 0, 8 − λ 0, 7 0, 8 − λ 1 1 = (1 − λ)(0, 1 − λ). = (1 − λ) 0, 7 0, 8 − λ
De eigenwaarden van P zijn dus λ1 = 1 en λ2 = 0, 1. Verder volgt : −0, 7 0, 2 −7 2 2 λ=1 : ∼ =⇒ E1 = Span{ }. 0, 7 −0, 2 0 0 7 Dus : als xk+1 = P xk ,
k = 0, 1, 2, . . . dan volgt voor iedere kansvector x0 dat 1 2 lim xk = x = . k→∞ 9 7
1 2 1 Als bijvoorbeeld x0 = , dan geldt dat lim xk = . 2 k→∞ 3 7 2 2 4 Als bijvoorbeeld x0 = , dan geldt dat lim xk = . 2 k→∞ 3 7 60 20 Als bijvoorbeeld x0 = , dan geldt dat lim xk = . 30 70 k→∞
6
0, 5 0, 2 0, 7 Voorbeeld 9. Stel dat P = 0 0, 8 0, 1 . Dan is P een reguliere Markov matrix, 0, 5 0 0, 2 want 0, 5 0, 2 0, 7 0, 5 0, 2 0, 7 0, 60 0, 26 0, 58 P 2 = 0 0, 8 0, 1 0 0, 8 0, 1 = 0, 05 0, 64 0, 11 . 0, 5 0 0, 2 0, 5 0 0, 2 0, 40 0, 10 0, 44 Hoewel de eigenwaarden niet zo mooi zijn, zijn ze in principe wel eenvoudig te berekenen : 0, 5 − λ 1 − λ 0, 2 0, 7 1 − λ 1 − λ 0, 8 − λ 0, 1 0 0, 8 − λ 0, 1 = 0 |P − λI| = 0, 5 0 0, 2 − λ 0, 5 0 0, 2 − λ 1 1 0 0 1 1 0, 1 0, 1 = (1 − λ) 0 0, 8 − λ = (1 − λ) 0 0, 8 − λ 0, 5 0, 5 −0, 5 −0, 3 − λ 0 0, 2 − λ 0, 8 − λ 0, 1 = (1 − λ)(λ2 − 0, 5λ − 0, 19). = (1 − λ) −0, 5 −0, 3 − λ De nulpunten van dit polynoom zijn nu eenvoudig te vinden.
We onderzoeken alleen de eigenwaarde λ = 1 : −0, 5 0, 2 0, 7 −0, 5 0, 2 0, 7 −0, 2 0, 1 −0, 2 0, 1 ∼ 0 λ=1 : 0 0 0, 2 −0, 1 0, 5 0 −0, 8 −0, 5 0 0, 8 −5 0 8 16 −0, 2 0, 1 ∼ 0 −2 1 =⇒ E1 = Span{ 5 }. ∼ 0 0 0 0 0 0 0 10 Uit stelling 2 volgt dus dat de Markov keten bepaald door xk+1 = P xk , k = 0, 1, 2, . . . convergeert voor iedere kansvector x0 ∈ R3 . Dat geldt dan natuurlijk ook voor ieder veelvoud van zo’n kansvector. 0, 3 16 1 5 . Als bijvoorbeeld x0 = 0, 6 , dan is lim xk = k→∞ 31 0, 1 10 25 16 Als bijvoorbeeld x0 = 0 , dan is lim xk = 5 . k→∞ 6 10 30 48 Als bijvoorbeeld x0 = 25 , dan is lim xk = 15 . k→∞ 38 30
7
