Algorithmus von Faddejew-Leverrier

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Der Algorithmus von Faddejew-Leverrier (nach Dmitri Konstantinowitsch Faddejew und Urbain Le Verrier) ist ein Verfahren, das für beliebige quadratische Matrizen die Koeffizienten des durch definierten charakteristischen Polynoms

ermittelt. Außerdem liefert der Algorithmus die Determinante sowie für reguläre Eingabematrizen die Inverse von .

Grundlagen[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus basiert auf folgender Rekursionsvorschrift für die Matrizen und die Koeffizienten

Hierin ist die sogenannte Spur einer quadratischen Matrix

Die Rekursion 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 die Rekursion korrekt terminiert. Durch Umformen erhält man hieraus für reguläres insbesondere auch die Inverse:

Algorithmus[Bearbeiten | Quelltext bearbeiten]

Hieraus resultiert folgender Algorithmus:

/* Eingabe: quadratische Matrix A der Dimension n */

B[0] = 0;
c[n] = 1;

for (k = 1; k <= n; k++)
{
    B[k]   =   A * B[k-1] + c[n-k+1] * I;
    c[n-k] = - 1/k * trace( A * B[k] );
}        

B[n+1] = A * B[n] + c[0] * I;

if ( B[n+1] <> O )
{
    printf("Fehler: Algorithmus terminiert nicht korrekt!");
}

if ( c[0] <> 0 )
{
    Ainv = -1/c[0] * B[n];
}
else
{
    printf("Die Eingabematrix ist singulär!");
}

/* Ausgabe:
    c[0] , ..., c[n]  : Koeffizienten des charakteristischen Polynoms von A
    (-1)^n * c[0]     : Determinante von A
    Ainv              : Inverse von A (sofern c[0] <> 0)                    */

Numerisches Beispiel[Bearbeiten | Quelltext bearbeiten]

Für Matrizen kleiner Dimension () ist es möglich, den Algorithmus von Hand durchzuführen. Wir betrachten folgendes einfaches Beispiel:

Dann liefert der Algorithmus:

Es zeigt sich, dass , was eine zusätzliche Kontrolle für die Korrektheit der Rechnung ist (s. o.).

Das charakteristische Polynom der Matrix lautet also:

Weiterhin gilt:

Für die Inverse von ergibt sich aus der obigen Rechnung:

Begründung für die Korrektheit des Algorithmus[Bearbeiten | Quelltext bearbeiten]

Dass der Algorithmus stets terminiert, ist offensichtlich. Die partielle Korrektheit des Algorithmus kann auf verschiedene Arten begründen. Meistens wird in der Literatur mit den Newton-Identitäten, den Eigenschaften von Determinanten und Adjunkten sowie dem Satz von Cayley-Hamilton argumentiert (vgl.[1] und Beweisarchiv auf den Wikibooks, siehe Weblinks). Ein eleganter Beweis neueren Datums geht einen anderen Weg und verwendet die Laplace-Transformation.[2]

Aufwand, Parallelisierbarkeit und numerische Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus von Faddejew-Leverrier hat einen Aufwand der Größenordnung (im Wesentlichen Matrizenmultiplikationen). Dies ist wesentlich besser als der Aufwand, den man bei einem naiven Algorithmus basierend auf der Determinantenberechnung nach der Leibniz-Formel investieren müsste: Die Auswertung von Summanden führt hier nach der Stirlingschen Formel auf eine Zeitkomplexität von . Die Berechnung mittels Gauß-Elimination mit einem Aufwand der Größenordnung ist zwar zumindest für die reine Determinantenberechnung günstiger, erfordert jedoch, wenn man auch an den Koeffizienten des charakteristischen Polynoms interessiert ist, erhöhten technischen Aufwand bei der Implementierung in einem Computerprogramm (man benötigt Polynomarithmetik für die Matrixeinträge).

Der Algorithmus lässt sich effizient parallelisieren. Genaueres hierzu findet man in der Originalarbeit von Csanky[3] sowie in der Übersicht in Algorithmen zur parallelen Determinantenberechnung.[4]

Ein Nachteil sowohl des Algorithmus von Faddejew-Leverrier als auch der Berechnung mittels Gauß-Elimination ist das Vorkommen von Divisionen, was konträr zur originären Definition der Determinante ist, die ohne Divisionen auskommt und daher auch auf Matrizen anwendbar ist, deren Einträge Elemente eines kommutativen Rings mit Einselement sind. Für diesen Fall bieten sich divisions-freie Algorithmen, wie z. B. der Algorithmus von Samuelson-Berkowitz an, die einen vergleichbaren Aufwand haben.

Vorsicht geboten ist bei „fast-singulären“ Matrizen, d. h. Matrizen bei denen sehr klein ist: Hier ist der Algorithmus von Faddejew-Leverrier bzgl. der Berechnung der Inversen wegen der auftretenden Division durch numerisch instabil.

Historisches[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus wurde bereits 1840 von Urbain Jean Joseph Leverrier beschrieben,[5] geriet dann aber für längere Zeit wieder in Vergessenheit. Ab 1935 wurde er dann mehrfach wiederentdeckt und weiterentwickelt, unter anderem durch P. Horst,[6] Jean-Marie Souriau,[7] Dmitri Konstantinowitsch Faddejew und Sominski,[8] J. S. Frame,[9] U. Wegner[10] und Csanky.[3] Der Algorithmus in der vorliegenden Form stammt von Faddejew, was auch die heute allgemein übliche Benennung erklärt. Weitere Details zur historischen Entwicklung (mit entsprechenden Literaturhinweisen) findet man z. B. im Buch von Householder.[11]

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. J. S. Frame: Matrix functions and applications, IEEE Spectrum 1 (1964) (fünf Artikel in den Nummern 3–7)
  2. Shui-Hung Hou: Classroom Note: A Simple Proof of the Leverrier-Faddeev Characteristic Polynomial Algorithm, SIAM, 1998, SIAM Review:40(3), S. 706–709, doi:10.1137/S003614459732076X, http://link.aip.org/link/?SIR/40/706/1
  3. a b L. Csanky: Fast Parallel Matrix Inversion Algorithms. SIAM Journal on Computing, 618–623, 1976, doi:10.1137/0205040
  4. H. Burbach: Algorithmen zur parallelen Determinantenberechnung. Diplom-Arbeit, Universität Dortmund, Oktober 1992, Online-Version (PDF-Datei; 801 kB)
  5. Urbain Le Verrier: Sur les variations séculaires des éléments des orbites pour les sept planètes principales, J. de Math. (1) 5, 230 (1840), Online-Version des Artikels verfügbar auf der Webseite der Bibliotheque nationale de France digital library (Gallica)
  6. Paul Horst: A method of determining the coefficients of a characteristic equation. Ann. Math. Stat. 6, 83–84 (1935), doi:10.1214/aoms/1177732612
  7. Jean-Marie Souriau : Une méthode pour la décomposition spectrale et l’inversion des matrices. Comptes Rend. 227, 1010–1011 (1948)
  8. D. K. Faddeev, I. S. Sominski: Sbornik zadatch po vyshej algebre. Moskow-Leningrad 1949
  9. J. S. Frame: A simple recursion formula for inverting a matrix (abstract). Bull. Am. Math. Soc. 55, 1045 (1949), doi:10.1090/S0002-9904-1949-09310-2
  10. U. Wegner: Bemerkungen zur Matrizentheorie. Z. angew. Math. Mech. 33, 262–264 (1953), doi:10.1002/zamm.19530330807
  11. Alston Scott Householder: The Theory of Matrices in Numerical Analysis. Dover, New York 1975, ISBN 0-486-61781-5