imported>Sokrates 399: Typografie.

2026-02-14T17:52:30Z

Typografie.

Neue Seite

Der '''Algorithmus von Samuelson-Berkowitz''' (nach [[Paul A. Samuelson]] und S. Berkowitz) ist ein Verfahren, das für beliebige quadratische Eingabematrizen <math> A\in R^{n\times n} </math> die Koeffizienten des [[charakteristisches Polynom|charakteristischen Polynoms]] von <math> A </math> ermittelt, d. h. insbesondere auch die [[Determinante (Mathematik)|Determinante]] von <math> A </math>. Im Gegensatz etwa zum [[Algorithmus von Faddejew-Leverrier]] sind die Voraussetzungen weniger restriktiv: Als Eingabe sind auch Matrizen <math> A </math> zulässig, deren Einträge Elemente eines beliebigen [[kommutativer Ring|kommutativen Rings]] <math> R </math> mit Einselement sind, da das Verfahren völlig ohne Divisionen auskommt.

== Notation und Idee des Verfahrens ==

Wir bezeichnen mit

* <math> I_r \in R^{r\times r} </math> die <math>r\times r</math>-[[Einheitsmatrix]]
* <math> A_r \in R^{r\times r} \;</math> die <math>r\times r</math>-Submatrix von <math> A </math> bestehend aus den ersten <math>r</math> Zeilen und Spalten
* <math> p_r \in R[\lambda] \;</math> das charakteristische Polynom von <math> A_r\; </math>, wobei <math>p_r(\lambda)=\sum\limits_{k=0}^r c_{r-k} \lambda^k </math>
* <math> R_r \in R^{r} \; </math> der [[Zeilenvektor]] mit den Komponenten <math> a_{r+1,j} \; </math> mit <math> 1 \leq j \leq r </math>
* <math> S_r \in R^{r} \; </math> der [[Spaltenvektor]] mit den Komponenten <math> a_{i,r+1} \; </math> mit <math> 1 \leq i \leq r </math>

und betrachten folgende Partitionierung von <math> A_{r+1} </math>:

:<math> A_{r+1} = \left[ \begin{array}{c|c}
A_r & S_r \\ \hline
R_r & a_{r+1,r+1}
\end{array} \right] </math>

Die grundlegende Idee des Verfahrens besteht darin, das charakteristische Polynom von <math> A_{r+1}\; </math>
rekursiv zu berechnen.
Mit der obigen Notation gilt zunächst
:<math> \det(A_{r+1}) = a_{r+1,r+1} \det(A_r) - R_r \; \textrm{Adj}(A_r) \; S_r \; </math>
wobei <math> \textrm{Adj}(A_r) </math> die [[Adjunkte]] von <math> A_r\; </math> bezeichnet (Begründung: Entwicklung nach letzter Zeile mittels [[Laplace’scher Entwicklungssatz#Laplacescher Entwicklungssatz|Entwicklungssatz von Laplace]], vgl.<ref name="ms42-54">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, [http://www.emis.de/journals/ELA/ela-articles/articles/vol9_pp42-54.pdf Online-Version] (PDF; 168 kB)</ref>).

Wenn man dies auf die Matrix <math>\lambda I_{r+1} - A_{r+1} </math> überträgt, dann erhält man speziell für das charakteristische Polynom von <math> A_{r+1}\; </math>:
:<math> \begin{align}
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{align} </math>
Außerdem kann man leicht zeigen, dass sich die Adjunkte in (*) folgendermaßen schreiben lässt (siehe z. B.<ref name="ms42-54"/>):
:<math> \begin{align}
\textrm{Adj}(\lambda I_r - A_r) &= \sum\limits_{k=1}^r \left( \sum\limits_{j=1}^k A_r^{j-1} c_{k-j} \right) \lambda^{r-k}\\
&= \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 (**)
\end{align} </math>
Hierin sind <math> c_0, \ldots, c_{r-1}</math> die Koeffizienten des charakteristischen Polynoms von <math> A_r </math>.

== Formel von Samuelson ==

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

:<math> \begin{align}
p_{r+1}(\lambda) &= (\lambda - a_{r+1,r+1}) \; p_r(\lambda) - \sum_{k=1}^r \left[ \sum_{j=1}^k (R_r A_r^{j-1} S_r) c_{k-j} \right] \lambda^{r-k} \\
&= (\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_rS_r)c_{k-1} \right] \lambda^{r-k}
\end{align} </math>

== Verfahren von Samuelson-Berkowitz ==

=== Matrix-Vektor Schreibweise ===

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 <math> \omega\; </math> vom Grad <math> d </math>

:<math> \omega(\lambda) = \sum_{k=0}^d \alpha_k \lambda^{d-k} </math>

den Koeffizientenvektor

:<math> \overrightarrow{\omega} = \left[ \begin{array}{c} \alpha_0 \\ \alpha_1 \\ \alpha_2 \\ \vdots \\ \alpha_d \end{array} \right] \in R^{d+1} </math>

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

:<math> \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} </math>

Genauer ist also der Eintrag an der Position <math>(i,j)</math> von <math> \textrm{Toep}(\omega) </math> gegeben durch

:<math> \left[ \textrm{Toep}(\omega) \right]_{i,j} = \left\{ \begin{array}{cl}
\alpha_k & \textrm{falls}\;i\ge j \; \textrm{und} \; i-j=k \\
0 & \textrm{falls}\;i<j
\end{array}\right. </math>

Definiert man nun noch das Polynom <math> q_{r+1} \; </math> durch

:<math> \begin{align}
q_{r+1}(\lambda) &= \lambda^{r+1} - a_{r+1,r+1} \lambda^r - \sum\limits_{k=1}^r (R_r A_r^{k-1} S_r) \lambda^{r-k} \\
&= \lambda^{r+1} - a_{r+1,r+1} \lambda^r - (R_rS_r) \lambda^{r-1} - \ldots - (R_r A_r^{r-1}S_r) \end{align}</math>

dann lässt sich die Formel von Samuelson in der folgenden kompakten Form darstellen (vgl.<ref name="ja21-32">J. Abdeljaoued, ''[https://www.researchgate.net/profile/Tony_Scott6/publication/338884321_MapleTech_Volume_4_no_3_Winter_1997/links/5e30fe5f458515072d6ab5f1/MapleTech-Volume-4-no-3-Winter-1997.pdf#page=27 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 </ref> und <ref name="sjb147-150">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}} </ref>):

:<math> \overrightarrow{p_{r+1}} = \textrm{Toep}(q_{r+1}) \overrightarrow{p_r} </math>

=== Algebraische Top-Level Formulierung ===

Durch sukzessives Anwenden dieses Prinzips erhält man folgende zentrale Aussage (siehe <ref name="ja21-32"/> und <ref name="sjb147-150"/>):

Mit <math> p_1(\lambda)=\lambda - a_{11} \; </math>, also

:<math> \overrightarrow{p_1} = \left[ \begin{array}{c} 1 \\ -a_{11} \end{array} \right] = \textrm{Toep}(q_1)</math>

gilt:

* Die Koeffizienten des charakteristischen Polynoms <math> p_r(\lambda) \; </math> von <math> A_r \; </math> für <math> 1\leq r \leq n </math> sind gegeben durch:
:<math> \overrightarrow{p_r} = \textrm{Toep}(q_{r}) \cdot \textrm{Toep}(q_{r-1}) \cdots \textrm{Toep}(q_{1}) </math>
* Insbesondere erhalten wir, falls <math> r=n </math>, die Koeffizienten des charakteristischen Polynoms <math> p_n(\lambda) \; </math> von <math> A \; </math> durch:
:<math> \overrightarrow{p_n} = \textrm{Toep}(q_{n}) \cdot \textrm{Toep}(q_{n-1}) \cdots \textrm{Toep}(q_{1}) </math>

=== Algorithmus ===

Damit kann man nun folgenden Algorithmus formulieren (vgl.<ref name="gnrw">G. Nakos and Robert M. Williams: ''A Fast Computation of the Characteristic polynomial'', Mathematica in Education and Research, Vol. 9, No. 1, 2000 </ref>):

<math> \textrm{Eingabe:} \;\; (n \times n) - \textrm{Matrix} \; A\in R^{n\times n} </math>

<math> \overrightarrow{\textrm{Vect}} := \left[ \begin{array}{c} 1 \\ -a_{11} \end{array} \right] </math>
<math> \textbf{For} \; r=1,\ldots, n-1 \; \textrm{berechne} </math>
* <math> \left\{-R_r A_r^{k-1} S_r \right\}_{k=1}^r \; \textrm{(Koeffizienten}\;\textrm{von}\; q_{r+1}\;\textrm{)} </math>
* <math> \overrightarrow{\textrm{Vect}} := \textrm{Toep}(q_{r+1}) \cdot \overrightarrow{\textrm{Vect}} \;</math>
<math> \textbf{End}\;\textbf{For} </math>

<math> \textrm{Ausgabe:} \;\; \overrightarrow{p_n} = \overrightarrow{\textrm{Vect}} \;\;\textrm{(Vektor}\;\textrm{der}\;\textrm{Koeffizienten}\;\textrm{des}\;\textrm{charakteristischen}\;\textrm{Polynoms)}</math>

Der Algorithmus berechnet nicht nur die Koeffizienten des charakteristischen Polynoms von <math> A </math>, sondern
darüber hinaus auch in jedem Schleifendurchlauf für die [[Untermatrix]] <math> A_r </math>.

== Historisches ==

Die grundlegende Idee des Verfahrens wurde zuerst 1942 von [[Paul A. Samuelson]] beschrieben und publiziert.<ref>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]]</ref> Der Algorithmus in der oben präsentierten und heute gebräuchlichen Form geht auf Berkowitz<ref name="sjb147-150" /> (parallele Version) und Abdeljaoued<ref name="ja21-32" /> (Beschreibung als serielles Verfahren) zurück, weswegen man manchmal auch die Bezeichnung ''Samuelson-Berkowitz-Abdeljaoued-Algorithmus'' ''(SBA-Algorithmus)'' in der Literatur findet.<ref name="gnrw" />

== Korrektheit des Algorithmus ==

Da im oben formulierten Verfahren nur endliche Schleifen auftreten, ist klar, dass der Algorithmus [[Terminiertheit|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.<ref name="ms42-54"/>). Genauer gesprochen
beruht die Korrektheit auf folgender [[Schleifeninvariante]]: Am Ende des <math>r</math>-ten Schleifendurchlaufs
enthält der Vektor <math>\overrightarrow{\textrm{Vect}}</math> die Koeffizienten des charakteristischen Polynoms von
<math> A_{r+1} </math>(Formulierung als [[Nachbedingung (Informatik)|Nachbedingung]]).

== Aufwand, Effizienz und Parallelisierbarkeit ==

Man kann zeigen<ref name="ja21-32"/>, dass der Aufwand (Zeitkomplexität) des Algorithmus die Größenordnung <math> \mathcal{O}(n^4) </math> hat. Eine genauere Schranke ist gegeben durch die Anzahl der arithmetischen Operationen <math> \frac 1 2 n^4 - n^3 + \frac 5 2 n^2 </math>. Bei der Implementierung des Verfahrens kann man zudem ausnutzen, dass es für die [[Matrizenmultiplikation|Multiplikation]] von
Toeplitz-Matrizen effektive Methoden gibt.
Der Algorithmus lässt sich auch sehr gut parallelisieren, genaueres dazu findet man speziell in <ref name="sjb147-150"/>.

== Numerisches Beispiel ==

Wir betrachten die Matrix

:<math>
A=\left[ \begin{array}{rrrr}
5 & 5 & -3 & -7 \\
2 & 1 & 9 & 6 \\
4 & 2 & -6 & -5 \\
5 & -8 & -9 & 2
\end{array} \right]
</math>

:Wir starten die [[Rekursion]] mit den charakteristischen Polynom der Matrix <math> A_1 = [5] </math>, für das <math> p_1 = \lambda - 5 \;</math> gilt, d. h.
:<math> \overrightarrow{\textrm{Vect}} = \left[ \begin{array}{r} 1 \\ -5 \end{array} \right] </math>

* '''<math> r=1 </math>''':
:Wir berechnen nun <math> p_2 </math>. Hierzu benötigen wir zunächst die Koeffizienten von <math> q_2 </math>:
::* <math> k=1 </math>:
::<math> -R_1S_1 = -2*5=-10 \;</math>
:Also
:<math> \begin{align}
q_2 &= \lambda^2 - a_{22}\lambda - R_1S_1 \\
&= \lambda^2 - 1 \lambda - 10\;
\end{align}</math>
:Hieraus resultiert nun die Toeplitz-Matrix
:<math> \textrm{Toep}(q_2)=
\left[ \begin{array}{rr}
1 & 0 \\
- 1 & 1 \\
-10 & -1
\end{array} \right] </math>
:und damit
:<math> \begin{align}
\textrm{Toep}(q_2) * \overrightarrow{p_1} &= \overrightarrow{\textrm{Vect}} \\
\left[ \begin{array}{rr}
1 & 0 \\
- 1 & 1 \\
-10 & -1
\end{array} \right] *
\left[ \begin{array}{r}
1 \\ -5
\end{array} \right]
&=
\left[ \begin{array}{r}
1 \\
- 6 \\
- 5
\end{array} \right] \end{align}
</math>
:Das charakteristische Polynom von <math> A_2</math> lautet also <math> p_2=\lambda^2 -6 \lambda - 5 \;</math>
* '''<math> r=2 </math>''':
:Wir ermitteln die Koeffizienten von <math> q_3 </math>:
::* <math> k=1 </math>:
::<math> - R_2 A_2^0 S_2 = - \left[4 \;\; 2\right] \cdot \left[ \begin{array}{r} -3 \\ 9 \end{array} \right] = -6 </math>
::* <math> k=2 </math>:
::<math> -R_2 A_2^1 S_2 = - \left[4 \;\; 2\right] \cdot \left[ \begin{array}{rr} 5 & 5 \\ 2 & 1 \end{array} \right] \cdot \left[ \begin{array}{r} -3 \\ 9 \end{array} \right] = -126 </math>
:Also
:<math> \begin{align}
q_{3}(\lambda) &= \lambda^{3} - a_{3,3} \lambda^2 - (R_2S_2) \lambda^{1} - (R_2 A_2^{1}S_2) \\
&= \lambda^{3} + 6\lambda^2 - 6\lambda - 126
\end{align}
</math>
:und
:<math>
\textrm{Toep}(q_3)=
\left[ \begin{array}{rrr}
1 & 0 & 0 \\
6 & 1 & 0 \\
-6 & 6 & 1 \\
-126 & -6 & 6
\end{array} \right]
</math>
:Damit erhalten wir
:<math>
\begin{align}
\textrm{Toep}(q_3) * \overrightarrow{p_2} &= \overrightarrow{\textrm{Vect}} \\
\left[ \begin{array}{rrr}
1 & 0 & 0 \\
6 & 1 & 0 \\
-6 & 6 & 1 \\
-126 & -6 & 6
\end{array} \right] \cdot
\left[ \begin{array}{r}
1 \\
- 6 \\
- 5
\end{array} \right] &=
\left[ \begin{array}{r}
1 \\
0 \\
-47 \\
-120
\end{array} \right]
\end{align}
</math>
:Das charakteristische Polynom von <math> A_3</math> lautet daher <math> p_3=\lambda^3 -47 \lambda -120 \;</math>
* '''<math> r=3 </math>''':
:Wir ermitteln die Koeffizienten von <math> q_4 </math>:
::* <math> k=1 </math>:
::<math> - R_3 A_3^0 S_3 = - \left[5 \;\; -8 \;\; -9\right] \cdot \left[ \begin{array}{r} -7 \\ 6 \\ -5 \end{array} \right] = 38 </math>
::* <math> k=2 </math>:
::<math> - R_3 A_3^1 S_3 = - \left[5 \;\; -8 \;\; -9\right] \cdot
\left[\begin{array}{rrr}
5 & 5 & -3 \\
2 & 1 & 9 \\
4 & 2 & -6
\end{array}\right] \cdot
\left[ \begin{array}{r} -7 \\ 6 \\ -5 \end{array} \right] = -348 </math>
::* <math> k=3 </math>:
::<math> - R_3 A_3^2 S_3 = - \left[5 \;\; -8 \;\; -9\right] \cdot
\left[\begin{array}{rrr}
5 & 5 & -3 \\
2 & 1 & 9 \\
4 & 2 & -6
\end{array}\right]^2 \cdot
\left[ \begin{array}{r} -7 \\ 6 \\ -5 \end{array} \right] = 679 </math>
:Also
:<math> \begin{align}
q_{4}(\lambda) &= \lambda^{4} - a_{4,4} \lambda^3 - (R_3S_3) \lambda^{2} - (R_3 A_2^{1}S_3) \lambda - (R_3 A_2^{2}S_3) \\
&= \lambda^{4} -2 \lambda^3 +38 \lambda^2 - 348 \lambda + 679
\end{align}
</math>
:und
:<math>
\textrm{Toep}(q_4)=
\left[ \begin{array}{rrrr}
1 & 0 & 0 & 0 \\
-2 & 1 & 0 & 0 \\
38 & -2 & 1 & 0 \\
-348 & 38 & -2 & 1 \\
679 & -348 & 38 & -2
\end{array} \right]
</math>
:Die finale [[Matrix-Vektor-Multiplikation]] liefert nun die Koeffizienten des gesuchten charakteristischen Polynoms der gesamten Matrix <math> A=A_4 </math>:
:<math>
\begin{align}
\textrm{Toep}(q_4) * \overrightarrow{p_3} &= \overrightarrow{\textrm{Vect}} \\
\left[ \begin{array}{rrrr}
1 & 0 & 0 & 0 \\
-2 & 1 & 0 & 0 \\
38 & -2 & 1 & 0 \\
-348 & 38 & -2 & 1 \\
679 & -348 & 38 & -2
\end{array} \right] \cdot
\left[ \begin{array}{r}
1 \\
0 \\
-47 \\
-120
\end{array} \right] &=
\left[ \begin{array}{r}
1 \\ -2 \\ -9 \\ -374 \\ -867
\end{array} \right] \end{align} </math>
:Hieraus liest man das gesuchte Endergebnis ab:
:<math> p_4 = \lambda^4 -2\lambda^3 -9 \lambda^2 - 374 \lambda - 867 \;</math>
:Insbesondere erhält man also für die Determinante von <math> A </math>
:<math> p_4(0) = \det(-A) = (-1)^4\cdot \det(A) = -867 \; \Rightarrow \det (A) = -867 </math>

== Literatur ==

* 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, [http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms+for+the+determinant+and+the+Pfaffian:+algebraic+and+combinatorial+approaches.pdf 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, [http://www.emis.de/journals/ELA/ela-articles/articles/vol9_pp42-54.pdf Online-Version] (PDF; 168 kB)
== Einzelnachweise ==

<references />

[[Kategorie:Algorithmus|Samuelson Berkowitz]]
[[Kategorie:Numerische lineare Algebra]]

Algorithmus von Samuelson-Berkowitz - Versionsgeschichte

imported>Sokrates 399: Typografie.