diff options
Diffstat (limited to 'buch/chapters/40-eigenwerte')
21 files changed, 2971 insertions, 7 deletions
diff --git a/buch/chapters/40-eigenwerte/Makefile.inc b/buch/chapters/40-eigenwerte/Makefile.inc index 64531c5..b15f476 100644 --- a/buch/chapters/40-eigenwerte/Makefile.inc +++ b/buch/chapters/40-eigenwerte/Makefile.inc @@ -6,6 +6,10 @@ CHAPTERFILES = $(CHAPTERFILES) \ chapters/40-eigenwerte/numerisch.tex \ + chapters/40-eigenwerte/normalformen.tex \ + chapters/40-eigenwerte/grundlagen.tex \ chapters/40-eigenwerte/spektralradius.tex \ chapters/40-eigenwerte/spektraltheorie.tex \ + chapters/40-eigenwerte/uebungsaufgaben/4001.tex \ + chapters/40-eigenwerte/uebungsaufgaben/4002.tex \ chapters/40-eigenwerte/chapter.tex diff --git a/buch/chapters/40-eigenwerte/beispiele/Makefile b/buch/chapters/40-eigenwerte/beispiele/Makefile new file mode 100644 index 0000000..543ef65 --- /dev/null +++ b/buch/chapters/40-eigenwerte/beispiele/Makefile @@ -0,0 +1,8 @@ +# +# Makefile -- Berechnungen für Beispiel durchführen +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +all: + octave i.m + diff --git a/buch/chapters/40-eigenwerte/beispiele/i.m b/buch/chapters/40-eigenwerte/beispiele/i.m new file mode 100644 index 0000000..353e3a2 --- /dev/null +++ b/buch/chapters/40-eigenwerte/beispiele/i.m @@ -0,0 +1,65 @@ +# +# i.m -- invariante +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# + +A0 = [ + 2, 1, 0, 0; + 0, 2, 1, 0; + 0, 0, 2, 0; + 0, 0, 0, 3 +]; + +# find a 3x3 matrix in SL(3,Z) + +function retval = zufallswert() + x = round(rand() * 10) - 2; + if (x >= 0) + x = x + 1; + endif + retval = x; +end + +function retval = zufallsmatrix(n) + retval = zeros(n, n); + for i = (1:n) + for j = (1:n) + retval(i,j) = zufallswert(); + end + end +end + +function retval = regulaer(n) + d = 0; + do + retval = zufallsmatrix(2); + d = det(retval); + until (d == 1); +end + +function retval = eingebettet(n,k) + retval = eye(n); + retval(k:k+1,k:k+1) = regulaer(2); +end + +format long + +B = eye(4); +B = B * eingebettet(4,3) +B = B * eingebettet(4,1) +B = B * inverse(eingebettet(4,2)) +#B = B * eingebettet(4,2) + +B +inverse(B) + +A = round(B * A0 * inverse(B)) + +D = A - 2 * eye(4) +rank(D) + +E = round(D*D*D*D) +rank(E') + +rref(E) diff --git a/buch/chapters/40-eigenwerte/beispiele/jp.maxima b/buch/chapters/40-eigenwerte/beispiele/jp.maxima new file mode 100644 index 0000000..a80a0a2 --- /dev/null +++ b/buch/chapters/40-eigenwerte/beispiele/jp.maxima @@ -0,0 +1,19 @@ +/* + * jp.maxima -- potenzen von Jordan-Blöcken + * + * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule + */ + +A: matrix( +[lambda, 1, 0, 0, 0, 0 ], +[ 0,lambda, 1, 0, 0, 0 ], +[ 0, 0,lambda, 1, 0, 0 ], +[ 0, 0, 0,lambda, 1, 0 ], +[ 0, 0, 0, 0,lambda, 1 ], +[ 0, 0, 0, 0, 0,lambda ] +); +B: A.A; +B: B.A; +B: B.A; +B: B.A; +B: B.A; diff --git a/buch/chapters/40-eigenwerte/beispiele/n.m b/buch/chapters/40-eigenwerte/beispiele/n.m new file mode 100644 index 0000000..af0219b --- /dev/null +++ b/buch/chapters/40-eigenwerte/beispiele/n.m @@ -0,0 +1,55 @@ +# +# n.m -- Polynome mit dem gleichen Wert von p(A) +# +# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# + +A0 = [ + 2, 1, 0; + 0, 2, 0; + 0, 0, 3 +]; + +# find a 3x3 matrix in SL(3,Z) + +function retval = zufallswert() + x = round(rand() * 10) - 2; + if (x >= 0) + x = x + 1; + endif + retval = x; +end + +function retval = zufallsmatrix(n) + retval = zeros(n, n); + for i = (1:n) + for j = (1:n) + retval(i,j) = zufallswert(); + end + end +end + +function retval = regulaer(n) + d = 0; + do + retval = zufallsmatrix(2); + d = det(retval); + until (d == 1); +end + +function retval = eingebettet(n,k) + retval = eye(n); + retval(k:k+1,k:k+1) = regulaer(2); +end + +format long + +B = eye(3); +B = B * eingebettet(3,2) +B = B * eingebettet(3,1) + +B +inverse(B) + +A = round(B * A0 * inverse(B)) + diff --git a/buch/chapters/40-eigenwerte/beispiele/n.maxima b/buch/chapters/40-eigenwerte/beispiele/n.maxima new file mode 100644 index 0000000..9ed83b6 --- /dev/null +++ b/buch/chapters/40-eigenwerte/beispiele/n.maxima @@ -0,0 +1,20 @@ +/* + * n.maxima + * + * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule + */ +A: matrix( + [ 1, 9, -4 ], + [ -1, 3, 0 ], + [ -2, 0, 3 ] +); + +p: expand(charpoly(A,x)); +factor(p); + +A.A; +A.A.A; + +A.A - 5*A; + +A.A.A -7*A.A +16 *A; diff --git a/buch/chapters/40-eigenwerte/chapter.tex b/buch/chapters/40-eigenwerte/chapter.tex index 95665f7..e769b38 100644 --- a/buch/chapters/40-eigenwerte/chapter.tex +++ b/buch/chapters/40-eigenwerte/chapter.tex @@ -1,5 +1,5 @@ % -% chapter.tex -- Kapitel über eigenwerte und eigenvektoren +% chapter.tex -- Kapitel über Eigenwerte und Eigenvektoren % % (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule % @@ -7,9 +7,42 @@ \label{buch:chapter:eigenwerte-und-eigenvektoren}} \lhead{Eigenwerte und Eigenvektoren} \rhead{} +Die algebraischen Eigenschaften einer Matrix $A$ sind eng mit der +Frage nach linearen Beziehungen unter den Potenzen von $A^k$ verbunden. +Im Allgemeinen ist die Berechnung dieser Potenzen eher unübersichtlich, +es sei denn, die Matrix hat eine spezielle Form. +Die Potenzen einer Diagonalmatrix erhält man, indem man die Diagonalelemente +potenziert. +Auch für Dreiecksmatrizen ist mindestens die Berechnung der Diagonalelemente +von $A^k$ einfach. +Die Theorie der Eigenwerte und Eigenvektoren ermöglicht, Matrizen in +eine solche besonders einfache Form zu bringen. +In Abschnitt~\ref{buch:section:grundlagen} werden die grundlegenden +Definitionen der Eigenwerttheorie in Erinnerung gerufen. +Damit kann dann in Abschnitt~\ref{buch:section:normalformen} +gezeigt werden, wie Matrizen in besonders einfache Form gebracht +werden können. +Die Eigenwerte bestimmen auch die Eigenschaften von numerischen +Algorithmen, wie in den Abschnitten~\ref{buch:section:spektralradius} +und \ref{buch:section:numerisch} dargestellt wird. +Für viele Funktionen kann man auch den Wert $f(A)$ berechnen, unter +geeigneten Voraussetzungen an den Spektralradius. +Dies wird in Abschnitt~\ref{buch:section:spektraltheorie} beschrieben. -\input{chapters/40-eigenwerte/numerisch.tex} + +\input{chapters/40-eigenwerte/grundlagen.tex} +\input{chapters/40-eigenwerte/normalformen.tex} \input{chapters/40-eigenwerte/spektralradius.tex} +\input{chapters/40-eigenwerte/numerisch.tex} \input{chapters/40-eigenwerte/spektraltheorie.tex} +\section*{Übungsaufgaben} +\rhead{Übungsaufgaben} +\aufgabetoplevel{chapters/40-eigenwerte/uebungsaufgaben} +\begin{uebungsaufgaben} +\uebungsaufgabe{4001} +\uebungsaufgabe{4002} +\uebungsaufgabe{4003} +\end{uebungsaufgaben} + diff --git a/buch/chapters/40-eigenwerte/grundlagen.tex b/buch/chapters/40-eigenwerte/grundlagen.tex new file mode 100644 index 0000000..d984452 --- /dev/null +++ b/buch/chapters/40-eigenwerte/grundlagen.tex @@ -0,0 +1,1002 @@ +% +% grundlagen.tex -- Grundlagen +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\section{Grundlagen +\label{buch:section:grundlagen}} +\rhead{Grundlagen} +Die Potenzen $A^k$ sind besonders einfach zu berechnen, wenn die Matrix +Diagonalform hat, wenn also $A=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$ +ist. +In diesem Fall ist $Ae_k=\lambda_k e_k$ für jeden Standardbasisvektor $e_k$. +Statt sich auf Diagonalmatrizen zu beschränken könnten man also auch +Vektoren $v$ suchen, für die gilt $Av=\lambda v$, die also von $A$ nur +gestreckt werden. +Gelingt es, eine Basis aus solchen sogenanten {\em Eigenvektoren} zu finden, +dann kann man die Matrix $A$ durch Basiswechsel in diese Form bringen. + +% +% Kern und Bild von Matrixpotenzen +% +\subsection{Kern und Bild von Matrixpotenzen +\label{buch:subsection:kern-und-bild}} +In diesem Abschnitt ist $A\in M_n(\Bbbk)$, $A$ beschreibt eine lineare +Abbildung $f\colon\Bbbk^n\to \Bbbk^n$. +In diesem Abschnitt sollen Kern und Bild der Potenzen $A^k$ untersucht +werden. +\begin{definition} +Wir bezeichnen Kern und Bild der iterierten Abbildung $A^k$ mit +\[ +\mathcal{K}^k(A) += +\ker A^k +\qquad\text{und}\qquad +\mathcal{J}^k(A) += +\operatorname{im} A^k. +\] +\end{definition} + +Durch Iteration wird das Bild immer kleiner. +Wegen +\[ +\mathcal{J}^k (A) += +\operatorname{im} A^k += +\operatorname{im} A^{k-1} A += +\{ A^{k-1} Av\;|\; v \in \Bbbk^n\} +\subset +\{ A^{k-1} v\;|\; v \in \Bbbk^n\} += +\mathcal{J}^{k-1}(A) +\] +folgt +\begin{equation} +\Bbbk^n += +\operatorname{im}E += +\operatorname{im}A^0 += +\mathcal{J}^0(A) +\supset +\mathcal{J}^1(A) += +\operatorname{im}A +\supset +\mathcal{J}^2(A) +\supset\dots\supset +\mathcal{J}^k(A) +\supset +\mathcal{J}^{k+1}(A) +\supset \dots \supset +\{0\}. +\label{buch:eigenwerte:eqn:Jkchain} +\end{equation} +Für die Kerne gilt etwas Ähnliches. +Ein Vektor $x\in \mathcal{K}^k(A)$ erfüllt $A^kx=0$. +Dann erfüllt er aber erst recht auch +\[ +A^{k+1}x=A\underbrace{A^kx}_{\displaystyle=0}=0, +\] +also ist $x\in\mathcal{K}^k(A)$. +Es folgt +\begin{equation} +\{0\} += +\mathcal{K}^0(A) = \ker A^0 = \ker E +\subset +\mathcal{K}^1(A) = \ker A +\subset +\dots +\subset +\mathcal{K}^k(A) +\subset +\mathcal{K}^{k+1}(A) +\subset +\dots +\subset +\Bbbk^n. +\label{buch:eigenwerte:eqn:Kkchain} +\end{equation} +Neben diesen offensichtlichen Resultaten kann man aber noch mehr +sagen. +Es ist klar, dass in beiden Ketten +\label{buch:eigenwerte:eqn:Jkchain} +und +\label{buch:eigenwerte:eqn:Kkchain} +nur in höchstens $n$ Schritten eine wirkliche Änderung stattfinden +kann. +Man kann aber sogar genau sagen, wo Änderungen stattfinden: + +\begin{satz} +\label{buch:eigenwerte:satz:ketten} +Ist $A\in M_n(\Bbbk)$ eine $n\times n$-Matrix, dann gibt es eine Zahl $k$ +so, dass +\[ +\begin{array}{rcccccccccccl} +0=\mathcal{K}^0(A) +&\subsetneq& \mathcal{K}^1(A) &\subsetneq& \mathcal{K}^2(A) +&\subsetneq&\dots&\subsetneq& +\mathcal{K}^k(A) &=& \mathcal{K}^{k+1}(A) &=& \dots +\\ +\Bbbk^n= \mathcal{J}^0(A) +&\supsetneq& \mathcal{J}^1(A) &\supsetneq& \mathcal{J}^2(A) +&\supsetneq&\dots&\supsetneq& +\mathcal{J}^k(A) &=& \mathcal{J}^{k+1}(A) &=& \dots +\end{array} +\] +ist. +\end{satz} + +\begin{proof}[Beweis] +Es sind zwei Aussagen zu beweisen. +Erstens müssen wir zeigen, dass die Dimension von $\mathcal{K}^i(A)$ +nicht mehr grösser werden kann, wenn sie zweimal hintereinander gleich war. +Nehmen wir daher an, dass $\mathcal{K}^i(A) = \mathcal{K}^{i+1}(A)$. +Wir müssen $\mathcal{K}^{i+2}(A)$ bestimmen. +$\mathcal{K}^{i+2}(A)$ besteht aus allen Vektoren $x\in\Bbbk^n$ derart, +dass $Ax\in \mathcal{K}^{i+1}(A)=\mathcal{K}^i(A)$ ist. +Daraus ergibt sich, dass $AA^ix=0$, also ist $x\in\mathcal{K}^{i+1}(A)$. +Wir erhalten also +$\mathcal{K}^{i+2}(A)\subset\mathcal{K}^{i+1}\subset\mathcal{K}^{i+2}(A)$, +dies ist nur möglich, wenn beide gleich sind. + +Analog kann man für die Bilder vorgehen. +Wir nehmen an, dass $\mathcal{J}^i(A) = \mathcal{J}^{i+1}(A)$ und +bestimmten $\mathcal{J}^{i+2}(A)$. +$\mathcal{J}^{i+2}(A)$ besteht aus all jenen Vektoren, die als +$Ax$ mit $x\in\mathcal{J}^{i+1}(A)=\mathcal{J}^i(A)$ erhalten +werden können. +Es gibt also insbesondere ein $y\in\Bbbk^i$ mit $x=A^iy$. +Dann ist $Ax=A^{i+1}y\in\mathcal{J}^{i+1}(A)$. +Insbesondere besteht $\mathcal{J}^{i+2}(A)$ genau aus den Vektoren +von $\mathcal{J}^{i+1}(A)$. + +Zweitens müssen wir zeigen, dass die beiden Ketten bei der gleichen +Potenz von $A$ konstant werden. +Dies folgt jedoch daraus, dass $\dim\mathcal{J}^i(A) = \operatorname{Rang} A^i += n - \dim\ker A^i = n -\dim\mathcal{K}^i(A)$. +Der Raum $\mathcal{J}^k(A)$ hört also beim gleichen $i$ auf, kleiner +zu werden, bei dem auch $\mathcal{K}^i(A)$ aufhört, grösser zu werden. +\end{proof} + +\begin{satz} +Die Zahl $k$ in Satz~\ref{buch:eigenwerte:satz:ketten} +ist nicht grösser als $n$, also +\[ +\mathcal{K}^n(A) = \mathcal{K}^l(A) +\qquad\text{und}\qquad +\mathcal{J}^n(A) = \mathcal{J}^l(A) +\] +für $l\ge n$. +\end{satz} + +\begin{proof}[Beweis] +Nach Satz~\ref{buch:eigenwerte:satz:ketten} muss die +Dimension von $\mathcal{K}^i(A)$ in jedem Schritt um mindestens +$1$ zunehmen, das ist nur möglich, bis zur Dimension $n$. +Somit können sich $\mathcal{K}^i(A)$ und $\mathcal{J}^i(A)$ für $i>n$ +nicht mehr ändern. +\end{proof} + +\begin{definition} +\label{buch:eigenwerte:def:KundJ} +Die gemäss Satz~\ref{buch:eigenwerte:satz:ketten} identischen Unterräume +$\mathcal{K}^i(A)$ für $i\ge k$ und die identischen Unterräume +$\mathcal{J}^i(A)$ für $i\ge k$ werden mit +\[ +\begin{aligned} +\mathcal{K} &= \mathcal{K}^i(A)&&\forall i\ge k \qquad\text{und} +\\ +\mathcal{J} &= \mathcal{J}^i(A)&&\forall i\ge k +\end{aligned} +\] +bezeichnet. +\end{definition} + +% +% Inveriante Unterräume +% +\subsection{Invariante Unterräume +\label{buch:subsection:invariante-unterraeume}} +Kern und Bild sind der erste Schritt zu einem besseren Verständnis +einer linearen Abbildung oder ihrer Matrix. +Invariante Räume dienen dazu, eine lineare Abbildung in einfachere +Abbildungen zwischen ``kleineren'' Räumen zu zerlegen, wo sie leichter +analysiert werden können. + +\begin{definition} +Sei $f\colon V\to V$ eine lineare Abbildung eines Vektorraums in sich +selbst. +Ein Unterraum $U\subset V$ heisst {\em invarianter Unterraum}, +wenn +\[ +f(U) = \{ f(x)\;|\; x\in U\} \subset U +\] +gilt. +\end{definition} + +Der Kern $\ker A$ einer linearen Abbildung ist trivialerweise ein +invarianter Unterraum, da alle Vektoren in $\ker A$ auf $0\in\ker A$ +abgebildet werden. +Ebenso ist natürlich $\operatorname{im}A$ ein invarianter Unterraum, +denn jeder Vektor wird in $\operatorname{im}A$ abgebildet, insbesondere +auch jeder Vektor in $\operatorname{im}A$. + +\begin{satz} +\label{buch:eigenwerte:satz:KJinvariant} +Sei $f\colon V\to V$ eine lineare Abbildung mit Matrix $A$. +Jeder der Unterräume $\mathcal{J}^i(A)$ und $\mathcal{K}^i(A)$ +ist ein invarianter Unterraum. +\end{satz} + +\begin{proof}[Beweis] +Sei $x\in\mathcal{K}^i(A)$, es gilt also $A^ix=0$. +Wir müssen überprüfen, dass $Ax\in\mathcal{K}^i(A)$. +Wir berechnen daher $A^i\cdot Ax=A^{i+1}x=A\cdot A^ix = A\cdot 0=0$, +was zeigt, dass $Ax\in\mathcal{K}^i(A)$. + +Sei jetzt $x\in\mathcal{J}^i(A)$, es gibt also ein $y\in V$ derart, dass +$A^iy=x$. +Wir müssen überprüfen, dass $Ax\in\mathcal{J}^i(A)$. +Dazu berechnen wir $Ax=AA^iy=A^iAy\in\mathcal{J}^i(A)$, $Ax$ ist also das +Bild von $Ay$ unter $A^i$. +\end{proof} + +\begin{korollar} +Die Unterräume $\mathcal{K}(A)\subset V$ und $\mathcal{J}(A)\subset V$ +sind invariante Unterräume. +\end{korollar} + +Die beiden Unterräume $\mathcal{K}(A)$ und $\mathcal{J}(A)$ sind besonders +interessant, da wir aus der Einschränkung der Abbildung $f$ auf diese +Unterräume mehr über $f$ lernen können. + +\begin{satz} +\label{buch:eigenwerte:satz:fJinj} +Die Einschränkung von $f$ auf $\mathcal{J}(A)$ ist injektiv. +\end{satz} + +\begin{proof}[Beweis] +Die Einschränkung von $f$ auf $\mathcal{J}^k(A)$ ist +$\mathcal{J}^k(A) \to \mathcal{J}^{k+1}(A)$, nach Definition von +$\mathcal{J}^{k+1}(A)$ ist diese Abbildung surjektiv. +Da aber $\mathcal{J}^k(A)=\mathcal{J}^{k+1}(A)$ ist, ist +$f\colon \mathcal{J}^k(A)\to\mathcal{J}^k(A)$ surjektiv, +also ist $f$ auf $\mathcal{J}^k(A)$ auch injektiv. +\end{proof} + +Die beiden Unterräume $\mathcal{J}(A)$ und $\mathcal{K}(A)$ +sind Bild und Kern der iterierten Abbildung mit Matrix $A^k$. +Das bedeutet, dass $\dim\mathcal{J}(A)+\mathcal{K}(A)=n$. +Da $\mathcal{K}(A)=\ker A^k$ und andererseits $A$ injektiv ist auf +$\mathcal{J}(A)$, muss $\mathcal{J}(A)\cap\mathcal{K}(A)=0$. +Es folgt, dass $V=\mathcal{J}(A) + \mathcal{K}(A)$. + +In $\mathcal{K}(A)$ und $\mathcal{J}(A)$ kann man unabhängig voneinander +jeweils eine Basis wählen. +Die Basen von $\mathcal{K}(A)$ und $\mathcal{J}(A)$ zusammen ergeben +eine Basis von $V$. +Die Matrix $A'$ in dieser Basis wird die Blockform +\[ +A' += +\left( +\begin{array}{ccc|ccc} +&&&&&\\ +&A_{\mathcal{K}'}&&&&\\ +&&&&&\\ +\hline +&&&&&\\ +&&&&A_{\mathcal{J}'}&\\ +&&&&&\\ +\end{array} +\right) +\] +haben, wobei die Matrix $A_\mathcal{J}'$ invertierbar ist. +Die Zerlegung in invariante Unterräume ergibt also eine natürlich +Aufteilung der Matrix $A$ in kleiner Matrizen mit zum Teil bekannten +Eigenschaften. + +% +% Spezialfall, nilpotente Matrizen +% +\subsection{Nilpotente Matrizen +\label{buch:subsection:nilpotente-matrizen}} +Die Zerlegung von $V$ in die beiden invarianten Unterräume $\mathcal{J}(A)$ +und $\mathcal{K}(A)$ reduziert die lineare Abbildung auf zwei Abbildungen +mit speziellen Eigenschaften. +Es wurde bereits in Satz~\label{buch:eigenwerte:satz:fJinj} gezeigt, +dass die Einschränkung auf $\mathcal{J}(A)$ injektiv ist. +Die Einschränkung auf $\mathcal{K}(A)$ bildet nach Definition alle +Vektoren nach $k$-facher Iteration auf $0$ ab, $A^k\mathcal{K}(A)=0$. +Solche Abbildungen haben eine speziellen Namen. + +\begin{definition} +\label{buch:eigenwerte:def:nilpotent} +Eine Matrix $A$ heisst nilpotent, wenn es eine Zahl $k$ gibt, so dass +$A^k=0$. +\end{definition} + +\begin{beispiel} +Obere (oder untere) Dreiecksmatrizen mit Nullen auf der Diagonalen +sind nilpotent. +Wir rechnen dies wie folgt nach. +Die Matrix $A$ mit Einträgen $a_{ij}$ +\[ +A=\begin{pmatrix} + 0 &a_{12}&a_{13}&\dots &a_{1,n-1}&a_{1n} \\ + 0 & 0 &a_{23}&\dots &a_{1,n-1}&a_{2n} \\ + 0 & 0 & 0 &\dots &a_{1,n-1}&a_{3n} \\ +\vdots&\vdots&\vdots&\ddots&\vdots &\vdots \\ + 0 & 0 & 0 &\dots & 0 &a_{n-1,n}\\ + 0 & 0 & 0 &\dots & 0 & 0 +\end{pmatrix} +\] +erfüllt $a_{ij}=0$ für $i\ge j$. +Wir zeigen jetzt, dass sich bei der Multiplikation die nicht +verschwinden Elemente bei der Multiplikation noch rechts oben +verschieben. +Dazu multiplizieren wir zwei Matrizen $B$ und $C$ mit +$b_{ij}=0$ für $i+k>j$ und $c_{ij}=0$ für $i+l>j$. +In der folgenden graphischen Darstellung der Matrizen sind die +Bereiche, wo die Matrixelemente verschwinden, weiss. +\begin{center} +\includegraphics{chapters/40-eigenwerte/images/nilpotent.pdf} +\end{center} +Bei der Berechnung des Elementes $d_{ij}$ wird die Zeile $i$ von $B$ +mit der Spalte $j$ von $C$ multipliziert. +Die blau eingefärbten Elemente in dieser Zeile und Spalte sind $0$. +Aus der Darstellung ist abzulesen, dass das Produkt verschwindet, +die roten, von $0$ verschiedenen Elemente von den blauen Elementen +annihiliert werden. +Dies passiert immer, wenn $i+k>j-l$ ist, oder $i+(k+l)> j$. + +Wir wenden diese Beobachtung jetzt auf die Potenzen $A^s$ an. +Für die Matrixelemente von $A^s$ schreiben wir $a^s_{ij}$. +Wir behaupten, dass die Matrixelemente $A^s$ die Bedingung +$a_{ij}^s=0$ für $i+s>j$ erfüllen. +Dies ist für $s=1$ nach Voraussetzung richtig, dies ist die +Induktionsvoraussetzung. +Nehmen wir jetzt an, dass $a_{ij}^s=0$ für $i+s>j$, dann folgt +aus obiger Rechnung, dass $a_{ij}^{s+1}=0$ für $i+s+1>j$, so +dass die Bedingung auch für $A^s$ gilt (Induktionsschritt). +Mit vollständiger Induktion folgt, dass $a_{ij}^s=0$ für $i+s>j$. +Insbesondere ist $A^n=0$, die Matrix $A$ ist nilpotent. +\end{beispiel} + +Man kann die Konstruktion der Unterräume $\mathcal{K}^i(A)$ weiter +dazu verwenden, eine Basis zu finden, in der eine nilpotente Matrix +eine besonders einfach Form erhält. + +\begin{satz} +\label{buch:eigenwerte:satz:nnilpotent} +Sei $A$ eine nilpotente $n\times n$-Matrix mit der Eigenschaft, dass +$A^{n-1}\ne 0$. +Dann gibt es eine Basis so, dass $A$ die Form +\begin{equation} +A' += +\begin{pmatrix} +0&1& & & & \\ + &0&1& & & \\ + & &0& & & \\ + & & &\ddots&1& \\ + & & & &0&1\\ + & & & & &0\\ +\end{pmatrix} +\label{buch:eigenwerte:eqn:nnilpotent} +\end{equation} +bekommt. +\end{satz} + +\begin{proof}[Beweis] +Da $A^{n-1}\ne 0$ ist, gibt es einen Vektor $b_n$ derart, dass $A^{n-1}b_n\ne0$. +Wir konstruieren die Vektoren +\[ +b_n,\; +b_{n-1}=Ab_n,\; +b_{n-2}=Ab_{n-1},\; +\dots,\; +b_2=Ab_3,\; +b_1=Ab_2. +\] +Aus der Konstruktion folgt $b_1=A^{n-1}b_n\ne 0$, aber $Ab_1=A^nb_n=0$. +Aus der Konstruktion der iterierten Kerne $\mathcal{K}^i(A)$ folgt jetzt, +dass die Vektoren $b_1,\dots,b_n$ eine Basis bilden. +In dieser Basis hat die Matrix die Form~\ref{buch:eigenwerte:eqn:nnilpotent}. +\end{proof} + +\begin{definition} +Wir bezeichnen mit $N_n$ eine Matrix der Form +\eqref{buch:eigenwerte:eqn:nnilpotent}. +\end{definition} + +Mit etwas mehr Sorgfalt kann man auch die Bedingung, dass $A^{n-1}\ne 0$ +sein muss, im Satz~\ref{buch:eigenwerte:satz:nnilpotent} loswerden. + +\begin{satz} +\label{buch:eigenwerte:satz:allgnilpotent} +Sei $A$ ein nilpotente Matrix, dann gibt es eine Basis, in der die Matrix +aus lauter Nullen besteht ausser in den Einträgen unmittelbar oberhalb der +Hauptdiagonalen, wo die Einträge $0$ oder $1$ sind. +Insbesondere zerfällt eine solche Matrix in Blöcke der Form $N_{k_i}$, +$i=1,\dots,l$, +wobei $k_1+\dots+k_l=n$ sein muss: +\begin{equation} +\def\temp#1{\multicolumn{1}{|c}{\raisebox{0pt}[17pt][12pt]{\phantom{x}$#1\mathstrut$}\phantom{x}}} +A' +=\left( +\begin{array}{cccc} +\cline{1-1} +\temp{N_{k_1}} &\multicolumn{1}{|c}{}& & \\ +\cline{1-2} + &\temp{N_{k_2}}&\multicolumn{1}{|c}{}& \\ +\cline{2-3} + & &\temp{\ddots}&\multicolumn{1}{|c}{}\\ +\cline{3-4} + & & &\multicolumn{1}{|c|}{\raisebox{0pt}[17pt][12pt]{\phantom{x}$N_{k_l}$}\phantom{x}}\\ +\cline{4-4} +\end{array} +\right) +\label{buch:eigenwerte:eqn:allgnilpotent} +\end{equation} +\end{satz} + +Die Einschränkung von $f$ auf den invarianten Unterraum $\mathcal{K}(A)$ +ist nilpotent. +Die Zerlegung $V=\mathcal{J}(A)\oplus \mathcal{K}(A)$ führt also zu einer +Zerlegung der Abbildung $f$ in eine invertierbare Abbildung +$\mathcal{J}(A)\to\mathcal{J}(A)$ und eine +nilpotente Abbildung $\mathcal{K}(A)\to\mathcal{K}(A)$. +Nach Satz~\ref{buch:eigenwerte:satz:allgnilpotent} kann man in +$\mathcal{K}(A)$ eine Basis so wählen, dass die Matrix die Blockform +\eqref{buch:eigenwerte:eqn:allgnilpotent} erhält. + +% +% Begriff des Eigenwertes und Eigenvektors +% +\subsection{Eigenwerte und Eigenvektoren +\label{buch:subsection:eigenwerte-und-eigenvektoren}} +In diesem Abschnitt betrachten wir Vektorräume $V=\Bbbk^n$ über einem +beliebigen Körper $\Bbbk$ und quadratische Matrizen +$A\in M_n(\Bbbk)$. +In den meisten Anwendungen wird $\Bbbk=\mathbb{R}$ sein. +Da aber in $\mathbb{R}$ nicht alle algebraischen Gleichungen lösbar sind, +ist es manchmal notwendig, den Vektorraum zu erweitern um zum Beispiel +Eigenschaften der Matrix $A$ abzuleiten. + +\begin{definition} +Ein Vektor $v\in V$ heisst {\em Eigenvektor} von $A$ zum Eigenwert +$\lambda\in\Bbbk$, wenn $v\ne 0$ und $Av=\lambda v$ gilt. +\end{definition} + +Die Bedingung $v\ne 0$ dient dazu, pathologische Situationen auszuschliessen. +Für den Nullvektor gilt $A0=\lambda 0$ für jeden beliebigen Wert von +$\lambda\in\Bbbk$. +Würde man $v=0$ zulassen, wäre jede Zahl in $\Bbbk$ ein Eigenwert, +ein Eigenwert von $A$ wäre nichts besonderes. +Ausserdem wäre $0$ ein Eigenvektor zu jedem beliebigen Eigenwert. + +Eigenvektoren sind nicht eindeutig bestimmt, jedes von $0$ verschiedene +Vielfache von $v$ ist ebenfalls ein Eigenvektor. +Zu einem Eigenwert kann man also einen Eigenvektor jeweils mit +geeigneten Eigenschaften finden, zum Beispiel kann man für $\Bbbk = \mathbb{R}$ +Eigenvektoren auf Länge $1$ normieren. +Im Folgenden werden wir oft die abkürzend linear unabhängige Eigenvektoren +einfach als ``verschiedene'' Eigenvektoren bezeichnen. + +Wenn $v$ ein Eigenvektor von $A$ zum Eigenwert $\lambda$ ist, dann kann +man ihn mit zusätzlichen Vektoren $v_2,\dots,v_n$ zu einer Basis +$\mathcal{B}=\{v,v_2,\dots,v_n\}$ +von $V$ ergänzen. +Die Vektoren $v_k$ mit $k=2,\dots,n$ werden von $A$ natürlich auch +in den Vektorraum $V$ abgebildet, können also als Linearkombinationen +\[ +Av = a_{1k}v + a_{2k}v_2 + a_{3k}v_3 + \dots a_{nk}v_n +\] +dargestellt werden. +In der Basis $\mathcal{B}$ bekommt die Matrix $A$ daher die Form +\[ +A' += +\begin{pmatrix} +\lambda&a_{12}&a_{13}&\dots &a_{1n}\\ + 0 &a_{22}&a_{23}&\dots &a_{2n}\\ + 0 &a_{32}&a_{33}&\dots &a_{3n}\\ +\vdots &\vdots&\vdots&\ddots&\vdots\\ + 0 &a_{n2}&a_{n3}&\dots &a_{nn} +\end{pmatrix}. +\] +Bereits ein einzelner Eigenwert und ein zugehöriger Eigenvektor +ermöglichen uns also, die Matrix in eine etwas einfachere Form +zu bringen. + +\begin{definition} +Für $\lambda\in\Bbbk$ heisst +\[ +E_\lambda += +\{ v\;|\; Av=\lambda v\} +\] +der {\em Eigenraum} zum Eigenwert $\lambda$. +\index{Eigenraum}% +\end{definition} + +Der Eigenraum $E_\lambda$ ist ein Unterraum von $V$, denn wenn +$u,v\in E_\lambda$, dann ist +\[ +A(su+tv) += +sAu+tAv += +s\lambda u + t\lambda v += +\lambda(su+tv), +\] +also ist auch $su+tv\in E_\lambda$. +Der Fall $E_\lambda = \{0\}=0$ bedeutet natürlich, dass $\lambda$ gar kein +Eigenwert ist. + +\begin{satz} +Wenn $\dim E_\lambda=n$, dann ist $A=\lambda E$. +\end{satz} + +\begin{proof}[Beweis] +Da $V$ ein $n$-dimensionaler Vektoraum ist, ist $E_\lambda=V$. +Jeder Vektor $v\in V$ erfüllt also die Bedingung $Av=\lambda v$, +oder $A=\lambda E$. +\end{proof} + +Wenn man die Eigenräume von $A$ kennt, dann kann man auch die Eigenräume +von $A+\mu E$ berechnen. +Ein Vektor $v\in E_\lambda$ erfüllt +\[ +Av=\lambda v +\qquad\Rightarrow\qquad +(A+\mu)v = \lambda v + \mu v += +(\lambda+\mu)v, +\] +somit ist $v$ ein Eigenvektor von $A+\mu E$ zum Eigenwert $\lambda+\mu$. +Insbesondere können wir statt die Eigenvektoren von $A$ zum Eigenwert $\lambda$ +zu studieren, auch die Eigenvektoren zum Eigenwert $0$ von $A-\lambda E$ +untersuchen. + +% +% Invariante Räume +% +\subsection{Verallgemeinerte Eigenräume +\label{buch:subsection:verallgemeinerte-eigenraeume}} +Wenn $\lambda$ ein Eigenwert der Matrix $A$ ist, dann ist +ist $A-\lambda E$ injektiv und $\ker(A-\lambda E)\ne 0$. +Man kann daher die invarianten Unterräume $\mathcal{K}(A-\lambda E)$ +und $\mathcal{J}(A-\lambda E)$. + +\begin{beispiel} +Wir untersuchen die Matrix +\[ +A += +\begin{pmatrix} +1&1&-1&0\\ +0&3&-1&1\\ +0&2& 0&1\\ +0&0& 0&2 +\end{pmatrix} +\] +Man kann zeigen, dass $\lambda=1$ ein Eigenwert ist. +Wir suchen die Zerlegung des Vektorraums $\mathbb{R}^4$ in invariante +Unterräume $\mathcal{K}(A-E)$ und $\mathcal{J}(A-E)$. +Die Matrix $B=A-E$ ist +\[ +B += +\begin{pmatrix} +0&1&-1&0\\ +0&2&-1&1\\ +0&2&-1&1\\ +0&0& 0&2 +\end{pmatrix} +\] +und wir berechnen davon die Potenz +\[ +D=B^4=(A-E)^4 += +\begin{pmatrix} +0&0& 0&0\\ +0&2&-1&4\\ +0&2&-1&4\\ +0&0& 0&1 +\end{pmatrix}. +\] +Daraus kann man ablesen, dass das Bild $\operatorname{im}D$ +von $D$ die Basis +\[ +b_1 += +\begin{pmatrix} +0\\0\\0\\1 +\end{pmatrix} +, \qquad +b_2 += +\begin{pmatrix} +0\\1\\1\\0 +\end{pmatrix} +\] +hat. +Für den Kern von $D$ können wir zum Beispiel die Basisvektoren +\[ +b_3 += +\begin{pmatrix} +0\\1\\2\\0 +\end{pmatrix} +,\qquad +b_4 += +\begin{pmatrix} +1\\0\\0\\0 +\end{pmatrix} +\] +verwenden. + +Als erstes überprüfen wir, ob diese Basisvektoren tatsächlich invariante +Unterräume sind. +Für $\mathcal{J}(A-E) = \langle b_1,b_2\rangle$ +berechnen wir +\begin{align*} +(A-E)b_1 +&= +\begin{pmatrix} 0\\4\\4\\1 \end{pmatrix} += +4b_2+b_1, +\\ +(A-E)b_2 +&= +\begin{pmatrix} 0\\1\\1\\0 \end{pmatrix} += +b_2. +\end{align*} +Dies beweist, dass $\mathcal{J}(A-E)$ invariant ist. +In dieser Basis hat die von $A-E$ beschriebene lineare Abbildung +auf $\mathcal{J}(A-E)$ die Matrix +\[ +A_{\mathcal{J}(A-E)} += +\begin{pmatrix} +1&4\\ +0&1 +\end{pmatrix}. +\] + +Für den Kern $\mathcal{K}(A-E)$ findet man analog +\[ +\left. +\begin{aligned} +Ab_3 +&= +-b_4 +\\ +Ab_4 +&=0 +\end{aligned} +\quad\right\} +\qquad\Rightarrow\qquad +A_{\mathcal{K}(A-E)} += +\begin{pmatrix} +0&-1\\ +0& 0 +\end{pmatrix}. +\] +In der Basis $\mathcal{B}=\{b_1,b_2,b_3,b_4\}$ hat $A$ die Matrix +in Blockform +\[ +A' += +\left( +\begin{array}{cc|cr} +2&4& & \\ +0&2& & \\ +\hline + & &1&-1\\ + & &0& 1 +\end{array}\right), +\] +die Blöcke gehören zu den invarianten Unterräumen $\mathcal{K}(A-E)$ +und $\mathcal{K}(A-E)$. +Die aus $A-E$ gewonnen invarianten Unterräume sind offenbar auch invariante +Unterräume für $A$. +\end{beispiel} + +\begin{definition} +Ist $A$ eine Matrix mit Eigenwert $\lambda$, dann heisst der invariante +Unterraum +\[ +\mathcal{E}_{\lambda}(A) += +\mathcal{K}(A-\lambda E) +\] +der verallgemeinerte Eigenraum von $A$. +\end{definition} + +Es ist klar, dass +$E_\lambda(A)=\ker (A-\lambda E)\subset\mathcal{E}_{\lambda}(A)$. + +\subsection{Zerlegung in invariante Unterräume +\label{buch:subsection:zerlegung-in-invariante-unterraeume}} +Wenn $\lambda$ kein Eigenwert von $A$ ist, dann ist $A-\lambda E$ +injektiv und damit $\ker(A-\lambda E)=0$. +Es folgt, dass $\mathcal{K}^i(A-\lambda E)=0$ und daher auch +$\mathcal{J}^i(A-\lambda E)=V$. +Die Zerlegung in invariante Unterräume $\mathcal{J}(A-\lambda E)$ und +$\mathcal{K}(A-\lambda E)$ liefert in diesem Falle also nichts Neues. + +Für einen Eigenwert $\lambda_1$ von $A$ dagegen, erhalten wir die Zerlegung +\[ +V += +\mathcal{E}_{\lambda_1}(A) +\oplus +\underbrace{\mathcal{J}(A-\lambda_1 E)}_{\displaystyle =V_2}, +\] +wobei $\mathcal{E}_{\lambda_1}(A)\ne 0$ ist. +Die Matrix $A-\lambda_1 E$ ist eingeschränkt auf $\mathcal{E}_{\lambda_1}(A)$ +nilpotent. +Die Zerlegung in invariante Unterräume ist zwar mit Hilfe von $A-\lambda_1E$ +gewonnen worden, ist aber natürlich auch eine Zerlegung in invariante +Unterräume für $A$. +Wir können daher das Problem auf $V_2$ einschränken und nach einem weiteren +Eigenwert $\lambda_2$ von $A$ in $V_2$ suchen, was wieder eine Zerlegung +in invariante Unterräume liefert. +Indem wir so weiterarbeiten, bis wir den ganzen Raum ausgeschöpft haben, +können wir eine Zerlegung des ganzen Raumes $V$ finden, so dass $A$ auf +jedem einzelnen Summanden eine sehr einfach Form hat: + +\begin{satz} +\label{buch:eigenwerte:satz:zerlegung-in-eigenraeume} +Sei $V$ ein $\Bbbk$-Vektorraum und $f$ eine lineare Abbildung mit Matrix +$A$ derart, dass alle Eigenwerte $\lambda_1,\dots,\lambda_l$ von $A$ +in $\Bbbk$ sind. +Dann gibt es eine Zerlegung von $V$ in verallgemeinerte Eigenräume +\[ +V += +\mathcal{E}_{\lambda_1}(A) +\oplus +\mathcal{E}_{\lambda_2}(A) +\oplus +\dots +\oplus +\mathcal{E}_{\lambda_l}(A). +\] +Die Einschränkung von $A-\lambda_{i}E$ auf den Eigenraum +$\mathcal{E}_{\lambda_i}(A)$ ist nilpotent. +\end{satz} + +\subsection{Das charakteristische Polynom +\label{buch:subsection:das-charakteristische-polynom}} +Ein Eigenvektor von $A$ erfüllt $Av=\lambda v$ oder gleichbedeutend +$(A-\lambda E)v=0$, er ist also eine nichttriviale Lösung des homogenen +Gleichungssystems mit Koeffizientenmatrix $A-\lambda E$. +Ein Eigenwert ist also ein Skalar derart, dass $A-\lambda E$ +singulär ist. +Ob eine Matrix singulär ist, kann mit der Determinante festgestellt +werden. +Die Eigenwerte einer Matrix $A$ sind daher die Nullstellen +von $\det(A-\lambda E)$. + +\begin{definition} +Das {\em charakteristische Polynom} +\[ +\chi_A(x) += +\det (A-x E) += +\left| +\begin{matrix} +a_{11}-x & a_{12} & \dots & a_{1n} \\ +a_{21} & a_{22}-x & \dots & a_{2n} \\ +\vdots &\vdots &\ddots & \vdots \\ +a_{n1} & a_{n2} &\dots & a_{nn}-x +\end{matrix} +\right|. +\] +der Matrix $A$ ist ein Polynom vom Grad $n$ mit Koeffizienten in $\Bbbk$. +\end{definition} + +Findet man eine Nullstelle $\lambda\in\Bbbk$ von $\chi_A(x)$, +dann ist die Matrix $A-\lambda E\in M_n(\Bbbk)$ und mit dem Gauss-Algorithmus +kann man auch mindestens einen Vektor $v\in \Bbbk^n$ finden, +der $Av=\lambda v$ erfüllt. +Eine Matrix der Form wie in Satz~\ref{buch:eigenwerte:satz:jordanblock} +hat +\[ +\chi_A(x) += +\left| +\begin{matrix} +\lambda-x & 1 & & & & \\ + & \lambda-x & 1 & & & \\ + & & \lambda-x & & & \\ + & & &\ddots& & \\ + & & & &\lambda-x& 1 \\ + & & & & &\lambda-x +\end{matrix} +\right| += +(\lambda-x)^n += +(-1)^n (x-\lambda)^n +\] +als charakteristisches Polynom, welches $\lambda$ als einzige +Nullstelle hat. +Der Eigenraum der Matrix ist aber nur eindimensional, man kann also +im Allgemeinen für jede Nullstelle des charakteristischen Polynoms +nicht mehr als einen Eigenvektor (d.~h.~einen eindimensionalen Eigenraum) +erwarten. + +Wenn das charakteristische Polynom von $A$ keine Nullstellen in $\Bbbk$ hat, +dann kann es auch keine Eigenvektoren in $\Bbbk^n$ geben. +Gäbe es nämlich einen solchen Vektor, dann müsste eine der Komponenten +des Vektors von $0$ verschieden sein, wir nehmen an, dass es die Komponente +in Zeile $k$ ist. +Die Komponente $v_k$ kann man auf zwei Arten berechnen, einmal als +die $k$-Komponenten von $Av$ und einmal als $k$-Komponente von $\lambda v$: +\[ +a_{k1}v_1+\dots+a_{kn}v_n = \lambda v_k. +\] +Da $v_k\ne 0$ kann man nach $\lambda$ auflösen und erhält +\[ +\lambda = \frac{a_{k1}v_1+\dots + a_{kn}v_n}{v_k}. +\] +Alle Terme auf der rechten Seite sind in $\Bbbk$ und werden nur mit +Körperoperationen in $\Bbbk$ verknüpft, also muss auch $\lambda\in\Bbbk$ +sein, im Widerspruch zur Annahme. + +Durch Hinzufügen von geeigneten Elementen können wir immer zu einem +Körper $\Bbbk'$ übergehen, in dem das charakteristische Polynom +in Linearfaktoren zerfällt. +In diesem Körper kann man jetzt das homogene lineare Gleichungssystem +mit Koeffizientenmatrix $A-\lambda E$ lösen und damit mindestens +einen Eigenvektor $v$ für jeden Eigenwert finden. +Die Komponenten von $v$ liegen in $\Bbbk'$, und mindestens eine davon kann +nicht in $\Bbbk$ liegen. +Das bedeutet aber nicht, dass man diese Vektoren nicht für theoretische +Überlegungen über von $\Bbbk'$ unabhängige Eigenschaften der Matrix $A$ machen. +Das folgende Beispiel soll diese Idee illustrieren. + +\begin{beispiel} +Wir arbeiten in diesem Beispiel über dem Körper $\Bbbk=\mathbb{Q}$. +Die Matrix +\[ +A=\begin{pmatrix} +-4&7\\ +-2&4 +\end{pmatrix} +\in +M_2(\mathbb{Q}) +\] +hat das charakteristische Polynom +\[ +\chi_A(x) += +\left| +\begin{matrix} +-4-x&7\\-2&4-x +\end{matrix} +\right| += +(-4-x)(4-x)-7\cdot(-2) += +-16+x^2+14 += +x^2-2. +\] +Die Nullstellen sind $\pm\sqrt{2}$ und damit nicht in $\mathbb{Q}$. +Wir gehen daher über zum Körper $\mathbb{Q}(\!\sqrt{2})$, in dem +sich zwei Nullstellen $\lambda=\pm\sqrt{2}$ finden lassen. +Zu jedem Eigenwert lässt sich auch ein Eigenvektor +$v_{\pm\sqrt{2}}\in \mathbb{Q}(\!\sqrt{2})^2$, und unter Verwendung dieser +Basis bekommt die Matrix $A'=TAT^{-1}$ Diagonalform. +Die Transformationsmatrix $T$ enthält Matrixelemente aus +$\mathbb{Q}(\!\sqrt{2})$, die nicht in $\mathbb{Q}$ liegen. +Die Matrix $A$ lässt sich also über dem Körper $\mathbb{Q}(\!\sqrt{2})$ +diagonalisieren, nicht aber über dem Körper $\mathbb{Q}$. + +Da $A'$ Diagonalform hat mit $\pm\sqrt{2}$ auf der Diagonalen, folgt +$A^{\prime 2} = 2E$, die Matrix $A'$ erfüllt also die Gleichung +\begin{equation} +A^{\prime 2}-E= \chi_{A}(A) = 0. +\label{buch:grundlagen:eqn:cayley-hamilton-beispiel} +\end{equation} +Dies is ein Spezialfall des Satzes von Cayley-Hamilton~\ref{XXX} +welcher besagt, dass jede Matrix $A$ eine Nullstelle ihres +charakteristischen Polynoms ist: $\chi_A(A)=0$. +Die Gleichung~\ref{buch:grundlagen:eqn:cayley-hamilton-beispiel} +wurde zwar in $\mathbb{Q}(\!\sqrt{2})$ hergeleitet, aber in ihr kommen +keine Koeffizienten aus $\mathbb{Q}(\!\sqrt{2})$ vor, die man nicht auch +in $\mathbb{Q}$ berechnen könnte. +Sie gilt daher ganz allgemein. +\end{beispiel} + +\begin{beispiel} +Die Matrix +\[ +A=\begin{pmatrix} +32&-41\\ +24&-32 +\end{pmatrix} +\in +M_2(\mathbb{R}) +\] +über dem Körper $\Bbbk = \mathbb{R}$ +hat das charakteristische Polynom +\[ +\det(A-xE) += +\left| +\begin{matrix} +32-x&-41 \\ +25 &-32-x +\end{matrix} +\right| += +(32-x)(-32-x)-25\cdot(-41) += +x^2-32^2 + 1025 += +x^2+1. +\] +Die charakteristische Gleichung $\chi_A(x)=0$ hat in $\mathbb{R}$ +keine Lösungen, daher gehen wir zum Körper $\Bbbk'=\mathbb{C}$ über, +in dem dank dem Fundamentalsatz der Algebra alle Nullstellen zu finden +sind, sie sind $\pm i$. +In $\mathbb C$ lassen sich dann auch Eigenvektoren finden, man muss dazu die +folgenden linearen Gleichungssyteme lösen: +\begin{align*} +\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} +32-i&-41\\ +25 &-32-i +\end{tabular} +& +\rightarrow +\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} +1 & t\\ +0 & 0 +\end{tabular} +& +\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} +32+i&-41\\ +25 &-32+i +\end{tabular} +& +\rightarrow +\begin{tabular}{|>{$}c<{$}>{$}c<{$}|} +1 & \overline{t}\\ +0 & 0 +\end{tabular}, +\intertext{wobei wir $t=-41/(32-i) =-41(32+i)/1025= -1.28 -0.04i = (64-1)/50$ +abgekürzt haben. +Die zugehörigen Eigenvektoren sind} +v_i&=\begin{pmatrix}t\\i\end{pmatrix} +& +v_{-i}&=\begin{pmatrix}\overline{t}\\i\end{pmatrix} +\end{align*} +Mit den Vektoren $v_i$ und $v_{-i}$ als Basis kann die Matrix $A$ als +komplexe Matrix, also mit komplexem $T$ in die komplexe Diagonalmatrix +$A'=\operatorname{diag}(i,-i)$ transformiert werden. +Wieder kann man sofort ablesen, dass $A^{\prime2}+E=0$, und wieder kann +man schliessen, dass für die relle Matrix $A$ ebenfalls $\chi_A(A)=0$ +gelten muss. +\end{beispiel} + + + + diff --git a/buch/chapters/40-eigenwerte/images/Makefile b/buch/chapters/40-eigenwerte/images/Makefile new file mode 100644 index 0000000..db00dac --- /dev/null +++ b/buch/chapters/40-eigenwerte/images/Makefile @@ -0,0 +1,16 @@ +# +# Makefile +# +# (c) 2020 Prof Dr Andreas Müller, Hochschule Rappersil +# +all: sp.pdf nilpotent.pdf + +sp.pdf: sp.tex sppaths.tex + pdflatex sp.tex + +sppaths.tex: spbeispiel.m + octave spbeispiel.m + +nilpotent.pdf: nilpotent.tex + pdflatex nilpotent.tex + diff --git a/buch/chapters/40-eigenwerte/images/nilpotent.pdf b/buch/chapters/40-eigenwerte/images/nilpotent.pdf Binary files differnew file mode 100644 index 0000000..2106697 --- /dev/null +++ b/buch/chapters/40-eigenwerte/images/nilpotent.pdf diff --git a/buch/chapters/40-eigenwerte/images/nilpotent.tex b/buch/chapters/40-eigenwerte/images/nilpotent.tex new file mode 100644 index 0000000..1e6cd79 --- /dev/null +++ b/buch/chapters/40-eigenwerte/images/nilpotent.tex @@ -0,0 +1,76 @@ +% +% nilpotent.tex -- Produkt nilpotenter Matrizen +% +% (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} +\usepackage[many]{tcolorbox} + +\begin{document} +\def\skala{1} + +\newtcbox{\myboxA}{blank,boxsep=0mm, +clip upper,minipage, +width=31.0mm,height=17.0mm,nobeforeafter, +borderline={0.0pt}{0.0pt}{white}, +} + +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\cx{1.8} +\def\cy{1.2} + +\draw[line width=0.3pt] (-3,2.5) -- (6,2.5); + +\begin{scope}[xshift=-4cm] +\node at (1.5,1.53) {$\left(\myboxA{}\right)$}; +\fill[color=red!30] (0.5,3) -- (3,0.5) -- (3,3) -- cycle; +\draw (0,0) rectangle (3,3); +\draw (0,3) -- (3,0); +\node at ({\cx+0.5*0.5},{\cy+0.5*0.5}) [rotate=-45] {$k$}; +\draw[color=blue,line width=1.4pt] (0,2.5) -- (1.0,2.5); +\draw[color=red,line width=1.4pt] (1.0,2.5) -- (3,2.5); +\node at (1,1) {$B$}; +\node at (-0.3,2.5) [left] {$i$}; +\node at (1,2.5) [above right] {$i+k$}; +\end{scope} + +\node at (-0.5,1.5) {$\mathstrut\cdot\mathstrut$}; + +\begin{scope} +\node at (1.5,1.53) {$\left(\myboxA{}\right)$}; +\fill[color=red!30] (1.0,3) -- (3,1.0) -- (3,3) -- cycle; +\draw (0,0) rectangle (3,3); +\draw (0,3) -- (3,0); +\node at ({\cx+1.0*0.5},{\cy+1.0*0.5}) [rotate=-45] {$l$}; +\draw[color=red,line width=1.4pt] (2,3)--(2,2); +\draw[color=blue,line width=1.4pt] (2,2)--(2,0); +\node at (1,1) {$C$}; +\node at (2,3) [above] {$j$}; +\node at (2,2) [above right] {$j-l$}; +\end{scope} + +\node at (3.5,1.5) {$\mathstrut=\mathstrut$}; + +\begin{scope}[xshift=4cm] +\node at (1.5,1.53) {$\left(\myboxA{}\right)$}; +\fill[color=red!30] (1.5,3) -- (3,1.5) -- (3,3) -- cycle; +\draw (0,0) rectangle (3,3); +\draw (0,3) -- (3,0); +\node at ({\cx+1.5*0.5},{\cy+1.5*0.5}) [rotate=-45] {$k+l$}; +\fill[color=red!50!blue] (2,2.5) circle[radius=0.1]; +\draw[line width=0.3pt] (2,3) -- (2,2.5); +\node at (2,3) [above] {$j$}; +\node at (1,1) {$D$}; +\end{scope} + +\end{tikzpicture} + +\end{document} + diff --git a/buch/chapters/40-eigenwerte/images/sp.pdf b/buch/chapters/40-eigenwerte/images/sp.pdf Binary files differnew file mode 100644 index 0000000..d4de984 --- /dev/null +++ b/buch/chapters/40-eigenwerte/images/sp.pdf diff --git a/buch/chapters/40-eigenwerte/images/sp.tex b/buch/chapters/40-eigenwerte/images/sp.tex new file mode 100644 index 0000000..db70889 --- /dev/null +++ b/buch/chapters/40-eigenwerte/images/sp.tex @@ -0,0 +1,62 @@ +% +% sp.tex -- template for standalon tikz images +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{2.33} +\input{sppaths.tex} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\xdef\sx{1} +\xdef\sy{1} + +% add image content here +\begin{scope} +\begin{scope} +\clip (0,0) rectangle (3,2.1); +\richardson +\end{scope} +\draw[->] (-0.1,0) -- (3.15,0) coordinate[label={$\tau$}]; +\draw[->] (0,-0.1) -- (0,2.3) coordinate[label={right:$\varrho(\frac1\tau A-E)$}]; +\draw (1,{-0.1/\skala}) -- (1,{0.1/\skala}); +\draw (2,{-0.1/\skala}) -- (2,{0.1/\skala}); +\draw (3,{-0.1/\skala}) -- (3,{0.1/\skala}); +\node at (1,{-0.1/\skala}) [below] {1}; +\node at (2,{-0.1/\skala}) [below] {2}; +\node at (3,{-0.1/\skala}) [below] {3}; +\draw ({-0.1/\skala},1) -- ({0.1/\skala},1); +\draw ({-0.1/\skala},2) -- ({0.1/\skala},2); +\node at ({-0.1/\skala},1) [left] {1}; +\node at ({-0.1/\skala},2) [left] {2}; +\end{scope} + +\xdef\sy{1} + +\begin{scope}[xshift=3.5cm] +\begin{scope} +\clip (0,0) rectangle (2,2); +\sor +\end{scope} +\draw[->] (-0.1,0) -- (2.15,0) coordinate[label={$\omega$}]; +\draw[->] (0,-0.1) -- (0,2.3) coordinate[label={right:$\varrho(B_\omega^{-1}C_\omega)$}]; +\draw (1,{-0.1/\skala}) -- (1,{0.1/\skala}); +\draw (2,{-0.1/\skala}) -- (2,{0.1/\skala}); +\node at (1,{-0.1/\skala}) [below] {1}; +\node at (2,{-0.1/\skala}) [below] {2}; +\draw ({-0.1/\skala},1) -- ({0.1/\skala},1); +\draw ({-0.1/\skala},2) -- ({0.1/\skala},2); +\node at ({-0.1/\skala},1) [left] {1}; +\node at ({-0.1/\skala},2) [left] {2}; +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/40-eigenwerte/images/spbeispiel.m b/buch/chapters/40-eigenwerte/images/spbeispiel.m new file mode 100644 index 0000000..81160b9 --- /dev/null +++ b/buch/chapters/40-eigenwerte/images/spbeispiel.m @@ -0,0 +1,51 @@ +# +# spbeispiel.m +# +# (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +# +N = 30 +R = 0.05 * rand(N,N); +R = R + R'; +A = eye(N) + R; +L = tril(A,-1) +U = tril(A',-1)' +D = diag(diag(A)) + +A + +function r = spektralradius(A) + r = max(abs(eig(A))); +end + +gaussseidel = spektralradius(inverse(L+D)*U) +jacobi = spektralradius(inverse(D)*(L+U)) +richardson = spektralradius(A - eye(N)) + +fd = fopen("sppaths.tex", "w"); + +fprintf(fd, "\\def\\richardson{\n") +tau = 0.1; +r = spektralradius((1/tau) * A - eye(N)) +fprintf(fd, "\\draw[line width=1.4pt,color=red] ({\\sx*0.1},{\\sy*%.5f})", r); +for tau = (11:300) / 100 + r = spektralradius((1/tau) * A - eye(N)); + fprintf(fd, "\n--({\\sx*%.5f},{\\sy*%.5f})", tau, r); +end +fprintf(fd, "\n;}\n"); + +fprintf(fd, "\\def\\sor{\n"); +omega = 1/100 +B = (1/omega) * D + L; +C = (1-1/omega) * D + U; +r = spektralradius(inverse(B) * C) +fprintf(fd, "\\draw[line width=1.4pt,color=red] ({\\sx*%.3f},{\\sy*%.3f})", omega, r); +for omega = (2:200) / 100 + B = (1/omega) * D + L; + C = (1-1/omega) * D + U; + r = spektralradius(inverse(B) * C); + fprintf(fd, "\n--({\\sx*%.5f},{\\sy*%.5f})", omega, r); +end +fprintf(fd, ";\n}\n"); + +fclose(fd); + diff --git a/buch/chapters/40-eigenwerte/normalformen.tex b/buch/chapters/40-eigenwerte/normalformen.tex new file mode 100644 index 0000000..c21c403 --- /dev/null +++ b/buch/chapters/40-eigenwerte/normalformen.tex @@ -0,0 +1,338 @@ +% +% normalformen.tex -- Normalformen einer Matrix +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\section{Normalformen +\label{buch:section:normalformen}} +\rhead{Normalformen} +In den Beispielen im vorangegangenen wurde wiederholt der Trick +verwendet, den Koeffizientenkörper so zu erweitern, dass das +charakteristische Polynom in Linearfaktoren zerfällt und +für jeden Eigenwert Eigenvektoren gefunden werden können. +Diese Idee ermöglicht, eine Matrix in einer geeigneten Körpererweiterung +in eine besonders einfache Form zu bringen, das Problem dort zu lösen. +Anschliessend kann man sich darum kümmern in welchem Mass die gewonnenen +Resultate wieder in den ursprünglichen Körper transportiert werden können. + +\subsection{Diagonalform} +Sei $A$ eine beliebige Matrix mit Koeffizienten in $\Bbbk$ und sei $\Bbbk'$ +eine Körpererweiterung von $\Bbbk$ derart, dass das charakteristische +Polynom in Linearfaktoren +\[ +\chi_A(x) += +(x-\lambda_1)^{k_1}\cdot (x-\lambda_2)^{k_2}\cdot\dots\cdot (x-\lambda_m)^{k_m} +\] +mit Vielfachheiten $k_1$ bis $k_m$ zerfällt, $\lambda_i\in\Bbbk'$. +Zu jedem Eigenwert $\lambda_i$ gibt es sicher einen Eigenvektor, wir +wollen aber in diesem Abschnitt zusätzlich annehmen, dass es eine Basis +aus Eigenvektoren gibt. +In dieser Basis bekommt die Matrix Diagonalform, wobei auf der +Diagonalen nur Eigenwerte vorkommen können. +Man kann die Vektoren so anordnen, dass die Diagonalmatrix in Blöcke +der Form $\lambda_iE$ zerfällt +\[ +\def\temp#1{\multicolumn{1}{|c}{\raisebox{0pt}[12pt][7pt]{\phantom{x}$#1$}\phantom{x}}} +A' +=\left( +\begin{array}{cccc} +\cline{1-1} +\temp{\lambda_1E} &\multicolumn{1}{|c}{}& & \\ +\cline{1-2} + &\temp{\lambda_2E}&\multicolumn{1}{|c}{}& \\ +\cline{2-3} + & &\temp{\ddots}&\multicolumn{1}{|c}{}\\ +\cline{3-4} + & & &\multicolumn{1}{|c|}{\raisebox{0pt}[12pt][7pt]{\phantom{x}$\lambda_mE$}\phantom{x}}\\ +\cline{4-4} +\end{array} +\right) +\] +Über die Grösse eines solchen $\lambda_iE$-Blockes können wir zum jetzigen +Zeitpunkt noch keine Aussagen machen. + +Die Matrizen $A-\lambda_kE$ enthalten jeweils einen Block aus lauter +Nullen. +Das Produkt all dieser Matrizen ist daher +\[ +(A-\lambda_1E) +(A-\lambda_2E) +\cdots +(A-\lambda_mE) += +0. +\] +Über dem Körper $\Bbbk'$ gibt es also das Polynom +$m(x)=(x-\lambda_1)(x-\lambda_2)\cdots(x-\lambda_m)$ mit der Eigenschaft +$m(A)=0$. +Dies ist auch das Polynom von kleinstmöglichem Grad, denn für jeden +Eigenwert muss ein entsprechender Linearfaktor in so einem Polynom vorkommen. +Das Polynom $m(x)$ ist daher das Minimalpolynom der Matrix $A$. +Da jeder Faktor in $m(x)$ auch ein Faktor von $\chi_A(x)$ ist, +folgt wieder $\chi_A(A)=0$. +Ausserdem ist über dem Körper $\Bbbk'$ das Polynom $m(x)$ ein Teiler +des charakteristischen Polynoms $\chi_A(x)$. + +\subsection{Jordan-Normalform +\label{buch:subsection:jordan-normalform}} +Die Eigenwerte einer Matrix $A$ können als Nullstellen des +charakteristischen Polynoms gefunden werden. +Da der Körper $\Bbbk$ nicht unbedingt algebraische abgeschlossen ist, +zerfällt das charakteristische Polynom nicht unbedingt in Linearfaktoren, +die Nullstellen sind nicht unbedingt in $\Bbbk$. +Wir können aber immer zu einem grösseren Körper $\Bbbk'$ übergehen, +in dem das charakteristische Polynom in Linearfaktoren zerfällt. +Wir nehmen im Folgenden an, dass +\[ +\chi_A(x) += +(x-\lambda_1)^{k_1} +\cdot +(x-\lambda_2)^{k_2} +\cdot +\dots +\cdot +(x-\lambda_l)^{k_l} +\] +ist mit $\lambda_i\in\Bbbk'$. + +Nach Satz~\ref{buch:eigenwerte:satz:zerlegung-in-eigenraeume} liefern +die verallgemeinerten Eigenräume $V_i=\mathcal{E}_{\lambda_i}(A)$ eine +Zerlegung von $V$ in invariante Eigenräume +\[ +V=V_1\oplus V_2\oplus \dots\oplus V_l, +\] +derart, dass $A-\lambda_iE$ auf $V_i$ nilpotent ist. +Wählt man in jedem der Unterräume $V_i$ eine Basis, dann zerfällt die +Matrix $A$ in Blockmatrizen +\begin{equation} +\def\temp#1{\multicolumn{1}{|c}{\raisebox{0pt}[17pt][12pt]{\phantom{x}$#1\mathstrut$}\phantom{x}}} +A' +=\left( +\begin{array}{cccc} +\cline{1-1} +\temp{A_{1}} &\multicolumn{1}{|c}{}& & \\ +\cline{1-2} + &\temp{A_{2}}&\multicolumn{1}{|c}{}& \\ +\cline{2-3} + & &\temp{\ddots}&\multicolumn{1}{|c}{}\\ +\cline{3-4} + & & &\multicolumn{1}{|c|}{\raisebox{0pt}[17pt][12pt]{\phantom{x}$A_{l}$}\phantom{x}}\\ +\cline{4-4} +\end{array} +\right) +\label{buch:eigenwerte:eqn:allgnilpotent} +\end{equation} +wobei, $A_i$ Matrizen mit dem einzigen Eigenwert $\lambda_i$ sind. + +Nach Satz~\ref{buch:eigenwerte:satz:allgnilpotent} +kann man in den Unterräume die Basis zusätzlich so wählen, dass +die entstehenden Blöcke $A_i-\lambda_i E$ spezielle nilpotente Matrizen +aus lauter Null sind, die höchstens unmittelbar über der Diagonalen +Einträge $1$ haben kann. +Dies bedeutet, dass sich immer eine Basis so wählen lässt, dass die +Matrix $A_i$ zerfällt in sogenannte Jordan-Blöcke. + +\begin{definition} +Ein $m$-dimensionaler {\em Jordan-Block} ist eine $m\times m$-Matrix +\index{Jordan-Block}% +der Form +\[ +J_m(\lambda) += +\begin{pmatrix} +\lambda & 1 & & & & \\ + & \lambda & 1 & & & \\ + & & \lambda & & & \\ + & & & \ddots & & \\ + & & & & \lambda & 1 \\ + & & & & & \lambda +\end{pmatrix}. +\] +Eine {\em Jordan-Matrix} ist eine Blockmatrix Matrix +\[ +J += +\def\temp#1{\multicolumn{1}{|c}{\raisebox{0pt}[17pt][12pt]{\phantom{x}$#1\mathstrut$}\phantom{x}}} +\left( +\begin{array}{cccc} +\cline{1-1} +\temp{J_{m_1}(\lambda)} &\multicolumn{1}{|c}{}& & \\ +\cline{1-2} + &\temp{J_{m_2}(\lambda)}&\multicolumn{1}{|c}{}& \\ +\cline{2-3} + & &\temp{\ddots}&\multicolumn{1}{|c}{}\\ +\cline{3-4} + & & &\multicolumn{1}{|c|}{\raisebox{0pt}[17pt][12pt]{\phantom{x}$J_{m_p}(\lambda)$}\phantom{x}}\\ +\cline{4-4} +\end{array} +\right) +\] +mit $m_1+m_2+\dots+m_p=m$. +\index{Jordan-Matrix}% +\end{definition} + +Da Jordan-Blöcke obere Dreiecksmatrizen sind, ist +das charakteristische Polynom eines Jordan-Blocks oder einer Jordan-Matrix +besonders einfach zu berechnen. +Es gilt +\[ +\chi_{J_m(\lambda)}(x) += +\det (J_m(\lambda) - xE) += +(\lambda-x)^m +\] +für einen Jordan-Block $J_m(\lambda)$. +Für eine $m\times m$-Jordan-Matrix $J$ mit Blöcken $J_{m_1}(\lambda)$ +bis $J_{m_p}(\lambda)$ ist +\[ +\chi_{J(\lambda)}(x) += +\chi_{J_{m_1}(\lambda)}(x) +\chi_{J_{m_2}(\lambda)}(x) +\cdot +\dots +\cdot +\chi_{J_{m_p}(\lambda)}(x) += +(\lambda-x)^{m_1} +(\lambda-x)^{m_2} +\cdot\dots\cdot +(\lambda-x)^{m_p} += +(\lambda-x)^m. +\] + +\begin{satz} +\label{buch:eigenwerte:satz:jordannormalform} +Über einem Körper $\Bbbk'\supset\Bbbk$, über dem das charakteristische +Polynom $\chi_A(x)$ in Linearfaktoren zerfällt, lässt sich immer +eine Basis finden derart, dass die Matrix $A$ zu einer Blockmatrix wird, +die aus lauter Jordan-Matrizen besteht. +Die Dimension der Jordan-Matrix zum Eigenwert $\lambda_i$ ist die +Vielfachheit des Eigenwerts im charakteristischen Polynom. +\end{satz} + +\begin{proof}[Beweis] +Es ist nur noch die Aussage über die Dimension der Jordan-Blöcke zu +beweisen. +Die Jordan-Matrizen zum Eigenwert $\lambda_i$ werden mit $J_i$ +bezeichnet und sollen $m_i\times m_i$-Matrizen sein. +Das charakteristische Polynom jedes Jordan-Blocks ist dann +$\chi_{J_i}(x)=(\lambda_i-x)^{m_i}$. +Das charakteristische Polynom der Blockmatrix mit diesen Jordan-Matrizen +als Blöcken ist das Produkt +\[ +\chi_A(x) += +(\lambda_1-x)^{m_1} +(\lambda_2-x)^{m_2} +\cdots +(\lambda_p-x)^{m_p} +\] +mit $m_1+m_2+\dots+m_p$. +Die Blockgrösse $m_i$ ist also auch die Vielfachheit von $\lambda_i$ im +charakteristischen Polynom $\chi_A(x)$. +\end{proof} + + + +\begin{satz}[Cayley-Hamilton] +Ist $A$ eine $n\times n$-Matrix über dem Körper $\Bbbk$, dann gilt +$\chi_A(A)=0$. +\end{satz} + +\begin{proof}[Beweis] +Zunächst gehen wir über zu einem Körper $\Bbbk'\supset\Bbbk$, indem +das charakteristische Polynom $\chi_A(x)$ in Linearfaktoren +$\chi_A(x) += +(\lambda_1-x)^{m_1} +(\lambda_2-x)^{m_2} +\dots +(\lambda_p-x)^{m_p}$ +zerfällt. +Im Vektorraum $\Bbbk'$ kann man eine Basis finden, in der die Matrix +$A$ in Jordan-Matrizen $J_1,\dots,J_p$ zerfällt, wobei $J_i$ eine +$m_i\times m_i$-Matrix ist. +Für den Block mit der Nummer $i$ erhalten wir +$(J_i - \lambda_i E)^{m_i} = 0$. +Setzt man also den Block $J_i$ in das charakteristische Polynom +$\chi_A(x)$ ein, erhält man +\[ +\chi_A(J_i) += +(\lambda_1E - J_1)^{m_1} +\cdot +\ldots +\cdot +\underbrace{ +(\lambda_iE - J_i)^{m_i} +}_{\displaystyle=0} +\cdot +\ldots +\cdot +(\lambda_iE - J_p)^{m_p} += +0. +\] +Jeder einzelne Block $J_i$ wird also zu $0$, wenn man ihn in das +charakteristische Polynome $\chi_A(x)$ einsetzt. +Folglich gilt auch $\chi_A(A)=0$. + +Die Rechnung hat zwar im Körper $\Bbbk'$ stattgefunden, aber die Berechnung +$\chi_A(A)$ kann in $\Bbbk$ ausgeführt werden, also ist $\chi_A(A)=0$. +\end{proof} + +Aus dem Beweis kann man auch noch eine strengere Bedingung ableiten. +Auf jedem verallgemeinerten Eigenraum $\mathcal{E}_{\lambda_i}(A)$ +ist $A_i-\lambda_i$ nilpotent, es gibt also einen minimalen Exponenten +$q_i$ derart, dass $(A_i-\lambda_iE)^{q_i}=0$ ist. +Wählt man eine Basis in jedem verallgemeinerten Eigenraum derart, +dass $A_i$ eine Jordan-Matrix ist, kann man wieder zeigen, dass +für das Polynom +\[ +m_A(x) += +(x-\lambda_1x)^{q_1} +(x-\lambda_2x)^{q_2} +\cdot +\ldots +\cdot +(x-\lambda_px)^{q_p} +\] +gilt $m_A(A)=0$. +$m_A(x)$ ist das {\em Minimalpolynom} der Matrix $A$. +\index{Minimalpolynom einer Matrix}% + +\begin{satz}[Minimalpolynom] +Über dem Körper $\Bbbk'\subset\Bbbk$, über dem das charakteristische +Polynom $\chi_A(x)$ in Linearfaktoren zerfällt, ist das Minimalpolynom +von $A$ das Polynom +\[ +m(x) += +(x-\lambda_1)^{q_1} +(x-\lambda_2)^{q_2} +\cdots +\ldots +\cdots +(x-\lambda_p)^{q_p} +\] +wobei $q_i$ der kleinste Index ist, für den die $q_i$-te Potenz +derEinschränkung von $A-\lambda_i E$ auf den verallgemeinerten Eigenraum +$\mathcal{E}_{\lambda_i}(A)$ verschwindet. +Es ist das Polynom geringsten Grades über $\Bbbk'$, welches $m(A)=0$ erfüllt. +\end{satz} + + +\subsection{Reelle Normalform +\label{buch:subsection:reelle-normalform}} + +\subsection{Obere Hessenberg-Form +\label{buch:subsection:obere-hessenberg-form}} + + + diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex index 67147f2..bdc725f 100644 --- a/buch/chapters/40-eigenwerte/spektralradius.tex +++ b/buch/chapters/40-eigenwerte/spektralradius.tex @@ -3,9 +3,802 @@ % % (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} +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)\in\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}% +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} + +\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} = 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} + +\begin{beispiel} +Wir berechnen die Norm eines Jordan-Blocks. + +\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) += +\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 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} diff --git a/buch/chapters/40-eigenwerte/uebungsaufgaben/4001.tex b/buch/chapters/40-eigenwerte/uebungsaufgaben/4001.tex new file mode 100644 index 0000000..2fab61a --- /dev/null +++ b/buch/chapters/40-eigenwerte/uebungsaufgaben/4001.tex @@ -0,0 +1,76 @@ +Verwenden Sie die Matrixdarstellung komplexer Zahlen, um $i^i$ zu +berechnen. + +\begin{hinweis} +Verwenden Sie die eulersche Formel um $\log J$ zu bestimmen. +\end{hinweis} + +\begin{loesung} +Wir berechnen $J^J$ mit Hilfe des Logarithmus als +$J^J = \exp(J\log J)$. +Zunächst erinnern wir an die Eulersche Formel +\[ +\exp tJ += +\sum_{k=0}^\infty \frac{t^k J^k}{k!} += +\sum_{i=0}^\infty \frac{t^{2i}(-1)^i}{(2i)!}\cdot E ++ +\sum_{i=0}^\infty \frac{t^{2i+1}(-1)^i}{(2i+1)!}\cdot J += +\cos t\cdot E ++ +\sin t\cdot J. +\] +Daraus liest man ab, dass +\[ +\log \begin{pmatrix} +\cos t&-\sin t\\ +\sin t& \cos t +\end{pmatrix} += +tJ +\] +gilt. +Für die Matrix $J$ heisst das +\begin{equation} +J = \begin{pmatrix} +0&-1\\1&0 +\end{pmatrix} += +\begin{pmatrix} +\cos\frac{\pi}2&-\sin\frac{\pi}2\\ +\sin\frac{\pi}2& \cos\frac{\pi}2 +\end{pmatrix} +\qquad\Rightarrow\qquad +\log J = \frac{\pi}2 J. +\label{4001:logvalue} +\end{equation} +Als nächstes müssen wir $J\log J$ berechnen. +Aus \eqref{4001:logvalue} folgt +\[ +J\log J = J\cdot \frac{\pi}2J = - \frac{\pi}2 \cdot E. +\] +Darauf ist die Exponentialreihe auszuwerten, also +\[ +J^J += +\exp (J\log J) += +\exp(-\frac{\pi}2 E) += +\exp +\begin{pmatrix} +-\frac{\pi}2&0\\ +0&-\frac{\pi}2 +\end{pmatrix} += +\begin{pmatrix} +e^{-\frac{\pi}2}&0\\ +0&e^{-\frac{\pi}2} +\end{pmatrix} += +e^{-\frac{\pi}2} E. +\] +Als komplexe Zahlen ausgedrückt folgt also $i^i = e^{-\frac{\pi}2}$. +\end{loesung} diff --git a/buch/chapters/40-eigenwerte/uebungsaufgaben/4002.tex b/buch/chapters/40-eigenwerte/uebungsaufgaben/4002.tex new file mode 100644 index 0000000..6c0223e --- /dev/null +++ b/buch/chapters/40-eigenwerte/uebungsaufgaben/4002.tex @@ -0,0 +1,23 @@ +Seien $z$ und $w$ komplexe Zahlen derart, dass $z=e^w$, d.~h.~$w$ ist +ein Wert des Logarithmus von $z$. +Zeigen Sie, dass die Zahlen $w+2\pi ik$ für $k\in\mathbb Z$ ebenfalls +Logarithmen von $z$ sind. +Dies zeigt, dass eine komlexe Zahl unendlich viele verschiedene +Logarithmen haben kann, die Logarithmusfunktion ist im Komplexen +nicht eindeutig. + +\begin{loesung} +Aus der Eulerschen Formel folgt +\begin{align*} +e^{w+2\pi ik} +&= +e^w\cdot e^{2\pi ik} += +e^w (\underbrace{\cos 2\pi k}_{\displaystyle=1} + i \underbrace{\sin 2\pi k}_{\displaystyle = 0}) += +e^w += +z. +\qedhere +\end{align*} +\end{loesung} diff --git a/buch/chapters/40-eigenwerte/uebungsaufgaben/4003.m b/buch/chapters/40-eigenwerte/uebungsaufgaben/4003.m new file mode 100644 index 0000000..e6e94db --- /dev/null +++ b/buch/chapters/40-eigenwerte/uebungsaufgaben/4003.m @@ -0,0 +1,66 @@ +# +# 4003.m +# +# (c) 2020 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# + +A = [ + -13, 5, -29, 29; + -27, 11, -51, 51; + -3, 1, -2, 5; + -6, 2, -10, 13 +]; + +eig(A) + + +lambda = 2 +B = A - lambda*eye(4) +rref(B) + +D = B*B*B*B + +lambda = 3 +B = A - lambda*eye(4) +rref(B) + +D = B*B*B*B + +b1 = [0;0;1;1] +b2 = [1;0;0;0] +b3 = [0;1;0;0] +b4 = [0;0;1;2] + +T = zeros(4,4); +T(:,1) = b1; +T(:,2) = b2; +T(:,3) = b3; +T(:,4) = b4; + +AA = inverse(T)*A*T + +A1 = AA(2:4,2:4) +B1 = A1 - 2*eye(3) +B1 * B1 +B1 * B1 * B1 + +c30 = [ 0; 1; 3; 1 ] + +c3 = T*c30 + +lambda=2 +B=A-lambda*eye(4) +c2=B*c3 +c1=B*c2 + +T = zeros(4,4); +T(:,1) = [0;0;1;1] +T(:,2) = c1; +T(:,3) = c2; +T(:,4) = c3 +det(T) +inverse(T) +det(T)*inverse(T) + +inverse(T)*A*T + diff --git a/buch/chapters/40-eigenwerte/uebungsaufgaben/4003.maxima b/buch/chapters/40-eigenwerte/uebungsaufgaben/4003.maxima new file mode 100644 index 0000000..bbbc045 --- /dev/null +++ b/buch/chapters/40-eigenwerte/uebungsaufgaben/4003.maxima @@ -0,0 +1,16 @@ +/* + * 4003.maxima - algebraische Lösung von Aufgabe 4003 + * + * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule + */ + +A: matrix( + [ -13, 5, -29, 29 ], + [ -27, 11, -51, 51 ], + [ -3, 1, -2, 5 ], + [ -6, 2, -10, 13 ]); + +p: expand(charpoly(A,x)); +tex(p); +factor(p); + diff --git a/buch/chapters/40-eigenwerte/uebungsaufgaben/4003.tex b/buch/chapters/40-eigenwerte/uebungsaufgaben/4003.tex new file mode 100644 index 0000000..3cd9959 --- /dev/null +++ b/buch/chapters/40-eigenwerte/uebungsaufgaben/4003.tex @@ -0,0 +1,241 @@ +Finden Sie eine Basis von $\mathbb{Q}^4$ derart, dass die Matrix $A$ +\[ +A += +\begin{pmatrix} +-13& 5& -29& 29\\ +-27& 11& -51& 51\\ + -3& 1& -2& 5\\ + -6& 2& -10& 13 +\end{pmatrix} +\] +Jordansche Normalform hat. + +\begin{loesung} +Zunächst muss man die Eigenwerte finden. +Dazu kann man das charakteristische Polynom berechnen, man findet nach +einiger Rechnung oder mit Hilfe einer Software für symbolische Rechnung: +\[ +\chi_A(\lambda) += +x^4-9x^3+30x^2-44x+24 += +(x-3)^3(x-2), +\] +Eigenwerte sind also $\lambda=3$ und $\lambda=2$. + +Der Eigenwert $\lambda=2$ ist ein einfacher Eigenwert, der zugehörige +Eigenraum ist daher eindimensional. +Ein Eigenvektor kann mit Hilfe des linearen Gleichungssystems +\begin{align*} +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +\hline +-13-\lambda& 5 &-29 &29 \\ +-27 &11-\lambda&-51 &51 \\ + -3 & 1 & -2-\lambda& 5 \\ + -6 & 2 &-10 &13-\lambda\\ +\hline +\end{tabular} +&\rightarrow +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +\hline + -16& 5& -29& 29\\ + -27& 8& -51& 51\\ + -3& 1& -5& 5\\ + -6& 2& -10& 10\\ +\hline +\end{tabular} +\to +\begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}>{$}c<{$}|} +\hline +1&0&0& 0\\ +0&1&0& 0\\ +0&0&1&-1\\ +0&0&0& 0\\ +\hline +\end{tabular} +\end{align*} +gefunden werden. +Daraus liest man den Eigenvektor +\[ +b_1 += +\begin{pmatrix} 0\\0\\1\\1\end{pmatrix}, +\qquad +Ab_1 = +\begin{pmatrix} +-13& 5& -29& 29\\ +-27& 11& -51& 51\\ + -3& 1& -2& 5\\ + -6& 2& -10& 13 +\end{pmatrix} +\begin{pmatrix} 0\\0\\1\\1\end{pmatrix} += +\begin{pmatrix} +0\\0\\3\\3 +\end{pmatrix} += +3b_1 +\] +ab. +Diesen Vektor können wir auch finden, indem wir $\mathcal{J}(A-eE)$ +bestimmen. +Die vierte Potenz von $A-2E$ ist +\begin{equation} +(A-2E)^4 += +\begin{pmatrix} + 0& 0& 0& 0\\ + 0& 0& 0& 0\\ + 0& 0& 2& -1\\ + 0& 0& 2& -1 +\end{pmatrix}, +\label{4003:potenz} +\end{equation} +der zugehörige Bildraum ist wieder aufgespannt von $b_1$. + +Aus \eqref{4003:potenz} kann man aber auch eine Basis +\[ +b_2 += +\begin{pmatrix}1\\0\\0\\0\end{pmatrix} +,\qquad +b_3 += +\begin{pmatrix}0\\1\\0\\0\end{pmatrix} +,\qquad +b_4 += +\begin{pmatrix}0\\0\\1\\2\end{pmatrix} +\] +für den Kern $\mathcal{K}(A-2E)$ ablesen. +Da $\lambda=2$ der einzige andere Eigenwert ist, muss $\mathcal{K}(A-2E) += \mathcal{J}(A-3E)$ sein. +Dies lässt sich überprüfen, indem wir die vierte Potenz von $A-2E$ +berechnen, sie ist +\[ +(A-2E)^4 += +\begin{pmatrix} + 79& -26& 152& -152\\ + 162& -53& 312& -312\\ + 12& -4& 23& -23\\ + 24& -8& 46& -46\\ +\end{pmatrix}. +\] +Die Spaltenvektoren lassen sich alle durch die Vektoren $b_2$, $b_3$ +und $b_4$ ausdrücken, also ist $\mathcal{J}(A-2E)=\langle b_2,b_3,b_4\rangle$. + +Indem die Vektoren $b_i$ als Spalten in eine Matrix $T$ schreibt, kann man +jetzt berechnen, wie die Matrix der linearen Abbildung in dieser neuen +Basis aussieht, es ist +\[ +A'=T^{-1}AT +\left( +\begin{array}{r|rrr} + 3& 0& 0& 0\\ +\hline + 0& -13& 5& 29\\ + 0& -27& 11& 51\\ + 0& -3& 1& 8 +\end{array} +\right), +\] +wir haben also tatsächlich die versprochene Blockstruktur. + +Der $3\times 3$-Block +\[ +A_1 += +\begin{pmatrix} + -13& 5& 29\\ + -27& 11& 51\\ + -3& 1& 8 +\end{pmatrix} +\] +in der rechten unteren Ecke hat den dreifachen Eigenwert $2$, +und die Potenzen von $A_1-2E$ sind +\[ +A_1-2E +\begin{pmatrix} + -15 & 5& 29\\ + -27 & 9& 51\\ + -3 & 1& 6 +\end{pmatrix} +,\qquad +(A_1-2E)^2 += +\begin{pmatrix} + 3 & -1 & -6\\ + 9 & -3 &-18\\ + 0 & 0 & 0\\ +\end{pmatrix} +,\qquad +(A_1-2E)^3=0. +\] +Für die Jordan-Normalform brauchen wir einen von $0$ verschiedenen +Vektor im Kern von $(A_1-2E)^2$, zum Beispiel den Vektor mit den +Komponenten $1,3,1$. +Man beachte aber, dass diese Komponenten jetzt in der neuen Basis +$b_2,\dots,b_4$ zu verstehen sind, d.~h.~der Vektor, den wir suchen, ist +\[ +c_3 += +b_1+ 3b_2+b_3 += +\begin{pmatrix}1\\3\\1\\2\end{pmatrix}. +\] +Jetzt berechnen wir die Bilder von $c_3$ unter $A-2E$: +\[ +c_2 += +\begin{pmatrix} +29\\51Ò\\6\\12 +\end{pmatrix} +,\qquad +c_1 += +\begin{pmatrix} +-6\\-18\\0\\0 +\end{pmatrix}. +\] +Die Basis $b_1,c_1,c_2,c_3$ ist also eine Basis, in der die Matrix $A$ +Jordansche Normalform annimmt. + +Die Umrechnung der Matrix $A$ in die Basis $\{b_1,c_1,c_2,c_3\}$ kann +mit der Matrix +\[ +T_1 += +\begin{pmatrix} + 0& -6& 29& 1\\ + 0& -18& 51& 3\\ + 1& 0& 6& 1\\ + 1& 0& 12& 2\\ +\end{pmatrix}, +\qquad +T_1^{-1} += +\frac{1}{216} +\begin{pmatrix} + 0& 0& 432& -216\\ + 33& -23& -36& 36\\ + 18& -6& 0& 0\\ + -108& 36& -216& 216 +\end{pmatrix} +\] +erfolgen und ergibt die Jordansche Normalform +\[ +A' += +\begin{pmatrix} +3&0&0&0\\ +0&2&1&0\\ +0&0&2&1\\ +0&0&0&2 +\end{pmatrix} +\] +wie erwartet. +\end{loesung} + + |