Weierstraß-Iteration für Polynomnullstellen

Die Weierstraß-Iteration für Polynomnullstellen (Karl Weierstraß, entwickelt 1859-1891), auch Durand-Kerner-Methode (E. Durand 1960, I. Kerner 1966) ist ein iteratives Verfahren zur simultanen Bestimmung aller Nullstellen eines univariaten Polynoms.

Das Verfahren

Es sei \(\displaystyle p(X)=X^n+p_{n-1}X^{n-1}+\dots+p_0\) ein normiertes univariates Polynom mit komplexen Koeffizienten und mit führendem Koeffizienten \(\displaystyle 1\). Dieses hat nach dem Fundamentalsatz der Algebra genau \(\displaystyle n\) Nullstellen \(\displaystyle \xi_1,\dots,\xi_n\in\mathbb C\) und kann in Linearfaktoren zerlegt werden,
\(\displaystyle p(X)=(X-\xi_1)\cdot\ldots\cdot(X-\xi_n)\).
Aus dieser Formel kann jede der Nullstellen formal isoliert werden, es gilt
\(\displaystyle \xi_k=X-\dfrac{p(X)}{\prod\limits_{j=1,\dots,n,\;j\ne k}(X-\xi_j)}\).
Diese Formel kann als triviale Fixpunktiteration verstanden werden, die Iteration
\(\displaystyle z_k^{(i+1)}:=z_k^{(i)}-\dfrac{p(z_k^{(i)})}{\prod\limits_{j=1,\dots,n,\;j\ne k}(z_k^{(i)}-\xi_j)}\)
wird offensichtlich nach dem ersten Iterationsschritt in der Nullstelle \(\displaystyle \xi_k\) stationär.
Ersetzt man nun in der Iterationsvorschrift die anderen Nullstellen durch gute Näherungen, so bleibt \(\displaystyle \xi_k\) ein Fixpunkt und jede Iteration, die in der Nähe dieser Nullstelle startet, konvergiert auch gegen diese. Die Weierstraß-Iteration 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 \(\displaystyle n\) zusätzliche, paarweise verschiedene komplexe Zahlen \(\displaystyle z_1^{(i)},\dots,z_n^{(i)}\in\mathbb C\). Für den ersten Schritt können diese Zahlen \(\displaystyle 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 \(\displaystyle p(X)\).
Dem Tupel \(\displaystyle \vec z^{(i)}=(z_1^{(i)},\dots,z_n^{(i)})\) wird das Verschwindungspolynom \(\displaystyle g_{\vec z^{(i)}}(X):=(X-z_1^{(i)})\cdot\ldots\cdot(X-z_n^{(i)})\) sowie dessen Ableitung \(\displaystyle g_{\vec z^{(i)}}'(X)\) zugeordnet. Es gelten
\(\displaystyle g_{\vec z^{(i)}}(z_k^{(i)})=0\) und \(\displaystyle g_{\vec z^{(i)}}'(z_k^{(i)})=\prod\limits_{j\ne k}(z_k^{(i)}-z_j^{(i)})\).
Aus \(\displaystyle p(X)\) und der Ableitung \(\displaystyle g_{\vec z^{(i)}}'(X)\) werden die Weierstraß-Korrekturen \(\displaystyle w_k^{(i)}=-\dfrac{p(z_k^{(i)})}{g_{\vec z^{(i)}}'(z_k^{(i)})}\), \(\displaystyle k=1,\dots ,n\) bestimmt und das korrigierte Tupel \(\displaystyle \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 zurückgegeben.
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.)
 
 

Beispiel

Zu lösen sei die kubische Gleichung \(\displaystyle x^3-3x^2+3x-5=0\). Als Starttupel werde \(\displaystyle (z_1,z_2,z_3)=(a^0,a^1,a^2)\) mit dem komplexen Parameter \(\displaystyle a=0\, 4+0\, 9\cdot \i\) gewählt. Es ergeben sich die folgenden ersten Iterationsschritte
It.-Nr. \(\displaystyle z_{1}\) \(\displaystyle z_{2}\) \(\displaystyle z_{3}\)
0 +1.0000+0.0000i +0.4000+0.9000i -0.6500+0.7200i
1 +1.3608+2.0222i -0.3658+2.4838i -2.3858-0.0284i
2 +2.6597+2.7137i +0.5977+0.8225i -0.6320-1.6716i
3 +2.2704+0.3880i +0.1312+1.3128i +0.2821-1.5015i
4 +2.5428-0.0153i +0.2044+1.3716i +0.2056-1.3721i
5 +2.5874+0.0000i +0.2063+1.3747i +0.2063-1.3747i
6 +2.5874+0.0000i +0.2063+1.3747i +0.2063-1.3747i
In den ersten 4 Iterationen wird das Tripel \(\displaystyle (z_1,z_2,z_3)\) scheinbar chaotisch bewegt, ab dem 5 Schritt bleiben zunehmend mehr Dezimalstellen konstant, Iteration 6 bestätigt die Korrektheit von Iteration 5 im Rahmen der angegebenen Genauigkeit. Dieses allgemeine Verhalten ist charakteristisch für diese Methode.
Als Gleichung 3. Grades mit reellen Koeffizienten hat \(\displaystyle p(X)\) eine reelle Nullstelle und ein konjugiertes Paar komplexer Nullstellen. Die Näherungen erfüllen dieses Muster. Nach der Satzgruppe 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
\(\displaystyle g_{\vec z}(X)=\prod\limits_{j=1}^n(X-z_j)=p(X)\).
Da die Polynome auf beiden Seiten normiert sind, ist die Identität im Grad \(\displaystyle n\) trivial und es ergeben sich \(\displaystyle n\) Gleichungen für die \(\displaystyle n\) Unbekannten.
Im Allgemeinen ist diese Identität nicht erfüllt. Die Korrektur \(\displaystyle \vec w=(w_1,\dots,w_n)\) in jedem Schritt der Newton-Iteration ergibt sich aus der Forderung, dass
\(\displaystyle g_{\vec z+\vec w}(X)=\prod\limits_{j=1}^n(X-z_j)=p(X)\)
in erster Ordnung in \(\displaystyle \vec w\) erfüllt sei. Aus der Taylor-Entwicklung erster Ordnung ergibt sich die in \(\displaystyle \vec w\) lineare Gleichung
\(\displaystyle \sum\limits_{k=1}^n(-w_k)\prod\limits_{j\ne k}(X-z_j)=p(X)-g_{\vec z}(X)\).
Jede einzelne Korrektur \(\displaystyle w_k\) kann daraus durch Einsetzen von \(\displaystyle X=z_k\) zu
\(\displaystyle w_k=-\dfrac{p(z_k)-g_{\vec z}(z_k)}{\prod\limits_{j\ne k}(z_k-z_j)} =-\dfrac{p(z_k)}{g_{\vec z}'(z_k)} \)
gewonnen werden, was die Korrektur der Weierstraß-Iteration 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 \(\displaystyle p(X)\) in der Vereinigung der Kreisscheiben \(\displaystyle D\big(z_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 \(\displaystyle D\big(z+n/2\cdot w_k,n/2\cdot|w_k|\big)\, \)

Literatur

  • Weierstraß, Karl (1891). "Neuer Beweis des Satzes, dass jede ganze rationale Function einer Veränderlichen dargestellt werden kann als ein Product aus linearen Functionen derselben Veränderlichen". Sitzungsberichte der königlich preussischen Akademie der Wissenschaften zu Berlin.
  • Durand, E. (1960). "Equations du type \(\displaystyle F(x)=0\): Racines d'un polynome". In: Solutions numeriques des equations algebriques, Editoren: Masson et al., vol. 1.
  • Bo Jacoby, Nulpunkter for polynomier, CAE-nyt (a periodical for Dansk CAE [!Gruppe] [Danish CAE Group]), 1988.
  • Agnethe Knudsen, Numeriske Metoder (lecture notes), Københavns Teknikum.
  • Bo Jacoby, Numerisk løsning af ligninger, Bygningsstatiske meddelelser (Published by Danish Society for Structural Science and Engineering) volume 63 no. 3-4, 1992, pp. 83-105.

Wer die erhabene Weisheit der Mathematik tadelt, nährt sich von Verwirrung.

Leonardo da Vinci

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Weierstraß-Iteration für Polynomnullstellen aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе