diff options
Diffstat (limited to 'buch/chapters')
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/Makefile.inc | 1 | ||||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/chapter.tex | 1 | ||||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/images/Makefile | 19 | ||||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg | bin | 0 -> 203856 bytes | |||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/images/diffusion.m | 33 | ||||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf | bin | 0 -> 220008 bytes | |||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/images/diffusion.tex | 46 | ||||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/positiv.tex | 617 |
8 files changed, 717 insertions, 0 deletions
diff --git a/buch/chapters/80-wahrscheinlichkeit/Makefile.inc b/buch/chapters/80-wahrscheinlichkeit/Makefile.inc index 6546e01..6fd104c 100644 --- a/buch/chapters/80-wahrscheinlichkeit/Makefile.inc +++ b/buch/chapters/80-wahrscheinlichkeit/Makefile.inc @@ -7,5 +7,6 @@ CHAPTERFILES = $(CHAPTERFILES) \ chapters/80-wahrscheinlichkeit/google.tex \ chapters/80-wahrscheinlichkeit/markov.tex \ + chapters/80-wahrscheinlichkeit/positiv.tex \ chapters/80-wahrscheinlichkeit/parrondo.tex \ chapters/80-wahrscheinlichkeit/chapter.tex diff --git a/buch/chapters/80-wahrscheinlichkeit/chapter.tex b/buch/chapters/80-wahrscheinlichkeit/chapter.tex index e9e7531..85b6d8c 100644 --- a/buch/chapters/80-wahrscheinlichkeit/chapter.tex +++ b/buch/chapters/80-wahrscheinlichkeit/chapter.tex @@ -33,4 +33,5 @@ dargestellt. \input{chapters/80-wahrscheinlichkeit/google.tex} \input{chapters/80-wahrscheinlichkeit/markov.tex} +\input{chapters/80-wahrscheinlichkeit/positiv.tex} \input{chapters/80-wahrscheinlichkeit/parrondo.tex} diff --git a/buch/chapters/80-wahrscheinlichkeit/images/Makefile b/buch/chapters/80-wahrscheinlichkeit/images/Makefile new file mode 100644 index 0000000..3c6a7f9 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/Makefile @@ -0,0 +1,19 @@ +# +# Makefile +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschulen +# +all: diffusion.png diffusion.pdf + +diffusion.pdf: diffusion.tex diffusion.jpg + pdflatex diffusion.tex + +diffusion.png: diffusion.pov vektoren.inc + povray +A0.1 +W1920 +H1080 -Odiffusion.png diffusion.pov + +diffusion.jpg: diffusion.png + convert diffusion.png -density 300 -units PixelsPerInch diffusion.jpg + +vektoren.inc: diffusion.m + octave diffusion.m + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg Binary files differnew file mode 100644 index 0000000..b79b07b --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.jpg diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.m b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.m new file mode 100644 index 0000000..ad56fe5 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.m @@ -0,0 +1,33 @@ +# +# diffusion.m +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +e1 = [ 1; 0; 0; 0; 0; 0 ]; +A = 0.8*eye(6) + 0.1*shift(eye(6),1) + 0.1*shift(eye(6),-1); +A(1,1) = 0.9; +A(6,6) = 0.9; +A(1,6) = 0; +A(6,1) = 0; + +N = 30; +b = zeros(6,N); +b(:,1) = e1; +for i = (2:N) + b(:,i) = A * b(:,i-1); +end +b + +f = fopen("vektoren.inc", "w"); +for i = (1:N) + fprintf(f, "vektor(%d,%.4f,%.4f,%.4f,%.4f,%.4f,%.4f)\n", i, + b(1,i), b(2,i), b(3,i), b(4,i), b(5,i), b(6,i)) +end +fclose(f); + +A1=A +A2=A*A +A3=A*A2 +A4=A*A3 +A5=A*A4 +A6=A*A5 diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf Binary files differnew file mode 100644 index 0000000..ac4c0ff --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.pdf diff --git a/buch/chapters/80-wahrscheinlichkeit/images/diffusion.tex b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.tex new file mode 100644 index 0000000..ff58659 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/diffusion.tex @@ -0,0 +1,46 @@ +% +% diffusion.tex -- Diffusion unter der Wirkung der Matrix +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\node at (0,0) {\includegraphics[width=12cm]{diffusion.jpg}}; + +\node at (-6.3,-1.2) [rotate=-10] {$k=6$}; +\node at (-5.15,-0.7) [rotate=-10] {$k=1$}; + +\node at (5.8,-3.25) [rotate=-10] {$k=6$}; +\node at (6.3,-2.5) [rotate=-10] {$k=1$}; + +\node at (-6.2,-1.7) [rotate=26] {$n=1$}; +\node at (4.8,-3.7) [rotate=53] {$n=30$}; + +%\foreach \x in {-6,-5.9,...,6.01}{ +% \draw[line width=0.1pt] (\x,-3.5) -- (\x,3.5); +%} +%\foreach \x in {-6,...,6}{ +% \draw[line width=0.5pt] (\x,-3.5) -- (\x,3.5); +% \node at (\x,-3.5) [below] {$\x$}; +%} +%\foreach \y in {-3.5,-3.4,...,3.51}{ +% \draw[line width=0.1pt] (-6,\y) -- (6,\y); +%} +%\foreach \y in {-3,...,3}{ +% \draw[line width=0.5pt] (-6,\y) -- (6,\y); +% \node at (-6,\y) [left] {$\y$}; +%} +%\fill (0,0) circle[radius=0.05]; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex new file mode 100644 index 0000000..f956374 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex @@ -0,0 +1,617 @@ +% +% positiv.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\section{Positive Vektoren und Matrizen +\label{buch:section:positive-vektoren-und-matrizen}} +\rhead{Positive Vektoren und Matrizen} +Die Google-Matrix und die Matrizen, die wir in Markov-Ketten angetroffen +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 +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 +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 +Abschnitt~\ref{buch:subsection:der-satz-von-perron-frobenius} +erklärt. + +% +% Elementare Definitionen und Eigenschaften +% +\subsection{Elementare Eigenschaften +\label{buch:subsection:elementare-eigenschaften}} +In diesem Abschnitt betrachten wir ausschliesslich reelle Vektoren +und Matrizen. +Die Komponenten sind somit immer mit miteinander vergleichbar, daraus +lässt sich auch eine Vergleichsrelation zwischen Vektoren +ableiten. + +\begin{definition} +Ein Vektor $v\in\mathbb{R}^n$ heisst {\em positiv}, geschrieben +$v>0$, wenn alle seine Komponenten positiv sind: $v_i>0\forall i$. +Ein Vektor $v\in\mathbb{R}^n$ heisst {\em nichtnegativ}, in Formeln +$v\ge 0$, wenn alle +seine Komponenten nicht negativ sind: $v_i\ge 0\forall i$. +\index{positiver Vektor}% +\index{nichtnegativer Vektor}% +\end{definition} + +Aus der Positivität eines Vektors lässt sich jetzt eine Vergleichsrelation +für beliebige Vektoren ableiten. +Mit der folgenden Definition wird erreicht, das mit Ungleichungen für Vektoren +auf die gleiche Art und Weise gerechnet werden kann, wie man sich +dies von Ungleichungen zwischen Zahlen gewohnt ist. + +\begin{definition} +Für zwei Vektoren $u,v\in\mathbb{R}^n$ ist genau dann $u>v$, wenn +$u-v > 0$ ist. +Ebenso ist $u\ge v$ genau dann, wenn $u-v\ge 0$. +\end{definition} + +Ungleichungen zwischen Vektoren kann man daher auch so interpretieren, +dass sie für jede Komponente einzeln gelten müssen. +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$. +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$. +\index{positive Matrix}% +\index{nichtnegative Matrix}% +Man schreibt $A>B$ bzw.~$A\ge B$ wenn $A-B>0$ bzw.~$A-B\ge 0$. +\end{definition} + +Die Permutationsmatrizen sind Beispiele von nichtnegativen Matrizen, +deren Produkte wieder nichtnegativ sind. +Dies ist aber ein sehr spezieller Fall, wie das folgende Beispiel +zeigt. + +\begin{beispiel} +Wir betrachten die Matrix +\begin{equation} +A= +\begin{pmatrix} +0.9&0.1& & & & \\ +0.1&0.8&0.1& & & \\ + &0.1&0.8&0.1& & \\ + & &0.1&0.8&0.1& \\ + & & &0.1&0.8&0.1\\ + & & & &0.1&0.9 +\end{pmatrix} +\label{buch:wahrscheinlichkeit:eqn:diffusion} +\end{equation} +Die Multiplikation eines Vektors mit dieser Matrix bewirkt, dass die +Komponenten des Vektors auf benachbarte Komponenten ``verschmiert'' werden. +Wendet man $A$ wiederholt auf den ersten Standardbasisvektor $v_1=e_1$ an, +erhält man nacheinander die Vektoren $v_2=Av_1$, $v_n = Av_{n-1}$. +\begin{figure} +\centering +\includegraphics{chapters/80-wahrscheinlichkeit/images/diffusion.pdf} +\caption{Die sechs Komponenten für $k=1$ bis $k=6$ der Vektoren $A^{n-1}e_1$ +für die Matrix $A$ in \eqref{buch:wahrscheinlichkeit:eqn:diffusion} +sind als Säulen dargestellt. +Sie zeigen, dass für genügend grosses $n$, alle Komponenten +des Vektors $A^{n-1}e_1$ positiv werden. +\label{buch:wahrscheinlichkeit:fig:diffusion}} +\end{figure} +In Abbildung~\ref{buch:wahrscheinlichkeit:fig:diffusion} sind die Komponenten +als Säulen dargestellt. +Man kann erkennen, dass für genügend grosse $n$ alle Komponenten +der Vektoren positiv werden. + +Man kann auch direkt die Potenzen $A^n$ ausrechen und sehen, dass +\[ +A^5 += +\begin{pmatrix} + 0.65658& 0.27690& 0.05925& 0.00685& 0.00041& 0.00001\\ + 0.27690& 0.43893& 0.22450& 0.05281& 0.00645& 0.00041\\ + 0.05925& 0.22450& 0.43249& 0.22410& 0.05281& 0.00685\\ + 0.00685& 0.05281& 0.22410& 0.43249& 0.22450& 0.05925\\ + 0.00041& 0.00645& 0.05281& 0.22450& 0.43893& 0.27690\\ + 0.00001& 0.00041& 0.00685& 0.05925& 0.27690& 0.65658 +\end{pmatrix} +>0 +\] +und dass daher für alle $n\ge 5$ die Matrix $A^n$ positiv ist. +\end{beispiel} + +Die Eigenschaft der Matrix $A$ von +\eqref{buch:wahrscheinlichkeit:eqn:diffusion}, dass $A^n>0$ +für genügend grosses $n$ ist bei Permutationsmatrizen nicht +vorhanden. +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 +Unterräumen statt. + +\begin{beispiel} +Die Matrix +\begin{equation} +A=\begin{pmatrix} +0.9&0.1& & & & \\ +0.1&0.8&0.1& & & \\ + &0.1&0.9& & & \\ + & & &0.9&0.1& \\ + & & &0.1&0.8&0.1\\ + & & & &0.1&0.9 +\end{pmatrix} +\label{buch:wahrscheinlichkeit:eqn:diffusionbloecke} +\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 +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 +Teilmatrizen, aber die Matrix $A^n$ ist für alle $n$ nicht positiv. +\end{beispiel} + +\begin{definition} +Eine nichtnegative Matrix mit der Eigenschaft, dass $A^n>0$ für +ein genügend grosses $n$, heisst {\em primitiv}. +\end{definition} + +Die Matrix $A$ von \eqref{buch:wahrscheinlichkeit:eqn:diffusion} +ist also primitiv, Permutationsmatrizen sind niemals primitiv. +Die Matrix $A$ von \eqref{buch:wahrscheinlichkeit:eqn:diffusionbloecke} +ist nicht primitiv, aber die einzelnen Blöcke sind primitiv. +Viele der Ausssagen über positive Matrizen lassen sich auf primitive +nichtnegative Matrizen verallgemeinern. + +Das Beispiel zeigt auch, dass der Begriff der primitiven Matrix +eng mit der Idee verknüpft ist, die Problemstellung in invariante +Unterräume aufzuteilen, in denen eine primitive Matrix vorliegt. +Primitive Matrizen werden damit zu naheliegenden Bausteinen für +die Problemlösung für nicht primitive Matrizen. + +Eine interessante Eigenschaft positiver Vektoren oder Matrizen +ist, dass die Positivität sich manchmal ``upgraden'' lässt, +wie im folgenden Satz. +Er zeigt, dass ein Vektor, der grösser ist als ein anderer, auch +um einen definierten Faktor $>1$ grösser ist. + +\begin{satz}[Trenntrick] +\label{buch:wahrscheinlichkeit:satz: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$. +Ausserdem kann $\varepsilon$ so gewählt werden, dass $u\not\ge(1+\mu)v$ +für $\mu>\varepsilon$. +\end{satz} + +\begin{proof}[Beweis] +Wir betrachten die Zahl +\[ +\vartheta += +\max_{v_i\ne 0} \frac{u_i}{v_i}. +\] +Wegen $u>v$ sind die Quotienten auf der rechten Seite alle $>0$. +Da nur endlich viele Quotienten miteinander verglichen werden, ist +daher auch $\vartheta >1$. +Es folgt $u\ge \vartheta v$. +Wegen $\vartheta >1$ ist $\varepsilon = \vartheta -1 >0$ und +$u\ge (1+\varepsilon)v$. +\end{proof} + +Der Satz besagt also, dass es eine Komponente $v_i\ne 0$ gibt +derart, dass $u_i = (1+\varepsilon)v_i$. +Diese Komponenten limitiert also, wie stark man $v$ strecken kann, +so dass er immer noch $\le u$ ist. +Natürlich folgt aus den der Voraussetzung $u>v$ auch, dass $u$ ein +positiver Vektor ist. + +\begin{satz}[Vergleichstrick] +\label{buch:wahrscheinlichkeit:satz:vergleichstrick} +Sei $A$ eine positive Matrix und seinen $u$ und $v$ Vektoren +mit $u\ge v$ und $u\ne v$, dann ist $Au > Av$. +\end{satz} + +\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. + +Die Ungleichung $Ad>0$ besagt, dass alle Komponenten von $Ad$ +positiv sind. +Um dies nachzuweisen, berechnen wir +\begin{equation} +(Ad)_i += +\sum_{j=1}^n +a_{ij} +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$. +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$ +zur Summe~\eqref{buch:wahrscheinlichkeit:eqn:Adpositiv}, +also ist $(Ad)_i>0$. +\end{proof} + +Der folgende Spezialfall folgt unmittelbar aus dem +Satz~\ref{buch:wahrscheinlichkeit:satz:vergleichstrick}. + +\begin{korollar} +\label{buch:wahrscheinlichkeit:satz:Au>0korollar} +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. + +% +% Die verallgemeinerte Dreiecksungleichung +% +\subsection{Die verallgemeinerte Dreiecksungleichung +\label{buch:subsection:verallgemeinerte-dreiecksungleichung}} +Die Dreiecksungleichung besagt, dass für beliebige Vektoren +$u,v\in\mathbb{R}^n$ gilt +\[ +|u+v|\le |u|+|v| +\] +mit Gleichheit genau dann, wenn $u$ und $v$ linear abhängig sind. +Wenn beide von $0$ verschieden sind, dann gibt es eine positive Zahl +$t$ mit $u=tv$. +Wir brauchen eine Verallgemeinerung für eine grössere Zahl von +Summanden. + +\begin{satz}[Verallgemeinerte Dreiecksungleichung] +\label{buch:wahrscheinlichkeit:satz:verallgemeinerte-dreiecksungleichung} +Für $n$ Vektoren $v_i\ne 0$ gilt +\[ +|u_1+\dots+u_n| \le |u_1|+\dots+|u_n| +\] +mit Gleichheit genau dann, wenn alle Vektoren nichtnegative Vielfache +eines gemeinsamen Einheitsvektors $c$ sind: $u_i=|u_i|c$. +\end{satz} + +\begin{proof}[Beweis] +Die Aussage kann mit vollständiger Induktion bewiesen werden. +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. +Die Summe von $n+1$ Vektoren kann man $u=u_1+\dots+u_n$ und $v=u_{n+1}$ +aufteilen. +Es gilt dann +\[ +|u+v| += +|u_1+\dots+u_n+u_{n+1}| +\] +und +\[ +|u_1+\dots+u_n| = |u_1|+\dots+|u_n|. +\] +Aus der Induktionsannahme folgt dann, dass 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). +\] +Aus der gewöhnlichen Dreiecksungleichung, angewendet auf $u$ und $v$ +folgt jetzt, dass $v$ ebenfalls ein nichtnegatives Vielfaches von $c$ ist. +Damit ist der Induktionsschritt vollzogen. +\end{proof} + +\begin{satz} +Seien $a_1,\dots,a_n$ positive Zahlen und $u_i\in\mathbb C$ derart, +dass +\[ +\biggl| +\sum_{i=1}^n a_i u_i +\biggr| += +\sum_{i=1}^n a_i |u_i|, +\] +dann gibt es eine komplexe Zahl $c$ und einen nichtnegativen Vektor $v$ +derart, dass $u=cv$. +\end{satz} + +Der Satz besagt, dass die komplexen Komponenten $u_i$ alle das gleiche +Argument haben. +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. +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}$. +\end{proof} + + +% +% Der Satz von Perron-Frobenius +% +\subsection{Der Satz von Perron-Frobenius +\label{buch:subsection:der-satz-von-perron-frobenius}} +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. + +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. + +\begin{satz} +Sei $A$ eine positive Matrix und $u$ ein nichtnegativer Eigenvektor zum +Eigenwert $\lambda\ne 0$. +Dann ist $u$ ein positiver Vektor und $\lambda > 0$. +\end{satz} + +\begin{proof}[Beweis] +Nach dem Korollar~\ref{buch:wahrscheinlichkeit:satz:Au>0korollar} +folgt, dass $Au>0$ ein positiver Vektor ist, es sind +also alle Komponenten positiv. +Der Vektor $u$ ist aber auch ein Eigenvektor, es gilt also +$\lambda u = Au$. +Da alle Komponenten von $Au$ positiv sind, müssen auch +alle Komponenten von $\lambda u$ positiv sein. +Das ist nur möglich, wenn $\lambda > 0$. +\end{proof} + +\begin{satz} +\label{buch:wahrscheinlichkeit:satz:positivereigenvektor} +Sei $A$ eine positive Matrix und $v$ ein Eigenvektor von $A$ zu einem +Eigenwert $\lambda$ mit Betrag $|\lambda|=\varrho(A)$, +dann ist der Vektor $u$ mit den Komponenten $u_i=|v_i|$ ein +positiver Eigenvektor zu Eigenwert $\varrho(A)$. +\end{satz} + +\begin{proof}[Beweis] +Es gilt natürlich auch, dass +\[ +(Au)_i += +\sum_{j=1}^n a_{ij}u_j += +\sum_{j=1}^n |a_{ij}v_j| +\ge +\biggl| +\sum_{j=1}^n a_{ij}v_j +\biggr| += +|(Av)_i| += +|\lambda v_i| += +\varrho(A) |v_i| += +\varrho(A) u_i, +\] +oder $Au \ge \varrho(A)u$. +Wir müssen zeigen, dass sogar $Au=\varrho(A)u$ gilt. +Wir nehmen daher an, dass $Au\ne \varrho(A)u$ ist, und führen dies zu +einem Widerspruch. + +Da $\varrho(A)u$ ein nichtnegativer Vektor ist, können wir den Vergleichstrick +Satz~\ref{buch:wahrscheinlichkeit:satz:vergleichstrick}, auf die beiden +Vektoren $Au$ und $\varrho(A)u$ anwenden. +Wir schliessen $A^2u > \varrho(A)Au$. + +Mit dem Trenntrick +Satz~\ref{buch:wahrscheinlichkeit:satz:trenntrick} +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*} +A^3 u & \ge (\vartheta \varrho(A))^2 Au +\\ +&\phantom{0}\vdots +\\ +A^{k+1} u & \ge (\vartheta \varrho(A))^{k} Au +\end{align*} +Daraus kann man jetzt die Norm abschätzen: +\[ +\begin{aligned} +\| A^{k}\|\, |Au| +&\ge +\| A^{k+1}u\| +\ge +(\vartheta\varrho(A))^{k} |Au| +&& +\Rightarrow +& +\|A^k\| &\ge (\vartheta\varrho(A))^k +\\ +&&&\Rightarrow& +\|A^k\|^{\frac{1}{k}} &\ge \vartheta\varrho(A) +\\ +&&&\Rightarrow& +\lim_{k\to\infty} +\|A^k\|^{\frac{1}{k}} &\ge \vartheta\varrho(A) +\\ +&&&\Rightarrow& +\varrho(A)&\ge \vartheta\varrho(A) +\end{aligned} +\] +Wegen $\vartheta>1$ ist dies aber gar nicht möglich. +Dieser Widerspruch zeigt, dass $u=v$ sein muss, insbesondere ist +$v$ ein nichtnegativer Eigenvektor. +\end{proof} + +\begin{satz} +Sei $A$ ein positive Matrix und $v$ ein Eigenvektor zu einem +Eigenwert $\lambda$ mit Betrag $|\lambda|=\varrho(A)$. +Dann ist $\lambda=\varrho(A)$. +\end{satz} + +\begin{proof}[Beweis] +Nach Satz~\ref{buch:wahrscheinlichkeit:satz:positivereigenvektor} +ist der Vektor $u$ mit den Komponenten $u_i=|v_i|$ ein positiver +Eigenvektor zum Eigenwert $\varrho(A)$. +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|. +\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. +\] +Der Betrag davon ist +\begin{equation} +\biggl| +\sum_{j=1}^n a_{ij}v_j +\biggr| += +|\lambda v_i| += +\varrho(A) |v_i| += +\varrho |v_i|. +\label{buch:wahrscheinlichkeit:eqn:pev2} +\end{equation} +Die beiden Gleichungen +\eqref{buch:wahrscheinlichkeit:eqn:pev1} +und +\eqref{buch:wahrscheinlichkeit:eqn:pev2} +zusammen ergeben die Gleichung +\[ +\biggl| +\sum_{j=1}^n a_{ij}v_j +\biggr| += +\sum_{j=1}^n a_{ij}|v_j|. +\] +Nach der verallgemeinerten Dreiecksungleichung +Satz~\ref{buch:subsection:verallgemeinerte-dreiecksungleichung} +folgt jetzt, 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 +\[ +\lambda v = Av = Acu = c Au = c\varrho(A) u = \varrho(A) v, +\] +woraus $\lambda=\varrho(A)$ folgt. +\end{proof} + +\begin{satz} +\label{buch:wahrscheinlichkeit:satz:geometrischeinfach} +Der Eigenraum einer positiven Matrix $A$ zum Eigenwert $\varrho(A)$ ist +eindimensional. +\end{satz} + +\begin{proof}[Beweis] +Sei $u$ der bereits gefundene Eigenvektor von $A$ zum Eigenwert $\varrho(A)$ +und sei $v$ ein weiterer, linear unabhängiger Eigenvektor zum +gleichen Eigenwert. +Da $A$ und $\varrho(A)$ reell sind, sind auch die Vektoren $\Re v$ und $\Im v$ +aus den Realteilen $\Re v_i$ oder den Imaginärteilen $\Im v_i$ Eigenvektoren. +Beide Vektoren sind reelle Vektoren und mindestens einer davon ist mit +$u$ linear unabhängig. +Wir dürfen daher annehmen, dass $v$ ein linear unabhängiger Eigenvektor +zum Eigenwert $\varrho(A)$ ist. + +Weil wir wissen, dass $u$ ein positiver Vektor ist, gibt es einen +grösstmöglichen Faktor $c>0$ derart, dass $u\ge cv$ oder $u\ge cv$. +Insbesondere verschwindet mindestens eine Komponente von $u-cv$. +Da $u$ und $v$ Eigenvektoren zum Eigenwert $\varrho(A)$ sind, +ist +\[ +A(u-cv) += +\varrho(A)(u-cv). +\] +Der Vektor auf der rechten Seite hat mindestens eine verschwindende +Komponente. +Der Vektor auf der linken Seite ist nach Vergleichstrick +Satz~\ref{buch:wahrscheinlichkeit:satz:vergleichstrick} +\[ +A(u-cv) > 0, +\] +alle seine Komponenten sind $>0$. +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} + +\begin{satz} +\label{buch:wahrscheinlichkeit:satz:algebraischeinfach} +Der verallgemeinerte Eigenraum zum Eigenwert $\varrho(A)$ einer +positiven Matrix $A$ ist eindimensional. +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 +\[ +\mathbb{R}^n += +\langle u\rangle +\oplus +\{ x\in\mathbb{R}^n\;|\; px=0\} += +\langle u\rangle +\oplus +\ker p +\] +eine Zerlegung in invariante Unterräume von $A$. +\end{satz} + +\begin{proof}[Beweis] +Die beiden Vektoren $x$ und $p$ sind beide positiv, daher ist das +Produkt $pu\ne 0$. +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$ +\[ +p(Ax)=(pA)x=(A^tp^t)^tx= +\varrho(A)(p^t)^tx += +\varrho(A)px = 0, +\] +somit ist $A\ker p \subset \ker p$. +Beide Räume sind also invariante Unteräume. + +$\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 +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. +Die beiden Vektoren $u$ und $u_1$ sind dann beide Eigenvektoren, was +nach Satz~\ref{buch:wahrscheinlichkeit:satz:geometrischeinfach} +nicht möglich ist. +\end{proof} + +Die in den Sätzen +\ref{buch:wahrscheinlichkeit:satz:positivereigenvektor} +bis +\ref{buch:wahrscheinlichkeit:satz:algebraischeinfach} +gefundenen Resultate können wir folgt zusammengefasst werden: + +\begin{satz}[Perron-Frobenius] +Sei $A$ eine positive Matrix mit Spektralradius $\varrho(A)$. +Dann gibt es einen positiven Eigenvektor zum Eigenwert $\varrho(A)$, +mit geometrischer und algebraischer Vielfachheit $1$. +\end{satz} + + |
