Beweisarchiv: Lineare Algebra: Endomorphismen: Korrektheit des Algorithmus von Faddejew-Leverrier

Beweisarchiv: Lineare Algebra

Endomorphismen: Satz von Cayley-Hamilton · Korrektheit des Algorithmus von Faddejew-Leverrier

Vektorräume: Jeder Vektorraum hat eine Basis

Lineare Abbildungen: Kreisesatz von Gerschgorin

---

Der Algorithmus von Faddejew-Leverrier (benannt nach dem russischen Mathematiker Dmitri Konstantinowitsch Faddejew und dem französischen Mathematiker Urbain Jean Joseph Leverrier) ist ein Verfahren, das für beliebige quadratische Matrizen $A\in \mathbb {C} ^{n\times n}$ die Koeffizienten $c_{k}\;(k=1,\ldots n)$ des durch $p(\lambda )=\det(\lambda I-A)\;$ definierten charakteristischen Polynoms

$p(\lambda )=c_{n}\lambda ^{n}+c_{n-1}\lambda ^{n-1}+c_{n-2}\lambda ^{n-2}+\ldots +c_{1}\lambda +c_{0}$

ermittelt. Außerdem liefert der Algorithmus sowohl die Determinante als auch die Inverse von $A$.

Beschreibung des Algorithmus und der Rekursion

Der Algorithmus basiert auf folgender Rekursionsvorschrift für die Matrizen $B_{0},\ldots ,B_{n}\in \mathbb {C} ^{n\times n}$ und die Koeffizienten $c_{0},\ldots ,c_{n}\in \mathbb {C}$

${\begin{aligned}B_{0}&=0&c_{n}&=1\qquad &(k=0)\\B_{k}&=AB_{k-1}+c_{n-k+1}I\qquad \qquad &c_{n-k}&=-{\frac {1}{k}}\mathrm {tr} (AB_{k})\qquad &k=1,\ldots ,n\end{aligned}}$

Hierin ist $\mathrm {tr} (M):=\sum \limits _{i=1}^{n}m_{ii}$ die sogenannte Spur einer quadratischen Matrix $M\in \mathbb {C} ^{n\times n}$

Der Algorithmus hat weitere interessante Eigenschaften:

• Wegen

$c_{0}=p(0)=\det(-A)=(-1)^{n}\;\det A$

erhält man unmittelbar den Wert der Determinanten von $A$.

• Außerdem kann man mit Hilfe der Beziehung

$B_{n+1}=AB_{n}+c_{0}I=0\;$

überprüfen, ob der Algorithmus korrekt terminiert. Durch Umformen erhält man hieraus insbesondere auch die Inverse von $A$ :

$A^{-1}=-{\frac {1}{c_{0}}}B_{n}$

Beweise für die Korrektheit Algorithmus

Direkter algebraischer Beweis

Wir verwenden folgenden bekannten Zusammenhang zwischen Determinante und Adjunkte einer Matrix, der auch zur Matrix-Inversion verwendet werden kann. Es gilt nämlich

$(\lambda I-A)\cdot \mathrm {adj} (\lambda I-A)=\det(\lambda I-A)\cdot I=p_{A}(\lambda )\cdot I$

Aus der Definition der Adjunkten folgt, dass $\lambda \;$ in $\mathrm {adj} (\lambda I-A)\;$ höchstens mit Grad $n-1\;$ auftritt. Man kann hierin nach Potenzen von $\lambda \;$ sortieren und dann geeignet als Summe zerlegen. Es ist für unsere Zwecke nützlich, das Polynom in $\lambda$ mit Matrix-Koeffizienten $B_{k}\in \mathbb {C} ^{n\times n}\;(k=0,\ldots ,n+1)\;$ zu schreiben ( wobei $B_{0}=0\;$ und $B_{n+1}=0\;$):

$\mathrm {adj} (\lambda I-A)=\sum _{k=0}^{n+1}B_{k}\lambda ^{n-k}$

Einsetzen und Umformen liefert:

${\begin{aligned}(\lambda I-A)\cdot \sum _{k=0}^{n+1}B_{k}\lambda ^{n-k}&=p_{A}(\lambda )\cdot I\\\sum _{k=1}^{n+1}\left(B_{k}-AB_{k-1}\right)\lambda ^{n-k+1}&=\sum _{k=1}^{n+1}c_{n-k+1}\lambda ^{n-k+1}\cdot I\qquad (*)\end{aligned}}$

Durch Koeffizientenvergleich folgt:

$B_{k}-AB_{k-1}=c_{n-k+1}I\quad \Longleftrightarrow \quad B_{k}=AB_{k-1}+c_{n-k+1}I$

Speziell haben wir per Definition (siehe oben):

$0=B_{n+1}=AB_{n}+c_{0}I\quad \Longleftrightarrow \quad A^{-1}=-{\frac {1}{c_{0}}}B_{n}$

Damit ist die Rekursionsvorschrift für die Matrizen $B_{k}\;$ sowie die Aussage für die Inverse von $A$ hergeleitet.

---

Bemerkung: Aus (*) folgt direkt der Satz von Cayley-Hamilton, denn Einsetzen von $A$ auf der linken Seite führt auf eine Teleskopsumme, in der sich alle Terme wegheben. Vergleiche dazu auch die Beweise im Beweisarchiv.

---

Es muss nun noch die Aussage für die Koeffizienten $c_{k}$ des charakteristischen Polynoms bewiesen werden:

Hierzu verwenden wir Jacobi's Formel zur Differentiation von Determinanten-Funktionen. Es gilt nämlich allgemein für eine Matrixfunktion $M(x)$:

${\frac {d}{dx}}\det(\;M(x)\;)=\mathrm {tr} \left(\;\mathrm {adj} (M(x))\cdot {\frac {d}{dx}}M(x)\;\right)$

Speziell für unsere Situation bedeutet das also:

$p'(\lambda )={\frac {d}{d\lambda }}\det(\;\lambda I-A)\;)=\mathrm {tr} \left(\;\mathrm {adj} (\lambda I-A)\cdot {\frac {d}{d\lambda }}(\lambda I-A)\;\right)=\mathrm {tr} (\;\mathrm {adj} (\lambda I-A)\;)$

Wir rechnen nun beide Seiten weiter aus. Einerseits haben wir dann:

$\mathrm {tr} (\;\mathrm {adj} (\lambda I-A)\;)=\mathrm {tr} \left(\sum _{k=0}^{n+1}B_{k}\lambda ^{n-k}\right)=\sum _{k=0}^{n+1}\mathrm {tr} (B_{k}\lambda ^{n-k})=\sum _{k=0}^{n+1}\mathrm {tr} (B_{k})\lambda ^{n-k}$

Andererseits können wir das charakteristische Polynom als

$p(\lambda )=\sum _{k=0}^{n}c_{n-k}\lambda ^{n-k}$

schreiben und erhalten als Ableitung:

$p'(\lambda )=\sum _{k=0}^{n}(n-k)\;c_{n-k}\;\lambda ^{n-k-1}$

schreiben. Koeffizientenvergleich in den beiden Ausdrücken für $\mathrm {tr} (\;\mathrm {adj} (\lambda I-A)\;)$ und $p'(\lambda )\;$ sowie anschließendes Einsetzen der Rekursionsvorschrift für $B_{k+1}\;$ ergibt

${\begin{aligned}(n-k)\;c_{n-k}&=\mathrm {tr} (B_{k+1})\\&=\mathrm {tr} \left(\;AB_{k}+c_{n-k}I\;\right)\\&=\mathrm {tr} (AB_{k})+c_{n-k}\;\mathrm {tr} (I)\\&=\mathrm {tr} (AB_{k})+n\cdot c_{n-k}\end{aligned}}$

und einige letzte Umformungen führen dann auf das behauptete Resultat:

$c_{n-k}=-{\frac {1}{k}}\;\mathrm {tr} (AB_{k})$