diff options
Diffstat (limited to 'buch/chapters/80-wahrscheinlichkeit/positiv.tex')
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/positiv.tex | 185 |
1 files changed, 118 insertions, 67 deletions
diff --git a/buch/chapters/80-wahrscheinlichkeit/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex index 9f8f38f..159d6d3 100644 --- a/buch/chapters/80-wahrscheinlichkeit/positiv.tex +++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex @@ -7,15 +7,18 @@ \label{buch:section:positive-vektoren-und-matrizen}} \rhead{Positive Vektoren und Matrizen} Die Google-Matrix und die Matrizen, die wir in Markov-Ketten angetroffen +\index{Google-Matrix}% haben, zeichnen sich dadurch aus, dass alle ihre Einträge positiv oder mindestens nicht negativ sind. Die Perron-Frobenius-Theorie, die in diesem Abschnitt entwickelt +\index{Perron-Frobenius-Theorie}% werden soll, zeigt, dass Positivität einer Matrix nützliche Konsequenzen für Eigenwerte und Eigenvektoren hat. -Das wichtigste Resultat ist die Tatsache, dass postive Matrizen immer +Das wichtigste Resultat ist die Tatsache, dass positive Matrizen immer einen einzigen einfachen Eigenwert mit Betrag $\varrho(A)$ haben, -was zum Beispiel die Konvergenz des Pagerank-Algorithmus garantiert. -Dies wird im Satz von Perron-Frobenius in +was zum Beispiel die Konvergenz des PageRank-Algorithmus garantiert. +Dies wird im Satz~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius} +von Perron-Frobenius in Abschnitt~\ref{buch:subsection:der-satz-von-perron-frobenius} erklärt. @@ -42,6 +45,8 @@ seine Komponenten nicht negativ sind: $v_i\ge 0\forall i$. Geometrisch kann man sich die Menge der positven Vektoren in zwei Dimensionen als die Punkte des ersten Quadranten oder in drei Dimensionen als die +\index{Quadrant}% +\index{Oktant}% Vektoren im ersten Oktanten vorstellen. Aus der Positivität eines Vektors lässt sich jetzt eine Vergleichsrelation @@ -62,9 +67,9 @@ Die Definition funktionieren analog auch für Matrizen: \begin{definition} Eine Matrix $A\in M_{m\times n}(\mathbb{R})$ heisst {\em positiv}, -wenn alle ihre Einträge $a_{ij}$ positiv sind: $a_{ij}>0\forall i,j$. +wenn alle ihre Einträge $a_{i\!j}$ positiv sind: $a_{i\!j}>0\forall i,j$. Eine Matrix $A\in M_{m\times n}(\mathbb{R})$ heisst {\em nichtnegativ}, -wenn alle ihre Einträge $a_{ij}$ nichtnegativ sind: $a_{ij}\ge 0\forall i,j$. +wenn alle ihre Einträge $a_{i\!j}$ nichtnegativ sind: $a_{i\!j}\ge 0\forall i,j$. \index{positive Matrix}% \index{nichtnegative Matrix}% Man schreibt $A>B$ bzw.~$A\ge B$ wenn $A-B>0$ bzw.~$A-B\ge 0$. @@ -133,7 +138,7 @@ Die Zyklen-Zerlegung einer Permutationsmatrix zeigt, welche Unterräume von $\mathbb{R}^n$ die iterierten Bilder eines Standardbasisvektors aufspannen. Diese sind invariante Unterräume der Matrix. -Das im Beispiel illustrierte Phänomen findet dann nur in invarianten +Das im Beispiel illustrierte Phänomen findet nur in invarianten Unterräumen statt. \begin{beispiel} @@ -151,7 +156,7 @@ A=\begin{pmatrix} \end{equation} besteht aus zwei $3\times 3$-Blöcken. Die beiden Unterräume $V_1=\langle e_1,e_2,e_3\rangle$ -und $V_2=\langle e_4,e_5,e_6\rangle$ sind daher invariante +und $V_2=\langle e_4,e_5,e_6\rangle$ sind invariante Unterräume von $A$ und damit auch von $A^n$. Die Potenzen haben daher auch die gleich Blockstruktur. Insbesondere sind zwar die Blöcke von $A^n$ für $n>1$ positive @@ -161,6 +166,7 @@ Teilmatrizen, aber die Matrix $A^n$ ist für alle $n$ nicht positiv. \begin{definition} Eine nichtnegative Matrix mit der Eigenschaft, dass $A^n>0$ für ein genügend grosses $n$, heisst {\em primitiv}. +\index{primitive Matrix}% \end{definition} Die Matrix $A$ von \eqref{buch:wahrscheinlichkeit:eqn:diffusion} @@ -200,6 +206,7 @@ hinaus. \begin{satz}[Trenntrick] \label{buch:wahrscheinlichkeit:satz:trenntrick} +\index{Trenntrick}% Sind $u$ und $v$ nichtnegative Vektoren und $u>v$, dann gibt es eine positive Zahl $\varepsilon>0$ derart, dass $u\ge (1+\varepsilon)v$. @@ -214,7 +221,7 @@ Wir betrachten die Zahl = \max_{v_i\ne 0} \frac{u_i}{v_i}. \] -Wegen $u>v$ sind die Quotienten auf der rechten Seite alle $>0$. +Wegen $u>v$ sind die Quotienten auf der rechten Seite alle $>1$. Da nur endlich viele Quotienten miteinander verglichen werden, ist daher auch $\vartheta >1$. Es folgt $u\ge \vartheta v$. @@ -244,6 +251,7 @@ $Au>Av$ (siehe auch Satz~\ref{buch:wahrscheinlichkeit:satz:vergleichstrick}) \begin{satz}[Vergleichstrick] \label{buch:wahrscheinlichkeit:satz:vergleichstrick} +\index{Vergleichstrick}% Sei $A$ eine positive Matrix und seinen $u$ und $v$ Vektoren mit $u\ge v$ und $u\ne v$, dann ist $Au > Av$ (siehe auch Abbildung~\ref{buch:wahrscheinlichkeit:fig:vergleich}). @@ -251,8 +259,8 @@ mit $u\ge v$ und $u\ne v$, dann ist $Au > Av$ \begin{proof}[Beweis] Wir schreiben $d=u-v$, nach Voraussetzung ist $d\ne 0$. -Der Satz besagt dann, dass aus $d\ge 0$ folgt, dass $Ad>0$, dies -müssen wir beweisen. +Der Satz besagt dann, dass aus $d\ge 0$ folgt, dass $Ad>0$. +Dies müssen wir beweisen. Die Ungleichung $Ad>0$ besagt, dass alle Komponenten von $Ad$ positiv sind. @@ -261,16 +269,16 @@ Um dies nachzuweisen, berechnen wir (Ad)_i = \sum_{j=1}^n -a_{ij} +a_{i\!j} d_j. \label{buch:wahrscheinlichkeit:eqn:Adpositiv} \end{equation} -Alle Terme $a_{ij}>0$, weil $A$ positiv ist, und mindestens eine -der Komponenten $d_j>0$, weil $d\ne 0$. +Alle Koeffizienten $a_{i\!j}$ sind $>0$, weil $A$ positiv ist. +Mindestens eine der Komponenten $d_j$ ist $>0$, weil $d\ne 0$. Insbesondere sind alle Terme der Summe $\ge 0$, woraus wir bereits schliessen können, dass $(Ad)_i\ge 0$ sein muss. Die Komponente $d_j>0$ liefert einen positiven Beitrag -$a_{ij}d_j>0$ +$a_{i\!j}d_j>0$ zur Summe~\eqref{buch:wahrscheinlichkeit:eqn:Adpositiv}, also ist $(Ad)_i>0$. \end{proof} @@ -284,8 +292,8 @@ Ist $A$ eine positive Matrix und $u\ge 0$ mit $u\ne 0$, dann ist $Au>0$. \end{korollar} -Eine positive Matrix macht also aus nicht verschwindenden -und nicht negativen Vektoren positive Vektoren. +Eine positive Matrix macht also aus nicht verschwindenden, +nicht negativen Vektoren positive Vektoren. % % Die verallgemeinerte Dreiecksungleichung @@ -331,30 +339,38 @@ eines gemeinsamen Einheitsvektors $c$ sind: $u_i=|u_i|c$ \begin{proof}[Beweis] Die Aussage kann mit vollständiger Induktion bewiesen werden. -Die Induktionsverankerung ist der Fall $n=2$ gegeben durch die +Die Induktionsverankerung ist der Fall $n=2$, gegeben durch die gewöhnliche Dreiecksungleichung. Wir nehmen daher jetzt an, die Aussage sei für $n$ bereits bewiesen, -wir müssen sie dann für $n+1$ beweisen. +wir müssen sie für $n+1$ beweisen. Die Summe von $n+1$ Vektoren kann man $u=u_1+\dots+u_n$ und $v=u_{n+1}$ aufteilen. -Es gilt dann +Es gilt nach der gewöhnlichen Dreiecksungleichung, dass \[ |u+v| = |u_1+\dots+u_n+u_{n+1}| +\le +|u_1+\dots+u_n|+|u_{n+1}| \] -und +mit Gleichheit genau dann, wenn $u_1+\dots+u_n$ und $u_{n+1}$ +linear abhängig sind. +Nach Induktionsannahme gilt ausserdem \[ -|u_1+\dots+u_n| = |u_1|+\dots+|u_n|. +|u_1+\dots+u_n| \le |u_1|+\dots+|u_n| \] -Aus der Induktionsannahme folgt dann, dass die Vektoren $u_1,\dots,u_n$ +mit Gleichheit genau dann, wenn die Vektoren $u_1,\dots,u_n$ positive Vielfache eines Einheitsvektors $u$ sind, $u_i=|u_i|c$. Es ist dann \[ -u=u_1+\dots+u_n = \biggl(\sum_{i=1}^n |u_i|\biggr). +u=u_1+\dots+u_n += +\biggl(\sum_{i=1}^n |u_i|c\biggr) += +\biggl(\sum_{i=1}^n |u_i|\biggr)c. \] -Aus der gewöhnlichen Dreiecksungleichung, angewendet auf $u$ und $v$ +Da $|u+v|=|u|+|v|$ genau dann gilt, wenn $u$ und $v$ linear abhängig sind, folgt jetzt, dass $v$ ebenfalls ein nichtnegatives Vielfaches von $c$ ist. Damit ist der Induktionsschritt vollzogen. \end{proof} @@ -380,7 +396,7 @@ Die motiviert den nachstehenden geometrischen Beweis des Satzes. \begin{proof}[Beweis] Wer stellen uns die komplexen Zahlen $u_i$ als Vektoren in der -zweidimensionalen Gaussschen Ebene vor. +zweidimensionalen Gauss\-schen Ebene vor. Dann ist die Aussage nichts anderes als ein Spezialfall von Satz~\ref{buch:wahrscheinlichkeit:satz:verallgemeinerte-dreiecksungleichung} für den zweidimensionalen reellen Vektorraum $\mathbb{C}$. @@ -396,8 +412,8 @@ Wir sind an den Eigenwerten und Eigenvektoren einer positiven oder primitiven Matrix interessiert. Nach Definition des Spektralradius $\varrho(A)$ muss es einen Eigenvektor zu einem Eigenwert $\lambda$ mit Betrag $|\lambda|=\varrho(A)$ geben, -aber a priori wissen wir nicht, ob es einen reellen Eigenwert vom -Betrag $\varrho(A)$ gibt, und ob der Eigenvektor dazu reell ist. +aber a priori wissen wir nicht, ob es einen reellen Eigenvektor zum +Eigenwert $\varrho(A)$ gibt. \begin{figure} \centering @@ -415,14 +431,16 @@ Iteriert man dies (Abbildung~\ref{buch:wahrscheinlichkeit:figure:positiv}), wird die Bildmenge immer enger, bis sie nur ein sehr enger Kegel um die Richtung des Eigenvektors ist. Tatsächlich kann man aus dieser Idee auch einen topologischen -Beweis des untenstehenden Satzes von Perron-Frobenius konstruieren. +Beweis des untenstehenden Satzes von Perron-Frobenius konstruieren +(\cite{skript:pftopo} und +\cite{skript:hilbertmetric}). Er beruht darauf, dass eine Abbildung, die Distanzen verkleinert, einen Fixpunkt hat. Die Konstruktion einer geeigneten Metrik ist allerdings eher kompliziert, weshalb wir im Beweise der nachstehenden Aussagen den konventionellen Weg wählen. -Wir beginnen damit zu zeigen, dass für positive Matrizen $A$, +Wir beginnen damit zu zeigen, dass für positive Matrizen $A$ nichtnegative Eigenvektoren zu Eigenwerten $\lambda\ne 0$ automatisch positiv sind. Ausserdem müssen die zugehörigen Eigenwerte sogar positiv sein. @@ -444,6 +462,14 @@ alle Komponenten von $\lambda u$ positiv sein. Das ist nur möglich, wenn $\lambda > 0$. \end{proof} +Wenn $v$ ein Eigenvektor von $A$ ist, dann ist auch jedes Vielfache +davon ein Eigenvektor, insbesondere können einzelne Komponenten +des Vektors $v$ auch negativ sein. +Der folgende Satz zeigt aber, dass man der Vektor aus den Beträgen +von der Komponenten von $v$ ebenfalls ein Eigenvektor zum +gleichen Eigenwert ist. +Insbesondere gibt es immer einen nichtnegativen Eigenvektor. + \begin{satz} \label{buch:wahrscheinlichkeit:satz:positivereigenvektor} Sei $A$ eine positive Matrix und $v$ ein Eigenvektor von $A$ zu einem @@ -457,12 +483,12 @@ Es gilt natürlich auch, dass \[ (Au)_i = -\sum_{j=1}^n a_{ij}u_j +\sum_{j=1}^n a_{i\!j}u_j = -\sum_{j=1}^n |a_{ij}v_j| +\sum_{j=1}^n |a_{i\!j}v_j| \ge \biggl| -\sum_{j=1}^n a_{ij}v_j +\sum_{j=1}^n a_{i\!j}v_j \biggr| = |(Av)_i| @@ -490,22 +516,26 @@ können wir jetzt eine Zahl $\vartheta>1$ finden derart, dass A^2 u \ge \vartheta \varrho(A) Au \] ist. -Durch weitere Anwendung von $A$ findet man -\begin{align*} +Durch wiederholte Anwendung von $A$ findet man +\begin{align} A^3 u & \ge (\vartheta \varrho(A))^2 Au +\notag \\ &\phantom{0}\vdots +\notag \\ A^{k+1} u & \ge (\vartheta \varrho(A))^{k} Au -\end{align*} -Daraus kann man jetzt die Norm abschätzen: +\label{buch:pf:eqn:ak+1} +\end{align} +Aus $|A^{k+1}u| \le \|A^k\|\,|Ak|$ und +\eqref{buch:pf:eqn:ak+1} kann man jetzt die Norm von $A^k$ abschätzen: \[ \begin{aligned} -\| A^{k}\|\, |Au| +\| A^{k}\|\cdot |Au| &\ge -\| A^{k+1}u\| +| A^{k+1}u| \ge -(\vartheta\varrho(A))^{k} |Au| +(\vartheta\varrho(A))^{k}\, |Au| && \Rightarrow & @@ -518,8 +548,11 @@ Daraus kann man jetzt die Norm abschätzen: \lim_{k\to\infty} \|A^k\|^{\frac{1}{k}} &\ge \vartheta\varrho(A) \\ -&&&\Rightarrow& -\varrho(A)&\ge \vartheta\varrho(A) +&&&&\|\phantom{00}& +\\ +&&&%\Rightarrow& +& +\varrho(A)&\ge \vartheta\varrho(A). \end{aligned} \] Wegen $\vartheta>1$ ist dies aber gar nicht möglich. @@ -527,6 +560,10 @@ Dieser Widerspruch zeigt, dass $u=v$ sein muss, insbesondere ist $v$ ein nichtnegativer Eigenvektor. \end{proof} +Die Potenzmethode funktioniert nur, wenn kein anderer Eigenwert +den Betrag $\varrho(A)$ hat. +Der folgende Satz garantiert dies. + \begin{satz} Sei $A$ eine positive Matrix und $v$ ein Eigenvektor zu einem Eigenwert $\lambda$ mit Betrag $|\lambda|=\varrho(A)$. @@ -541,24 +578,22 @@ Aus der Eigenvektorgleichung für $u$ folgt \begin{equation} Au = \varrho(A) u \quad\Rightarrow\quad -\sum_{j=1}^n a_{ij}|v_j| = \varrho(A) |v_i|. +\sum_{j=1}^n a_{i\!j}|v_j| = \varrho(A) |v_i|. \label{buch:wahrscheinlichkeit:eqn:pev1} \end{equation} Anderseits ist $v$ ein Eigenvektor zum Eigenwert $\lambda$, also gilt \[ -\sum_{j=1}^n a_{ij}v_j = \lambda v_i. +\sum_{j=1}^n a_{i\!j}v_j = \lambda v_i. \] Der Betrag davon ist \begin{equation} \biggl| -\sum_{j=1}^n a_{ij}v_j +\sum_{j=1}^n a_{i\!j}v_j \biggr| = |\lambda v_i| = -\varrho(A) |v_i| -= -\varrho |v_i|. +\varrho(A) |v_i|. \label{buch:wahrscheinlichkeit:eqn:pev2} \end{equation} Die beiden Gleichungen @@ -566,28 +601,35 @@ Die beiden Gleichungen und \eqref{buch:wahrscheinlichkeit:eqn:pev2} zusammen ergeben die Gleichung -\[ +\begin{equation} \biggl| -\sum_{j=1}^n a_{ij}v_j +\sum_{j=1}^n a_{i\!j}v_j \biggr| = -\sum_{j=1}^n a_{ij}|v_j|. -\] +\sum_{j=1}^n a_{i\!j}|v_j|. +\label{buch:pf:eqn:gleich} +\end{equation} Nach der verallgemeinerten Dreiecksungleichung Satz~\ref{buch:subsection:verallgemeinerte-dreiecksungleichung} -folgt jetzt, dass es eine komplexe Zahl $c$ vom Betrag $1$ gibt derart, +folgt jetzt aus der Gleichheit in~\eqref{buch:pf:eqn:gleich}, +dass es eine komplexe Zahl $c$ vom Betrag $1$ gibt derart, dass $v_j = |v_j|c=u_jc$. -Insbesondere ist $v=cu$ und damit ist +Insbesondere ist $v=cu$. +Damit kann man jetzt $\lambda$ berechnen, es ist \[ \lambda v = Av = Acu = c Au = c\varrho(A) u = \varrho(A) v, \] woraus $\lambda=\varrho(A)$ folgt. \end{proof} +In Anwendungen wollen wir schliessen, dass die Grenzverteilung +eindeutig ist, dazu ist notwendig, dass der Eigenraum des +Eigenwertes $\varrho(A)$ eindimensional ist. + \begin{satz} \label{buch:wahrscheinlichkeit:satz:geometrischeinfach} -Der Eigenraum einer positiven Matrix $A$ zum Eigenwert $\varrho(A)$ ist -eindimensional. +Der Eigenraum $E_{\varrho(A)}(A)$ einer positiven Matrix $A$ +zum Eigenwert $\varrho(A)$ ist eindimensional. \end{satz} \begin{proof}[Beweis] @@ -613,7 +655,7 @@ A(u-cv) \] Der Vektor auf der rechten Seite hat mindestens eine verschwindende Komponente. -Der Vektor auf der linken Seite ist nach Vergleichstrick +Der Vektor auf der linken Seite ist nach dem Vergleichstrick Satz~\ref{buch:wahrscheinlichkeit:satz:vergleichstrick} \[ A(u-cv) > 0, @@ -623,14 +665,20 @@ Dieser Widerspruch zeigt, dass die Annahme, es gäbe einen von $u$ linear unabhängigen Eigenvektor zum Eigenwert $\varrho(A)$ nicht haltbar ist. \end{proof} +Satz~\ref{buch:wahrscheinlichkeit:satz:geometrischeinfach} garantiert, +dass der Eigenwert einfach ist. +Es ist aber immer noch möglich, dass die algebraische Vielfachheit +von $\varrho(A) >1$ ist, dass also $\dim\mathcal{E}_{\varrho(A)}(A)>1$ +ist. +Dies ist jedoch nicht der Fall. + \begin{satz} \label{buch:wahrscheinlichkeit:satz:algebraischeinfach} -Der verallgemeinerte Eigenraum zum Eigenwert $\varrho(A)$ einer -positiven Matrix $A$ ist eindimensional. +Sei $A$ eine positive Matrix und $p^t$ ein positiver Eigenvektor +der Matrix $A^t$ zum Eigenwert $\varrho(A^t)=\varrho(A)$. Ist $u$ der Eigenvektor von $A$ zum Eigenwert $\varrho(A)$ nach -Satz~\ref{buch:wahrscheinlichkeit:satz:geometrischeinfach} -und $p^t$ der entsprechende Eigenvektor $A^t$, dann -ist +Satz~\ref{buch:wahrscheinlichkeit:satz:geometrischeinfach}, +dann ist \[ \mathbb{R}^n = @@ -643,6 +691,8 @@ ist \ker p \] eine Zerlegung in invariante Unterräume von $A$. +Insbesondere ist der verallgemeinerte Eigenraum $\mathcal{E}_{\varrho(A)}(A)$ +von $A$ eindimensional. \end{satz} \begin{proof}[Beweis] @@ -652,7 +702,8 @@ Insbesondere ist $u\not\in\ker p$ Es ist klar, dass $A\langle u\rangle = \langle Au\rangle = \langle u\rangle$ ein invarianter Unterraum ist. -Für einen Vektor $x\in\mathbb{R}^n$ mit $px=0$ erfüllt das Bild $Ax$ +Für einen Vektor $x\in\mathbb{R}^n$ mit $px=0$, also $x\in\ker p$, +erfüllt das Bild $Ax$ die Gleichung \[ p(Ax)=(pA)x=(A^tp^t)^tx= \varrho(A)(p^t)^tx @@ -666,8 +717,8 @@ $\ker p$ ist $(n-1)$-dimensional, $\langle u\rangle$ ist eindimensional und $u$ ist nicht in $\ker p$ enthalten. Folglich spannen $\langle u\rangle$ und $\ker p$ den ganzen Raum auf. -Gäbe es einen weitern linear unabhängigen Vektor im verallgemeinerten -Eigenraum von $\mathcal{E}_{\varrho(A)}$, dann müsste es auch einen +Gäbe es einen weiteren linear unabhängigen Vektor im verallgemeinerten +Eigenraum $\mathcal{E}_{\varrho(A)}(A)$, dann müsste es auch einen solchen Vektor in $\ker p$ geben. Da $\ker p$ invariant ist, müsste es also auch einen weiteren Eigenvektor $u_2$ zum Eigenwert $\varrho(A)$ in $\ker p$ geben. @@ -712,10 +763,10 @@ Dann ist $\varrho(A)$ der einzige Eigenwert vom Betrag $\varrho(A)$ und er hat geometrische und algebraische Vielfachheit $1$. \end{satz} -\begin{proof}[Beweis] +\begin{proof}[Beweisansatz] Nach Voraussetzung gibt es ein $n$ derart, dass $A^n>0$. Für $A^n$ gelten die Resultate von Satz~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius}. - -XXX TODO +Man kann zeigen, dass die Eigenvektoren von $A^n$ auch +Eigenvektoren von $A$ sind. \end{proof} |