Matrix/Stochastisch/Potenzen/Textabschnitt

Wir untersuchen nun die Potenzen von stochastischen Matrizen mit Hilfe der Summennorm und den Ergebnissen der letzten Vorlesung.


Für einen beliebigen Vektor ist Wegen

Iterative Anwendung dieser Beobachtung zeigt, dass Fakt  (2) erfüllt ist.



Es sei

eine reelle quadratische Matrix mit nichtnegativen Einträgen.

Dann ist genau dann spaltenstochastisch, wenn für Vektoren mit nichtnegativen Einträgen isometrisch bezüglich der Summennorm ist, wenn also

für alle gilt.

Es sei eine spaltenstochastische Matrix und

ein Vektor mit nichtnegativen Einträgen. Dann ist

Wenn umgekehrt die angegebene isometrische Eigenschaft gilt, so gilt insbesondere für die Bilder der Standardvektoren, dass ihre Summennorm gleich sein muss. Diese Bilder stehen in der entsprechenden Spalte der Matrix, alle Spaltensummen haben also den Wert .



Es sei eine spaltenstochastische Matrix. Dann gelten folgende Aussagen.

  1. Es gibt Eigenvektoren zum Eigenwert .
  2. Wenn es eine Zeile gibt, in der alle Einträge positiv sind, so gilt für jeden Vektor , der sowohl positive als auch negative Einträge besitzt, die Abschätzung
  3. Wenn es eine Zeile gibt, in der alle Einträge positiv sind, so ist der Eigenraum zum Eigenwert eindimensional. Es gibt dann einen Eigenvektor, der nur nichtnegative Einträge hat und insbesondere eine eindeutig bestimmte stationäre Verteilung.

(1). Die transponierte Matrix ist zeilenstochastisch und besitzt daher den Eigenvektor zum Eigenwert . Daher besitzt nach Fakt das charakteristische Polynom der transponierten Matrix eine Nullstelle an der Stelle und dies gilt nach Aufgabe dann auch für die ursprüngliche Matrix. Daher besitzt einen Eigenvektor zum Eigenwert .

(2). Es seien nun zusätzlich alle Einträge der -ten Zeile positiv und sei ein Vektor mit (mindestens) einem positiven und einem negativen Eintrag. Dann ist

(3). Wie im Beweis zu (2) seien alle Einträge der -ten Zeile positiv. Für einen jeden Eigenvektor zum Eigenwert sind nach (2) entweder alle Einträge nichtnegativ oder nichtpositiv. Somit ist für einen solchen Vektor wegen der -te Eintrag ungleich . Es seien solche Eigenvektoren. Dann gehört auch zum Fixraum. Allerdings ist die -te Komponente davon gleich und daher ist es der Nullvektor. Das bedeutet, dass und linear abhängig sind. Somit ist dieser Eigenraum eindimensional. Wegen (2) gibt es einen Eigenvektor zum Eigenwert mit nichtnegativen Einträgen. Durch Normieren sieht man, dass es auch eine stationäre Verteilung gibt.



Wir betrachten die spaltenstochastische -Matrix

bei der alle Einträge der ersten Zeile positiv sind. Nach Fakt gibt es eine eindeutige Eigenverteilung. Um diese zu bestimmen, berechnet man den Kern von

Dieser wird von erzeugt und die stationäre Verteilung ist



Für die spaltenstochastische -Matrix

ist der Eigenraum zum Eigenwert gleich , also zweidimensional. Die Aussage Fakt gilt also nicht, wenn es eine Spalte (aber keine Zeile) mit ausschließlich positiven Einträgen gibt.




Es sei eine spaltenstochastische Matrix mit der Eigenschaft, dass es eine Zeile gibt, in der alle Einträge positiv sind.

Dann konvergiert zu jedem Verteilungsvektor mit die Folge gegen die eindeutig bestimmte stationäre Verteilung von .

Es sei die nach Fakt  (3) eindeutig bestimmte stationäre Verteilung und

Dies ist ein Untervektorraum von der Dimension . Nach Fakt  (2) hat ausschließlich nichtnegative Einträge und gehört damit nicht zu . Wegen

ist invariant unter der Matrix . Somit ist

eine direkte Summenzerlegung in invariante Untervektorräume. Für jedes mit ist

nach Fakt  (2). Da die Sphäre zum Radius bezüglich jeder Norm kompakt ist, ist die induzierte Maximumsnorm von kleiner als . Nach Fakt und Fakt konvergiert daher die Folge für jedes gegen den Nullvektor.

Es sei nun ein Verteilungsvektor, den wir wegen

als

mit schreiben können. Wegen

und der Vorüberlegung konvergiert diese Folge gegen .


In der Situation von Fakt kann man die Eigenverteilung dadurch finden, dass man ein lineares Gleichungssystem löst. Wenn es sich um eine sehr große Matrix (man denke an Knoten) handelt, ist eine solche Rechnung sehr aufwändig. Häufig muss man die Eigenverteilung aber gar nicht genau kennen, sondern es reicht eine gute Approximation aus. Dann kann man zu einer beliebigen Startverteilung endlich viele Iterationen ausrechnen und weiß aufgrund von Fakt, dass dieses Verfahren die Eigenverteilung beliebig gut approximiert. Eine Suchmaschine im Internet erstellt beispielsweise zu einem Suchbegriff eine Reihenfolge von Seiten, die diesen Begriff enthalten. Wie kommt diese Reihenfolge zustande? Die wahre Antwort ist, zumindest für die ersten Einträge, dass dies davon abhängt, wer am meisten dafür zahlt. Ansonsten ist ein natürlicher Ansatz, der auch Grundlage des Page ranks ist, die numerische Ordnung in der Eigenverteilung als ausschlaggebend anzusehen. Der oberste Eintrag ist derjenige, bei dem die meisten Leute „schließlich“ landen, wenn sie mit gleicher Wahrscheinlichkeit den möglichen Links folgen. Diese Wanderungsbewegung wird eben durch die stochastische Matrix, die man im Sinne von Beispiel erhält, modelliert.[1]


Den numerischen Unterschied zwischen dem exakten Lösen eines linearen Gleichungssystems zur Bestimmung eines Eigenvektors und der Potenzmethode kann man folgendermaßen erfassen. Sei eine -Matrix gegeben. Das Gaussche Eliminationsverfahren braucht, um die erste Variable in Gleichungen zu eliminieren, Multiplikationen (Additionen sind vom Rechenaufwand her einfacher und werden hier nicht berücksichtigt), die Größenordung der Multiplikationen der Gesamtelimination ist somit

Dagegen sind für die Auswertung der Matrix auf einen Vektor Multiplikationen nötig. Wenn man Iterationen berechnen möchte, braucht man also Operationen. Wenn also deutlich kleiner als gewählt werden kann, so ist der Gesamtrechenaufwand deutlich kleiner.

  1. Unter Modellierung versteht man in der (insbesondere angewandten) Mathematik den Vorgang, realweltliche Phänomene mathematisch zu erfassen, zu verstehen und zu beeinflussen. Mathematisch modelliert werden physikalische Prozesse, Wetterphänomene, Finanzaktionen, etc.