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