From 812a80acf52275699afb285db46aa76be03006c2 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 18 Jan 2021 21:01:26 +0100 Subject: add more stuff about spectral radius --- buch/chapters/40-eigenwerte/spektralradius.tex | 428 +++++++++++++++++++++++++ 1 file changed, 428 insertions(+) (limited to 'buch/chapters/40-eigenwerte/spektralradius.tex') diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex index 67147f2..be986f1 100644 --- a/buch/chapters/40-eigenwerte/spektralradius.tex +++ b/buch/chapters/40-eigenwerte/spektralradius.tex @@ -9,3 +9,431 @@ % Konvergenz von Matrixreihen % Konditionszahl +\begin{definition} +\index{Norm}% +Die {\em Norm} einer Matrix $M$ ist +\[ +\|M\| += +\max\{|Mx|\,|\, x\in\mathbb R^n\wedge |x|=1\}. +\] +Für einen Vektor $x\in\mathbb R^n$ gilt $|Mx| \le \|M\|\cdot |x|$. +\end{definition} + +Die Bedingung \eqref{buch:gs:fehler} bedeutet jedoch nicht, +dass die Norm der Ableitung $<1$ sein muss, es genügt, wenn +genügend hohe Potenzen der Ableitung eine Norm $<1$ haben. +\index{Ableitung}% + +\begin{beispiel} +Die Matrix +\[ +M=\begin{pmatrix} +0&2\\ +\frac13&0 +\end{pmatrix} +\] +hat Norm +\[ +\|M\| += +\max_{|x|=1} |Mx| += +\max_{t\in\mathbb R} \sqrt{2^2\cos^2 t +\frac1{3^2}\sin^2t} \ge 2. +\] +Da aber +\[ +M^2 = \begin{pmatrix} +\frac{2}{3}&0\\ +0&\frac{2}{3} +\end{pmatrix} +\qquad\Rightarrow\qquad \|M^2\|=\frac23 +\] +ist, wird eine Iteration mit Ableitungsmatrix $M$ trotzdem +konvergieren, weil der Fehler nach jedem zweiten Schritt um den +Faktor $\frac23$ kleiner geworden ist. +\end{beispiel} + +Dies führt uns auf die Grösse +\begin{equation} +\pi(M) += +\limsup_{n\to\infty} \|M^n\|^\frac1n. +\label{buch:eqn:gelfand-grenzwert} +\end{equation} +Ist $\pi(M) > 1$, dann gibt es Anfangsvektoren $v$ für die Iteration, +für die $M^kv$ über alle Grenzen wächst. +Ist $\pi(M) < 1$, dann wird jeder Anfangsvektor $v$ zu einer Iterationsfolge +$M^kv$ führen, die gegen $0$ konvergiert. +Die Kennzahl $\pi(M)$ erlaubt also zu entscheiden, ob ein +Iterationsverfahren konvergent ist. +\index{Konvergenzbedingung}% + +Die Berechnung von $\pi(M)$ als Grenzwert ist sehr unhandlich. +Viel einfacher ist der Begriff des Spektralradius. +\index{Spektralradius}% + +\begin{definition} +\label{buch:definition:spektralradius} +Der {\em Spektralradius} der Matrix $M$ ist der Betrag des betragsgrössten +Eigenwertes. +\end{definition} + +% +% Gelfand-Radius und Eigenwerte +% +\subsection{Gelfand-Radius und Eigenwerte +\label{buch:subsection:spektralradius}} +In Abschnitt~\ref{buch:subsection:konvergenzbedingung} +ist der Gelfand-Radius mit Hilfe eines Grenzwertes definiert worden. +\index{Gelfand-Radius}% +Nur dieser Grenzwert ist in der Lage, über die Konvergenz eines +Iterationsverfahrens Auskunft zu geben. +Der Grenzwert ist aber sehr mühsam zu berechnen. +\index{Grenzwert}% +Es wurde angedeutet, dass der Gelfand-Radius mit dem Spektralradius +übereinstimmt, dem Betrag des des betragsgrössten Eigenwertes. +Dies hat uns ein vergleichsweise einfach auszuwertendes Konvergenzkriterium +geliefert. +\index{Konvergenzkriterium}% +In diesem Abschnitt soll diese Identität zunächst an Spezialfällen +und später ganz allgemein gezeigt werden. + +\subsubsection{Spezialfall: Diagonalisierbare Matrizen} +Ist eine Matrix $A$ diagonalisierbar, dann kann Sie durch eine Wahl +einer geeigneten Basis in Diagonalform +\index{diagonalisierbar}% +\index{Diagonalform}% +\[ +A' += +\begin{pmatrix} +\lambda_1& 0&\dots &0\\ +0 &\lambda_2&\dots &0\\ +\vdots & &\ddots&\vdots\\ +0 & 0&\dots &\lambda_n +\end{pmatrix} +\] +gebracht werden, wobei die Eigenwerte $\lambda_i$ möglicherweise auch +komplex sein können. +\index{komplex}% +Die Bezeichnungen sollen so gewählt sein, dass $\lambda_1$ der +betragsgrösste Eigenwert ist, dass also +\[ +|\lambda_1| \ge |\lambda_2| \ge \dots \ge |\lambda_n|. +\] +Wir nehmen für die folgende, einführende Diskussion ausserdem an, dass +sogar $|\lambda_1|>|\lambda_2|$ gilt. + +Unter den genannten Voraussetzungen kann man jetzt den Gelfand-Radius +von $A$ berechnen. +Dazu muss man $|A^nv|$ für einen beliebigen Vektor $v$ und für +beliebiges $n$ berechnen. +Der Vektor $v$ lässt sich in der Eigenbasis von $A$ zerlegen, also +als Summe +\index{Eigenbasis}% +\[ +v = v_1+v_2+\dots+v_n +\] +schreiben, wobei $v_i$ Eigenvektoren zum Eigenwert $\lambda_i$ sind oder +Nullvektoren. +Die Anwendung von $A^k$ ergibt dann +\[ +A^k v += +A^k v_1 + A^k v_2 + \dots + A^k v_n += +\lambda_1^k v_1 + \lambda_2^k v_2 + \dots + \lambda_n^k v_n. +\] +Für den Grenzwert braucht man die Norm von $A^kv$, also +\begin{align} +|A^kv| +&= |\lambda_1^k v_1 + \lambda_2^k v_2 + \dots + \lambda_3 v_3| +\notag +\\ +\Rightarrow\qquad +\frac{|A^kv|}{\lambda_1^k} +&= +\biggl| +v_1 + +\biggl(\frac{\lambda_2}{\lambda_1}\biggr)^k v_2 ++ +\dots ++ +\biggl(\frac{\lambda_n}{\lambda_1}\biggr)^k v_n +\biggr|. +\label{buch:spektralradius:eqn:eigenwerte} +\end{align} +Da alle Quotienten $|\lambda_i/\lambda_1|<1$ sind für $i\ge 2$, +konvergieren alle Terme auf der rechten Seite von +\eqref{buch:spektralradius:eqn:eigenwerte} +ausser dem ersten gegen $0$. +Folglich ist +\[ +\lim_{k\to\infty} \frac{|A^kv|}{|\lambda_1|^k} += +|v_1| +\qquad\Rightarrow\qquad +\lim_{k\to\infty} \frac{|A^kv|^\frac1k}{|\lambda_1|} += +\lim_{k\to\infty}|v_1|^{\frac1k} += +1. +\] +Dies gilt für alle Vektoren $v$, für die $v_1\ne 0$ ist. +Der maximale Wert dafür wird erreicht, wenn man für +$v$ einen Eigenvektor der Länge $1$ zum Eigenwert $\lambda_1$ einsetzt, +dann ist $v=v_1$. +Es folgt dann +\[ +\pi(A) += +\lim_{k\to\infty} \| A^k\|^\frac1k += +\lim_{k\to\infty} |A^kv|^\frac1k += +|\lambda_1| += +\varrho(A). +\] +Damit ist gezeigt, dass im Spezialfall einer diagonalisierbaren Matrix der +Gelfand-Radius tatsächlich der Betrag des betragsgrössten Eigenwertes ist. +\index{Gelfand-Radius}% + +\subsubsection{Blockmatrizen} +Wir betrachten jetzt eine $(n+m)\times(n+m)$-Blockmatrix der Form +\begin{equation} +A = \begin{pmatrix} B & 0 \\ 0 & C\end{pmatrix} +\label{buch:spektralradius:eqn:blockmatrix} +\end{equation} +mit einer $n\times n$-Matrix $B$ und einer $m\times m$-Matrix $C$. +Ihre Potenzen haben ebenfalls Blockform: +\[ +A^k = \begin{pmatrix} B^k & 0 \\ 0 & C^k\end{pmatrix}. +\] +Ein Vektor $v$ kann in die zwei Summanden $v_1$ bestehen aus den +ersten $n$ Komponenten und $v_2$ bestehen aus den letzten $m$ +Komponenten zerlegen. +Dann ist +\[ +A^kv = B^kv_1 + C^kv_2. +\qquad\Rightarrow\qquad +|A^kv| +\le +|B^kv_1| + |C^kv_2| +\le +\pi(B)^k |v_1| + \pi(C)^k |v_2|. +\] +Insbesondere haben wir das folgende Lemma gezeigt: + +\begin{lemma} +\label{buch:spektralradius:lemma:diagonalbloecke} +Eine diagonale Blockmatrix $A$ \eqref{buch:spektralradius:eqn:blockmatrix} +Blöcken $B$ und $C$ hat Gelfand-Radius +\[ +\pi(A) = \max ( \pi(B), \pi(C) ) +\] +\end{lemma} + +Selbstverständlich lässt sich das Lemma auf Blockmatrizen mit beliebig +vielen diagonalen Blöcken verallgemeinern. +\index{Blockmatrix}% + +Für Diagonalmatrizen der genannten Art sind aber auch die +Eigenwerte leicht zu bestimmen. +\index{Diagonalmatrix}% +Hat $B$ die Eigenwerte $\lambda_i^{(B)}$ mit $1\le i\le n$ und $C$ die +Eigenwerte $\lambda_j^{(C)}$ mit $1\le j\le m$, dann ist das charakteristische +Polynom der Blockmatrix $A$ natürlich +\index{charakteristisches Polynom}% +\index{Polynom!charakteristisch}% +\[ +\chi_A(\lambda) = \chi_B(\lambda)\chi_C(\lambda), +\] +woraus folgt, dass die Eigenwerte von $A$ die Vereinigung der Eigenwerte +von $B$ und $C$ sind. +Daher gilt auch für die Spektralradius die Formel +\[ +\varrho(A) = \max(\varrho(B) , \varrho(C)). +\] + +\subsubsection{Jordan-Blöcke} +\index{Jordan-Block}% +Nicht jede Matrix ist diagonalisierbar, die bekanntesten Beispiele sind +die Matrizen +\begin{equation} +J_n(\lambda) += +\begin{pmatrix} +\lambda & 1& & & & \\ + &\lambda& 1& & & \\[-5pt] + & &\lambda&\ddots & & \\[-5pt] + & & &\ddots & 1& \\ + & & & &\lambda& 1\\ + & & & & &\lambda +\end{pmatrix}, +\label{buch:spektralradius:eqn:jordan} +\end{equation} +wobei $\lambda\in\mathbb C$ eine beliebige komplexe Zahl ist. +Wir nennen diese Matrizen {\em Jordan-Matrizen}. +Es ist klar, dass $J_n(\lambda)$ nur den $n$-fachen Eigenwert +$\lambda$ hat und dass der erste Standardbasisvektor ein +Eigenvektor zu diesem Eigenwert ist. + +In der linearen Algebra lernt man, dass jede Matrix durch Wahl +\index{lineare!Algebra}% +einer geeigneten Basis als Blockmatrix der Form +\[ +A += +\begin{pmatrix} +J_{n_1}(\lambda_1) & 0 & \dots & 0 \\ + 0 & J_{n_2}(\lambda_2) & \dots & 0 \\[-4pt] +\vdots &\vdots &\ddots &\vdots \\ + 0 & 0 & \dots &J_{n_l}(\lambda_l) +\end{pmatrix} +\] +geschrieben werden kann\footnote{Sofern die Matrix komplexe Eigenwerte +hat muss man auch komplexe Basisvektoren zulassen.}. +Die früheren Beobachtungen über den Spektralradius und den +Gelfand-Radius von Blockmatrizen zeigen uns daher, dass +nur gezeigt werden muss, dass nur die Gleichheit des Gelfand-Radius +und des Spektral-Radius von Jordan-Blöcken gezeigt werden muss. + +\subsubsection{Iterationsfolgen} +\begin{satz} +\label{buch:spektralradius:satz:grenzwert} +Sei $A$ eine $n\times n$-Matrix mit Spektralradius $\varrho(A)$. +Dann ist $\varrho(A)<1$ genau dann, wenn +\[ +\lim_{k\to\infty} A^k = 0. +\] +Ist andererseits $\varrho(A) > 1$, dann ist +\[ +\lim_{k\to\infty} \|A^k\|=\infty. +\] +\end{satz} + +\begin{proof}[Beweis] +Wie bereits angedeutet reicht es, diese Aussagen für einen einzelnen +Jordan-Block mit Eigenwert $\lambda$ zu beweisen. +Die $k$-te Potenz von $J_n(\lambda)$ ist +\[ +J_n(\lambda)^k += +\renewcommand\arraystretch{1.35} +\begin{pmatrix} +\lambda^k & \binom{k}{1} \lambda^{k-1} & \binom{k}{2}\lambda^{k-2}&\dots& +\binom{k}{n-1}\lambda^{k-n+1}\\ + 0 &\lambda^k & \binom{k}{1} \lambda^{k-1} & \dots &\binom{k}{n-2}\lambda^{k-n+2}\\ + 0 & 0 & \lambda^k & \dots &\binom{k}{n-k+3}\lambda^{k-n+3}\\ +\vdots & \vdots & &\ddots & \vdots\\ + 0 & 0 & 0 &\dots &\lambda^k +\end{pmatrix}. +\] +Falls $|\lambda| < 1$ ist, gehen alle Potenzen von $\lambda$ exponentiell +schnell gegen $0$, während die Binomialkoeffizienten nur polynomiell +schnell anwachsen. +\index{Binomialkoeffizient}% +In diesem Fall folgt also $J_n(\lambda)\to 0$. + +Falls $|\lambda| >1$ divergieren bereits die Elemente auf der Diagonalen, +also ist $\|J_n(\lambda)^k\|\to\infty$ mit welcher Norm auch immer man +man die Matrix misst. +\end{proof} + +Aus dem Beweis kann man noch mehr ablesen. +Für $\varrho(A)< 1$ ist die Norm $ \|A^k\| \le M \varrho(A)^k$ für eine +geeignete Konstante $M$, +für $\varrho(A) > 1$ gibt es eine Konstante $m$ mit +$\|A^k\| \ge m\varrho(A)^k$. + +\subsubsection{Der Satz von Gelfand} +Der Satz von Gelfand ergibt sich jetzt als direkte Folge aus dem +Satz~\ref{buch:spektralradius:satz:grenzwert}. + +\begin{satz}[Gelfand] +\index{Satz von Gelfand}% +\index{Gelfand!Satz von}% +\label{buch:satz:gelfand} +Für jede komplexe $n\times n$-Matrix $A$ gilt +\[ +\pi(A) += +\lim_{k\to\infty}\|A^k\|^\frac1k += +\varrho(A). +\] +\end{satz} + +\begin{proof}[Beweis] +Der Satz~\ref{buch:spektralradius:satz:grenzwert} zeigt, dass der +Spektralradius ein scharfes Kriterium dafür ist, ob $\|A^k\|$ +gegen 0 oder $\infty$ konvergiert. +Andererseits ändert ein Faktor $t$ in der Matrix $A$ den Spektralradius +ebenfalls um den gleichen Faktor, also $\varrho(tA)=t\varrho(A)$. +Natürlich gilt auch +\[ +\pi(tA) += +\lim_{k\to\infty} \|t^kA^k\|^\frac1k += +\lim_{k\to\infty} t\|A^k\|^\frac1k += +t\lim_{k\to\infty} \|A^k\|^\frac1k += +t\pi(A). +\] + +Wir betrachten jetzt die Matrix +\[ +A(\varepsilon) = \frac{A}{\varrho(A) + \varepsilon}. +\] +Der Spektralradius von $A(\varepsilon)$ ist +\[ +\varrho(A(\varepsilon)) = \frac{\varrho(A)}{\varrho(A)+\varepsilon}, +\] +er ist also $>1$ für negatives $\varepsilon$ und $<1$ für positives +$\varepsilon$. +Aus dem Satz~\ref{buch:spektralradius:satz:grenzwert} liest man daher ab, +dass $\|A(\varepsilon)^k\|$ genau dann gegen $0$ konvergiert, wenn +$\varepsilon > 0$ ist und divergiert genau dann, wenn $\varepsilon< 0$ ist. + +Aus der Bemerkung nach dem Beweis von +Satz~\ref{buch:spektralradius:satz:grenzwert} schliesst man daher, dass +es im Fall $\varepsilon > 0$ eine Konstante $M$ gibt mit +\begin{align*} +\|A(\varepsilon) ^k\|\le M\varrho(A(\varepsilon))^k +\quad&\Rightarrow\quad +\|A(\varepsilon) ^k\|^\frac1k\le M^\frac1k\varrho(A(\varepsilon)) +\\ +&\Rightarrow\quad +\pi(A) \le \varrho(A(\varepsilon)) +\underbrace{\lim_{k\to\infty} M^\frac1k}_{\displaystyle=1} += +\varrho(A(\varepsilon)) += +\varrho(A)+\varepsilon. +\end{align*} +Dies gilt für beliebige $\varepsilon >0$, es folgt daher +$\pi(A) \le \varrho(A)$. + +Andererseits gibt es für $\varepsilon <0$ eine Konstante $m$ mit +\begin{align*} +\|A(\varepsilon) ^k\|\ge m\varrho(A(\varepsilon))^k +\quad&\Rightarrow\quad +\|A(\varepsilon) ^k\|^\frac1k\ge m^\frac1k\varrho(A(\varepsilon)) +\\ +&\Rightarrow\quad +\pi(A) \ge \varrho(A(\varepsilon)) +\underbrace{\lim_{k\to\infty} m^\frac1k}_{\displaystyle=1} += +\varrho(A(\varepsilon)) += +\varrho(A)+\varepsilon. +\end{align*} +Dies gilt für beliebige $\varepsilon> 0$, es folgt daher +$\pi(A) \ge \varrho(A)$. +Zusammen mit $\pi(A) \le \varrho(A)$ folgt $\pi(A)=\varrho(A)$. +\end{proof} + -- cgit v1.2.1 From 3d97112ba93690936fad4cd6493610069cbfacdd Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 18 Jan 2021 21:14:48 +0100 Subject: repurposing spectral radius section --- buch/chapters/40-eigenwerte/spektralradius.tex | 34 ++++++++++++++++++-------- 1 file changed, 24 insertions(+), 10 deletions(-) (limited to 'buch/chapters/40-eigenwerte/spektralradius.tex') diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex index be986f1..0c99106 100644 --- a/buch/chapters/40-eigenwerte/spektralradius.tex +++ b/buch/chapters/40-eigenwerte/spektralradius.tex @@ -3,11 +3,22 @@ % % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswi % -\section{Spektralradius -\label{buch:section:spektralradius}} -% Satz von Gelfand -% Konvergenz von Matrixreihen -% Konditionszahl +\section{Funktionen einer Matrix +\label{buch:section:funktionen-einer-matrix}} +\rhead{Funktionen einer Matrix} + +% +% Polynom-Funktionen von Matrizen +% +\subsection{Polynom-Funktionen +\label{buch:subsection:polynom-funktionen}} + + +% +% Approximationen für Funktionswerte f(A) +% +\subsection{Approximation von $f(A)$ +\label{buch:subsection:approximation}} \begin{definition} \index{Norm}% @@ -20,11 +31,6 @@ Die {\em Norm} einer Matrix $M$ ist Für einen Vektor $x\in\mathbb R^n$ gilt $|Mx| \le \|M\|\cdot |x|$. \end{definition} -Die Bedingung \eqref{buch:gs:fehler} bedeutet jedoch nicht, -dass die Norm der Ableitung $<1$ sein muss, es genügt, wenn -genügend hohe Potenzen der Ableitung eine Norm $<1$ haben. -\index{Ableitung}% - \begin{beispiel} Die Matrix \[ @@ -54,6 +60,14 @@ konvergieren, weil der Fehler nach jedem zweiten Schritt um den Faktor $\frac23$ kleiner geworden ist. \end{beispiel} +% +% Potenzreihen für Funktionen $f(z)$ +% +\subsection{Potenzreihen +\label{buch:subsection:potenzreihen}} + + + Dies führt uns auf die Grösse \begin{equation} \pi(M) -- cgit v1.2.1 From 45794fb198c8fac02b5c82b6ac3f1e17bac1075e Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 19 Jan 2021 22:08:40 +0100 Subject: =?UTF-8?q?Permutationen=20hinzugef=C3=BCgt?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/40-eigenwerte/spektralradius.tex | 351 +++++++++++++++++++++++++ 1 file changed, 351 insertions(+) (limited to 'buch/chapters/40-eigenwerte/spektralradius.tex') diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex index 0c99106..3afac18 100644 --- a/buch/chapters/40-eigenwerte/spektralradius.tex +++ b/buch/chapters/40-eigenwerte/spektralradius.tex @@ -6,19 +6,365 @@ \section{Funktionen einer Matrix \label{buch:section:funktionen-einer-matrix}} \rhead{Funktionen einer Matrix} +Eine zentrale Motivation in der Entwicklung der Eigenwerttheorie +war das Bestreben, Potenzen $A^k$ auch für grosse $k$ effizient +zu berechnen. +Mit der Jordan-Normalform ist dies auch gelungen, wenigstens über +einem Körper, in dem das charakteristische Polynom in Linearfaktoren +zerfällt. +Die Berechnung von Potenzen war aber nur der erste Schritt, das Ziel +in diesem Abschnitt ist, $f(A)$ für eine genügend grosse Klasse von +Funktionen $f$ berechnen zu können. % % Polynom-Funktionen von Matrizen % \subsection{Polynom-Funktionen \label{buch:subsection:polynom-funktionen}} +In diesem Abschnitt ist $B\in M_n(\Bbbk)$ und $\Bbbk'\supset\Bbbk$ ein +Körper, über dem das charakteristische Polynome $\chi_A(x)$ in +Linearfaktoren +\[ +\chi_A(x) += +(\lambda_1-x)^{m_1}(\lambda_2-x)^{m_2}\cdot\ldots\cdot(\lambda_p-x)^{m_p} +\] +zerfällt. + +Für jedes beliebige Polynome $p(X)=\Bbbk[X]$ der Form +\[ +p(X) = a_nX^n + a_{n-1}X^{n-1} + \dots a_1x + a_0 +\] +kann man auch +\[ +p(A) = a_nA^n + a_{n-1}A^{n-1} + \dots a_1A + a_0E +\] +berechnen. +In der Jordan-Normalform können die Potenzen $A^k$ leicht zusammengstellt +werden, sobald man die Potenzen von Jordan-Blöcken berechnet hat. +\begin{satz} +Die $k$-te Potenz von $J_n(\lambda)$ ist die Matrix mit +\begin{equation} +J_n(\lambda)^k += +\begin{pmatrix} +\lambda^k + & \binom{k}{1}\lambda^{k-1} + & \binom{k}{2} \lambda^{k-2} + & \binom{k}{3} \lambda^{k-3} + & \dots + &\binom{k}{n-1}\lambda^{k-n+1} +\\ +0 + & \lambda^k + & \binom{k}{1}\lambda^{k-1} + & \binom{k}{2} \lambda^{k-2} + & \dots + &\binom{k}{n-2}\lambda^{k-n+2} +\\ +0 + & 0 + & \lambda^k + & \binom{k}{1}\lambda^{k-1} + & \dots + &\binom{k}{n-3}\lambda^{k-n+3} +\\ +\vdots &\vdots &\vdots &\vdots &\ddots & \vdots +\\ +0 & 0 & 0 & 0 & \dots & \lambda^k +\end{pmatrix} +\label{buch:eigenwerte:eqn:Jnkpotenz} +\end{equation} +mit den Matrixelementen +\[ +(J_n(\lambda)^k)_{ij} += +\binom{k}{j-i}\lambda^{k-j+i} +\] +Die Binomialkoeffizienten verschwinden für $ji+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 $ Date: Wed, 27 Jan 2021 15:04:26 +0100 Subject: Typos. --- buch/chapters/40-eigenwerte/spektralradius.tex | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'buch/chapters/40-eigenwerte/spektralradius.tex') diff --git a/buch/chapters/40-eigenwerte/spektralradius.tex b/buch/chapters/40-eigenwerte/spektralradius.tex index 3afac18..bdc725f 100644 --- a/buch/chapters/40-eigenwerte/spektralradius.tex +++ b/buch/chapters/40-eigenwerte/spektralradius.tex @@ -31,7 +31,7 @@ Linearfaktoren \] zerfällt. -Für jedes beliebige Polynome $p(X)=\Bbbk[X]$ der Form +Für jedes beliebige Polynome $p(X)\in\Bbbk[X]$ der Form \[ p(X) = a_nX^n + a_{n-1}X^{n-1} + \dots a_1x + a_0 \] @@ -80,7 +80,7 @@ mit den Matrixelementen \[ (J_n(\lambda)^k)_{ij} = -\binom{k}{j-i}\lambda^{k-j+i} +\binom{k}{j-i}\lambda^{k-j+i}. \] Die Binomialkoeffizienten verschwinden für $ji+k$. \end{satz} @@ -391,7 +391,7 @@ hat Norm = \max_{|x|=1} |Mx| = -\max_{t\in\mathbb R} \sqrt{2^2\cos^2 t +\frac1{3^2}\sin^2t} \ge 2. +\max_{t\in\mathbb R} \sqrt{2^2\cos^2 t +\frac1{3^2}\sin^2t} = 2. \] Da aber \[ @@ -457,7 +457,7 @@ Iterationsverfahrens Auskunft zu geben. Der Grenzwert ist aber sehr mühsam zu berechnen. \index{Grenzwert}% Es wurde angedeutet, dass der Gelfand-Radius mit dem Spektralradius -übereinstimmt, dem Betrag des des betragsgrössten Eigenwertes. +übereinstimmt, dem Betrag des betragsgrössten Eigenwertes. Dies hat uns ein vergleichsweise einfach auszuwertendes Konvergenzkriterium geliefert. \index{Konvergenzkriterium}% -- cgit v1.2.1