Weierstraß-(Durand-Kerner)-Verfahren
# Weierstraß-(Durand-Kerner)-Verfahren

Das Weierstraß-(Durand-Kerner)-Verfahren (W-(D-K)-Verfahren) ist ein iteratives Verfahren zur simultanen Bestimmung aller Nullstellen eines univariaten Polynoms. Es ist benannt nach Karl Weierstraß, der es als Teil eines Beweises zum Fundamentalsatz der Algebra zwischen 1859 und 1891 entwickelte, sowie E. Durand und Immo Kerner, die es 1960 bzw. 1966 in einen Computeralgorithmus überführten.

## Das Verfahren

Es sei $p(X)=X^{n}+p_{n-1}X^{n-1}+\cdots +p_{0}$ ein normiertes univariates Polynom mit komplexen Koeffizienten und mit führendem Koeffizienten 1. Dieses hat nach dem Fundamentalsatz der Algebra genau n Nullstellen $\xi _{1},\dots ,\xi _{n}\in \mathbb {C}$ und kann in Linearfaktoren zerlegt werden,

    $p(X)=(X-\xi _{1})\cdots (X-\xi _{n}).\,$

Aus dieser Formel kann jede der Nullstellen formal isoliert werden, es gilt

    $\xi _{k}=X-{\frac {p(X)}{\prod _{j=1,\dots ,n,\;j\neq k}(X-\xi _{j})}}.$

Diese Formel kann als triviale Fixpunktiteration verstanden werden, die Iteration

    $z_{k}^{(i+1)}:=z_{k}^{(i)}-{\frac {p(z_{k}^{(i)})}{\prod _{j=1,\dots ,n,\;j\neq k}(z_{k}^{(i)}-\xi _{j})}}$

wird offensichtlich nach dem ersten Iterationsschritt in der Nullstelle $\xi _{k}$ stationär.

Ersetzt man nun in der Iterationsvorschrift die anderen Nullstellen durch gute Näherungen, so bleibt $\xi _{k}$ ein Fixpunkt und jede Iteration, die in der Nähe dieser Nullstelle startet, konvergiert auch gegen diese. Die Iteration des W-(D-K)-Verfahrens ergibt sich, wenn nun für alle Nullstellen gleichzeitig mittels dieser Iterationsvorschrift Näherungsfolgen bestimmt werden, und die jeweils bestimmte Näherung einer Nullstelle sofort in die Bestimmung der nächsten Näherungen der anderen Nullstellen eingeht.

Am Anfang eines jeden Iterationsschrittes stehen n paarweise verschiedene komplexe Zahlen $z_{1}^{(i)},\dots ,z_{n}^{(i)}\in \mathbb {C}$. Für den ersten Schritt können diese Zahlen $z_{1}^{(0)},\dots ,z_{n}^{(0)}\in \mathbb {C}$ zufällig, aber paarweise verschieden gewählt werden, in späteren Schritten stehen diese Zahlen für Approximationen der Nullstellen von p(X).

Dem Tupel ${\vec {z}}^{(i)}=(z_{1}^{(i)},\dots ,z_{n}^{(i)})$ wird das Polynom $g(X):=(X-z_{1}^{(i)})\cdot \ldots \cdot (X-z_{n}^{(i)})$ zugeordnet, das diese komplexen Zahlen als Nullstellen hat. Von diesem Polynom wird die Ableitung $g'(X)$ nach der Unbestimmten X bestimmt. Es gelten

    $g(z_{k}^{(i)})=0$ und $g'(z_{k}^{(i)})=\prod _{j\neq k}(z_{k}^{(i)}-z_{j}^{(i)}).$

Aus p(X) und der Ableitung $g_{{\vec {z}}^{(i)}}'(X)$ werden die Weierstraß-Korrekturen $w_{k}^{(i)}=-{\frac {p(z_{k}^{(i)})}{g'(z_{k}^{(i)})}}$, k = 1, ..., n bestimmt und das korrigierte Tupel ${\vec {z}}^{(i+1)}={\vec {z}}^{(i)}+{\vec {w}}^{(i)}=(z_{1}^{(i)}+w_{1}^{(i)},\dots ,z_{n}^{(i)}+w_{n}^{(i)})$ als Ergebnis und Eingabe des nächsten Iterationsschrittes erhalten.

Die Iteration kann z. B. abgebrochen werden, wenn die Korrektur eine zuvor festgelegte Rückgabegenauigkeit unterschreitet. (Die Rechengenauigkeit sollte etwas höher als diese Rückgabegenauigkeit sein.)

## Varianten des Verfahrens

Die oben angegebene Herleitung bestimmt die neuen Approximationen gleichzeitig, parallel, aus den alten Approximationen. In der einfachsten Implementierung der Methode werden aber die Aufdatierungen und damit die neuen Approximationen nacheinander, sequentiell, bestimmt. Daher bietet sich die Idee an, jede neue Approximation einer Nullstelle sofort anstelle der alten zu verwenden. Dieser Unterschied zwischen paralleler und sequentieller Aufdatierung entspricht dem analogen Vorgehen im Jacobi- und Gauß-Seidel-Verfahren zur iterativen Lösung linearer Gleichungssysteme.

Die sequentielle Variante konvergiert in vielen Fällen schneller, jedoch ist dieser Geschwindigkeitsvorteil schwer theoretisch zu fassen. Die parallele Variante erlaubt bei hohen Polynomgraden die Anwendung von Verfahren schneller Polynommultiplikation, wie Karatsuba oder Schönhage-Strassen in der Berechnung der Aufdatierung.

## Beispiel

Zu lösen sei die kubische Gleichung $x^{3}-3x^{2}+3x-5=0$. Als Starttupel werde $(z_{1},z_{2},z_{3})=(a^{0},a^{1},a^{2})$ mit dem komplexen Parameter $a=0{,}4+0{,}9\cdot i$ gewählt. Es ergeben sich die folgenden ersten Iterationsschritte für die parallele Variante der Iteration

| It.-Nr. | $z_1$ | $z_2$ | $z_3$ |
| - | - | - | - |
| 0 | +1,000000 + 0,000000i | +0,400000 + 0,900000i | −0,650000 + 0,720000i |
| 1 | +1,360773 + 2,022230i | −1,398213 − 0,693566i | +3,037440 − 1,328664i |
| 2 | +0,980963 + 1,347463i | −0,335252 − 0,644069i | +2,354289 − 0,703394i |
| 3 | +0,317181 + 0,936495i | +0,490016 − 0,966141i | +2,192804 + 0,029647i |
| 4 | +0,209016 + 1,572742i | +0,041206 − 1,527519i | +2,749778 − 0,045223i |
| 5 | +0,212971 + 1,394827i | +0,184678 − 1,384565i | +2,602351 − 0,010262i |
| 6 | +0,206531 + 1,374879i | +0,206001 − 1,374653i | +2,587468 − 0,000226i |
| 7 | +0,206300 + 1,374730i | +0,206299 − 1,374730i | +2,587401 − 0,000000i |
| 8 | +0,206299 + 1,374730i | +0,206299 − 1,374730i | +2,587401 + 0,000000i |

und für die sequentielle Variante der Iteration

| It.-Nr. | $z_1$ | $z_2$ | $z_3$ |
| - | - | - | - |
| 0 | +1,000000 + 0,000000i | +0,400000 + 0,900000i | −0,650000 + 0,720000i |
| 1 | +1,360773 + 2,022230i | −0,365804 + 2,483787i | −2,385807 − 0,028361i |
| 2 | +2,659661 + 2,713714i | +0,597676 + 0,822483i | −0,631985 − 1,671566i |
| 3 | +2,270389 + 0,387972i | +0,131179 + 1,312808i | +0,282054 − 1,501550i |
| 4 | +2,542817 − 0,015337i | +0,204444 + 1,371609i | +0,205573 − 1,372072i |
| 5 | +2,587418 − 0,000012i | +0,206300 + 1,374733i | +0,206299 − 1,374730i |
| 6 | +2,587401 − 0,000000i | +0,206299 + 1,374730i | +0,206299 − 1,374730i |
| 7 | +2,587401 − 0,000000i | +0,206299 + 1,374730i | +0,206299 − 1,374730i |

In den ersten 4 Iterationen beider Varianten wird das Tripel $(z_{1},z_{2},z_{3})$ scheinbar chaotisch bewegt, ab dem 5 Schritt bleiben zunehmend mehr Dezimalstellen konstant, Iteration 8 im parallelen bzw. 7 im sequentiellen Fall bestätigen die Korrektheit von Iteration 7 bzw. 6 im Rahmen der angegebenen Genauigkeit. Dieses allgemeine Verhalten ist charakteristisch für diese Methode.

Als Gleichung 3. Grades mit reellen Koeffizienten hat p(X) eine reelle Nullstelle und ein konjugiertes Paar komplexer Nullstellen. Die Näherungen erfüllen dieses Muster. Nach dem Satz von Vieta muss z. B. die Summe aller Nullstellen dem Negativen des Koeffizienten zweithöchsten Grades entsprechen, also 3 sein. Auch dies bestätigt sich in den Näherungen.

## Begründung als Newton-Verfahren

Die – wenigstens lokale – Konvergenz der Weierstraß-Iteration ergibt sich aus ihrer Interpretation als mehrdimensionales Newton-Verfahren. Das Gleichungssystem dazu ergibt sich aus dem Vergleich der Koeffizienten gleichen Grades in der angestrebten Identität

    $g({\vec {z}})(X)=\prod _{j=1}^{n}(X-z_{j})=p(X).$

Da die Polynome auf beiden Seiten normiert sind (der höchstgradige Koeffizient ist 1), ist die Identität im Grad n trivial und es ergeben sich n Gleichungen für die n Unbekannten.

Im Allgemeinen ist diese Identität nicht erfüllt. Die Korrektur ${\vec {w}}=(w_{1},\dots ,w_{n})$ in jedem Schritt der Newton-Iteration ergibt sich aus der Forderung, dass die Identität

    $g({\vec {z}}+{\vec {w}})(X)=\prod _{j=1}^{n}(X-z_{j}-w_{j})=p(X)$

in erster Ordnung in ${\vec {w}}$ erfüllt sei. Aus der Taylor-Entwicklung erster Ordnung ergibt sich die in ${\vec {w}}$ lineare Gleichung

    $g({\vec {z}})(X)-\sum _{k=1}^{n}w_{k}\,\prod _{j\neq k}(X-z_{j})=p(X).$

Jede einzelne Korrektur $w_{k}$ kann daraus durch Einsetzen von $X=z_{k}$ zu

    $w_{k}=-{\frac {p(z_{k})-g({\vec {z}})(z_{k})}{\prod _{j\neq k}(z_{k}-z_{j})}}=-{\frac {p(z_{k})}{\partial _{X}g({\vec {z}})(z_{k})}}$

gewonnen werden, was die oben angegebene Weierstraß-Korrektur ergibt.

Ein globaler Konvergenzbeweis für dieses Verfahren wurde schon in (K. Weierstraß 1891) als alternativer Beweis für den Fundamentalsatz der Algebra angegeben.

## Fehlerschätzung mittels Gerschgorin-Kreisen

Eine Fehlerabschätzung und eine alternative Herleitung des Verfahrens ist im Artikel zum Satz von Gerschgorin angegeben. Danach sind in jedem Iterationsschritt alle Nullstellen des Polynoms p(X) in der Vereinigung der Kreisscheiben $D{\bigz_{k}+w_{k},(n-1)\cdot |w_{k}|{\big )}$ enthalten. Sind die Kreisscheiben paarweise disjunkt, so enthält jede genau eine Nullstelle. (A. Neumaier 2003) zeigt die gleiche Aussage für die etwas kleineren Kreisscheiben $D{\bigz_{k}+n/2\cdot w_{k},n/2\cdot |w_{k}|{\big )}.$

## Nicht-generelle Konvergenz

Das Weierstrass / Durand-Kerner-Verfahren ist nicht generell konvergent (d. h. für ein gegebenes Polynom ist die Menge der Startvektoren, die gegen die Nullstellen konvergieren, nicht offen und dicht). In der Tat gibt es eine offene Menge von Polynomen und eine offene Menge von Startvektoren, die gegen periodische Zyklen konvergieren, die nicht Nullstellen sind (siehe Reinke et al). Beispielsweise hat das Polynom $z^{3}+z+177$ eine offene Menge von Startvektoren, die gegen einen Zyklus der Länge 4 konvergieren.

