From 812a80acf52275699afb285db46aa76be03006c2 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@othello.ch>
Date: Mon, 18 Jan 2021 21:01:26 +0100
Subject: add more stuff about spectral radius

---
 buch/chapters/40-eigenwerte/spektralradius.tex | 428 +++++++++++++++++++++++++
 1 file changed, 428 insertions(+)

(limited to 'buch/chapters/40-eigenwerte/spektralradius.tex')

diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex
index 67147f2..be986f1 100644
--- a/buch/chapters/40-eigenwerte/spektralradius.tex
+++ b/buch/chapters/40-eigenwerte/spektralradius.tex
@@ -9,3 +9,431 @@
 % Konvergenz von Matrixreihen
 % Konditionszahl
 
+\begin{definition}
+\index{Norm}%
+Die {\em Norm} einer Matrix $M$ ist
+\[
+\|M\|
+=
+\max\{|Mx|\,|\, x\in\mathbb R^n\wedge |x|=1\}.
+\]
+Für einen Vektor $x\in\mathbb R^n$ gilt $|Mx| \le \|M\|\cdot |x|$.
+\end{definition}
+
+Die Bedingung \eqref{buch:gs:fehler} bedeutet jedoch nicht,
+dass die Norm der Ableitung $<1$ sein muss, es genügt, wenn
+genügend hohe Potenzen der Ableitung eine Norm $<1$ haben.
+\index{Ableitung}%
+
+\begin{beispiel}
+Die Matrix
+\[
+M=\begin{pmatrix}
+0&2\\
+\frac13&0
+\end{pmatrix}
+\]
+hat Norm
+\[
+\|M\|
+=
+\max_{|x|=1} |Mx| 
+=
+\max_{t\in\mathbb R} \sqrt{2^2\cos^2 t +\frac1{3^2}\sin^2t} \ge 2.
+\]
+Da aber
+\[
+M^2 = \begin{pmatrix}
+\frac{2}{3}&0\\
+0&\frac{2}{3}
+\end{pmatrix}
+\qquad\Rightarrow\qquad \|M^2\|=\frac23
+\]
+ist, wird eine Iteration mit Ableitungsmatrix $M$ trotzdem
+konvergieren, weil der Fehler nach jedem zweiten Schritt um den
+Faktor $\frac23$ kleiner geworden ist.
+\end{beispiel}
+
+Dies führt uns auf die Grösse
+\begin{equation}
+\pi(M)
+=
+\limsup_{n\to\infty} \|M^n\|^\frac1n.
+\label{buch:eqn:gelfand-grenzwert}
+\end{equation}
+Ist $\pi(M) > 1$, dann gibt es Anfangsvektoren $v$ für die Iteration,
+für die $M^kv$ über alle Grenzen wächst.
+Ist $\pi(M) < 1$, dann wird jeder Anfangsvektor $v$ zu einer Iterationsfolge
+$M^kv$ führen, die gegen $0$ konvergiert.
+Die Kennzahl $\pi(M)$ erlaubt also zu entscheiden, ob ein
+Iterationsverfahren konvergent ist.
+\index{Konvergenzbedingung}%
+
+Die Berechnung von $\pi(M)$ als Grenzwert ist sehr unhandlich.
+Viel einfacher ist der Begriff des Spektralradius.
+\index{Spektralradius}%
+
+\begin{definition}
+\label{buch:definition:spektralradius}
+Der {\em Spektralradius} der Matrix $M$ ist der Betrag des betragsgrössten
+Eigenwertes.
+\end{definition}
+
+%
+% Gelfand-Radius und Eigenwerte
+%
+\subsection{Gelfand-Radius und Eigenwerte
+\label{buch:subsection:spektralradius}}
+In Abschnitt~\ref{buch:subsection:konvergenzbedingung}
+ist der Gelfand-Radius mit Hilfe eines Grenzwertes definiert worden.
+\index{Gelfand-Radius}%
+Nur dieser Grenzwert ist in der Lage, über die Konvergenz eines 
+Iterationsverfahrens Auskunft zu geben.
+Der Grenzwert ist aber sehr mühsam zu berechnen.
+\index{Grenzwert}%
+Es wurde angedeutet, dass der Gelfand-Radius mit dem Spektralradius
+übereinstimmt, dem Betrag des des betragsgrössten Eigenwertes.
+Dies hat uns ein vergleichsweise einfach auszuwertendes Konvergenzkriterium
+geliefert.
+\index{Konvergenzkriterium}%
+In diesem Abschnitt soll diese Identität zunächst an Spezialfällen
+und später ganz allgemein gezeigt werden.
+
+\subsubsection{Spezialfall: Diagonalisierbare Matrizen}
+Ist eine Matrix $A$ diagonalisierbar, dann kann Sie durch eine Wahl
+einer geeigneten Basis in Diagonalform
+\index{diagonalisierbar}%
+\index{Diagonalform}%
+\[
+A'
+=
+\begin{pmatrix}
+\lambda_1&        0&\dots &0\\
+0        &\lambda_2&\dots &0\\
+\vdots   &         &\ddots&\vdots\\
+0        &        0&\dots &\lambda_n
+\end{pmatrix}
+\]
+gebracht werden, wobei die Eigenwerte $\lambda_i$  möglicherweise auch
+komplex sein können.
+\index{komplex}%
+Die Bezeichnungen sollen so gewählt sein, dass $\lambda_1$ der
+betragsgrösste Eigenwert ist, dass also
+\[
+|\lambda_1| \ge |\lambda_2| \ge \dots \ge |\lambda_n|.
+\]
+Wir nehmen für die folgende, einführende Diskussion ausserdem an, dass
+sogar $|\lambda_1|>|\lambda_2|$ gilt.
+
+Unter den genannten Voraussetzungen kann man jetzt den Gelfand-Radius
+von $A$ berechnen.
+Dazu muss man $|A^nv|$ für einen beliebigen Vektor $v$ und für
+beliebiges $n$ berechnen.
+Der Vektor $v$ lässt sich in der Eigenbasis von $A$ zerlegen, also
+als Summe
+\index{Eigenbasis}%
+\[
+v = v_1+v_2+\dots+v_n
+\]
+schreiben, wobei $v_i$ Eigenvektoren zum Eigenwert $\lambda_i$ sind oder
+Nullvektoren.
+Die Anwendung von $A^k$ ergibt dann
+\[
+A^k v
+=
+A^k v_1 + A^k v_2 + \dots + A^k v_n
+=
+\lambda_1^k v_1 + \lambda_2^k v_2 + \dots + \lambda_n^k v_n.
+\]
+Für den Grenzwert braucht man die Norm von $A^kv$, also
+\begin{align}
+|A^kv|
+&= |\lambda_1^k v_1 + \lambda_2^k v_2 + \dots + \lambda_3 v_3|
+\notag
+\\
+\Rightarrow\qquad
+\frac{|A^kv|}{\lambda_1^k}
+&=
+\biggl|
+v_1 +
+\biggl(\frac{\lambda_2}{\lambda_1}\biggr)^k v_2
++
+\dots
++
+\biggl(\frac{\lambda_n}{\lambda_1}\biggr)^k v_n
+\biggr|.
+\label{buch:spektralradius:eqn:eigenwerte}
+\end{align}
+Da alle Quotienten $|\lambda_i/\lambda_1|<1$ sind für $i\ge 2$,
+konvergieren alle Terme auf der rechten Seite von
+\eqref{buch:spektralradius:eqn:eigenwerte}
+ausser dem ersten gegen $0$.
+Folglich ist
+\[
+\lim_{k\to\infty} \frac{|A^kv|}{|\lambda_1|^k}
+=
+|v_1|
+\qquad\Rightarrow\qquad
+\lim_{k\to\infty} \frac{|A^kv|^\frac1k}{|\lambda_1|}
+=
+\lim_{k\to\infty}|v_1|^{\frac1k}
+=
+1.
+\]
+Dies gilt für alle Vektoren $v$, für die $v_1\ne 0$ ist.
+Der maximale Wert dafür wird erreicht, wenn man für 
+$v$ einen Eigenvektor der Länge $1$ zum Eigenwert $\lambda_1$ einsetzt,
+dann ist $v=v_1$.
+Es folgt dann
+\[
+\pi(A)
+=
+\lim_{k\to\infty} \| A^k\|^\frac1k
+=
+\lim_{k\to\infty} |A^kv|^\frac1k
+=
+|\lambda_1|
+=
+\varrho(A).
+\]
+Damit ist gezeigt, dass im Spezialfall einer diagonalisierbaren Matrix der
+Gelfand-Radius tatsächlich der Betrag des betragsgrössten Eigenwertes ist.
+\index{Gelfand-Radius}%
+
+\subsubsection{Blockmatrizen}
+Wir betrachten jetzt eine $(n+m)\times(n+m)$-Blockmatrix der Form
+\begin{equation}
+A = \begin{pmatrix} B & 0 \\ 0 & C\end{pmatrix}
+\label{buch:spektralradius:eqn:blockmatrix}
+\end{equation}
+mit einer $n\times n$-Matrix $B$ und einer $m\times m$-Matrix $C$.
+Ihre Potenzen haben ebenfalls Blockform:
+\[
+A^k = \begin{pmatrix} B^k & 0 \\ 0 & C^k\end{pmatrix}.
+\]
+Ein Vektor $v$ kann in die zwei Summanden $v_1$ bestehen aus den
+ersten $n$ Komponenten und $v_2$ bestehen aus den letzten $m$ 
+Komponenten zerlegen.
+Dann ist
+\[
+A^kv = B^kv_1 + C^kv_2.
+\qquad\Rightarrow\qquad
+|A^kv|
+\le
+|B^kv_1| + |C^kv_2|
+\le 
+\pi(B)^k |v_1| + \pi(C)^k |v_2|.
+\]
+Insbesondere haben wir das folgende Lemma gezeigt:
+
+\begin{lemma}
+\label{buch:spektralradius:lemma:diagonalbloecke}
+Eine diagonale Blockmatrix $A$ \eqref{buch:spektralradius:eqn:blockmatrix}
+Blöcken $B$ und $C$  hat Gelfand-Radius
+\[
+\pi(A) = \max ( \pi(B), \pi(C) )
+\]
+\end{lemma}
+
+Selbstverständlich lässt sich das Lemma auf Blockmatrizen mit beliebig
+vielen diagonalen Blöcken verallgemeinern.
+\index{Blockmatrix}%
+
+Für Diagonalmatrizen der genannten Art sind aber auch die 
+Eigenwerte leicht zu bestimmen.
+\index{Diagonalmatrix}%
+Hat $B$ die Eigenwerte $\lambda_i^{(B)}$ mit $1\le i\le n$ und $C$ die
+Eigenwerte $\lambda_j^{(C)}$ mit $1\le j\le m$, dann ist das charakteristische
+Polynom der Blockmatrix $A$ natürlich
+\index{charakteristisches Polynom}%
+\index{Polynom!charakteristisch}%
+\[
+\chi_A(\lambda) = \chi_B(\lambda)\chi_C(\lambda),
+\]
+woraus folgt, dass die Eigenwerte von $A$ die Vereinigung der Eigenwerte
+von $B$ und $C$ sind.
+Daher gilt auch für die Spektralradius die Formel
+\[
+\varrho(A) = \max(\varrho(B) , \varrho(C)).
+\]
+
+\subsubsection{Jordan-Blöcke}
+\index{Jordan-Block}%
+Nicht jede Matrix ist diagonalisierbar, die bekanntesten Beispiele sind
+die Matrizen
+\begin{equation}
+J_n(\lambda)
+=
+\begin{pmatrix}
+\lambda &      1&       &       &       &       \\
+        &\lambda&      1&       &       &       \\[-5pt]
+        &       &\lambda&\ddots &       &       \\[-5pt]
+        &       &       &\ddots &      1&       \\
+        &       &       &       &\lambda&      1\\
+        &       &       &       &       &\lambda
+\end{pmatrix},
+\label{buch:spektralradius:eqn:jordan}
+\end{equation}
+wobei $\lambda\in\mathbb C$ eine beliebige komplexe Zahl ist.
+Wir nennen diese Matrizen {\em Jordan-Matrizen}.
+Es ist klar, dass $J_n(\lambda)$ nur den $n$-fachen Eigenwert
+$\lambda$ hat und dass der erste Standardbasisvektor ein
+Eigenvektor zu diesem Eigenwert ist.
+
+In der linearen Algebra lernt man, dass jede Matrix durch Wahl
+\index{lineare!Algebra}%
+einer geeigneten Basis als Blockmatrix der Form
+\[
+A
+=
+\begin{pmatrix}
+J_{n_1}(\lambda_1) &        0         & \dots & 0 \\
+       0         & J_{n_2}(\lambda_2) & \dots & 0 \\[-4pt]
+\vdots           &\vdots            &\ddots &\vdots \\
+       0         &        0         & \dots &J_{n_l}(\lambda_l)
+\end{pmatrix}
+\]
+geschrieben werden kann\footnote{Sofern die Matrix komplexe Eigenwerte
+hat muss man auch komplexe Basisvektoren zulassen.}.
+Die früheren Beobachtungen über den Spektralradius und den
+Gelfand-Radius von Blockmatrizen zeigen uns daher, dass
+nur gezeigt werden muss, dass nur die Gleichheit des Gelfand-Radius
+und des Spektral-Radius von Jordan-Blöcken gezeigt werden muss.
+
+\subsubsection{Iterationsfolgen}
+\begin{satz}
+\label{buch:spektralradius:satz:grenzwert}
+Sei $A$ eine $n\times n$-Matrix mit Spektralradius $\varrho(A)$.
+Dann ist $\varrho(A)<1$ genau dann, wenn
+\[
+\lim_{k\to\infty} A^k = 0.
+\]
+Ist andererseits $\varrho(A) > 1$, dann ist
+\[
+\lim_{k\to\infty} \|A^k\|=\infty.
+\]
+\end{satz}
+
+\begin{proof}[Beweis]
+Wie bereits angedeutet reicht es, diese Aussagen für einen einzelnen
+Jordan-Block mit Eigenwert $\lambda$ zu beweisen.
+Die $k$-te Potenz von $J_n(\lambda)$ ist
+\[
+J_n(\lambda)^k
+=
+\renewcommand\arraystretch{1.35}
+\begin{pmatrix}
+\lambda^k    & \binom{k}{1} \lambda^{k-1} & \binom{k}{2}\lambda^{k-2}&\dots&
+\binom{k}{n-1}\lambda^{k-n+1}\\
+      0      &\lambda^k & \binom{k}{1} \lambda^{k-1} & \dots &\binom{k}{n-2}\lambda^{k-n+2}\\
+      0     &      0    & \lambda^k & \dots &\binom{k}{n-k+3}\lambda^{k-n+3}\\
+\vdots      & \vdots    &               &\ddots & \vdots\\
+     0      &      0    &      0        &\dots  &\lambda^k
+\end{pmatrix}.
+\]
+Falls $|\lambda| < 1$ ist, gehen alle Potenzen von $\lambda$ exponentiell
+schnell gegen $0$, während die Binomialkoeffizienten nur polynomiell
+schnell anwachsen. 
+\index{Binomialkoeffizient}%
+In diesem Fall folgt also $J_n(\lambda)\to 0$.
+
+Falls $|\lambda| >1$ divergieren bereits die Elemente auf der Diagonalen,
+also ist $\|J_n(\lambda)^k\|\to\infty$ mit welcher Norm auch immer man
+man die Matrix misst.
+\end{proof}
+
+Aus dem Beweis kann man noch mehr ablesen.
+Für $\varrho(A)< 1$ ist die Norm $ \|A^k\| \le M \varrho(A)^k$ für eine
+geeignete Konstante $M$,
+für $\varrho(A) > 1$ gibt es eine Konstante $m$ mit
+$\|A^k\| \ge m\varrho(A)^k$.
+
+\subsubsection{Der Satz von Gelfand}
+Der Satz von Gelfand ergibt sich jetzt als direkte Folge aus dem
+Satz~\ref{buch:spektralradius:satz:grenzwert}.
+
+\begin{satz}[Gelfand]
+\index{Satz von Gelfand}%
+\index{Gelfand!Satz von}%
+\label{buch:satz:gelfand}
+Für jede komplexe $n\times n$-Matrix $A$ gilt
+\[
+\pi(A)
+=
+\lim_{k\to\infty}\|A^k\|^\frac1k
+=
+\varrho(A).
+\]
+\end{satz}
+
+\begin{proof}[Beweis]
+Der Satz~\ref{buch:spektralradius:satz:grenzwert} zeigt, dass der
+Spektralradius ein scharfes Kriterium dafür ist, ob $\|A^k\|$ 
+gegen 0 oder $\infty$ konvergiert.
+Andererseits ändert ein Faktor $t$ in der Matrix $A$ den Spektralradius
+ebenfalls um den gleichen Faktor, also $\varrho(tA)=t\varrho(A)$.
+Natürlich gilt auch
+\[
+\pi(tA)
+=
+\lim_{k\to\infty} \|t^kA^k\|^\frac1k
+=
+\lim_{k\to\infty} t\|A^k\|^\frac1k
+=
+t\lim_{k\to\infty} \|A^k\|^\frac1k
+=
+t\pi(A).
+\]
+
+Wir betrachten jetzt die Matrix
+\[
+A(\varepsilon) = \frac{A}{\varrho(A) + \varepsilon}.
+\]
+Der Spektralradius von $A(\varepsilon)$ ist
+\[
+\varrho(A(\varepsilon)) = \frac{\varrho(A)}{\varrho(A)+\varepsilon},
+\]
+er ist also $>1$ für negatives $\varepsilon$ und $<1$ für positives
+$\varepsilon$.
+Aus dem Satz~\ref{buch:spektralradius:satz:grenzwert} liest man daher ab,
+dass $\|A(\varepsilon)^k\|$ genau dann gegen $0$ konvergiert, wenn
+$\varepsilon > 0$ ist und divergiert genau dann, wenn $\varepsilon< 0$ ist.
+
+Aus der Bemerkung nach dem Beweis von
+Satz~\ref{buch:spektralradius:satz:grenzwert} schliesst man daher, dass 
+es im Fall $\varepsilon > 0$ eine Konstante $M$ gibt mit
+\begin{align*}
+\|A(\varepsilon) ^k\|\le M\varrho(A(\varepsilon))^k
+\quad&\Rightarrow\quad
+\|A(\varepsilon) ^k\|^\frac1k\le M^\frac1k\varrho(A(\varepsilon))
+\\
+&\Rightarrow\quad
+\pi(A) \le  \varrho(A(\varepsilon))
+\underbrace{\lim_{k\to\infty} M^\frac1k}_{\displaystyle=1}
+=
+\varrho(A(\varepsilon))
+=
+\varrho(A)+\varepsilon.
+\end{align*}
+Dies gilt für beliebige $\varepsilon >0$, es folgt daher
+$\pi(A) \le \varrho(A)$.
+
+Andererseits gibt es für $\varepsilon <0$ eine Konstante $m$ mit
+\begin{align*}
+\|A(\varepsilon) ^k\|\ge m\varrho(A(\varepsilon))^k
+\quad&\Rightarrow\quad
+\|A(\varepsilon) ^k\|^\frac1k\ge m^\frac1k\varrho(A(\varepsilon))
+\\
+&\Rightarrow\quad
+\pi(A) \ge  \varrho(A(\varepsilon))
+\underbrace{\lim_{k\to\infty} m^\frac1k}_{\displaystyle=1}
+=
+\varrho(A(\varepsilon))
+=
+\varrho(A)+\varepsilon.
+\end{align*}
+Dies gilt für beliebige $\varepsilon> 0$, es folgt daher
+$\pi(A) \ge \varrho(A)$.
+Zusammen mit $\pi(A) \le \varrho(A)$ folgt $\pi(A)=\varrho(A)$.
+\end{proof}
+
-- 
cgit v1.2.1


From 3d97112ba93690936fad4cd6493610069cbfacdd Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@othello.ch>
Date: Mon, 18 Jan 2021 21:14:48 +0100
Subject: repurposing spectral radius section

---
 buch/chapters/40-eigenwerte/spektralradius.tex | 34 ++++++++++++++++++--------
 1 file changed, 24 insertions(+), 10 deletions(-)

(limited to 'buch/chapters/40-eigenwerte/spektralradius.tex')

diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex
index be986f1..0c99106 100644
--- a/buch/chapters/40-eigenwerte/spektralradius.tex
+++ b/buch/chapters/40-eigenwerte/spektralradius.tex
@@ -3,11 +3,22 @@
 %
 % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswi
 %
-\section{Spektralradius
-\label{buch:section:spektralradius}}
-% Satz von Gelfand
-% Konvergenz von Matrixreihen
-% Konditionszahl
+\section{Funktionen einer Matrix
+\label{buch:section:funktionen-einer-matrix}}
+\rhead{Funktionen einer Matrix}
+
+%
+% Polynom-Funktionen von Matrizen
+%
+\subsection{Polynom-Funktionen
+\label{buch:subsection:polynom-funktionen}}
+
+
+%
+% Approximationen für Funktionswerte f(A)
+%
+\subsection{Approximation von $f(A)$
+\label{buch:subsection:approximation}}
 
 \begin{definition}
 \index{Norm}%
@@ -20,11 +31,6 @@ Die {\em Norm} einer Matrix $M$ ist
 Für einen Vektor $x\in\mathbb R^n$ gilt $|Mx| \le \|M\|\cdot |x|$.
 \end{definition}
 
-Die Bedingung \eqref{buch:gs:fehler} bedeutet jedoch nicht,
-dass die Norm der Ableitung $<1$ sein muss, es genügt, wenn
-genügend hohe Potenzen der Ableitung eine Norm $<1$ haben.
-\index{Ableitung}%
-
 \begin{beispiel}
 Die Matrix
 \[
@@ -54,6 +60,14 @@ konvergieren, weil der Fehler nach jedem zweiten Schritt um den
 Faktor $\frac23$ kleiner geworden ist.
 \end{beispiel}
 
+%
+% Potenzreihen für Funktionen $f(z)$
+%
+\subsection{Potenzreihen
+\label{buch:subsection:potenzreihen}}
+
+
+
 Dies führt uns auf die Grösse
 \begin{equation}
 \pi(M)
-- 
cgit v1.2.1


From 45794fb198c8fac02b5c82b6ac3f1e17bac1075e Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Andreas=20M=C3=BCller?= <andreas.mueller@othello.ch>
Date: Tue, 19 Jan 2021 22:08:40 +0100
Subject: =?UTF-8?q?Permutationen=20hinzugef=C3=BCgt?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 buch/chapters/40-eigenwerte/spektralradius.tex | 351 +++++++++++++++++++++++++
 1 file changed, 351 insertions(+)

(limited to 'buch/chapters/40-eigenwerte/spektralradius.tex')

diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex
index 0c99106..3afac18 100644
--- a/buch/chapters/40-eigenwerte/spektralradius.tex
+++ b/buch/chapters/40-eigenwerte/spektralradius.tex
@@ -6,19 +6,365 @@
 \section{Funktionen einer Matrix
 \label{buch:section:funktionen-einer-matrix}}
 \rhead{Funktionen einer Matrix}
+Eine zentrale Motivation in der Entwicklung der Eigenwerttheorie
+war das Bestreben, Potenzen $A^k$ auch für grosse $k$ effizient
+zu berechnen.
+Mit der Jordan-Normalform ist dies auch gelungen, wenigstens über
+einem Körper, in dem das charakteristische Polynom in Linearfaktoren
+zerfällt.
+Die Berechnung von Potenzen war aber nur der erste Schritt, das Ziel
+in diesem Abschnitt ist, $f(A)$ für eine genügend grosse Klasse von
+Funktionen $f$ berechnen zu können.
 
 %
 % Polynom-Funktionen von Matrizen
 %
 \subsection{Polynom-Funktionen
 \label{buch:subsection:polynom-funktionen}}
+In diesem Abschnitt ist $B\in M_n(\Bbbk)$ und $\Bbbk'\supset\Bbbk$ ein
+Körper, über dem das charakteristische Polynome $\chi_A(x)$ in
+Linearfaktoren
+\[
+\chi_A(x)
+=
+(\lambda_1-x)^{m_1}(\lambda_2-x)^{m_2}\cdot\ldots\cdot(\lambda_p-x)^{m_p}
+\]
+zerfällt.
+
+Für jedes beliebige Polynome $p(X)=\Bbbk[X]$ der Form
+\[
+p(X) = a_nX^n + a_{n-1}X^{n-1} + \dots a_1x + a_0
+\]
+kann man auch
+\[
+p(A) = a_nA^n + a_{n-1}A^{n-1} + \dots a_1A + a_0E
+\]
+berechnen.
+In der Jordan-Normalform können die Potenzen $A^k$ leicht zusammengstellt
+werden, sobald man die Potenzen von Jordan-Blöcken berechnet hat.
 
+\begin{satz}
+Die $k$-te Potenz von $J_n(\lambda)$ ist die Matrix mit
+\begin{equation}
+J_n(\lambda)^k
+=
+\begin{pmatrix}
+\lambda^k
+	& \binom{k}{1}\lambda^{k-1}
+		& \binom{k}{2} \lambda^{k-2}
+			& \binom{k}{3} \lambda^{k-3}
+				& \dots
+					&\binom{k}{n-1}\lambda^{k-n+1}
+\\
+0
+	& \lambda^k
+		& \binom{k}{1}\lambda^{k-1}
+			& \binom{k}{2} \lambda^{k-2}
+				& \dots
+					&\binom{k}{n-2}\lambda^{k-n+2}
+\\
+0
+	& 0
+		& \lambda^k
+			& \binom{k}{1}\lambda^{k-1}
+				& \dots
+					&\binom{k}{n-3}\lambda^{k-n+3}
+\\
+\vdots  &\vdots &\vdots &\vdots &\ddots & \vdots
+\\
+0	& 0	& 0	& 0	& \dots	& \lambda^k
+\end{pmatrix}
+\label{buch:eigenwerte:eqn:Jnkpotenz}
+\end{equation}
+mit den Matrixelementen
+\[
+(J_n(\lambda)^k)_{ij}
+=
+\binom{k}{j-i}\lambda^{k-j+i}
+\]
+Die Binomialkoeffizienten verschwinden für $j<i$ und $j>i+k$.
+\end{satz}
+
+\begin{proof}[Beweis]
+Die Herkunft der Binomialkoeffizienten wird klar, wenn man
+\[
+J_n(\lambda) = \lambda E + N_n
+\]
+schreibt, wobei $N_n$ die Matrix \eqref{buch:eigenwerte:eqn:nnilpotent} ist.
+Die Potenzen von $N_n$ haben die Matrix-Elemente
+\[
+(N_n^k)_{ij}
+=
+\delta_{i,j-k}
+=
+\begin{cases}
+1&\qquad j-i=k\\
+0&\qquad\text{sonst,}
+\end{cases}
+\]
+sie haben also Einsen genau dort, wo in der
+\label{buch:eigenwerte:eqn:Jnkpotenz} die Potenz $\lambda^{k}$ steht.
+Die $kt$-te Potenz von $J_n(\lambda)$ kann dann mit dem binomischen
+Satz berechnet werden:
+\[
+J_n(\lambda)^k
+=
+\sum_{l=0}^k \binom{k}{l}\lambda^l N_n^{k-l},
+\]
+dies ist genau die Form \eqref{buch:eigenwerte:eqn:Jnkpotenz}.
+\end{proof}
+
+Wir haben bereits gesehen, dass $\chi_A(A)=0$, ersetzt man also das
+Polynom $p(X)$ durch $p(X)+\chi_A(X)$, dann ändert sich am Wert 
+\[
+(p+\chi_A)(A)
+=
+p(A) + \chi_A(A)
+=
+p(A)
+\]
+nichts.
+Man kann also nicht erwarten, dass verschiedene Polynome 
+$p(X)$ zu verschiedenen Matrizen $p(A)$ führen.
+Doch welche Unterschiede zwischen Polynomen wirken sich genau aus?
+
+\begin{satz}
+Für zwei Polynome $p(X)$ und $q(X)$ ist genau dann $p(A)=q(A)$, wenn
+das Minimalpolynom von $A$ die Differenz $p-q$ teilt.
+\end{satz}
+
+\begin{proof}[Beweis]
+Wenn $p(A)=q(A)$, dann ist $h(X)=p(X)-q(X)$ ein Polynom mit $h(A)=0$,
+daher muss $h(X)$ vom Minimalpolynom geteilt werden.
+Ist andererseits $p(X)-q(X)=m(X)t(X)$, dann ist
+$p(A)-q(A)=m(A)t(A)=0\cdot t(A) = 0$, also $p(A)=q(A)$.
+\end{proof}
+
+Über einem Körper $\Bbbk'\supset\Bbbk$, über dem das charakteristische
+Polynom in Linearfaktoren zerfällt, kann man das Minimalpolynom aus
+der Jordanschen Normalform ableiten.
+Es ist
+\[
+m(X)
+=
+(\lambda_1-X)^{q_1}
+(\lambda_2-X)^{q_2}
+\cdot\ldots
+\cdot
+(\lambda_p-X)^{q_p},
+\]
+wobei $q_i$ die Dimension des grössten Jordan-Blocks ist, der in der
+Jordan-Normalform vorkommt.
+Zwei Polynome $p_1(X)$ und $p_2(X)$ haben genau dann den gleichen Wert,
+wenn die Differenz $p_1(X)-p_2(X)$ genau die Nullstellen
+$\lambda_1,\dots,\lambda_p$ mit Vielfachheiten $q_1,\dots,q_p$ hat.
+
+\begin{beispiel}
+Wir betrachten die Matrix
+\[
+A
+=
+\begin{pmatrix}
+   1&  9& -4\\
+  -1&  3&  0\\
+  -2&  0&  3
+\end{pmatrix}
+\]
+mit dem charakteristischen Polynom
+\[
+\chi_A(x)
+=
+-x^3+7x^2-16 x+12
+=
+-(x-3)(x-2)^2.
+\]
+Daraus kann man bereits ablesen, dass das Minimalpolynom $m(X)$ von $A$ 
+entweder $(X-2)(X-3)$ oder $(X-2)^2(X-3)$ ist.
+Es genügt also nachzuprüfen, ob $p(A)=0$ für das Polynom
+$p(X)=(X-2)(X-3) = X^2-5X+6$ ist.
+Tatsächlich sind die Potenzen von $A$:
+\[
+A^2=
+\begin{pmatrix}
+  0&  36& -16 \\
+ -4&   0&   4 \\
+ -8& -18&  17 
+\end{pmatrix}
+,\qquad
+A^3=
+\begin{pmatrix}
+ -4& 108& -48\\
+-12& -36&  28\\
+-24&-126&  83
+\end{pmatrix}
+\]
+und daraus kann man jetzt $P(A)$ berechnen:
+\begin{equation}
+p(A)
+=
+\begin{pmatrix}
+  0&  36& -16 \\
+ -4&   0&   4 \\
+ -8& -18&  17 
+\end{pmatrix}
+-5
+\begin{pmatrix}
+   1&  9& -4\\
+  -1&  3&  0\\
+  -2&  0&  3
+\end{pmatrix}
++
+6
+\begin{pmatrix}
+1&0&0\\
+0&1&0\\
+0&0&1
+\end{pmatrix}
+=
+\begin{pmatrix}
+   1& -9&  4\\
+   1& -9&  4\\
+   2&-18&  8
+\end{pmatrix}
+=
+\begin{pmatrix}1\\1\\2\end{pmatrix}
+\begin{pmatrix}1&-9&4\end{pmatrix}
+\label{buch:eigenwerte:eqn:nichtminimalpolynom}
+\end{equation}
+Also ist tatsächlich $(X-2)^2(X-3)$ das Minimalpolynom.
+
+Das Quadrat des Polynoms $p(X)$ ist $p(X)^2 = (X-2)^2(X-3)^2$, es hat
+das Minimalpolynom als Teiler, also muss $p(A)^2=0$ sein.
+Die Gleichung \eqref{buch:eigenwerte:eqn:nichtminimalpolynom} ermöglicht,
+das Quaddrat $p(A)^2$ leichter zu berechnen:
+\[
+p(A)^2
+=
+\begin{pmatrix}1\\1\\2\end{pmatrix}
+\underbrace{
+\begin{pmatrix}1&-9&4\end{pmatrix}
+\begin{pmatrix}1\\1\\2\end{pmatrix}
+}_{\displaystyle = 0}
+\begin{pmatrix}1&-9&4\end{pmatrix}
+=
+0
+,
+\]
+wie zu erwarten war.
+
+Wenn sich zwei Polynome nur um das charakteristische Polynom unterscheiden,
+dann haben sie den gleichen Wert auf $A$.
+Das Polynom $p_1(X)=X^3$ unterschiedet sich vom Polynom $p_2(X)=7X^2-16X+12$ 
+um das charakteristische Polynom, welches wir bereits als das Minimalpolynom
+von $A$ erkannt haben.
+Die dritte Potenz $A^3$ von $A$ muss sich daher auch mit $p_2(X)$ berechnen
+lassen:
+\[
+7
+\begin{pmatrix}
+  0&  36& -16 \\
+ -4&   0&   4 \\
+ -8& -18&  17 
+\end{pmatrix}
+-16
+\begin{pmatrix}
+   1&  9& -4\\
+  -1&  3&  0\\
+  -2&  0&  3
+\end{pmatrix}
++12
+\begin{pmatrix}
+1&0&0\\
+0&1&0\\
+0&0&1
+\end{pmatrix}
+=
+\begin{pmatrix}
+ -4& 108&  -48\\
+-12& -36&   28\\
+-24&-126&   83
+\end{pmatrix}
+=
+A^3.
+\qedhere
+\]
+\end{beispiel}
+
+\begin{satz}
+Wenn $A$ diagonalisierbar ist über einem geeignet erweiterten Körper $\Bbbk'$,
+dann haben zwei Polynome $p(X)$ und $q(X)$ in $\Bbbk[X]$ genau dann
+den gleichen Wert auf $A$, also $p(A)=q(A)$, wenn $p(\lambda) = q(\lambda)$
+für alle Eigenwerte $\lambda$ von $A$.
+\end{satz}
+
+Über dem Körper der komplexen Zahlen ist die Bedingung, dass die Differenz
+$d(X)=p_1(X)-p_2(X)$ vom Minimalpolynom geteilt werden muss, gleichbedeutend
+damit, dass $p_1(X)$ und $p_2(X)$ den gleichen Wert und gleiche Ableitungen
+bis zur Ordnung $q_i-1$ haben in allen Eigenwerten $\lambda_i$, wobei 
+$q_i$ der Exponent von $\lambda_i-X$ im Minimalpolynom von $A$ ist.
+
+Das Beispiel illustriert auch noch ein weiteres wichtiges Prinzip.
+Schreiben wir das Minimalpolynom von $A$ in der Form
+\[
+m(X)
+=
+X^k + a_{k-1}X^{k-1} + \dots + a_1X + a_0,
+\]
+dann kann man wegen $m(A)=0$ die Potenzen $A^i$ mit $i\ge k$ mit der
+Rekursionsformel
+\[
+A^i
+=
+A^{i-k}A^k
+=
+A^{i-k}(-a_{k-1}A^{k-1}+ \dots + a_1 A + a_0E)
+\]
+in einer Linearkombination kleinerer Potenzen reduzieren.
+Jedes Polynom vom Grad $\ge k$ kann also reduizert werden in
+ein Polynom vom Grad $<k$ mit dem gleichen Wert auf $A$.
+
+\begin{satz}
+\label{buch:eigenwerte:satz:reduktion}
+Sei $A$ eine Matrix über $\Bbbk$ mit Minimalpolynom $m(X)$.
+Zu jedem $p(X)\in\Bbbk[X]$ gibt es ein Polynom $q(X)\in\Bbbk[X]$
+vom Grad $\deg q<\deg m$ mit $p(A)=q(A)$.
+\end{satz}
 
 %
 % Approximationen für Funktionswerte f(A)
 %
 \subsection{Approximation von $f(A)$
 \label{buch:subsection:approximation}}
+Die Quadratwurzelfunktion $x\mapsto\sqrt{x}$ lässt sich nicht durch ein
+Polynom darstellen, es gibt also keine direkte Möglichkeit, $\sqrt{A}$
+für eine beliebige Matrix zu definieren.
+Wir können versuchen, die Funktion durch ein Polynom zu approximieren.
+Damit dies geht, müssen wir folgende zwei Fragen klären:
+\begin{enumerate}
+\item
+Wie misst man, ob ein Polynom eine Funktion gut approximiert?
+\item
+Was bedeutet es genau, dass zwei Matrizen ``nahe beeinander'' sind?
+\item
+In welchem Sinne müssen Polynome ``nahe'' beeinander sein, damit
+auch die Werte auf $A$ nahe beeinander sind.
+\end{enumerate}
+
+Wir wissen bereits, dass nur die Werte und gewisse Ableitungen des
+Polynoms $p(X)$ in den Eigenwerten einen Einfluss auf $p(A)$ haben.
+Es genügt also, Approximationspolynome zu verwenden, welche in der Nähe
+der Eigenwerte ``gut genug'' approximieren.
+Solche Polynome gibt es dank dem Satz von Stone-Weierstrass immer:
+
+\begin{satz}[Stone-Weierstrass]
+Ist $I\subset\mathbb{R}$ kompakt, dann lässt sich jede stetige Funktion
+durch eine Folge $p_n(x)$ beliebig genau approximieren.
+\end{satz}
+
+Wir haben schon gezeigt, dass es dabei auf die höheren Potenzen gar nicht
+ankommt, nach Satz~\ref{buch:eigenwerte:satz:reduktion} kann man ein
+approximierendes Polynom immer durch ein Polynom von kleinerem Grad
+als das Minimalpolynom ersetzen.
 
 \begin{definition}
 \index{Norm}%
@@ -60,6 +406,11 @@ konvergieren, weil der Fehler nach jedem zweiten Schritt um den
 Faktor $\frac23$ kleiner geworden ist.
 \end{beispiel}
 
+\begin{beispiel}
+Wir berechnen die Norm eines Jordan-Blocks.
+
+\end{beispiel}
+
 %
 % Potenzreihen für Funktionen $f(z)$
 %
-- 
cgit v1.2.1


From 70215b72a37c2191bc6119c008d2117ed122cc7e Mon Sep 17 00:00:00 2001
From: Roy Seitz <roy.seitz@ost.ch>
Date: Wed, 27 Jan 2021 15:04:26 +0100
Subject: Typos.

---
 buch/chapters/40-eigenwerte/spektralradius.tex | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

(limited to 'buch/chapters/40-eigenwerte/spektralradius.tex')

diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex
index 3afac18..bdc725f 100644
--- a/buch/chapters/40-eigenwerte/spektralradius.tex
+++ b/buch/chapters/40-eigenwerte/spektralradius.tex
@@ -31,7 +31,7 @@ Linearfaktoren
 \]
 zerfällt.
 
-Für jedes beliebige Polynome $p(X)=\Bbbk[X]$ der Form
+Für jedes beliebige Polynome $p(X)\in\Bbbk[X]$ der Form
 \[
 p(X) = a_nX^n + a_{n-1}X^{n-1} + \dots a_1x + a_0
 \]
@@ -80,7 +80,7 @@ mit den Matrixelementen
 \[
 (J_n(\lambda)^k)_{ij}
 =
-\binom{k}{j-i}\lambda^{k-j+i}
+\binom{k}{j-i}\lambda^{k-j+i}.
 \]
 Die Binomialkoeffizienten verschwinden für $j<i$ und $j>i+k$.
 \end{satz}
@@ -391,7 +391,7 @@ hat Norm
 =
 \max_{|x|=1} |Mx| 
 =
-\max_{t\in\mathbb R} \sqrt{2^2\cos^2 t +\frac1{3^2}\sin^2t} \ge 2.
+\max_{t\in\mathbb R} \sqrt{2^2\cos^2 t +\frac1{3^2}\sin^2t} = 2.
 \]
 Da aber
 \[
@@ -457,7 +457,7 @@ Iterationsverfahrens Auskunft zu geben.
 Der Grenzwert ist aber sehr mühsam zu berechnen.
 \index{Grenzwert}%
 Es wurde angedeutet, dass der Gelfand-Radius mit dem Spektralradius
-übereinstimmt, dem Betrag des des betragsgrössten Eigenwertes.
+übereinstimmt, dem Betrag des  betragsgrössten Eigenwertes.
 Dies hat uns ein vergleichsweise einfach auszuwertendes Konvergenzkriterium
 geliefert.
 \index{Konvergenzkriterium}%
-- 
cgit v1.2.1

