Benutzer:Hightower74/Algorithmus von Faddejew-Leverrier

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 und die Adjunkte sowie für reguläre Eingabematrizen die Inverse von .

Für den Ring der Matrixelemente wird vorausgesetzt, dass es sich um einen kommutativen Ring mit Einselement handelt und dass eine der beiden folgenden Voraussetzungen erfüllt ist (vgl. Johannson[1]):

  • hat die Charakteristik 0 (wie z.B. für oder )
  • Die Charakteristik von ist teilerfremd zu

Motivation

Bearbeiten

Durch Ausmultiplizieren der faktorisierten Darstellung des charakteristische Polynoms erhält man

 

wobei die in der resultierenden Summe auftretenden elementarsymmetrischen Polynome   durch

 

definiert sind.

Die Newton-Identitäten stellen einen Zusammenhang zwischen den elementarsymmetrischen Polynomen   und den Potenzsummen der Eigenwerte   her, wobei wir uns zu Nutze machen können, dass sich   als Spur der Matrixpotenz   ausdrücken lässt:

 

Wegen   übersetzten sich die Newton-Identitäten dann in folgende Gleichungen, mit denen sich die Koeffizienten sukzessive ermitteln lassen ( :

 

Rekursive Formulierung

Bearbeiten

Die in der Motivation hergeleiteten Formeln für die Koeffizienten   lassen sich mit Hilfe der Matrizen   folgendermaßen rekursiv formulieren:

 

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

Hieraus resultiert folgender Algorithmus:

/* Eingabe: Quadratische Matrix A der Dimension n                                               */
/*          Für den kommutativen Ring R mit Einselement der Matrixelemente wird vorausgesetzt:  */
/*          char(R) = 0 oder char(R) teilerfremd zu 1,...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 * tr( 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
    (-1)^(n+1) * B[n]  : Adjunkte von A
    Ainv               : Inverse von A (sofern c[0] ungleich 0)
*/

Numerisches Beispiel

Bearbeiten

Für Matrizen kleiner Dimension lässt sich der Algorithmus leicht 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

Dass der Algorithmus stets terminiert, ist offensichtlich. Für die partielle Korrektheit des Algorithmus muss man zeigen, dass die per Rekursion ermittelten Koeffizienten   mit der in der Motivation hergeleiteten Darstellung übereinstimmen.

Zu diesem Zweck weisen wir induktiv nach, dass die Rekursion im  -ten Schritt die folgenden Ergebnisse liefert:

 

Für den ersten Rekursionsschritt ( ) sind die beiden Beziehungen offensichtlich erfüllt.

Um die Gültigkeit für den  ten Schritt zu zeigen, nehmen wir an, dass die Beziehungen für den  ten Schritt richtig sind (Schluss von   auf  ):

 
 

Alternative Begründungen für die partielle Korrektheit

Bearbeiten

Generell wird in der Literatur mit

argumentiert.

Ein eleganter Beweis neueren Datums geht einen anderen Weg und nutzt aus, dass die Laplace-Transformierte des Matrixexponential gerade der Resolvente von   entspricht[4]:

 

Anwendungsbereich und Voraussetzungen

Bearbeiten

Wie bereits in der Einleitung erwähnt, ist der Algorithmus nur dann auf die Matrix   anwendbar, wenn der Ring   der Matrixelemente ein kommutativer Ring mit Einselement ist und eine der beiden folgenden Voraussetzungen erfüllt ist (vgl. Johannson[5]):

  •   hat die Charakteristik 0 (wie z.B. für   oder  )
  • Die Charakteristik von   ist teilerfremd zu  

Diese Bedingung stellt sicher, dass die im Algorithmus auftretenden Divisionen durch   im Ring   exakt durchführbar sind, d.h. dass

 

Ein genereller Nachteil des Algorithmus von Faddejew-Leverrier ist das Auftreten von Divisionen, was konträr zur Definition der Determinante über die Leibniz-Formel ist, die ohne Divisionen auskommt und daher auch auf Matrizen anwendbar ist, deren Einträge Elemente eines beliebigen kommutativen Rings mit Einselement sind. Für diesen allgemeinen Fall (d.h. insbesondere wenn die oben angegebenen Voraussetzungen nicht erfüllbar sind) bieten sich divisions-freie Algorithmen, wie z. B. der Algorithmus von Samuelson-Berkowitz als Alternative an, die einen vergleichbaren Aufwand haben.

Wir notieren mit   den Aufwand für die Methode, die für die Matrizenmultiplikation verwendet wird. Da der Zeitaufwand für den Algorithmus von Faddejew-Leverrier von den auftretenden   Matrizenmultiplikationen dominiert wird, ergibt sich für den Gesamtaufwand eine asymptotische obere Schranke von  .

Beispiele:

  • Klassische Matrizenmultiplikation ( : Aufwand  
  • Strassen-Algorithmus ( ): Aufwand  

Vergleich mit anderen Verfahren

Bearbeiten

Determinantenberechnung nach der Leibniz-Formel

Bearbeiten

Der naive Algorithmus basierend auf der Determinantenberechnung nach der Leibniz-Formel ermittelt und addiert   Summanden was nach der Stirlingschen Formel einer asymptotischen Zeitkomplexität von   entspricht.

Neben dem exponentiellen Aufwand macht auch die Notwendigkeit von Polynomarithmetik diesen Ansatz inpraktikabel.

Gauß-Elimination

Bearbeiten

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).

Algorithmus von Samuelson-Berkowitz

Bearbeiten

Der Algorithmus von Samuelson-Berkowitz hat ebenfalls eine asymptotische obere Schranke von   für die Zeitkomplexität.

Parallelisierbarkeit

Bearbeiten

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

Numerische Stabilität

Bearbeiten

Der Algorithmus von Faddejew-Leverrier ist numerisch nicht stabil (siehe z.B Wilkinson[8] und Rehman/Ipsen[9]). Daher ist er für die Anwendung mit Gleitkomma-Arithmetik nicht gut geeignet, kann aber mit exakter Bruch-Arithmetik verwendet werden. Trotz seiner seiner eingeschränkten praktischen Relevanz ist der Algorithmus von theoretischer Bedeutung, da er eine formale Charakterisierung für die Koeffizienten des charakteristischen Polynoms sowie entsprechende Zusammenhänge zu Determinanten, Inversen und Adjunkten angibt.

Charakterisierung der Koeffizienten als Lösung eines Gleichungssystems

Bearbeiten

Die zu Beginn in der Motivation hergeleiteten Gleichungen für die Koeffizienten   lassen sich in folgendes lineares Gleichungssystem umschreiben:

 

Dieses lässt sich durch Vorwärtseinsetzen lösen, was gerade der sukzessiven Berechnung der   aus der Motivation entspricht.

Durch Anwenden der Cramerschen Regel auf das obige LGS kann man folgende explizite Darstellung gewinnen:

 

Historisches

Bearbeiten

Der Algorithmus wurde bereits 1840 von Urbain Jean Joseph Leverrier beschrieben,[10] 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,[11] Jean-Marie Souriau,[12] Dmitri Konstantinowitsch Faddejew und Sominski,[13] J. S. Frame,[14] U. Wegner[15] und Csanky.[6] 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.[16]

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. F. Johannson: On a fast and nearly division-free algorithm for the characteristic polynomial. Preprint (2020), arxiv:2011.12573
  2. F. R. Gantmacher: The Theory of Matrices, Chelsea, 1990, siehe speziell Kapitel IV §5, pp. 87-89
  3. J. S. Frame: Matrix functions and applications, IEEE Spectrum 1 (1964) (fünf Artikel in den Nummern 3–7)
  4. 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@2Vorlage:Toter Link/link.aip.org (Seite nicht mehr abrufbar, festgestellt im März 2018. Suche in Webarchiven)  Info: Der Link wurde automatisch als defekt markiert. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis.
  5. F. Johannson: On a fast and nearly division-free algorithm for the characteristic polynomial. Preprint (2020), arxiv:2011.12573
  6. a b L. Csanky: Fast Parallel Matrix Inversion Algorithms. SIAM Journal on Computing, 618–623, 1976, doi:10.1137/0205040
  7. H. Burbach: Algorithmen zur parallelen Determinantenberechnung. Diplom-Arbeit, Universität Dortmund, Oktober 1992, Online-Version (PDF-Datei; 801 kB)
  8. J. H. Wilkinson: The algebraic eigenvalue problem, volume 87. Clarendon press Oxford, 1965, ISBN 978-0198534181, Kapitel 7, §19, pp. 434-435
  9. R. Rehman and I. C. F. Ipsen: La Budde's Method for Computing Characteristic Polynomials. Preprint (2011), arxiv:1104.3769
  10. 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)
  11. Paul Horst: A method of determining the coefficients of a characteristic equation. Ann. Math. Stat. 6, 83–84 (1935), doi:10.1214/aoms/1177732612
  12. Jean-Marie Souriau: Une méthode pour la décomposition spectrale et l’inversion des matrices. Comptes Rend. 227, 1010–1011 (1948)
  13. D. K. Faddeev, I. S. Sominski: Sbornik zadatch po vyshej algebre. Moskow-Leningrad 1949
  14. 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
  15. U. Wegner: Bemerkungen zur Matrizentheorie. Z. angew. Math. Mech. 33, 262–264 (1953), doi:10.1002/zamm.19530330807
  16. Alston Scott Householder: The Theory of Matrices in Numerical Analysis. Dover, New York 1975, ISBN 0-486-61781-5

Faddejew Leverrier Kategorie:Numerische lineare Algebra