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 p(X)=Xn+pn−1Xn−1+⋯+p0p(X)=X^n+p_{n-1}X^{n-1}+\dots+p_0 ein normiertes univariates Polynom mit komplexen Koeffizienten und mit führendem Koeffizienten 11. Dieses hat nach dem Fundamentalsatz der Algebra genau nn Nullstellen ξ1,…,ξn∈C\xi_1,\dots,\xi_n\in\mathbb C und kann in Linearfaktoren zerlegt werden,
p(X)=(X−ξ1)⋅…⋅(X−ξn)p(X)=(X-\xi_1)\cdot\ldots\cdot(X-\xi_n).
Aus dieser Formel kann jede der Nullstellen formal isoliert werden, es gilt
ξk=X−p(X)∏j=1,…,n,  j≠k(X−ξj)\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
zk(i+1):=zk(i)−p(zk(i))∏j=1,…,n,  j≠k(zk(i)−ξj)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 ξk\xi_k stationär.
Ersetzt man nun in der Iterationsvorschrift die anderen Nullstellen durch gute Näherungen, so bleibt ξk\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 nn zusätzliche, paarweise verschiedene komplexe Zahlen z1(i),…,zn(i)∈Cz_1^{(i)},\dots,z_n^{(i)}\in\mathbb C. Für den ersten Schritt können diese Zahlen z1(0),…,zn(0)∈Cz_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)p(X).
Dem Tupel z(i)=(z1(i),…,zn(i))\vec z^{(i)}=(z_1^{(i)},\dots,z_n^{(i)}) wird das Verschwindungspolynom gz(i)(X):=(X−z1(i))⋅…⋅(X−zn(i))g_{\vec z^{(i)}}(X):=(X-z_1^{(i)})\cdot\ldots\cdot(X-z_n^{(i)}) sowie dessen Ableitung gz(i)′(X)g_{\vec z^{(i)}}'(X) zugeordnet. Es gelten
gz(i)(zk(i))=0g_{\vec z^{(i)}}(z_k^{(i)})=0 und gz(i)′(zk(i))=∏j≠k(zk(i)−zj(i))g_{\vec z^{(i)}}'(z_k^{(i)})=\prod\limits_{j\ne k}(z_k^{(i)}-z_j^{(i)}).
Aus p(X)p(X) und der Ableitung gz(i)′(X)g_{\vec z^{(i)}}'(X) werden die Weierstraß-Korrekturen wk(i)=−p(zk(i))gz(i)′(zk(i))w_k^{(i)}=-\dfrac{p(z_k^{(i)})}{g_{\vec z^{(i)}}'(z_k^{(i)})}, k=1,…,nk=1,\dots ,n bestimmt und das korrigierte Tupel z(i+1)=z(i)+w(i)=(z1(i)+w1(i),…,zn(i)+wn(i))\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 x3−3x2+3x−5=0x^3-3x^2+3x-5=0. Als Starttupel werde (z1,z2,z3)=(a0,a1,a2)(z_1,z_2,z_3)=(a^0,a^1,a^2) mit dem komplexen Parameter a=0 4+0 9⋅i⁡a=0\, 4+0\, 9\cdot \i gewählt. Es ergeben sich die folgenden ersten Iterationsschritte
It.-Nr. z1z_{1} z2z_{2} z3z_{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 (z1,z2,z3)(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 p(X)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
gz(X)=∏j=1n(X−zj)=p(X)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 nn trivial und es ergeben sich nn Gleichungen für die nn Unbekannten.
Im Allgemeinen ist diese Identität nicht erfüllt. Die Korrektur w=(w1,…,wn)\vec w=(w_1,\dots,w_n) in jedem Schritt der Newton-Iteration ergibt sich aus der Forderung, dass
gz+w(X)=∏j=1n(X−zj)=p(X)g_{\vec z+\vec w}(X)=\prod\limits_{j=1}^n(X-z_j)=p(X)
in erster Ordnung in w\vec w erfüllt sei. Aus der Taylor-Entwicklung erster Ordnung ergibt sich die in w\vec w lineare Gleichung
∑k=1n(−wk)∏j≠k(X−zj)=p(X)−gz(X)\sum\limits_{k=1}^n(-w_k)\prod\limits_{j\ne k}(X-z_j)=p(X)-g_{\vec z}(X).
Jede einzelne Korrektur wkw_k kann daraus durch Einsetzen von X=zkX=z_k zu
wk=−p(zk)−gz(zk)∏j≠k(zk−zj)=−p(zk)gz′(zk) 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 p(X)p(X) in der Vereinigung der Kreisscheiben D(zk+wk,(n−1)⋅∣wk∣)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 D(z+n/2⋅wk,n/2⋅∣wk∣) 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 F(x)=0F(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.
 
 

Gott existiert, weil die Mathematik widerspruchsfrei ist, und der Teufel existiert, weil wir das nicht beweisen können.

Andre Weil

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е
Datenschutzerklärung

 

Numerische Verfahren