Anwendungen: Matrixpotenzen, Rekursionen und Markow-Ketten
Lesen anpassen
Nach dieser Lektion kannst du
hohe Potenzen einer diagonalisierbaren Matrix mit 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 bestimmen und erklären, wie schnell sich die Kette ihr nähert,
Lösungen eines linearen Differentialgleichungssystems aus Eigenvektoren zusammensetzen.
Vorausgesetzt: Diagonalisierbarkeit
Drei Fragen, die zunächst nichts miteinander zu tun haben:
- Wie sieht für aus, ohne neunzehn Matrixprodukte auszurechnen?
- Die Fibonacci-Zahlen 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 geht durch Multiplikation mit einer festen Matrix in den nächsten über, . Dann ist , und die Frage lautet jedes Mal: Was macht für große ? Mit Eigenwerten wird daraus eine Rechnung mit Zahlenpotenzen.
Die Quotienten aufeinanderfolgender Fibonacci-Zahlen sind , , , . Was passiert mit für große ?
Potenzen diagonalisierbarer Matrizen
Sei und invertierbar mit , . Dann gilt für jede natürliche Zahl
Induktion nach . Für steht da. Gilt , dann ist
Das Produkt zweier Diagonalmatrizen ist die Diagonalmatrix der Produkte der Diagonaleinträge. Mit Induktion folgt daraus .
Eine geschlossene Formel für
Eine geschlossene Formel für
Für kennen wir aus der letzten Lektion , und . Erst (die Spalten von mal und ), dann mal :
Probe: Für kommt heraus, für die Matrix , und die stimmt mit überein.
Die Formel zeigt mehr als eine einzelne Potenz: Für große ist neben vernachlässigbar, also . Der größte Eigenwert bestimmt das Wachstum, und alle Spalten von drehen sich in die Richtung des Eigenvektors .
Berechne mit der Formel den Eintrag oben links von für .
Die Formel von Binet für die Fibonacci-Zahlen
Die Formel von Binet für die Fibonacci-Zahlen
Die Fibonacci-Zahlen sind durch , und für festgelegt. Gesucht ist eine Formel für .
Fasse zwei aufeinanderfolgende Zahlen zu einem Vektor zusammen. Die Rekursion wird eine Matrixgleichung mit :
Was die Formel verrät
Was die Formel verrät
Obwohl irrational ist, kommt für jedes eine ganze Zahl heraus. Wegen ist für alle . Also ist die ganze Zahl, die am nächsten liegt. Zum Beispiel ist und .
Außerdem wächst wie , also exponentiell, und der Quotient
geht gegen , weil ist. Das erklärt die Beobachtung aus der Frage oben. Weil negativ ist, wechselt das Vorzeichen von ; deshalb liegen die Quotienten abwechselnd über und unter . Dasselbe Vorgehen funktioniert für jede Rekursion , deren Matrix zwei verschiedene Eigenwerte hat.
Wie viele Ziffern hat ? Nutze sowie und .
Markow-Kette und stationäre Verteilung
Ein System ist zu jedem Zeitpunkt in einem von Zuständen . Von einem Schritt zum nächsten wechselt es zufällig, und die Wahrscheinlichkeit , von Zustand in Zustand zu wechseln, hängt nur von und ab, nicht von der Vorgeschichte und nicht von . So ein Modell heißt (endliche, zeitlich homogene) Markow-Kette, nach Andrei Markow.
Die Übergangsmatrix hat Einträge , und jede Spalte hat die Summe , denn von Zustand aus landet das System sicher in irgendeinem Zustand. Solche Matrizen heißen spaltenstochastisch.
Sei der Vektor der Wahrscheinlichkeiten, zum Zeitpunkt in den einzelnen Zuständen zu sein. Nach dem Satz von der totalen Wahrscheinlichkeit ist die -te Komponente von gleich , also .
Eine stationäre Verteilung ist ein Vektor mit Einträgen und Summe , für den gilt. Das ist ein Eigenvektor von zum Eigenwert , so normiert, dass seine Einträge sich zu addieren.
Viele Bücher rechnen mit Zeilenvektoren, , und Zeilensummen ; das ist dasselbe, transponiert.
Ein Carsharing-Auto zwischen zwei Stationen
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 wieder an A und mit an B. Steht es an B, kommt es mit nach A und bleibt mit an B. Mit ist
Eigenwert : ergibt , also den Eigenvektor und, normiert, die stationäre Verteilung . Eigenwert : ergibt den Eigenvektor .
Am ersten Morgen steht das Auto an B: . Damit ist
| Tag | ||||||
|---|---|---|---|---|---|---|
| Wahrscheinlichkeit für A |
Die Werte für und sind gerundet. Langfristig steht das Auto mit Wahrscheinlichkeit an A, unabhängig vom Start. Der Abstand zur stationären Verteilung schrumpft mit dem Faktor pro Tag; der zweite Eigenwert bestimmt also, wie schnell sich die Kette einpendelt.
Jede spaltenstochastische Matrix hat den Eigenwert 1
Sei eine Matrix, deren Spalten jeweils die Summe haben. Dann ist ein Eigenwert von .
Sei . Die -te Komponente von ist die Summe der -ten Zeile von , also der -ten Spalte von , und die ist . Somit , und ist ein Eigenwert von . Eine Matrix und ihre Transponierte haben dasselbe charakteristische Polynom, denn . Also ist auch ein Eigenwert von .
Im Carsharing-Beispiel: Welche Zahl bestimmt, wie schnell sich der stationären Verteilung nähert?
Jede Markow-Kette pendelt sich ein
Jede Markow-Kette pendelt sich ein
„Weil ein Eigenwert ist, konvergiert immer gegen die stationäre Verteilung.“
Nicht immer. Für wechselt das System bei jedem Schritt sicher den Zustand. Die stationäre Verteilung gibt es, aber vom Start aus springt ewig zwischen und . Der Grund ist der zweite Eigenwert : Sein Betrag ist , also schrumpft der Anteil nicht. Konvergenz gegen die stationäre Verteilung erhält man, wenn alle anderen Eigenwerte einen Betrag kleiner als haben, zum Beispiel wenn alle Einträge von positiv sind.
Potenzen eintragsweise nehmen
Potenzen eintragsweise nehmen
„ bekommt man, indem man jeden Eintrag quadriert.“ Für ergäbe das .
Richtig ist . Eintragsweise potenzieren darf man nur bei Diagonalmatrizen. Genau deshalb geht man den Umweg : Die Potenz wird bei genommen, wo sie eintragsweise ist, und und übersetzen hin und zurück. Achte dabei auf die Reihenfolge: , wenn die Spalten von die Eigenvektoren sind.
Ausblick: lineare Differentialgleichungssysteme
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 die Temperaturdifferenz von Raum zur Umgebung in Kelvin, die Zeit in Stunden, und beide Vorgänge laufen mit der Rate pro Stunde: und . In Matrixform ist das mit .
Ist ein Eigenvektor von zum Eigenwert , dann ist eine Lösung, denn . Hier hat die Eigenwerte mit und mit . Für ergibt , :
Die Rolle von übernimmt hier . Der Mittelwert der beiden Räume klingt mit ab, der Unterschied zwischen ihnen schneller, mit : Nach einer Stunde ist er auf gesunken. Die Theorie der Differentialgleichungen zeigt, dass es keine weiteren Lösungen gibt: Ist diagonalisierbar, hat jede Lösung die Form .
Zusammenfassung
Ist mit , dann ist , und entsteht durch Potenzieren der Diagonaleinträge.
Ohne Inverse: Zerlege in Eigenvektoren, dann ist ; der betragsgrößte Eigenwert bestimmt das Langzeitverhalten.
Eine Rekursion zweiter Ordnung wird mit zur Gleichung ; für Fibonacci ergibt das die Formel von Binet mit .
ist die nächste ganze Zahl zu , und .
Eine Markow-Kette wird durch eine spaltenstochastische Matrix beschrieben, ; jede solche Matrix hat den Eigenwert .
Die stationäre Verteilung ist ein normierter Eigenvektor zum Eigenwert ; wie schnell die Kette sich einpendelt, bestimmen die übrigen Eigenwerte, und mit einem Eigenwert vom Betrag neben der muss sie es nicht.
Bei übernimmt die Rolle von .
Übungen
Die Matrix hat die Eigenvektoren zum Eigenwert und zum Eigenwert . Bestimme den Eintrag oben links von .
Sei . Gib den Eintrag oben rechts von als Term in an.
Die Folge , , gehört zur Matrix mit den Eigenwerten und . Leite eine geschlossene Formel her und berechne damit .
Welche Verteilung ist stationär für die Markow-Kette mit der Übergangsmatrix ?
Im Carsharing-Beispiel steht das Auto am ersten Morgen () an Station B. Mit welcher Wahrscheinlichkeit steht es am Morgen an Station A? Gib die Wahrscheinlichkeit als Dezimalzahl an.
Sei spaltenstochastisch und ein Eigenvektor von zu einem Eigenwert . Beweise, dass sich die Einträge von zu addieren. Prüfe die Aussage am Carsharing-Beispiel.
Bestimme für die Lösung von mit in der Form , und prüfe durch Ableiten, dass sie die Gleichung erfüllt.