Lektion 7.4

Anwendungen: Matrixpotenzen, Rekursionen und Markow-Ketten

50 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • hohe Potenzen einer diagonalisierbaren Matrix mit Ak=SDkS−1A^k = S D^k S^{-1} berechnen,

  • eine lineare Rekursion als Matrixgleichung schreiben und mit Eigenwerten eine geschlossene Formel herleiten, etwa die Formel von Binet für die Fibonacci-Zahlen,

  • die stationäre Verteilung einer Markow-Kette als Eigenvektor zum Eigenwert 11 bestimmen und erklären, wie schnell sich die Kette ihr nähert,

  • Lösungen eines linearen Differentialgleichungssystems x′(t)=Ax(t)x'(t) = Ax(t) aus Eigenvektoren zusammensetzen.

Vorausgesetzt: Diagonalisierbarkeit

Drei Fragen, die zunächst nichts miteinander zu tun haben:

  • Wie sieht A20A^{20} für A=(4123)A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix} aus, ohne neunzehn Matrixprodukte auszurechnen?
  • Die Fibonacci-Zahlen 0,1,1,2,3,5,8,13,…0, 1, 1, 2, 3, 5, 8, 13, \dots entstehen, indem man jeweils die zwei vorigen addiert. Gibt es eine Formel für die fünfzigste, ohne alle davor zu berechnen? Und wie schnell wachsen sie?
  • Ein Carsharing-Auto wechselt jeden Tag zufällig zwischen zwei Stationen. Mit welcher Wahrscheinlichkeit steht es nach langer Zeit an welcher Station?

Alle drei haben dieselbe Gestalt: Ein Zustand xkx_k geht durch Multiplikation mit einer festen Matrix in den nächsten über, xk+1=Axkx_{k+1} = A x_k. Dann ist xk=Akx0x_k = A^k x_0, und die Frage lautet jedes Mal: Was macht AkA^k für große kk? Mit Eigenwerten wird daraus eine Rechnung mit Zahlenpotenzen.

Vermute zuerst

Die Quotienten aufeinanderfolgender Fibonacci-Zahlen sind 138=1,625\frac{13}{8} = 1{,}625, 2113≈1,615\frac{21}{13} \approx 1{,}615, 3421≈1,619\frac{34}{21} \approx 1{,}619, 5534≈1,618\frac{55}{34} \approx 1{,}618. Was passiert mit Fk+1Fk\frac{F_{k+1}}{F_k} für große kk?

Satz

Potenzen diagonalisierbarer Matrizen

Sei A∈Kn×nA \in K^{n \times n} und SS invertierbar mit A=SDS−1A = S D S^{-1}, D=diag⁡(d1,…,dn)D = \operatorname{diag}(d_1, \dots, d_n). Dann gilt für jede natürliche Zahl kk

Ak=SDkS−1,Dk=diag⁡(d1k,…,dnk)A^k = S D^k S^{-1}, \qquad D^k = \operatorname{diag}(d_1^k, \dots, d_n^k)
Beispiel

Eine geschlossene Formel für AkA^k

Für A=(4123)A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix} kennen wir aus der letzten Lektion S=(111−2)S = \begin{pmatrix} 1 & 1 \\ 1 & -2 \end{pmatrix}, S−1=13(211−1)S^{-1} = \frac{1}{3} \begin{pmatrix} 2 & 1 \\ 1 & -1 \end{pmatrix} und D=diag⁡(5,2)D = \operatorname{diag}(5, 2). Erst SDk=(5k2k5k−2⋅2k)S D^k = \begin{pmatrix} 5^k & 2^k \\ 5^k & -2 \cdot 2^k \end{pmatrix} (die Spalten von SS mal 5k5^k und 2k2^k), dann mal S−1S^{-1}:

Ak=13(2⋅5k+2k5k−2k2⋅5k−2⋅2k5k+2⋅2k)A^k = \frac{1}{3} \begin{pmatrix} 2 \cdot 5^k + 2^k & 5^k - 2^k \\ 2 \cdot 5^k - 2 \cdot 2^k & 5^k + 2 \cdot 2^k \end{pmatrix}

Probe: Für k=1k = 1 kommt 13(12369)=A\frac{1}{3} \begin{pmatrix} 12 & 3 \\ 6 & 9 \end{pmatrix} = A heraus, für k=2k = 2 die Matrix (1871411)\begin{pmatrix} 18 & 7 \\ 14 & 11 \end{pmatrix}, und die stimmt mit A⋅AA \cdot A überein.

Die Formel zeigt mehr als eine einzelne Potenz: Für große kk ist 2k2^k neben 5k5^k vernachlässigbar, also Ak≈5k3(2121)A^k \approx \frac{5^k}{3} \begin{pmatrix} 2 & 1 \\ 2 & 1 \end{pmatrix}. Der größte Eigenwert bestimmt das Wachstum, und alle Spalten von AkA^k drehen sich in die Richtung des Eigenvektors (1,1)(1, 1).

Kurz geprüft

Berechne mit der Formel den Eintrag oben links von A3A^3 für A=(4123)A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}.

Schritt für Schritt

Die Formel von Binet für die Fibonacci-Zahlen

Die Fibonacci-Zahlen sind durch F0=0F_0 = 0, F1=1F_1 = 1 und Fk+1=Fk+Fk−1F_{k+1} = F_k + F_{k-1} für k≥1k \geq 1 festgelegt. Gesucht ist eine Formel für FkF_k.

  1. Fasse zwei aufeinanderfolgende Zahlen zu einem Vektor xk=(Fk+1,Fk)x_k = (F_{k+1}, F_k) zusammen. Die Rekursion wird eine Matrixgleichung mit x0=(1,0)x_0 = (1, 0):

    xk=(Fk+1Fk)=(1110)(FkFk−1)=Axk−1,xk=Akx0x_k = \begin{pmatrix} F_{k+1} \\ F_k \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_k \\ F_{k-1} \end{pmatrix} = A x_{k-1}, \qquad x_k = A^k x_0
Schritt 1 von 5
Beispiel

Was die Formel verrät

Obwohl 5\sqrt{5} irrational ist, kommt für jedes kk eine ganze Zahl heraus. Wegen ∣ψ∣<1|\psi| < 1 ist ∣ψk5∣≤15≈0,447<12\left| \frac{\psi^k}{\sqrt{5}} \right| \leq \frac{1}{\sqrt{5}} \approx 0{,}447 < \frac{1}{2} für alle k≥0k \geq 0. Also ist FkF_k die ganze Zahl, die φk5\frac{\varphi^k}{\sqrt{5}} am nächsten liegt. Zum Beispiel ist φ105≈55,004\frac{\varphi^{10}}{\sqrt{5}} \approx 55{,}004 und F10=55F_{10} = 55.

Außerdem wächst FkF_k wie φk\varphi^k, also exponentiell, und der Quotient

Fk+1Fk=φk+1−ψk+1φk−ψk=φ⋅1−(ψ/φ)k+11−(ψ/φ)k⟶φ\frac{F_{k+1}}{F_k} = \frac{\varphi^{k+1} - \psi^{k+1}}{\varphi^k - \psi^k} = \varphi \cdot \frac{1 - (\psi/\varphi)^{k+1}}{1 - (\psi/\varphi)^k} \longrightarrow \varphi

geht gegen φ\varphi, weil ∣ψ/φ∣<1|\psi / \varphi| < 1 ist. Das erklärt die Beobachtung aus der Frage oben. Weil ψ\psi negativ ist, wechselt das Vorzeichen von ψk\psi^k; deshalb liegen die Quotienten abwechselnd über und unter φ\varphi. Dasselbe Vorgehen funktioniert für jede Rekursion ak+1=p ak+q ak−1a_{k+1} = p\, a_k + q\, a_{k-1}, deren Matrix (pq10)\begin{pmatrix} p & q \\ 1 & 0 \end{pmatrix} zwei verschiedene Eigenwerte hat.

Kurz geprüft

Wie viele Ziffern hat F50F_{50}? Nutze Fk≈φk5F_k \approx \frac{\varphi^k}{\sqrt{5}} sowie log⁡10φ≈0,2090\log_{10} \varphi \approx 0{,}2090 und log⁡105≈0,3495\log_{10} \sqrt{5} \approx 0{,}3495.

Definition

Markow-Kette und stationäre Verteilung

Ein System ist zu jedem Zeitpunkt k=0,1,2,…k = 0, 1, 2, \dots in einem von nn Zuständen 1,…,n1, \dots, n. Von einem Schritt zum nächsten wechselt es zufällig, und die Wahrscheinlichkeit pijp_{ij}, von Zustand jj in Zustand ii zu wechseln, hängt nur von ii und jj ab, nicht von der Vorgeschichte und nicht von kk. So ein Modell heißt (endliche, zeitlich homogene) Markow-Kette, nach Andrei Markow.

Die Übergangsmatrix P=(pij)P = (p_{ij}) hat Einträge pij≥0p_{ij} \geq 0, und jede Spalte hat die Summe 11, denn von Zustand jj aus landet das System sicher in irgendeinem Zustand. Solche Matrizen heißen spaltenstochastisch.

Sei xk∈Rnx_k \in \mathbb{R}^n der Vektor der Wahrscheinlichkeiten, zum Zeitpunkt kk in den einzelnen Zuständen zu sein. Nach dem Satz von der totalen Wahrscheinlichkeit ist die ii-te Komponente von xk+1x_{k+1} gleich ∑jpij (xk)j\sum_j p_{ij}\, (x_k)_j, also xk+1=Pxkx_{k+1} = P x_k.

Eine stationäre Verteilung ist ein Vektor xx mit Einträgen ≥0\geq 0 und Summe 11, für den Px=xPx = x gilt. Das ist ein Eigenvektor von PP zum Eigenwert 11, so normiert, dass seine Einträge sich zu 11 addieren.

Viele Bücher rechnen mit Zeilenvektoren, xk+1=xkPx_{k+1} = x_k P, und Zeilensummen 11; das ist dasselbe, transponiert.

Beispiel

Ein Carsharing-Auto zwischen zwei Stationen

Ein Auto steht jeden Morgen an Station A oder B. Steht es an A, steht es am nächsten Morgen mit Wahrscheinlichkeit 0,90{,}9 wieder an A und mit 0,10{,}1 an B. Steht es an B, kommt es mit 0,20{,}2 nach A und bleibt mit 0,80{,}8 an B. Mit xk=(Wahrscheinlichkeit fu¨r A,Wahrscheinlichkeit fu¨r B)x_k = (\text{Wahrscheinlichkeit für A}, \text{Wahrscheinlichkeit für B}) ist

P=(0,90,20,10,8),χP(t)=t2−1,7 t+0,7=(t−1)(t−0,7).P = \begin{pmatrix} 0{,}9 & 0{,}2 \\ 0{,}1 & 0{,}8 \end{pmatrix}, \qquad \chi_P(t) = t^2 - 1{,}7\,t + 0{,}7 = (t - 1)(t - 0{,}7).

Eigenwert 11: P−E2=(−0,10,20,1−0,2)P - E_2 = \begin{pmatrix} -0{,}1 & 0{,}2 \\ 0{,}1 & -0{,}2 \end{pmatrix} ergibt x1=2x2x_1 = 2x_2, also den Eigenvektor (2,1)(2, 1) und, normiert, die stationäre Verteilung (23,13)(\frac{2}{3}, \frac{1}{3}). Eigenwert 0,70{,}7: P−0,7E2=(0,20,20,10,1)P - 0{,}7 E_2 = \begin{pmatrix} 0{,}2 & 0{,}2 \\ 0{,}1 & 0{,}1 \end{pmatrix} ergibt den Eigenvektor (1,−1)(1, -1).

Am ersten Morgen steht das Auto an B: x0=(0,1)=13(2,1)−23(1,−1)x_0 = (0, 1) = \frac{1}{3}(2, 1) - \frac{2}{3}(1, -1). Damit ist

xk=13(21)−23⋅0,7k(1−1)  ⟶  (2/31/3)x_k = \frac{1}{3} \begin{pmatrix} 2 \\ 1 \end{pmatrix} - \frac{2}{3} \cdot 0{,}7^k \begin{pmatrix} 1 \\ -1 \end{pmatrix} \;\longrightarrow\; \begin{pmatrix} 2/3 \\ 1/3 \end{pmatrix}
Tag kk00112233551010
Wahrscheinlichkeit für A000,20{,}20,340{,}340,4380{,}4380,5550{,}5550,6480{,}648

Die Werte für k=5k = 5 und k=10k = 10 sind gerundet. Langfristig steht das Auto mit Wahrscheinlichkeit 23\frac{2}{3} an A, unabhängig vom Start. Der Abstand zur stationären Verteilung schrumpft mit dem Faktor 0,70{,}7 pro Tag; der zweite Eigenwert bestimmt also, wie schnell sich die Kette einpendelt.

Satz

Jede spaltenstochastische Matrix hat den Eigenwert 1

Sei P∈Rn×nP \in \mathbb{R}^{n \times n} eine Matrix, deren Spalten jeweils die Summe 11 haben. Dann ist 11 ein Eigenwert von PP.

Kurz geprüft

Im Carsharing-Beispiel: Welche Zahl bestimmt, wie schnell sich xkx_k der stationären Verteilung nähert?

Häufige Fehler

Jede Markow-Kette pendelt sich ein

„Weil 11 ein Eigenwert ist, konvergiert Pkx0P^k x_0 immer gegen die stationäre Verteilung.“

Richtig ist

Nicht immer. Für P=(0110)P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} wechselt das System bei jedem Schritt sicher den Zustand. Die stationäre Verteilung (12,12)(\frac{1}{2}, \frac{1}{2}) gibt es, aber vom Start (1,0)(1, 0) aus springt xkx_k ewig zwischen (1,0)(1, 0) und (0,1)(0, 1). Der Grund ist der zweite Eigenwert −1-1: Sein Betrag ist 11, also schrumpft der Anteil (−1)k(1,−1)(-1)^k (1, -1) nicht. Konvergenz gegen die stationäre Verteilung erhält man, wenn alle anderen Eigenwerte einen Betrag kleiner als 11 haben, zum Beispiel wenn alle Einträge von PP positiv sind.

Häufige Fehler

Potenzen eintragsweise nehmen

„A2A^2 bekommt man, indem man jeden Eintrag quadriert.“ Für A=(4123)A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix} ergäbe das (16149)\begin{pmatrix} 16 & 1 \\ 4 & 9 \end{pmatrix}.

Richtig ist

Richtig ist A2=A⋅A=(1871411)A^2 = A \cdot A = \begin{pmatrix} 18 & 7 \\ 14 & 11 \end{pmatrix}. Eintragsweise potenzieren darf man nur bei Diagonalmatrizen. Genau deshalb geht man den Umweg Ak=SDkS−1A^k = S D^k S^{-1}: Die Potenz wird bei DD genommen, wo sie eintragsweise ist, und SS und S−1S^{-1} übersetzen hin und zurück. Achte dabei auf die Reihenfolge: SDkS−1S D^k S^{-1}, wenn die Spalten von SS die Eigenvektoren sind.

Beispiel

Ausblick: lineare Differentialgleichungssysteme

Zwei Räume tauschen Wärme miteinander aus und geben Wärme an die Umgebung ab. In einem stark vereinfachten Modell sei xi(t)x_i(t) die Temperaturdifferenz von Raum ii zur Umgebung in Kelvin, tt die Zeit in Stunden, und beide Vorgänge laufen mit der Rate 11 pro Stunde: x1′=−x1+(x2−x1)x_1' = -x_1 + (x_2 - x_1) und x2′=−x2+(x1−x2)x_2' = -x_2 + (x_1 - x_2). In Matrixform ist das x′(t)=Ax(t)x'(t) = A x(t) mit A=(−211−2)A = \begin{pmatrix} -2 & 1 \\ 1 & -2 \end{pmatrix}.

Ist vv ein Eigenvektor von AA zum Eigenwert λ\lambda, dann ist x(t)=eλtvx(t) = e^{\lambda t} v eine Lösung, denn x′(t)=λeλtv=eλtAv=Ax(t)x'(t) = \lambda e^{\lambda t} v = e^{\lambda t} A v = A x(t). Hier hat AA die Eigenwerte −1-1 mit v1=(1,1)v_1 = (1, 1) und −3-3 mit v2=(1,−1)v_2 = (1, -1). Für x(0)=(3,1)x(0) = (3, 1) ergibt c1+c2=3c_1 + c_2 = 3, c1−c2=1c_1 - c_2 = 1:

x(t)=2e−t(11)+e−3t(1−1)x(t) = 2 e^{-t} \begin{pmatrix} 1 \\ 1 \end{pmatrix} + e^{-3t} \begin{pmatrix} 1 \\ -1 \end{pmatrix}

Die Rolle von λk\lambda^k übernimmt hier eλte^{\lambda t}. Der Mittelwert der beiden Räume klingt mit e−te^{-t} ab, der Unterschied zwischen ihnen schneller, mit e−3te^{-3t}: Nach einer Stunde ist er auf e−3≈5 %e^{-3} \approx 5\,\% gesunken. Die Theorie der Differentialgleichungen zeigt, dass es keine weiteren Lösungen gibt: Ist AA diagonalisierbar, hat jede Lösung die Form c1eλ1tv1+⋯+cneλntvnc_1 e^{\lambda_1 t} v_1 + \dots + c_n e^{\lambda_n t} v_n.

Zusammenfassung

  • Ist A=SDS−1A = S D S^{-1} mit D=diag⁡(d1,…,dn)D = \operatorname{diag}(d_1, \dots, d_n), dann ist Ak=SDkS−1A^k = S D^k S^{-1}, und DkD^k entsteht durch Potenzieren der Diagonaleinträge.

  • Ohne Inverse: Zerlege x0=∑civix_0 = \sum c_i v_i in Eigenvektoren, dann ist Akx0=∑ciλikviA^k x_0 = \sum c_i \lambda_i^k v_i; der betragsgrößte Eigenwert bestimmt das Langzeitverhalten.

  • Eine Rekursion zweiter Ordnung wird mit xk=(ak+1,ak)x_k = (a_{k+1}, a_k) zur Gleichung xk=Axk−1x_k = A x_{k-1}; für Fibonacci ergibt das die Formel von Binet mit φ,ψ=1±52\varphi, \psi = \frac{1 \pm \sqrt{5}}{2}.

  • FkF_k ist die nächste ganze Zahl zu φk5\frac{\varphi^k}{\sqrt{5}}, und Fk+1Fk→φ\frac{F_{k+1}}{F_k} \to \varphi.

  • Eine Markow-Kette wird durch eine spaltenstochastische Matrix PP beschrieben, xk+1=Pxkx_{k+1} = P x_k; jede solche Matrix hat den Eigenwert 11.

  • Die stationäre Verteilung ist ein normierter Eigenvektor zum Eigenwert 11; wie schnell die Kette sich einpendelt, bestimmen die übrigen Eigenwerte, und mit einem Eigenwert vom Betrag 11 neben der 11 muss sie es nicht.

  • Bei x′(t)=Ax(t)x'(t) = Ax(t) übernimmt eλtve^{\lambda t} v die Rolle von λkv\lambda^k v.

Übungen

Aufgabe 1Numerisch

Die Matrix A=(1221)A = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} hat die Eigenvektoren (1,1)(1, 1) zum Eigenwert 33 und (1,−1)(1, -1) zum Eigenwert −1-1. Bestimme den Eintrag oben links von A4A^4.

Aufgabe 2Term eingeben

Sei T=(2103)T = \begin{pmatrix} 2 & 1 \\ 0 & 3 \end{pmatrix}. Gib den Eintrag oben rechts von TkT^k als Term in kk an.

Potenzen mit ^, Wurzel als sqrt(x), Brüche mit / und Klammern.

Aufgabe 3Numerisch

Die Folge a0=0a_0 = 0, a1=1a_1 = 1, ak+1=ak+2ak−1a_{k+1} = a_k + 2a_{k-1} gehört zur Matrix (1210)\begin{pmatrix} 1 & 2 \\ 1 & 0 \end{pmatrix} mit den Eigenwerten 22 und −1-1. Leite eine geschlossene Formel her und berechne damit a10a_{10}.

Aufgabe 4Multiple Choice

Welche Verteilung ist stationär für die Markow-Kette mit der Übergangsmatrix P=(0,50,250,50,75)P = \begin{pmatrix} 0{,}5 & 0{,}25 \\ 0{,}5 & 0{,}75 \end{pmatrix}?

Aufgabe 5Numerisch

Im Carsharing-Beispiel steht das Auto am ersten Morgen (k=0k = 0) an Station B. Mit welcher Wahrscheinlichkeit steht es am Morgen k=2k = 2 an Station A? Gib die Wahrscheinlichkeit als Dezimalzahl an.

Aufgabe 6Freitext

Sei P∈Rn×nP \in \mathbb{R}^{n \times n} spaltenstochastisch und vv ein Eigenvektor von PP zu einem Eigenwert λ≠1\lambda \neq 1. Beweise, dass sich die Einträge von vv zu 00 addieren. Prüfe die Aussage am Carsharing-Beispiel.

Aufgabe 7Freitext

Bestimme für A=(−211−2)A = \begin{pmatrix} -2 & 1 \\ 1 & -2 \end{pmatrix} die Lösung von x′(t)=Ax(t)x'(t) = Ax(t) mit x(0)=(1,3)x(0) = (1, 3) in der Form c1eλ1tv1+c2eλ2tv2c_1 e^{\lambda_1 t} v_1 + c_2 e^{\lambda_2 t} v_2, und prüfe durch Ableiten, dass sie die Gleichung erfüllt.