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 $