imported>Leyo: Halbgeviertstrich

2026-01-09T21:40:24Z

Neue Seite

Der '''Algorithmus von Faddejew-Leverrier''' (nach [[Dmitri Konstantinowitsch Faddejew]] und [[Urbain Le Verrier]]) ist ein Verfahren, das für beliebige quadratische [[Matrix (Mathematik)|Matrizen]] <math>A\in R^{n\times n}</math> die Koeffizienten <math>c_k \; (k = 1, \ldots, n)</math>, <math>c_n = 1 </math> des durch <math>p(\lambda) = \det (\lambda I-A)</math> definierten [[Charakteristisches Polynom|charakteristischen Polynoms]]

:<math> p(\lambda) = c_n \lambda^n + c_{n-1} \lambda^{n-1} + c_{n-2} \lambda^{n-2} + \ldots + c_1 \lambda + c_0 </math>

ermittelt. Außerdem liefert der Algorithmus die [[Determinante (Mathematik)|Determinante]] und die [[Adjunkte]] sowie für [[Reguläre Matrix|reguläre Eingabematrizen]] die [[Inverse]] von <math>A</math>.

Für den Ring <math> R </math> der Matrixelemente wird vorausgesetzt, dass es sich um einen [[kommutativer Ring|kommutativen Ring]] mit [[Einselement]] handelt und dass eine der beiden folgenden Voraussetzungen erfüllt ist (vgl. Johannson<ref>F. Johannson: ''On a fast and nearly division-free algorithm for the characteristic polynomial''. Preprint (2020), {{arXiv|2011.12573}}</ref>):
* <math> R </math> hat die [[Charakteristik (Algebra)|Charakteristik]] 0 (wie z. B. für <math> R=\mathbb{R} </math> oder <math> R=\mathbb{C} </math>)
* Die [[Charakteristik (Algebra)|Charakteristik]] von <math> R </math> ist [[teilerfremd]] zu <math> k \in\{1,\ldots, n\} </math>

== Motivation und theoretischer Hintergrund ==

Durch Ausmultiplizieren der faktorisierten Darstellung des charakteristische Polynoms einer [[Matrix (Mathematik)|Matrix]] <math>A\in R^{n\times n}</math> mit den Eigenwerten <math> \lambda_1,\ldots,\lambda_n </math> erhält man
:<math> p(\lambda) = \prod_{k=1}^n (\lambda-\lambda_i) = \sum_{k=0}^n (-1)^k \sigma_k(\lambda_1,\ldots, \lambda_n) \lambda^{n-k}</math>
wobei die in der resultierenden Summe auftretenden [[elementarsymmetrisches Polynom|elementarsymmetrischen Polynome]] <math> \sigma_k </math> folgendermaßen definiert sind:
:<math>\sigma_k(\lambda_1,\dots,\lambda_n)= \sum_{ S \subseteq \{ 1, \dotsc, n \} \atop \# S=k} \ \prod_{i \in S} \lambda_i \qquad k=0,1,\dots,n</math>
Die [[Newton-Identitäten]] stellen einen Zusammenhang zwischen den elementarsymmetrischen Polynomen <math> \sigma_k </math> und den
Potenzsummen der Eigenwerte <math> s_k = \sum_{i=1}^n \lambda_i^k </math> her.

=== Gleichungen für die Koeffizienten ===

Mit <math> \sum_{i=1}^n \lambda_i^k = \operatorname{tr}~A^k </math> lässt sich <math> s_k </math> als [[Spur (Mathematik)|Spur]] der Matrixpotenz <math> A^k </math> ausdrücken und
auf Grund von <math> c_{n-k} = (-1)^k \sigma_k (\lambda_1,\ldots, \lambda_n) </math> übersetzten sich die Newton-Identitäten

dann in folgende Gleichungen, mit denen sich die Koeffizienten sukzessive ermitteln lassen <math> (k=1,\ldots, n) </math>:

:<math>\begin{align}
c_n &= 1,\\[4pt]
c_{n-1} &=- c_n \operatorname{tr}~A,\\[4pt]
c_{n-2} &= -\frac{1}{2}(c_{n-1} \operatorname{tr}~A + c_n \operatorname{tr}~A^2),\\[4pt]
c_{n-3} &=-\frac{1}{3}(c_{n-2} \operatorname{tr}~A + c_{n-1} \operatorname{tr}~A^2 + c_n \operatorname{tr}~A^3),\\[4pt]
\vdots \\[4pt]
c_{n-k} &=-\frac 1 k \sum_{i=1}^k c_{n-k+i} \operatorname{tr}~A^i
\end{align}</math>

=== Formulierung als lineares Gleichungssystem ===

Die soeben hergeleiteten Gleichungen für die Koeffizienten <math> c_{n-k} </math> lassen sich etwas kompakter (und für theoretische Zwecke besser geeignet) in folgendes äquivalentes [[lineares Gleichungssystem]] umformulieren:

:<math>

\left[
\begin{matrix}
1 & 0 & 0 & \cdots & 0 \\
\operatorname{tr}A & 2 & 0 & \ddots & \vdots \\
\operatorname{tr}A^2 & \operatorname{tr}A & 3 & \ddots & 0 \\
\vdots & \vdots & \ddots & \ddots & \vdots \\
\operatorname{tr}A^{n-1} & \operatorname{tr}A^{n-2} & \cdots & \operatorname{tr}A & n
\end{matrix}
\right]

\left[
\begin{matrix}
c_{n-1} \\[0.21cm]
c_{n-2} \\[0.21cm]
c_{n-3} \\[0.21cm]
\vdots \\
c_0
\end{matrix}
\right]

=

\left[
\begin{matrix}
-\operatorname{tr}A \\[0.21cm]
-\operatorname{tr}A^2 \\[0.21cm]
-\operatorname{tr}A^3 \\[0.21cm]
\vdots \\
-\operatorname{tr}A^n
\end{matrix}
\right]

</math>

Das Auflösen des Gleichungssystems nach den Koeffizienten <math> c_{n-k} </math> durch [[Gaußsches Eliminationsverfahren#Vorwärtseinsetzen|Vorwärtseinsetzen]] führt gerade auf die Formeln aus dem vorherigen Abschnitt.

=== Explizite Darstellungen der Koeffizienten ===

Aus dem linearen Gleichungssystem gewinnt man durch Anwenden der [[Cramersche Regel|Cramerschen Regel]] folgende explizite Darstellung für die Koeffizienten <math> c_{n-k} </math>:

:<math>c_{n-k} = \frac{(-1)^k}{k!} \;
\begin{vmatrix} \operatorname{tr}A & k-1 &0&\cdots & 0\\
\operatorname{tr}A^2 &\operatorname{tr}A& k-2 &\ddots & \vdots \\
\vdots & \vdots & \ddots & \ddots & 0 \\
\operatorname{tr}A^{k-1} &\operatorname{tr}A^{k-2}& \cdots & \operatorname{tr}A & 1 \\
\operatorname{tr}A^k &\operatorname{tr}A^{k-1}& \cdots & \operatorname{tr}A^2 & \operatorname{tr}A \end{vmatrix} ~.</math>

Ein Vergleich mit der [[Bell-Polynom#Vollständige Bell-Polynome|Determinantendarstellung der vollständigen Bell-Polynome]] <math> {\mathcal B}_k </math> (vgl. z. B. A. Zúñiga-Segundo et al.<ref> 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, [http://www.asiamath.org/issue1/AM-1904-3103.pdf Online-Version des Artikels]</ref> und <ref> 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, [http://idosi.org/weasj/9(3)18/3.pdf Online-Version des Artikels]</ref>) zeigt, dass man dies äquivalent dazu auch etwas bequemer folgendermaßen ausdrücken kann:

:<math> c_{n-k} = \frac{(-1)^k}{k!} \; {\mathcal B}_k \Bigl ( 0! ~\operatorname{tr}A , -1! ~ \operatorname{tr}A^2, 2! ~\operatorname{tr}A^3, \ldots, (-1)^{k-1} (k-1)! ~ \operatorname{tr}A^k\Bigr ) </math>

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 ==

Mit Hilfe der Matrizen <math> B_0,\ldots, B_n \in R^{n\times n}</math> kann man die Formeln für die Koeffizienten <math> c_0,\ldots , c_n \in R </math> aus der Motivation
in folgendes rekursives Schema übersetzen
(Nachweis durch Induktion nach <math> k </math>, siehe [[#Begründung für die Korrektheit des Algorithmus|Begründung für die Korrektheit des Algorithmus]] weiter unten):

:<math>
\begin{align}
B_0 &= 0 & c_n &= 1 \qquad &(k=0) \\
B_k &= AB_{k-1} + c_{n-k+1} I \qquad \qquad & c_{n-k} &= -\frac 1 k \mathrm{tr}(AB_k) \qquad &k=1,\ldots ,n
\end{align}
</math>

Hierin ist <math>\textstyle \mathrm{tr}(M) := \sum_{i=1}^n m_{ii} </math> die sogenannte [[Spur (Mathematik)|Spur]] einer quadratischen Matrix <math> M \in R^{n\times n}</math>

Aus der Rekursion lassen sich weitere interessante Beziehungen ableiten:

* Wegen
:<math> c_0 = p(0) = \det(-A) = (-1)^n \; \det A </math>

erhält man unmittelbar den Wert der [[Determinante (Mathematik)|Determinanten]] von <math> A </math>.
* Außerdem kann man mit Hilfe von

:<math> B_{n+1} = AB_{n} + c_{0} I = 0 \; </math>

überprüfen, ob die Rekursion korrekt terminiert. Durch Umformen erhält man hieraus für [[reguläre Matrix|reguläres]] <math>A</math> insbesondere auch die [[Inverse]]:

:<math> A^{-1} = - \frac 1 {c_0} B_n \qquad \textrm{(falls} \; c_0\neq 0\textrm{)} .</math>

* Schließlich folgt wegen <math> A \cdot \operatorname{adj}(A) = \operatorname{det}A \cdot I </math> für die [[Adjunkte]]:

:<math> \operatorname{adj}(A) = (-1)^{n+1} B_n </math>

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

<syntaxhighlight lang="C">
/* 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)
* /
</syntaxhighlight>

== Numerisches Beispiel ==

Für Matrizen kleiner Dimension lässt sich der Algorithmus leicht von Hand durchzuführen. Wir betrachten folgendes einfaches Beispiel:

:<math>
A = \left[ \begin{array}{rrr}
3 & 1 & 5 \\
3 & 3 & 1 \\
4 & 6 & 4
\end{array}
\right]
</math>

Dann liefert der Algorithmus:

:<math>
\begin{align}
B_0 &= \left[ \begin{array}{rrr}
0 & 0 & 0 \\
0 & 0 & 0 \\
0 & 0 & 0
\end{array}
\right] \qquad \qquad &&& c_3 &&&&&= &1 \\
B_{\mathbf{\color{blue}1}} &= \left[ \begin{array}{rrr}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{array}
\right] \qquad \qquad
&A*B_1 &= \left[ \begin{array}{rrr}
\mathbf{\color{red} 3} & 1 & 5 \\
3 & \mathbf{\color{red} 3} & 1 \\
4 & 6 & \mathbf{\color{red} 4}
\end{array}
\right] \qquad \qquad
&c_2 &&&= -\frac 1 {\mathbf{\color{blue}1}} \cdot \mathbf{\color{red} 10} &&= &-10 \\
B_{\mathbf{\color{blue}2}} &= \left[ \begin{array}{rrr}
-7 & 1 & 5 \\
3 & -7 & 1 \\
4 & 6 & -6
\end{array}
\right] \qquad \qquad
&A*B_2 &= \left[ \begin{array}{rrr}
\mathbf{\color{red} 2} & 26 & -14 \\
-8 & \mathbf{\color{red} -12} & 12 \\
6 & -14 & \mathbf{\color{red} 2}
\end{array}
\right] \qquad \qquad
&c_1 &&&= -\frac 1 {\mathbf{\color{blue}2}} \cdot \mathbf{\color{red} (-8)} &&= &4 \\
B_{\mathbf{\color{blue}3}} &= \left[ \begin{array}{rrr}
6 & 26 & -14 \\
-8 & -8 & 12 \\
6 & -14 & 6
\end{array}
\right] \qquad \qquad
&A*B_3 &= \left[ \begin{array}{rrr}
\mathbf{\color{red} 40} & 0 & 0 \\
0 & \mathbf{\color{red} 40} & 0 \\
0 & 0 & \mathbf{\color{red} 40}
\end{array}
\right] \qquad \qquad
&c_0 &&&= -\frac 1 {\mathbf{\color{blue}3}} \cdot \mathbf{\color{red} 120} &&= &-40
\end{align}
</math>

Es zeigt sich, dass <math> B_4 = A*B_3 + c_0 * I = 0</math>, was eine zusätzliche Kontrolle für
die Korrektheit der Rechnung ist (s. o.).

Das charakteristische Polynom der Matrix <math> A </math> lautet also:
:<math> p_A(\lambda) = \lambda^3 -10 \lambda^2 + 4\lambda - 40.</math>
Weiterhin gilt:
:<math> \det(A) = (-1)^{3} \cdot c_0 = 40 </math>
Für die Inverse von <math> A </math> ergibt sich aus der obigen Rechnung:
:<math> A^{-1} = -\frac 1 {c_0} \cdot B_3
= \frac 1 {40} \cdot
\left[ \begin{array}{rrr}
6 & 26 & -14 \\
-8 & -8 & 12 \\
6 & -14 & 6
\end{array}
\right]
= \left[ \begin{array}{rrr}
0{,}15 & 0{,}65 & -0{,}35 \\
-0{,}20 & -0{,}20 & 0{,}30 \\
0{,}15 & -0{,}35 & 0{,}15
\end{array}
\right]
</math>

== Begründung für die Korrektheit des Algorithmus ==

Für die [[Korrektheit (Informatik)|Korrektheit]] des Algorithmus muss man dessen [[Terminiertheit]] und [[partielle Korrektheit]] nachweisen.
Dass der Algorithmus stets [[Terminiertheit|terminiert]], ist offensichtlich. Die [[partielle Korrektheit]] des
Algorithmus folgt, wenn die per Rekursion ermittelten Koeffizienten <math> c_0, \ldots, c_n </math> mit der in der Motivation hergeleiteten Darstellung übereinstimmen.

Zu diesem Zweck weisen wir induktiv nach, dass die Rekursion im <math>k</math>-ten Schritt die folgenden Ergebnisse liefert:

:<math>
\begin{align}
B_k =& \qquad \sum_{i=1}^k c_{n-k+i}A^{i-1} \\
c_{n-k} =& - \frac 1 k \sum_{i=1}^k c_{n-k+i} \operatorname{tr}~A^i
\end{align}
</math>

Für den ersten Rekursionsschritt (<math>k=1</math>) sind die beiden Beziehungen wegen <math> B_1 = I </math> und <math> c_{n-1} = - \operatorname{tr}~A </math> offensichtlich erfüllt.

Um die Gültigkeit für den <math>(k+1)-</math>ten Schritt zu zeigen, nehmen wir an, dass die Beziehungen für den <math>k-</math>ten Schritt richtig sind (Schluss von <math> k </math> auf <math> k+1 </math>):

:<math>
\begin{align}
B_{k+1} =& AB_k + c_{n-k}I \\
=& A \left( \sum_{i=1}^k c_{n-k+i}A^{i-1} \right) + c_{n-k}I \\
=& \sum_{i=1}^{k+1} c_{n-(k+1)+i}A^{i-1} \quad \checkmark
\end{align}
</math>

:<math>
\begin{align}
c_{n-(k+1)} =& -\frac 1 {k+1} \mathrm{tr}(AB_{k+1}) \\
=& -\frac 1 {k+1} \mathrm{tr}\left(A \sum_{j=1}^{k+1} c_{n-(k+1)+j}A^{j-1}\right)\\
=& -\frac 1 {k+1} \sum_{j=1}^{k+1} c_{n-(k+1)+j} ~\mathrm{tr} A^{j} \quad \checkmark \\
\end{align}
</math>

== Alternative Zugänge zum Algorithmus ==

Der Weg über die [[Newton-Identitäten]] (wie oben vorgeführt und z. B. in Gantmacher<ref>[[Felix Ruwimowitsch Gantmacher|F. R. Gantmacher]]: ''The Theory of Matrices'', Chelsea, 1990, siehe speziell Kapitel IV §5, S. 87–89 </ref>) 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 [[Lineare Algebra|Linearen Algebra]] bietet. Insbesondere erscheint die Notwendigkeit zur Verwendung der Matrizen <math> B_k </math> etwas künstlich.

Daher verfolgen einige Darstellungen in der Literatur einen anderen Ansatz und motivieren zunächst die rekursive Darstellung für die Matrizen <math> B_k </math> (vgl.<ref>J. S. Frame: ''Matrix functions and applications'', IEEE Spectrum 1 (1964) (fünf Artikel in den Nummern 3–7)</ref> und Beweisarchiv auf den Wikibooks, siehe [[#Weblinks|Weblinks]]):

Der bekannte Zusammenhang zwischen [[Determinante (Mathematik)|Determinante]] und [[Adjunkte]] angewendet auf die Matrix <math> \lambda I - A </math> ergibt:

:<math> (\lambda I - A) \cdot \mathrm{adj}(\lambda I - A) = \det(\lambda I - A) \cdot I = p_A(\lambda) \cdot I </math>

Hieraus folgt, dass <math> \lambda\; </math> in <math> \mathrm{adj}(\lambda I - A) \; </math>
höchstens mit Grad <math> n-1 \; </math> auftritt, so dass sich <math>\mathrm{adj}(\lambda I - A) \; </math> als Polynom in <math> \lambda </math> mit Matrix-Koeffizienten <math> B_k \in \mathbb{C}^{n\times n} \; (k=0,\ldots,n+1) \;</math> schreiben lässt (wobei <math> B_0 = 0 \;</math> und <math> B_{n+1} = 0 \;</math>):

:<math> \mathrm{adj}(\lambda I - A) = \sum_{k=0}^{n+1} B_k \lambda^{n-k} </math>

Einsetzen und Umformen liefert:

:<math>
\begin{align}
(\lambda I - A) \cdot \sum_{k=0}^{n+1} B_k \lambda^{n-k} &= p_A(\lambda) \cdot I \\
\sum_{k=1}^{n+1} \left( B_k - AB_{k-1} \right) \lambda^{n-k+1} &= \sum_{k=1}^{n+1} c_{n-k+1} \lambda^{n-k+1} \cdot I
\end{align}
</math>

Durch [[Koeffizientenvergleich]] erhält man schließlich die rekursive Darstellung für die <math> B_k </math>:

:<math> B_k - AB_{k-1} = c_{n-k+1} I \quad \Longleftrightarrow \quad B_k = AB_{k-1} + c_{n-k+1} I </math>

Zur Ableitung der Beziehung für die Koeffizienten <math> c_{n-k} </math> 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
* [[Determinante (Mathematik)#Ableitung|Jacobi’s Formel zur Differentiation von Determinanten-Funktionen]] (vgl.<ref>J. S. Frame: ''Matrix functions and applications'', IEEE Spectrum 1 (1964) (fünf Artikel in den Nummern 3–7)</ref> und Beweisarchiv auf den Wikibooks, siehe [[#Weblinks|Weblinks]])
* die [[Laplace-Transformation|Laplace-Transformierte]] des [[Matrixexponential]] <math> \mathcal{L}(e^{tA}) = (sI-A)^{-1} </math> welche gerade der [[Resolvente]] von <math> A </math> entspricht (vgl. Hou<ref>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]]</ref>)

verwendet.

== Anwendungsbereich und Voraussetzungen ==

Wie bereits in der Einleitung erwähnt, ist der Algorithmus nur dann auf die Matrix <math>A\in R^{n\times n} </math> anwendbar, wenn der Ring <math> R </math> der Matrixelemente ein [[kommutativer Ring]] mit [[Einselement]] ist und eine der beiden folgenden Voraussetzungen erfüllt ist (vgl. Johannson<ref>F. Johannson: ''On a fast and nearly division-free algorithm for the characteristic polynomial''. Preprint (2020), {{arXiv|2011.12573}}</ref>):
* <math> R </math> hat die [[Charakteristik (Algebra)|Charakteristik]] 0 (wie z. B. für <math> R=\mathbb{R} </math> oder <math> R=\mathbb{C} </math>)
* Die [[Charakteristik (Algebra)|Charakteristik]] von <math> R </math> ist [[teilerfremd]] zu <math> k \in\{1,\ldots, n\} </math>

Diese Bedingung stellt sicher, dass die im Algorithmus auftretenden Divisionen durch <math> k \in \{1,\ldots , n \}</math> im Ring <math> R </math> exakt durchführbar sind, d. h. dass
:<math> (xk)/k = x \qquad \forall x\in R, k\leq n </math>

Ein genereller Nachteil des Algorithmus von Faddejew-Leverrier ist das Auftreten von Divisionen, was konträr zur Definition der Determinante über die [[Determinante#Leibniz-Formel|Leibniz-Formel]] ist, die ohne Divisionen auskommt und daher auch auf Matrizen anwendbar ist, deren Einträge Elemente eines beliebigen [[Kommutativer Ring|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 ==

Der Zeitaufwand für den Algorithmus von Faddejew-Leverrier wird von den auftretenden <math>n</math> [[Matrizenmultiplikation]]en dominiert.
Wenn man nun mit <math> \mathcal{O}(n^\omega )</math> 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 <math>\mathcal{O}(n^{\omega +1 })</math>.

Beispiele:

* Klassische Matrizenmultiplikation (<math> \omega = 3 </math>): Aufwand <math> \mathcal{O}(n^4) </math>
* [[Strassen-Algorithmus]] (<math> \omega = \log_2 7 \approx 2{,}807 </math>): Aufwand <math> \mathcal{O}(n^{3{,}807}) </math>

=== Determinantenberechnung nach der Leibniz-Formel ===
Der naive Algorithmus basierend auf der Determinantenberechnung nach der [[Determinante#Leibniz-Formel|Leibniz-Formel]] ermittelt und addiert <math> n! </math> Summanden was nach der [[Stirlingsche Formel|Stirlingschen Formel]] einer asymptotischen Zeitkomplexität von <math> \mathcal{O}(n!)=\mathcal{O}\left((\tfrac{n}{e})^{n+\frac 1 2}\right) </math> entspricht.

Neben dem exponentiellen Aufwand macht auch die Notwendigkeit von [[Computeralgebra#Polynome|Polynomarithmetik]] diesen Ansatz inpraktikabel.

=== Gauß-Elimination ===
Die Berechnung mittels [[Gaußsches Eliminationsverfahren|Gauß-Elimination]] mit einem Aufwand der Größenordnung <math>\mathcal{O}(n^3)</math> 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 [[Computeralgebra#Polynome|Polynomarithmetik]] für die Matrixeinträge).

=== Algorithmus von Samuelson-Berkowitz ===
Der [[Algorithmus von Samuelson-Berkowitz]] hat ebenfalls eine asymptotische obere Schranke von <math> \mathcal{O}(n^4) </math> für die Zeitkomplexität.

== Parallelisierbarkeit ==

Der Algorithmus lässt sich effizient parallelisieren. Genaueres hierzu findet man in der Originalarbeit von Csanky<ref name="CS76">L. Csanky: ''Fast Parallel Matrix Inversion Algorithms''. SIAM Journal on Computing, 618–623, 1976, [[doi:10.1137/0205040]]</ref> sowie in der Übersicht in ''Algorithmen zur parallelen Determinantenberechnung''.<ref>H. Burbach: ''Algorithmen zur parallelen Determinantenberechnung''. Diplom-Arbeit, Universität Dortmund, Oktober 1992, [http://www.hburbach.de/diplom.pdf Online-Version] (PDF-Datei; 801 kB)</ref>

== Numerische Stabilität ==

Der Algorithmus von Faddejew-Leverrier ist numerisch nicht stabil (siehe z. B. Wilkinson<ref>[[James Hardy Wilkinson|J. H. Wilkinson]]: ''The algebraic eigenvalue problem'', volume 87. Clarendon press Oxford, 1965, ISBN 978-0-19-853418-1, Kapitel 7, §19, S. 434–435 </ref> und Rehman/Ipsen<ref>R. Rehman and [[Ilse Ipsen|I. C. F. Ipsen]]: ''La Budde's Method for Computing Characteristic Polynomials''. Preprint (2011), {{arXiv|1104.3769}}</ref>).
Daher ist er für die Anwendung mit [[Gleitkomma-Arithmetik]] nicht gut geeignet, kann aber mit [[Computeralgebra#Effiziente exakte Arithmetik mit rationalen Zahlen|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.

== Historisches ==

Der Algorithmus wurde bereits 1840 von [[Urbain Jean Joseph Leverrier]] beschrieben,<ref>[[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), [https://gallica.bnf.fr/ark:/12148/bpt6k163849/f228n35.capture# Online-Version des Artikels] verfügbar auf der Webseite der [https://gallica.bnf.fr/ Bibliotheque nationale de France digital library (Gallica)]</ref> 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,<ref>Paul Horst: ''A method of determining the coefficients of a characteristic equation''. Ann. Math. Stat. 6, 83–84 (1935), [[doi:10.1214/aoms/1177732612]]</ref> [[Jean-Marie Souriau]],<ref>[[Jean-Marie Souriau]]: ''Une méthode pour la décomposition spectrale et l’inversion des matrices.'' Comptes Rend. 227, 1010–1011 (1948)</ref> [[Dmitri Faddejew|Dmitri Konstantinowitsch Faddejew]] und Sominski,<ref>D. K. Faddeev, I. S. Sominski: ''Sbornik zadatch po vyshej algebre''. Moskow-Leningrad 1949</ref> J. S. Frame,<ref>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]]</ref> U. Wegner<ref>U. Wegner: ''Bemerkungen zur Matrizentheorie''. Z. angew. Math. Mech. 33, 262–264 (1953), [[doi:10.1002/zamm.19530330807]]</ref> und Csanky.<ref name="CS76" /> 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.<ref>[[Alston Scott Householder]]: ''The Theory of Matrices in Numerical Analysis''. Dover, New York 1975, ISBN 0-486-61781-5</ref>

== Literatur ==

* H. Burbach: ''Algorithmen zur parallelen Determinantenberechnung''. Diplom-Arbeit, Universität Dortmund, Oktober 1992, [https://archive.org/download/diplom_201811/diplom.pdf Online-Version] (PDF-Datei; 801 kB)
* L. Csanky: ''Fast Parallel Matrix Inversion Algorithms''. SIAM Journal on Computing, 618–623, 1976, [[doi:10.1137/0205040]].
* [[Dmitri Konstantinowitsch Faddejew|D. K. Faddev]], I. S. Sominsky. Collection of problems on higher algebra, Moscow, 1949.
* [[Wera Faddejewa|V. N. Faddeva]]: ''Computational Methods of Linear Algebra'', (Translated From The Russian By Curtis D. Benster), Dover Publications Inc. N.Y., Date Published 1959, ISBN 0-486-60424-1.
* 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]].
* J. S. Frame: ''Matrix functions and applications'', IEEE Spectrum 1 (1964) (fünf Artikel in den Nummern 3–7)
* [[Felix Ruwimowitsch Gantmacher|F. R. Gantmacher]]: ''The Theory of Matrices'', Chelsea, 1990, siehe speziell §IV.5.
* [[Alston Scott Householder]]: ''The Theory of Matrices in Numerical Analysis'', Dover, New York, 1975, ISBN 0-486-61781-5
* Paul Horst: ''A method of determining the coefficients of a characteristic equation''. Ann. Math. Stat. 6, 83–84 (1935), [[doi:10.1214/aoms/1177732612]].
* 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
* F. Johannson: ''On a fast and nearly division-free algorithm for the characteristic polynomial''. Preprint (2020), {{arXiv|2011.12573}}
* [[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), [https://gallica.bnf.fr/ark:/12148/bpt6k163849/f228n35.capture# Online-Version des Artikels] verfügbar auf der Webseite der [https://gallica.bnf.fr/ Bibliotheque nationale de France digital library (Gallica)]
* R. Rehman and [[Ilse Ipsen|I. C. F. Ipsen]]: ''La Budde's Method for Computing Characteristic Polynomials''. Preprint (2011), {{arXiv|1104.3769}}
* [[Jean-Marie Souriau]]: ''Une méthode pour la décomposition spectrale et l’inversion des matrices.'' Comptes Rend. 227, 1010–1011 (1948).
* U. Wegner: Bemerkungen zur Matrizentheorie. Z. angew. Math. Mech. 33, 262–264 (1953), [[doi:10.1002/zamm.19530330807]].
* [[James Hardy Wilkinson|J. H. Wilkinson]]: ''The algebraic eigenvalue problem'', volume 87. Clarendon press Oxford, 1965, ISBN 978-0-19-853418-1.
* 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, [http://www.asiamath.org/issue1/AM-1904-3103.pdf Online-Version des Artikels]
* 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, [http://idosi.org/weasj/9(3)18/3.pdf Online-Version des Artikels]

== Weblinks ==

{{Wikibooks|Beweisarchiv: Lineare Algebra: Endomorphismen: Korrektheit des Algorithmus von Faddejew-Leverrier|Beweis der Korrektheit des Algorithmus von Faddejew-Leverrier}}

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus|Faddejew Leverrier]]
[[Kategorie:Numerische lineare Algebra]]

Algorithmus von Faddejew-Leverrier - Versionsgeschichte

imported>Leyo: Halbgeviertstrich