7. Eigenwertprobleme

In diesem Kapitel beschäftigen wir uns mit Eigenwertproblemen. Für eine Matrix \(A\in\C^{n\times n}\) betrachten wir das Problem

\[\begin{aligned} A x = \lambda x \end{aligned}\]

mit Eigenwert \(\lambda\in\C\) und Eigenwert \(x\in\C^n\). In manchen ist man nur an einzelnen Eigenwerten interessiert (z.B. die Bestimmung des größten Eigenwerts als Spektralradius um Konvergenz iterativer Verfahren abzusichern), in anderen an vielen (oder allen) Eigenwerten und Eigenvektoren (z.B. bei der Singulärwertzerlegung) und in manchen nur an einzelnen Eigenvektoren. Ein modernes Beispiel für den letzten Fall sind Ranking-Probleme wie sie z.B. Google für Suchergebnisse anwendet.

Beispiel 7.1 (PageRank Algorithmus)

Wir betrachten \(n\in\N\) Dokumente (oder Seiten) \(p_1,\ldots, p_n\) welche sich jeweils gegenseitig verlinken. Der Wert \(\tilde{l}(p_i,p_j)\in\{0,1\}\) beschreibt hier, ob die Seite \(p_i\) auf die Seite \(p_j\) verweist oder nicht. Für eine Seite \(p_i\) berechnen wir die Anzahl der Seiten auf die \(p_i\) verweist durch

\[\begin{aligned} d(p_i) = \sum_{j=1}^n \tilde{l}(p_i,p_j) \end{aligned}\]

womit wir die normalisierte Größe \(L_{i,j} := \tilde{l}(p_i,p_j)/d(p_i)\) definieren und so eine stochastische Matrix \(L\in\R^{n,n}\) erhalten. Wir gehen hier davon aus, dass jede Seite auch Ausganglinks hat, d.h. dass heißt, dass \(d(p_i)>0, i=1,\ldots,n\). Wir wollen nun die Relevanz der Dokumente bestimmen, d.h. wir möchten ein Ranking erstellen, welches wir als Vektor \(R\in\R_+^N\) modellieren. Der Eintrag \(R_i\) modelliert hier die Relevanz der Seite \(p_i\). Dazu betrachten wir einen random Surfer, d.h. eine Person welche zufällig auf Links klickt und wollen die Wahrscheinlichkeit bestimmen, dass der random Surfer auf Seite \(p_i\) landet. Für ein gegebene Verteilung nach \(k\) Klicks \(R^k\in\R^n\) mit \(\sum_{i=1}^n R^k_i = 0\) erhalten wir die Verteilung nach \(k+1\) Klicks durch

\[\begin{aligned} R^{k+1} = L R^k \end{aligned}\]

was einen sogenannte Markov Chain beschreibt. Der stationäre Zustand \(R\in\R^n\) dieses Prozesses ist durch die Gleichung

\[\begin{aligned} R = L^T R \end{aligned}\]

gegeben. Für den klassichen Google PageRank Algorithmus [BP98] geht man zusätzlich davon aus, dass der random Surfer mit einer Wahrscheinlichkeit von \(1-d\) zu einer zufälligen Seite springt unabhängig von den Links auf der momentanen Seite, wobei \(d\in(0,1)\) der sogenannte Dämpfungsfaktor ist. In diesem Fall erhält man die Gleichung

\[\begin{aligned} R = \underbrace{\left(\frac{1-d}{n} I + d\ L^T\right)}_{:=P^T} R \end{aligned}\]

wobei \(P\in\R^{n,n}\) die sogenannte Google-Matrix ist. Da auch \(P\) eine stochastische Matrix ist und somit \(\lambda=!\) als größten Eigenwert hat, suchen wir also einen Eigenvektor zum größten Eigenwert.

Beispiel 7.2 (Ranking im Sport)

Wir betrachten eine Liga mit \(n\) Teams und modellieren mit \(s_i\in\R_+^n\) die Spielstärke des \(i\)-ten Teams. Ist \(A\) nun eine Matrix von Spielergebnissen,

\[\begin{aligned} A_{ij} = \begin{cases} 0 &\text{ falls } i \text{ gegen } j \text{ verloren hat},\\ 1 &\text{ falls } i \text{ gegen } j \text{ unentschieden oder nicht gespielt hat},\\ 2 &\text{ falls } i \text{ gegen } j \text{ gewonnen hat}. \end{cases} \end{aligned}\]

dann ist der Rang durch \(r = A s\) gegeben. Für eine faire Bewertung sollte \(r = \lambda s\) gelten, also können wir die Spielstärke aus dem Eigenwertproblem \(\lambda s = A s\) bzw. das Ranking aus

\[\begin{aligned} \lambda r = A r \end{aligned}\]

bestimmen. Hier ist natürlich nur ein nicht-negativer Eigenwert und Eigenvektor interessant, welcher nach dem Satz von Perron–Frobenius existiert (und der betragsmäßig größte ist). Wir interessieren uns also für den Eigenvektor zum größten Eigenwert.