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

Aus Wikibooks

Wechseln zu: Navigation, Suche

Beweisarchiv: Lineare Algebra

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

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.

[Bearbeiten] 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{align} 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{align}

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

[Bearbeiten] Beweise für die Korrektheit Algorithmus

[Bearbeiten] 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 λ 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{align} (\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{align}


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 ck 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{align} (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{align}

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

c_{n-k} = -\frac 1 k \; \mathrm{tr}(AB_k)
Von „http://de.wikibooks.org/wiki/Beweisarchiv:_Lineare_Algebra:_Endomorphismen:_Korrektheit_des_Algorithmus_von_Faddejew-Leverrier“
Persönliche Werkzeuge