Benutzer:Hightower74/Algorithmus von Samuelson-Berkowitz

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

Wir bezeichnen mit

• ${\displaystyle I_{r}\in R^{r\times r}}$ die ${\displaystyle r\times r}$-Einheitsmatrix
• ${\displaystyle A_{r}\in R^{r\times r}\;}$ die ${\displaystyle r\times r}$-Submatrix von ${\displaystyle A}$ bestehend aus den ersten ${\displaystyle r}$ Zeilen und Spalten
• ${\displaystyle p_{r}\in R[\lambda ]\;}$ das charakteristische Polynom von ${\displaystyle A_{r}\;}$, wobei ${\displaystyle p_{r}(\lambda )=\sum \limits _{k=0}^{r}c_{r-k}\lambda ^{k}}$
• ${\displaystyle R_{r}\in R^{r}\;}$ der Zeilenvektor mit den Komponenten ${\displaystyle a_{r+1,j}\;}$ mit ${\displaystyle 1\leq j\leq r}$
• ${\displaystyle S_{r}\in R^{r}\;}$ der Spaltenvektor mit den Komponenten ${\displaystyle a_{i,r+1}\;}$ mit ${\displaystyle 1\leq i\leq r}$

und betrachten folgende Partitionierung von ${\displaystyle A_{r+1}}$:

${\displaystyle A_{r+1}=\left[{\begin{array}{c|c}A_{r}&S_{r}\\\hline R_{r}&a_{r+1,r+1}\end{array}}\right]}$

Die grundlegende Idee des Verfahrens besteht darin, das charakteristische Polynom von ${\displaystyle A_{r+1}\;}$ rekursiv zu berechnen. Mit der obigen Notation gilt zunächst

${\displaystyle \det(A_{r+1})=a_{r+1,r+1}\det(A_{r})-R_{r}\;{\textrm {Adj}}(A_{r})\;S_{r}\;}$

wobei ${\displaystyle {\textrm {Adj}}(A_{r})}$ die Adjunkte von ${\displaystyle A_{r}\;}$ bezeichnet (Begründung: Entwicklung nach letzter Zeile bzw. Spalte mittels Entwicklungssatz von Laplace).

Speziell für das charakteristische Polynom von ${\displaystyle A_{r+1}\;}$ bedeutet das also:

${\displaystyle {\begin{aligned}p_{r+1}(\lambda )&=\det(\lambda I_{r+1}-A_{r+1})\\&=(\lambda -a_{r+1,r+1})\;p_{r}(\lambda )-R_{r}\;{\textrm {Adj}}(\lambda I_{r}-A_{r})\;S_{r}\qquad (*)\end{aligned}}}$

Außerdem lässt sich zeigen, dass sich die Adjunkte in (*) folgendermaßen schreiben lässt:

${\displaystyle {\textrm {Adj}}(\lambda I_{r}-A_{r})=\sum \limits _{k=1}^{r}\left(A_{r}^{k-1}c_{0}+\ldots +A_{r}^{1}c_{k-2}+I_{r}c_{k-1}\right)\;\lambda ^{r-k}\qquad (**)}$

Hierin sind ${\displaystyle c_{0},\ldots ,c_{r}}$ die Koeffizienten des charakteristischen Polynoms von ${\displaystyle A_{r}}$.

Wir erhalten nun die gewünschte rekursive Darstellung für das charakteristische Polynom ${\displaystyle p_{r+1}(\lambda )\;}$ von ${\displaystyle A_{r+1}\;}$ (in der Literatur Formel von Samuelson genannt), indem wir die beiden obigen Beziehungen (*) und (**) zusammenfügen:

${\displaystyle p_{r+1}(\lambda )=(\lambda -a_{r+1,r+1})\;p_{r}(\lambda )-\sum _{k=1}^{r}\left[(R_{r}A_{r}^{k-1}S_{r})c_{0}+\ldots +R_{r}A_{r}^{1}S_{r}c_{k-2}+(R_{r}S_{r})c_{k-1}\right]\lambda ^{r-k}}$

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 ${\displaystyle \omega \;}$ vom Grad ${\displaystyle d}$

${\displaystyle \omega (\lambda )=\sum _{k=0}^{d}\alpha _{k}\lambda ^{d-k}}$

den Koeffizientenvektor

${\displaystyle {\overrightarrow {\omega }}=\left[{\begin{array}{c}\alpha _{0}\\\alpha _{1}\\\alpha _{2}\\\vdots \\\alpha _{d}\end{array}}\right]\in R^{d}}$

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

${\displaystyle {\textrm {Toep}}(\omega )=\left[{\begin{array}{ccccc}\alpha _{0}&0&0&\ldots &0\\\alpha _{1}&\alpha _{0}&0&\ldots &0\\\alpha _{2}&\alpha _{1}&\alpha _{0}&\ldots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\\cdot &\cdot &\cdot &\ldots &a_{0}\\\alpha _{d}&\alpha _{d-1}&\alpha _{d-2}&\ldots &a_{1}\end{array}}\right]\in R^{(d+1)\times d}}$

Definiert man nun noch das Polynom ${\displaystyle q_{r+1}\;}$ durch

${\displaystyle q_{r+1}(\lambda )=\lambda ^{r+1}-a_{r+1,r+1}\lambda ^{r}-(R_{r}S_{r})\lambda ^{r-1}-\ldots -(R_{r}A_{r}^{r-1}S_{r})}$

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

${\displaystyle {\overrightarrow {p_{r+1}}}={\textrm {Toep}}(q_{r+1}){\overrightarrow {p_{r}}}}$

Die partielle Korrektheit des im Folgeabschnitt formulierten Algorithmus basiert auf der Gültigkeit der folgenden Aussage (siehe ^[3] und ^[4]):

Mit ${\displaystyle p_{1}(\lambda )=\lambda -a_{11}\;}$, also

${\displaystyle {\overrightarrow {p_{1}}}=\left[{\begin{array}{c}1\\-a_{11}\end{array}}\right]={\textrm {Toep}}(q_{1})}$

gilt:

• Die Koeffizienten des charakteristischen Polynoms ${\displaystyle p_{r}(\lambda )\;}$ von ${\displaystyle A_{r}\;}$ für ${\displaystyle 1\leq r\leq n}$ sind gegeben durch:

${\displaystyle {\overrightarrow {p_{r}}}={\textrm {Toep}}(q_{r})\cdot {\textrm {Toep}}(q_{r-1})\cdots {\textrm {Toep}}(q_{1})}$

• Insbesondere erhalten wir, falls ${\displaystyle r=n}$, die Koeffizienten des charakteristischen Polynoms ${\displaystyle p_{n}(\lambda )\;}$ von ${\displaystyle A\;}$ durch:

${\displaystyle {\overrightarrow {p_{n}}}={\textrm {Toep}}(q_{n})\cdot {\textrm {Toep}}(q_{n-1})\cdots {\textrm {Toep}}(q_{1})}$

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

${\displaystyle {\textrm {Eingabe:}}\;\;(n\times n)-{\textrm {Matrix}}\;A\in R^{n\times n}}$

${\displaystyle {\overrightarrow {\textrm {Vect}}}:=\left[{\begin{array}{c}1\\-a_{11}\end{array}}\right]}$
${\displaystyle {\textbf {For}}\;r=1,\ldots ,n-1\;{\textrm {berechne}}}$
   
  * ${\displaystyle \left\{-R_{r}A_{r}^{k-1}S_{r}\right\}_{k=1}^{r}\;{\textrm {(Koeffizienten}}\;{\textrm {von}}\;q_{r+1}\;{\textrm {)}}}$
  * ${\displaystyle {\overrightarrow {\textrm {Vect}}}:={\textrm {Toep}}(q_{r+1})\cdot {\overrightarrow {\textrm {Vect}}}\;}$
${\displaystyle {\textbf {End}}\;{\textbf {For}}}$

${\displaystyle {\textrm {Ausgabe:}}\;\;{\overrightarrow {p_{n}}}={\overrightarrow {\textrm {Vect}}}\;\;{\textrm {(Vektor}}\;{\textrm {der}}\;{\textrm {Koeffizienten}}\;{\textrm {des}}\;{\textrm {charakteristischen}}\;{\textrm {Polynoms)}}}$

Der Algorithmus berechnet nicht nur die Koeffizienten des charakteristischen Polynoms von ${\displaystyle A}$, sondern darüber hinaus auch in jedem Schleifendurchlauf für die Untermatrix ${\displaystyle A_{r}}$.

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

Man kann zeigen (siehe ^[10], dass der Aufwand (Zeitkomplexität) des Algorithmus die Größenordnung ${\displaystyle {\mathcal {O}}(n^{4})}$ hat. Eine genauere Schranke ist gegeben durch die Anzahl der arithmetischen Operationen ${\displaystyle {\frac {1}{2}}n^{4}-n^{3}+{\frac {5}{2}}n^{2}}$. 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 ^[11].

• 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

1. ↑ 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
2. ↑ 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
3. ↑ 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
4. ↑ 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
5. ↑ G. Nakos and Robert M. Williams: A Fast Computation of the Characteristic polynomial, Mathematica in Education and Research, Vol. 9, No. 1, 2000
6. ↑ 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
7. ↑ 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
8. ↑ 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
9. ↑ G. Nakos and Robert M. Williams: A Fast Computation of the Characteristic polynomial, Mathematica in Education and Research, Vol. 9, No. 1, 2000
10. ↑ 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
11. ↑ 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