diff options
Diffstat (limited to 'buch')
| -rw-r--r-- | buch/chapters/10-vektorenmatrizen/linear.tex | 170 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/beispiele/Makefile | 8 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/beispiele/i.m | 65 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/chapter.tex | 1 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/grundlagen.tex | 735 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/images/Makefile | 13 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/images/sp.pdf | bin | 0 -> 24049 bytes | |||
| -rw-r--r-- | buch/chapters/40-eigenwerte/images/sp.tex | 62 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/images/spbeispiel.m | 51 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/normalformen.tex | 263 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/spektralradius.tex | 428 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/uebungsaufgaben/4003.m | 66 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/uebungsaufgaben/4003.maxima | 16 | ||||
| -rw-r--r-- | buch/chapters/40-eigenwerte/uebungsaufgaben/4003.tex | 241 | ||||
| -rw-r--r-- | buch/common/packages.tex | 1 |
15 files changed, 1913 insertions, 207 deletions
diff --git a/buch/chapters/10-vektorenmatrizen/linear.tex b/buch/chapters/10-vektorenmatrizen/linear.tex index 461bf9f..4e3454d 100644 --- a/buch/chapters/10-vektorenmatrizen/linear.tex +++ b/buch/chapters/10-vektorenmatrizen/linear.tex @@ -857,173 +857,3 @@ Das Bild der Matrix $A$ ist der Unterraum \] von $\Bbbk^m$, aufgespannt von den Spaltenvektoren $a_i$ von $A$. -\subsubsection{Kern und Bild von Matrixpotenzen} -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:vektoren-und-matrizen: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\} -\subset -\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:vektoren-und-matrizen:eqn:Kkchain} -\end{equation} -Neben diesen offensichtlichen Resultaten kann man aber noch mehr -sagen. -Es ist klar, dass in beiden Ketten -\label{buch:vektoren-und-matrizen:eqn:Jkchain} -und -\label{buch:vektoren-und-matrizen: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:vektoren-und-matrizen: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:vektoren-und-matrizen: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:vektoren-und-matrizen: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} - -\subsubsection{Nilpotente Matrizen} - - - - - - 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/chapter.tex b/buch/chapters/40-eigenwerte/chapter.tex index 5f237a4..e097b8d 100644 --- a/buch/chapters/40-eigenwerte/chapter.tex +++ b/buch/chapters/40-eigenwerte/chapter.tex @@ -42,5 +42,6 @@ Dies wird in Abschnitt~\ref{buch:section:spektraltheorie} beschrieben. \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 index 471c7fb..5c8f169 100644 --- a/buch/chapters/40-eigenwerte/grundlagen.tex +++ b/buch/chapters/40-eigenwerte/grundlagen.tex @@ -17,10 +17,501 @@ 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 +\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\} +\subset +\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 aine 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} + +\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] + +\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{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 @@ -132,42 +623,218 @@ 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. -\begin{satz} -\label{buch:eigenwerte:satz:jordanblock} -Wenn $\dim E_\lambda=1$ ist, dann gibt es eine Basis von $V$ derart, dass -$A$ in dieser Matrix die Form -\begin{equation} -A' +% +% 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} - \lambda & 1 & & & & \\ - & \lambda & 1 & & & \\ - & & \lambda & & & \\ - & & & \ddots & & \\ - & & & & \lambda & 1 \\ - & & & & & \lambda +1&1&-1&0\\ +0&3&-1&1\\ +0&2& 0&1\\ +0&0& 0&2 \end{pmatrix} -\label{buch:eigenwerte:eqn:jordanblock} -\end{equation} +\] +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. -\end{satz} +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. -\begin{proof}[Beweis] -Entsprechend der Bemerkung vor dem Satz können wir uns auf die Betrachtung -der Matrix $B=A-\lambda E$ konzentrieren, deren Eigenraum zum Eigenwert $0$ -$1$-dimensional ist. -Es gibt also einen Vektor $v_1\ne 0$ mit $Bv_1=0$. -Der Vektor $v_1$ spannt den Eigenraum auf: $E_0 = \langle v_1\rangle$. - -Wir konstruieren jetzt rekursiv eine Folge $v_2,\dots,v_n$ von Vektoren -mit folgenden Eigenschaften. -Zunächst soll $v_k=Bv_{k+1}$ für $k=1,\dots,n-1$ sein. -Ausserdem soll $v_{k+1}$ in jedem Schritt linear unabhängig von den -Vektoren $v_1,\dots,v_{k-1}$ gewählt werden. -Wenn diese Konstruktion gelingt, dann ist $\mathcal{B}=\{v_1,\dots,v_n\}$ -eine Basis von $V$ und die Matrix von $B$ in dieser Basis ist -$A'$ wie in \eqref{buch:eigenwerte:eqn:jordanblock}. -\end{proof} +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 und man kann ablesen, +dass in dieser Basis, 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)$ +\[ +\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}} @@ -249,7 +916,7 @@ 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 +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 diff --git a/buch/chapters/40-eigenwerte/images/Makefile b/buch/chapters/40-eigenwerte/images/Makefile new file mode 100644 index 0000000..5915d30 --- /dev/null +++ b/buch/chapters/40-eigenwerte/images/Makefile @@ -0,0 +1,13 @@ +# +# Makefile +# +# (c) 2020 Prof Dr Andreas Müller, Hochschule Rappersil +# +all: sp.pdf + +sp.pdf: sp.tex sppaths.tex + pdflatex sp.tex + +sppaths.tex: spbeispiel.m + octave spbeispiel.m + 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..5346e06 --- /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 index f695435..536fa7d 100644 --- a/buch/chapters/40-eigenwerte/normalformen.tex +++ b/buch/chapters/40-eigenwerte/normalformen.tex @@ -74,8 +74,265 @@ 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} +\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 \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}} + -\subsection{Reelle Normalform} -\subsection{Obere Hessenberg-Form} 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} + 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} + + diff --git a/buch/common/packages.tex b/buch/common/packages.tex index 65e5879..7d4ec7c 100644 --- a/buch/common/packages.tex +++ b/buch/common/packages.tex @@ -64,6 +64,7 @@ \usepackage{algorithm} \usepackage{gensymb} \usepackage{mathtools} +\usepackage[many]{tcolorbox} % import the listing styles \input{common/lststyles.tex} |