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

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 RekursionBearbeiten

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:

  • Wegen
 

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 AlgorithmusBearbeiten

Direkter algebraischer BeweisBearbeiten

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: