Algorithmus von Faddejew-Leverrier

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 und theoretischer Hintergrund

[Bearbeiten | Quelltext bearbeiten]

Durch Ausmultiplizieren der faktorisierten Darstellung des charakteristische Polynoms einer Matrix mit den Eigenwerten erhält man

wobei die in der resultierenden Summe auftretenden elementarsymmetrischen Polynome folgendermaßen definiert sind:

Die Newton-Identitäten stellen einen Zusammenhang zwischen den elementarsymmetrischen Polynomen und den Potenzsummen der Eigenwerte her.

Gleichungen für die Koeffizienten

[Bearbeiten | Quelltext bearbeiten]

Mit lässt sich als Spur der Matrixpotenz ausdrücken und auf Grund von übersetzten sich die Newton-Identitäten

dann in folgende Gleichungen, mit denen sich die Koeffizienten sukzessive ermitteln lassen :

Formulierung als lineares Gleichungssystem

[Bearbeiten | Quelltext bearbeiten]

Die soeben hergeleiteten Gleichungen für die Koeffizienten lassen sich etwas kompakter (und für theoretische Zwecke besser geeignet) in folgendes äquivalentes lineares Gleichungssystem umformulieren:

Das Auflösen des Gleichungssystems nach den Koeffizienten durch Vorwärtseinsetzen führt gerade auf die Formeln aus dem vorherigen Abschnitt.

Explizite Darstellungen der Koeffizienten

[Bearbeiten | Quelltext bearbeiten]

Aus dem linearen Gleichungssystem gewinnt man durch Anwenden der Cramerschen Regel folgende explizite Darstellung für die Koeffizienten :

Ein Vergleich mit der Determinantendarstellung der vollständigen Bell-Polynome (vgl. z. B. A. Zúñiga-Segundo et al.[2] und [3]) zeigt, dass man dies äquivalent dazu auch etwas bequemer folgendermaßen ausdrücken kann:

Wenn man nicht -- wie vorgeführt -- auf dem oben formulierten linearen Gleichungssystem aufbaut, dann benötigt man für die Herleitung der Formeln aus diesem Abschnitt tieferliegende Hilfsmittel aus der Analysis (z. B. die Plemelj-Smithies-Formeln).

Rekursive Formulierung

[Bearbeiten | Quelltext bearbeiten]

Mit Hilfe der Matrizen kann man die Formeln für die Koeffizienten aus der Motivation in folgendes rekursives Schema übersetzen (Nachweis durch Induktion nach , siehe Begründung für die Korrektheit des Algorithmus weiter unten):

Hierin ist die sogenannte Spur einer quadratischen Matrix

Aus der Rekursion lassen sich weitere interessante Beziehungen ableiten:

  • Wegen

erhält man unmittelbar den Wert der Determinanten von .

  • Außerdem kann man mit Hilfe von

überprüfen, ob die Rekursion korrekt terminiert. Durch Umformen erhält man hieraus für reguläres insbesondere auch die Inverse:

  • Schließlich folgt wegen für die Adjunkte:

Basierend auf dem rekursiven Schema kann man nun den Algorithmus von Faddejew-Leverrier formulieren:

/* 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 | Quelltext 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 | Quelltext bearbeiten]

Für die Korrektheit des Algorithmus muss man dessen Terminiertheit und partielle Korrektheit nachweisen. Dass der Algorithmus stets terminiert, ist offensichtlich. Die partielle Korrektheit des Algorithmus folgt, wenn 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 wegen und 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 Zugänge zum Algorithmus

[Bearbeiten | Quelltext bearbeiten]

Der Weg über die Newton-Identitäten (wie oben vorgeführt und z. B. in Gantmacher[4]) ist zwar sehr ökonomisch im Aufbau und in der Darstellung, hat aber den Nachteil, dass er Vorwissen aus dem Bereich der Algebra benötigt und keinen intuitiven Zugang über die grundlegenden Konzepte der Linearen Algebra bietet. Insbesondere erscheint die Notwendigkeit zur Verwendung der Matrizen etwas künstlich.

Daher verfolgen einige Darstellungen in der Literatur einen anderen Ansatz und motivieren zunächst die rekursive Darstellung für die Matrizen (vgl.[5] und Beweisarchiv auf den Wikibooks, siehe Weblinks):

Der bekannte Zusammenhang zwischen Determinante und Adjunkte angewendet auf die Matrix ergibt:

Hieraus folgt, dass in höchstens mit Grad auftritt, so dass sich als Polynom in mit Matrix-Koeffizienten schreiben lässt (wobei und ):

Einsetzen und Umformen liefert:

Durch Koeffizientenvergleich erhält man schließlich die rekursive Darstellung für die :

Zur Ableitung der Beziehung für die Koeffizienten muss man nun allerdings auf Hilfsmittel aus der Analysis zurückgreifen, was ein Nachteil dieses Zugangs ist. In der Literatur wird zu diesem Zweck beispielsweise

verwendet.

Anwendungsbereich und Voraussetzungen

[Bearbeiten | Quelltext 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[8]):

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

Aufwand und Vergleich mit anderen Verfahren

[Bearbeiten | Quelltext bearbeiten]

Der Zeitaufwand für den Algorithmus von Faddejew-Leverrier wird von den auftretenden Matrizenmultiplikationen dominiert. Wenn man nun mit den Aufwand für die Methode notiert, die für die Matrizenmultiplikation verwendet wird, so ergibt sich für den Gesamtaufwand eine asymptotische obere Schranke von .

Beispiele:

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

Determinantenberechnung nach der Leibniz-Formel

[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

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

Parallelisierbarkeit

[Bearbeiten | Quelltext bearbeiten]

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

Numerische Stabilität

[Bearbeiten | Quelltext bearbeiten]

Der Algorithmus von Faddejew-Leverrier ist numerisch nicht stabil (siehe z. B. Wilkinson[11] und Rehman/Ipsen[12]). Daher ist er für die Anwendung mit Gleitkomma-Arithmetik nicht gut geeignet, kann aber mit exakter Bruch-Arithmetik verwendet werden. Trotz 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.

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

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. F. Johannson: On a fast and nearly division-free algorithm for the characteristic polynomial. Preprint (2020), arxiv:2011.12573
  2. A. Zúñiga-Segundo, J. López-Bonilla, S. Vidal-Beltrán: Characteristic equation of a matrix via Bell polynomials, Asia Mathematika Volume 2 Issue 2 (2018) page: 49-51, Online-Version des Artikels
  3. A. Zúñiga-Segundo, J. López-Bonilla, S. Vidal-Beltrán: Some Applications of Complete Bell Polynomials, World Engineering & Applied Sciences Journal 9 (3): 89-92, 2018, ISSN 2079-2204, Online-Version des Artikels
  4. F. R. Gantmacher: The Theory of Matrices, Chelsea, 1990, siehe speziell Kapitel IV §5, pp. 87-89
  5. J. S. Frame: Matrix functions and applications, IEEE Spectrum 1 (1964) (fünf Artikel in den Nummern 3–7)
  6. J. S. Frame: Matrix functions and applications, IEEE Spectrum 1 (1964) (fünf Artikel in den Nummern 3–7)
  7. 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
  8. F. Johannson: On a fast and nearly division-free algorithm for the characteristic polynomial. Preprint (2020), arxiv:2011.12573
  9. a b L. Csanky: Fast Parallel Matrix Inversion Algorithms. SIAM Journal on Computing, 618–623, 1976, doi:10.1137/0205040
  10. H. Burbach: Algorithmen zur parallelen Determinantenberechnung. Diplom-Arbeit, Universität Dortmund, Oktober 1992, Online-Version (PDF-Datei; 801 kB)
  11. J. H. Wilkinson: The algebraic eigenvalue problem, volume 87. Clarendon press Oxford, 1965, ISBN 978-0-19-853418-1, Kapitel 7, §19, pp. 434-435
  12. R. Rehman and I. C. F. Ipsen: La Budde's Method for Computing Characteristic Polynomials. Preprint (2011), arxiv:1104.3769
  13. 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)
  14. Paul Horst: A method of determining the coefficients of a characteristic equation. Ann. Math. Stat. 6, 83–84 (1935), doi:10.1214/aoms/1177732612
  15. Jean-Marie Souriau: Une méthode pour la décomposition spectrale et l’inversion des matrices. Comptes Rend. 227, 1010–1011 (1948)
  16. D. K. Faddeev, I. S. Sominski: Sbornik zadatch po vyshej algebre. Moskow-Leningrad 1949
  17. 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
  18. U. Wegner: Bemerkungen zur Matrizentheorie. Z. angew. Math. Mech. 33, 262–264 (1953), doi:10.1002/zamm.19530330807
  19. Alston Scott Householder: The Theory of Matrices in Numerical Analysis. Dover, New York 1975, ISBN 0-486-61781-5