Beweisarchiv: Lineare Algebra
- Endomorphismen: Satz von Cayley-Hamilton · Korrektheit des Algorithmus von Faddejew-Leverrier · Kreisesatz von Gerschgorin
- Vektorräume: Jeder Vektorraum hat eine Basis
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 die Koeffizienten des durch definierten charakteristischen Polynoms
ermittelt. Außerdem liefert der Algorithmus sowohl die Determinante als auch die Inverse von .
Beschreibung des Algorithmus und der Rekursion
[Bearbeiten]
Der Algorithmus basiert auf folgender Rekursionsvorschrift für die Matrizen und
die Koeffizienten
Hierin ist die sogenannte Spur einer quadratischen
Matrix
Der Algorithmus hat weitere interessante Eigenschaften:
erhält man unmittelbar den Wert der Determinanten von .
- Außerdem kann man mit Hilfe der Beziehung
überprüfen, ob der Algorithmus korrekt terminiert. Durch Umformen erhält man hieraus insbesondere auch
die Inverse von :
Beweise für die Korrektheit Algorithmus
[Bearbeiten]
Wir verwenden folgenden bekannten Zusammenhang zwischen Determinante und Adjunkte einer Matrix, der auch zur Matrix-Inversion verwendet werden kann. Es gilt nämlich
Aus der Definition der Adjunkten folgt, dass in
höchstens mit Grad auftritt. Man kann hierin nach
Potenzen von sortieren und dann geeignet als Summe zerlegen.
Es ist für unsere Zwecke nützlich, das Polynom in mit Matrix-Koeffizienten zu schreiben ( wobei und ):
Einsetzen und Umformen liefert:
Durch Koeffizientenvergleich folgt:
Speziell haben wir per Definition (siehe oben):
Damit ist die Rekursionsvorschrift für die Matrizen sowie die Aussage für die
Inverse von hergeleitet.
Bemerkung:
Aus (*) folgt direkt der Satz von Cayley-Hamilton, denn Einsetzen
von 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 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 :
Speziell für unsere Situation bedeutet das also:
Wir rechnen nun beide Seiten weiter aus. Einerseits haben wir dann:
Andererseits können wir das charakteristische Polynom als
schreiben und erhalten als Ableitung:
schreiben. Koeffizientenvergleich in den beiden Ausdrücken für und sowie anschließendes Einsetzen der Rekursionsvorschrift für ergibt
und einige letzte Umformungen führen dann auf das behauptete Resultat: