Algorithmus von Samuelson-Berkowitz

Algorithmus zur Ermittlung der Koeffizienten des charakteristischen Polynoms einer Matrix

Der Algorithmus von Samuelson-Berkowitz (nach Paul A. Samuelson und S. Berkowitz) ist ein Verfahren, das für beliebige quadratische Eingabematrizen die Koeffizienten des charakteristischen Polynoms von ermittelt, d. h. insbesondere auch die Determinante von . Im Gegensatz etwa zum Algorithmus von Faddejew-Leverrier sind die Voraussetzungen weniger restriktiv: Als Eingabe sind auch Matrizen zulässig, deren Einträge Elemente eines beliebigen kommutativen Rings mit Einselement sind, da das Verfahren völlig ohne Divisionen auskommt.

Notation und Idee des Verfahrens

Bearbeiten

Wir bezeichnen mit

  •   die  -Einheitsmatrix
  •   die  -Submatrix von   bestehend aus den ersten   Zeilen und Spalten
  •   das charakteristische Polynom von  , wobei  
  •   der Zeilenvektor mit den Komponenten   mit  
  •   der Spaltenvektor mit den Komponenten   mit  

und betrachten folgende Partitionierung von  :

 

Die grundlegende Idee des Verfahrens besteht darin, das charakteristische Polynom von   rekursiv zu berechnen. Mit der obigen Notation gilt zunächst

 

wobei   die Adjunkte von   bezeichnet (Begründung: Entwicklung nach letzter Zeile mittels Entwicklungssatz von Laplace, vgl.[1]).

Wenn man dies auf die Matrix   überträgt, dann erhält man speziell für das charakteristische Polynom von  :

 

Außerdem kann man leicht zeigen, dass sich die Adjunkte in (*) folgendermaßen schreiben lässt (siehe z. B.[1]):

 

Hierin sind   die Koeffizienten des charakteristischen Polynoms von  .

Formel von Samuelson

Bearbeiten

Wir erhalten nun die gewünschte rekursive Darstellung für das charakteristische Polynom   von   (in der Literatur Formel von Samuelson genannt), indem wir die beiden obigen Beziehungen (*) und (**) zusammenfügen:

 

Verfahren von Samuelson-Berkowitz

Bearbeiten

Matrix-Vektor Schreibweise

Bearbeiten

Um einen effektiven und leichter lesbaren Algorithmus formulieren zu können, transferieren wir nun die Formel von Samuelson in Matrix-Schreibweise. Dazu ordnen wir einem Polynom   vom Grad  

 

den Koeffizientenvektor

 

sowie die folgende Toeplitz-Matrix (die zugleich eine untere Dreiecksmatrix ist) zu:

 

Genauer ist also der Eintrag an der Position   von   gegeben durch

 

Definiert man nun noch das Polynom   durch

 

dann lässt sich die Formel von Samuelson in der folgenden kompakten Form darstellen (vgl.[2] und [3]):

 

Algebraische Top-Level Formulierung

Bearbeiten

Durch sukzessives Anwenden dieses Prinzips erhält man folgende zentrale Aussage (siehe [2] und [3]):

Mit  , also

 

gilt:

  • Die Koeffizienten des charakteristischen Polynoms   von   für   sind gegeben durch:
 
  • Insbesondere erhalten wir, falls  , die Koeffizienten des charakteristischen Polynoms   von   durch:
 

Algorithmus

Bearbeiten

Damit kann man nun folgenden Algorithmus formulieren (vgl.[4]):

 
 
 
  *  
  *  
 
 

Der Algorithmus berechnet nicht nur die Koeffizienten des charakteristischen Polynoms von  , sondern darüber hinaus auch in jedem Schleifendurchlauf für die Untermatrix  .

Historisches

Bearbeiten

Die grundlegende Idee des Verfahrens wurde zuerst 1942 von Paul A. Samuelson beschrieben und publiziert.[5] Der Algorithmus in der oben präsentierten und heute gebräuchlichen Form geht auf Berkowitz[3] (parallele Version) und Abdeljaoued[2] (Beschreibung als serielles Verfahren) zurück, weswegen man manchmal auch die Bezeichnung Samuelson-Berkowitz-Abdeljaoued-Algorithmus (SBA-Algorithmus) in der Literatur findet.[4]

Korrektheit des Algorithmus

Bearbeiten

Da im oben formulierten Verfahren nur endliche Schleifen auftreten, ist klar, dass der Algorithmus terminiert. Die partielle Korrektheit folgt aus der Formel von Samuelson und der daraus abgeleiteten algebraischen Top-Level-Formulierung in Matrix-Vektor-Form (s. o., vgl. z. B.[1]). Genauer gesprochen beruht die Korrektheit auf folgender Schleifeninvariante: Am Ende des  -ten Schleifendurchlaufs enthält der Vektor   die Koeffizienten des charakteristischen Polynoms von  (Formulierung als Nachbedingung).

Aufwand, Effizienz und Parallelisierbarkeit

Bearbeiten

Man kann zeigen[2], dass der Aufwand (Zeitkomplexität) des Algorithmus die Größenordnung   hat. Eine genauere Schranke ist gegeben durch die Anzahl der arithmetischen Operationen  . Bei der Implementierung des Verfahrens kann man zudem ausnutzen, dass es für die Multiplikation von Toeplitz-Matrizen effektive Methoden gibt. Der Algorithmus lässt sich auch sehr gut parallelisieren, genaueres dazu findet man speziell in [3].

Numerisches Beispiel

Bearbeiten

Wir betrachten die Matrix

 
Wir starten die Rekursion mit den charakteristischen Polynom der Matrix  , für das   gilt, d. h.
 
  •  :
Wir berechnen nun  . Hierzu benötigen wir zunächst die Koeffizienten von  :
  •  :
 
Also
 
Hieraus resultiert nun die Toeplitz-Matrix
 
und damit
 
Das charakteristische Polynom von   lautet also  
  •  :
Wir ermitteln die Koeffizienten von  :
  •  :
 
  •  :
 
Also
 
und
 
Damit erhalten wir
 
Das charakteristische Polynom von   lautet daher  
  •  :
Wir ermitteln die Koeffizienten von  :
  •  :
 
  •  :
 
  •  :
 
Also
 
und
 
Die finale Matrix-Vektor-Multiplikation liefert nun die Koeffizienten des gesuchten charakteristischen Polynoms der gesamten Matrix  :
 
Hieraus liest man das gesuchte Endergebnis ab:
 
Insbesondere erhält man also für die Determinante von  
 

Literatur

Bearbeiten
  • J. Abdeljaoued, The Berkowitz algorithm, Maple and computing the characteristic polynomial in an arbitrary commutative ring, MapleTech Vol. 4, No. 3, pp. 21-32, Birkhäuser Boston Basel Berlin, 1997
  • Stuart J. Berkowitz: On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, 18, pp. 147-150, 1985, doi:10.1016/0020-0190(84)90018-8
  • G. Nakos and Robert M. Williams: A Fast Computation of the Characteristic polynomial, Mathematica in Education and Research, Vol. 9, No. 1, 2000
  • Paul A. Samuelson: A method for determining explicitly the characteristic equation, Annals of Mathematical Statistics, 13, pp. 424-429, 1942, doi:10.1214/aoms/1177731540
  • Günter Rote: Division-free algorithms for the determinant and the Pfaffian: algebraic and combinatorial approaches , in: Computational Discrete Mathematics, Editor: Helmut Alt, Lecture Notes in Computer Science 2122, Springer-Verlag, 2001, pp. 119-135, Online-Version (PDF; 250 kB)
  • Michael Soltys: Berkowitz's Algorithm and Clow Sequences, The Electronic Journal of Linear Algebra (ELA), ISSN 1081-3810, Volume 9, pp. 42-54, April 2002, Online-Version (PDF; 168 kB)

Einzelnachweise

Bearbeiten
  1. a b c Michael Soltys: Berkowitz's Algorithm and Clow Sequences, The Electronic Journal of Linear Algebra (ELA), ISSN 1081-3810, Volume 9, pp. 42-54, April 2002, Online-Version (PDF; 168 kB)
  2. a b c d J. Abdeljaoued, The Berkowitz algorithm, Maple and computing the characteristic polynomial in an arbitrary commutative ring, MapleTech Vol. 4, No. 3, pp. 21-32, Birkhäuser Boston Basel Berlin, 1997
  3. a b c d Stuart J. Berkowitz: On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, 18, pp. 147-150, 1985, doi:10.1016/0020-0190(84)90018-8
  4. a b G. Nakos and Robert M. Williams: A Fast Computation of the Characteristic polynomial, Mathematica in Education and Research, Vol. 9, No. 1, 2000
  5. Paul A. Samuelson: A method for determining explicitly the characteristic equation, Annals of Mathematical Statistics, 13, S. 424–429, 1942, doi:10.1214/aoms/1177731540