Remove ads
Aus Wikipedia, der freien Enzyklopädie
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.
Es sei ein normiertes univariates Polynom mit komplexen Koeffizienten und mit führendem Koeffizienten 1. Dieses hat nach dem Fundamentalsatz der Algebra genau n Nullstellen und kann in Linearfaktoren zerlegt werden,
Aus dieser Formel kann jede der Nullstellen formal isoliert werden, es gilt
Diese Formel kann als triviale Fixpunktiteration verstanden werden, die Iteration
wird offensichtlich nach dem ersten Iterationsschritt in der Nullstelle stationär.
Ersetzt man nun in der Iterationsvorschrift die anderen Nullstellen durch gute Näherungen, so bleibt 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 . Für den ersten Schritt können diese Zahlen 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 wird das Polynom zugeordnet, das diese komplexen Zahlen als Nullstellen hat. Von diesem Polynom wird die Ableitung nach der Unbestimmten X bestimmt. Es gelten
Aus p(X) und der Ableitung werden die Weierstraß-Korrekturen , k = 1, ..., n bestimmt und das korrigierte Tupel 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.)
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.
Zu lösen sei die kubische Gleichung . Als Starttupel werde mit dem komplexen Parameter gewählt. Es ergeben sich die folgenden ersten Iterationsschritte für die parallele Variante der Iteration
It.-Nr. | z1 | z2 | z3 |
---|---|---|---|
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. | z1 | z2 | z3 |
---|---|---|---|
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 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.
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
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 in jedem Schritt der Newton-Iteration ergibt sich aus der Forderung, dass die Identität
in erster Ordnung in erfüllt sei. Aus der Taylor-Entwicklung erster Ordnung ergibt sich die in lineare Gleichung
Jede einzelne Korrektur kann daraus durch Einsetzen von zu
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.
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 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
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 eine offene Menge von Startvektoren, die gegen einen Zyklus der Länge 4 konvergieren.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.