Lineaire Algebra – Eigenwaarden en eigenvectoren – Discrete dynamische systemen

Een discreet dynamisch systeem wordt gegeven door \(\mathbf{x}_{k+1}=A\mathbf{x}_k\) voor \(k=0,1,2,\ldots\), waarbij \(A\) een vierkante matrix is. Startend met een begintoestand \(\mathbf{x}_0\) leidt vermenigvuldiging met \(A\) tot de volgende toestand \(\mathbf{x}_1=A\mathbf{x}_0\), \(\mathbf{x}_2=A\mathbf{x}_1=A^2\mathbf{x}\) enzovoort. Merk op dat hieruit volgt dat \(\mathbf{x}_k=A^k\mathbf{x}_0\) voor \(k=0,1,2,\ldots\).

Als \(A\) een \(n\times n\) matrix is die diagonaliseerbaar is, dan bestaat er een basis \(\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\) van \(\mathbb{R}^n\) bestaande uit eigenvectoren van \(A\) behorende bij de eigenwaarden \(\lambda_1,\ldots,\lambda_n\) respectievelijk. Dan geldt dat elke begintoestand \(\mathbf{x}_0\in\mathbb{R}^n\) geschreven kan worden als een lineaire combinatie van deze eigenvectoren:

\[\mathbf{x}_0=c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n.\]

Hieruit volgt dat

\[\mathbf{x}_1=A\mathbf{x}_0=A\left(c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n\right)=c_1A\mathbf{v}_1+\cdots+c_nA\mathbf{v}_n =c_1\lambda_1\mathbf{v}_1+\cdots+c_n\lambda_n\mathbf{v}_n.\]

In het algemeen geldt:

\[\mathbf{x}_k=c_1\lambda_1^k\mathbf{x}_1+\cdots+c_n\lambda_n^k\mathbf{v}_n,\quad k=0,1,2,\ldots.\]

Markov ketens

Een speciaal geval van een discreet dynamisch systeem leidt tot een zogenaamde Markov keten, dat is een rij kansvectoren \(\mathbf{x}_0\), \(\mathbf{x}_1\), \(\mathbf{x}_2\), \(\ldots\) gegeven door een differentievergelijking \(\mathbf{x}_{k+1}=M\mathbf{x}_k\) with \(k=0,1,2,\ldots\), waarbij \(M\) een stochastische (of Markov) matrix is.

Definitie: Een vector met niet-negatieve elementen die optellen tot \(1\) heet een waarschijnlijkheidsvector of kansvector. Een stochastische matrix (of Markov matrix) is een vierkante matrix waarvan de kolommen kansvectoren zijn.

Voorbeeld: Beschouw het discreet dynamische systeem \(\mathbf{x}_{k+1}=A\mathbf{x}_k\) met \(k=0,1,2,\ldots\) en \(A=\begin{pmatrix}\frac{1}{2}&\frac{1}{4}\\\frac{1}{2}&\frac{3}{4}\end{pmatrix}\). Merk op dat \(A\) een stochastische (of Markov) matrix is. Nu volgt:

\[\det(A-\lambda I)=\begin{vmatrix}\frac{1}{2}-\lambda&\frac{1}{4}\\\frac{1}{2}&\frac{3}{4}-\lambda\end{vmatrix} =\lambda^2-\tfrac{5}{4}\lambda+\tfrac{1}{4}=(\lambda-1)(\lambda-\tfrac{1}{4}).\]

Dus, de eigenwaarden zijn \(\lambda_1=1\) en \(\lambda_2=\frac{1}{4}\). Verder volgt:

\[\lambda_1=1:\quad\begin{pmatrix}-\frac{1}{2}&\frac{1}{4}\\\frac{1}{2}&-\frac{1}{4}\end{pmatrix} \sim\begin{pmatrix}-2&1\\0&0\end{pmatrix}\quad\Longrightarrow\quad\mathbf{v}_1=\begin{pmatrix}1\\2\end{pmatrix}\]

en

\[\lambda_2=\tfrac{1}{4}:\quad\begin{pmatrix}\frac{1}{4}&\frac{1}{4}\\\frac{1}{2}&\frac{1}{2}\end{pmatrix} \sim\begin{pmatrix}1&1\\0&0\end{pmatrix}\quad\Longrightarrow\quad\mathbf{v}_2=\begin{pmatrix}1\\-1\end{pmatrix}.\]

We concluderen dat

\[\mathbf{x}_k=c_1\lambda_1^k\mathbf{v}_1+c_2\lambda_2^k\mathbf{v}_2=c_1\begin{pmatrix}1\\2\end{pmatrix} +c_2\left(\tfrac{1}{4}\right)^k\begin{pmatrix}1\\-1\end{pmatrix},\quad k=0,1,2,\ldots,\]

waarbij \(c_1\) en \(c_2\) bepaald worden door de begintoestand: \(\mathbf{x}_0=c_1\mathbf{v}_1+c_2\mathbf{v}_2\). Bijvoorbeeld, als \(\mathbf{x}_0=\begin{pmatrix}\frac{1}{2}\\\frac{1}{2}\end{pmatrix}\), dan volgt:

\[c_1\begin{pmatrix}1\\2\end{pmatrix}+c_2\begin{pmatrix}1\\-1\end{pmatrix}=\begin{pmatrix}\frac{1}{2}\\\frac{1}{2}\end{pmatrix}: \quad\left(\left.\begin{matrix}1&1\\2&-1\end{matrix}\,\right|\,\begin{matrix}\frac{1}{2}\\\frac{1}{2}\end{matrix}\right) \sim\left(\left.\begin{matrix}1&1\\0&-3\end{matrix}\,\right|\,\begin{matrix}\frac{1}{2}\\-\frac{1}{2}\end{matrix}\right) \sim\left(\left.\begin{matrix}3&0\\0&3\end{matrix}\,\right|\,\begin{matrix}1\\\frac{1}{2}\end{matrix}\right) \quad\Longrightarrow\quad\left\{\begin{array}{l}c_1=\frac{1}{3}\\[2.5mm]c_2=\frac{1}{6}.\end{array}\right.\]

Nu volgt: \(\lim\limits_{k\to\infty}\mathbf{x}_k=\frac{1}{3}\begin{pmatrix}1\\2\end{pmatrix}\). Dit heet een evenwichtstoestand of evenwichtstoestandsvector.

Stelling: Iedere stochastische (of Markov) matrix \(M\) heeft een evenwichtstoestand(svector) \(\mathbf{q}\), dat is een kansvector zodat \(M\mathbf{q}=\mathbf{q}\).
Dus, \(\mathbf{q}\) is een eigenvector van \(M\) behorende bij de eigenwaarde \(1\).

Als \(M\) een stochastische (of Markov) matrix is, dan tellen de elementen in elke kolom op tot \(1\). Hieruit volgt dat \(\det(M-\lambda I)\) gelijk is aan de determinant van de matrix die uit \(M-\lambda I\) ontstaat door alle andere rijen op te tellen bij de eerste (bijvoorbeeld). Dan zijn alle elementen in de eerste rij gelijk aan \(1-\lambda\) waaruit volgt dat \(1-\lambda\) een factor is van het karakteristieke polynoom \(\det(M-\lambda I)\). Hieruit volgt dat \(\lambda=1\) een eigenwaarde van \(M\) is. Het is veel lastiger om aan te tonen dat er een kansvector bestaat die een eigenvector is van \(M\) behorende bij de eigenwaarde \(\lambda=1\).

Voorbeeld: Eerder bekeken we een voorbeeld van een autoverhuurbedrijf met drie vestigingen (vliegveld, centrum en buitenwijk):

\[\mathbf{x}_{k+1}=A\mathbf{x}_k,\quad k=0,1,2,\ldots\quad\text{with}\quad A=\begin{pmatrix}0.85&0.15&0.15\\0.10&0.80&0.05\\0.05&0.05&0.80\end{pmatrix}.\]

Merk op dat \(A\) een stochastische (of Markov) matrix is. Nu geldt:

\begin{align*} \det(A-\lambda I)&=\begin{vmatrix}0.85-\lambda&0.15&0.15\\0.10&0.80-\lambda&0.05\\0.05&0.05&0.80-\lambda\end{vmatrix} =\begin{vmatrix}1-\lambda&1-\lambda&1-\lambda\\0.10&0.80-\lambda&0.05\\0.05&0.05&0.80-\lambda\end{vmatrix} =\begin{vmatrix}1-\lambda&0&0\\0.10&0.70-\lambda&-0.05\\0.05&0&0.75-\lambda\end{vmatrix}\\[2.5mm] &=(1-\lambda)\begin{vmatrix}0.70-\lambda&-0.05\\0&0.75-\lambda\end{vmatrix}=(1-\lambda)(0.75-\lambda)(0.70-\lambda). \end{align*}

Hieruit volgt dat de eigenwaarden zijn \(\lambda_1=1\), \(\lambda_2=0.75\) en \(\lambda_3=0.70\). Verder geldt:

\[\lambda_1=1:\quad\begin{pmatrix}-0.15&0.15&0.15\\0.10&-0.20&0.05\\0.05&0.05&-0.20\end{pmatrix} \sim\begin{pmatrix}1&-1&-1\\2&-4&1\\1&1&-4\end{pmatrix}\sim\begin{pmatrix}1&-1&-1\\0&-2&3\\0&2&-3\end{pmatrix} \sim\begin{pmatrix}2&0&-5\\0&2&-3\\0&0&0\end{pmatrix}\quad\Longrightarrow\quad\mathbf{v}_1=\begin{pmatrix}5\\3\\2\end{pmatrix},\] \[\lambda_2=0.75:\quad\begin{pmatrix}0.05&0.15&0.15\\0.10&0.05&0.05\\0.05&0.05&0.05\end{pmatrix} \sim\begin{pmatrix}1&3&3\\2&1&1\\1&1&1\end{pmatrix}\sim\begin{pmatrix}1&1&1\\0&1&1\\0&0&0\end{pmatrix} \sim\begin{pmatrix}1&0&0\\0&1&1\\0&0&0\end{pmatrix}\quad\Longrightarrow\quad\mathbf{v}_2=\begin{pmatrix}0\\1\\-1\end{pmatrix}\]

en

\[\lambda_3=0.70:\quad\begin{pmatrix}0.15&0.15&0.15\\0.10&0.10&0.05\\0.05&0.05&0.10\end{pmatrix} \sim\begin{pmatrix}1&1&1\\2&2&1\\1&1&2\end{pmatrix}\sim\begin{pmatrix}1&1&1\\0&0&1\\0&0&0\end{pmatrix} \sim\begin{pmatrix}1&1&0\\0&0&1\\0&0&0\end{pmatrix}\quad\Longrightarrow\quad\mathbf{v}_3=\begin{pmatrix}1\\-1\\0\end{pmatrix}.\]

Dus geldt

\[\mathbf{x}_k=c_1\lambda_1^k\mathbf{v}_1+c_2\lambda_2^k\mathbf{v}_2+c_3\lambda_3^k\mathbf{v}_3=c_1\begin{pmatrix}5\\3\\2\end{pmatrix} +c_2\left(0.75\right)^k\begin{pmatrix}0\\1\\-1\end{pmatrix}+c_3\left(0.70\right)^k\begin{pmatrix}1\\-1\\0\end{pmatrix},\quad k=0,1,2,\ldots,\]

waarbij \(c_1\), \(c_2\) en \(c_3\) bepaald worden door de begintoestand: \(\mathbf{x}_0=c_1\mathbf{v}_1+c_2\mathbf{v}_2+c_3\mathbf{v}_3\). Bijvoorbeeld, als \(\mathbf{x}_0=\begin{pmatrix}0.40\\0.30\\0.30\end{pmatrix}\), dan volgt:

\[c_1\begin{pmatrix}5\\3\\2\end{pmatrix}+c_2\begin{pmatrix}0\\1\\-1\end{pmatrix}+c_3\begin{pmatrix}1\\-1\\0\end{pmatrix}=\begin{pmatrix}0.40\\0.30\\0.30\end{pmatrix} \quad\Longrightarrow\quad c_1=0.10,\quad c_2=-0.10\quad\text{en}\quad c_3=-0.10.\]

Omdat \(\mathbf{x}_0\) een kansvector is, leidt dit tot een Markov keten. Echter, het is ook mogelijk om met aantallen auto's te werken (bijvoorbeeld):

\[\mathbf{x}_0=\begin{pmatrix}40\\30\\30\end{pmatrix}\quad\Longrightarrow\quad\mathbf{x}_k=\begin{pmatrix}50\\30\\20\end{pmatrix} -(0.75)^k\begin{pmatrix}0\\10\\-10\end{pmatrix}-(0.70)^k\begin{pmatrix}10\\-10\\0\end{pmatrix},\quad k=0,1,2,\ldots.\]

Merk op dat \(\lim\limits_{k\to\infty}\mathbf{x}_k=\begin{pmatrix}50\\30\\20\end{pmatrix}\) en dat betekent dat de optimale verdeling van de auto's over de drie vestigingen is: \(50\) bij het vliegveld, \(30\) in de binnenstad en \(20\) in de buitenwijk. Echter, omdat de eigenwaarden gelijk zijn voor iedere begintoestand \(\mathbf{x}_0\) zal elke (redelijke) verdeling van de auto's uiteindelijk stabiliseren tot de evenwichtstoestand(svector) \(\begin{pmatrix}50\\30\\20\end{pmatrix}\).

De oplossing van een discreet dynamisch systeem \(\mathbf{x}_{k+1}=A\mathbf{x}_k\) met \(k=0,1,2,\ldots\) kan geschreven worden als \(\mathbf{x}_k=A^k\mathbf{x}_0\) voor \(k=0,1,2,\ldots\). Als \(A\) diagonaliseerbaar is, dan geldt: \(A=PDP^{-1}\) voor zekere inverteerbare matrix \(P\) en diagonaalmatrix \(D\). In dat geval geldt: \(A^k=PD^kP^{-1}\).

Neem aan dat \(A\) diagonaliseerbaar is en dat \(A=PDP^{-1}\) voor zekere inverteerbare matrix \(P\) en diagonaalmatrix \(D\). Stel nu \(\mathbf{x}_k=P\mathbf{y}_k\) voor \(k=0,1,2,\ldots\), dan volgt:

\[\mathbf{x}_{k+1}=A\mathbf{x}_k\quad\Longleftrightarrow\quad P\mathbf{y}_{k+1}=AP\mathbf{y}_k=PDP^{-1}P\mathbf{y}_k=PD\mathbf{y}_k,\quad k=0,1,2,\ldots.\]

Omdat \(P\) inverteerbaar is, kunnen we (links) vermenigvuldigen met \(P^{-1}\) en dan volgt

\[\mathbf{x}_{k+1}=A\mathbf{x}_k\quad\Longleftrightarrow\quad\mathbf{y}_{k+1}=D\mathbf{y}_k,\quad k=0,1,2,\ldots.\]

Als \(D=\text{diag}(\lambda_1,\ldots,\lambda_n)\) dan volgt hieruit dat \(\mathbf{y}_k=\begin{pmatrix}c_1\lambda_1^k\\\vdots\\c_n\lambda_n^k\end{pmatrix}\) voor \(k=0,1,2,\ldots\). Laat \(P=\Bigg(\mathbf{v}_1\;\ldots\;\mathbf{v}_n\Bigg)\), dan geldt:

\[\mathbf{x}_k=P\mathbf{y}_k=\Bigg(\mathbf{v}_1\;\ldots\;\mathbf{v}_n\Bigg)\begin{pmatrix}c_1\lambda_1^k\\\vdots\\c_n\lambda_n^k\end{pmatrix} =c_1\lambda_1^k\mathbf{v}_1+\cdots+c_n\lambda_n^k\mathbf{v}_n,\quad k=0,1,2,\ldots.\]

In het geval van een \(2\times2\) matrix \(A\) kunnen we de rij vectoren \(\{\mathbf{x}_k\}_{k=0}^{\infty}\) die voldoen aan het discreet dynamische systeem \(\mathbf{x}_{k+1}=A\mathbf{x}_k\) voor \(k=0,1,2\ldots\) 'plotten' in het platte vlak \(\mathbb{R}^2\). De grafiek van \(\{\mathbf{x}_k\}_{k=0}^{\infty}\) heet een baan van het discreet dynamische systeem. Merk op dat zo'n baan bestaat uit 'losse punten' in \(\mathbb{R}^2\) en dat die alleen afhangt van de begintoestand \(\mathbf{x}_0\).

Laat \(A\) diagonaliseerbaar zijn met eigenvectoren \(\mathbf{v}_1\) en \(\mathbf{v}_2\) behorende bij de eigenwaarden \(\lambda_1\) en \(\lambda_2\) respectievelijk. Dan wordt het gedrag van de oplossingen \(\mathbf{x}_k=c_1\lambda_1^k\mathbf{v}_1+c_2\lambda_2^k\mathbf{v}_2\) met \(k=0,1,2,\ldots\) bepaald door de eigenwaarden.

Als \(|\lambda_1| < 1\) en \(|\lambda_2| < 1\), dan gaan alle oplossingen naar de oorsprong voor \(k\to\infty\). In dat geval heet de oorsprong een aantrekker (attractor) van het dynamische systeem.

Als \(|\lambda_1| > 1\) en \(|\lambda_2| > 1\), dan gaan alle oplossingen naar oneindig (weg van de oorsprong) voor \(k\to\infty\). In dat geval heet de oorsprong een afstoter van het dynamische systeem.

Als \(|\lambda_1| > 1\) en \(|\lambda_2| < 1\), dan heet de oorspring een zadelpunt van het dynamische systeem. Sommige banen bewegen naar de oorsprong toe, terwijl andere banen naar oneindig gaan (weg van de oorsprong) afhankelijk van de begintoestand \(\mathbf{x}_0\).

In het geval van niet-reële eigenwaarden \(\lambda=\alpha\pm i\beta\) met \(\alpha,\beta\in\mathbb{R}\) en \(\beta\neq0\) hebben de banen de vorm van een spiraal. Als \(|\lambda|=\sqrt{\alpha^2+\beta^2} < 1\), dan bewegen deze in de richting van de oorsprong, en als \(|\lambda|=\sqrt{\alpha^2+\beta^2} > 1\), dan bewegen deze naar oneindig (weg van de oorsprong).

---

Laatst gewijzigd op 5 april 2021