Inhalt

- Grundlagen der Mathematik

- Diskrete Mathematik

- Algebra

- Lineare Algebra

- Geometrie

- Analysis

- Differentialgleichungen

- Funktionalanalysis

- Differentialgeometrie

- Topologie

- Numerik

   - Numerische Verfahren

       Kondition

       Stabilität

       Konsistenz

      - Lineare Gleichungssysteme

      - Nichtlineare

       Gleichungssysteme

          Sekantenverfahren

          Regula Falsi

          Fixpunktiteration

         - Newton-Verfahren

          Halley-Verfahren

          Euler-Tschebyschow-

          Verfahren

          Bairstow-Verfahren

          Weierstraß-Iteration

          Trennkreisverfahren

      - Interpolation

      - Approximation

      - Numerische Integration

   - Optimierung

- Stochastik

- Unsortiertes

- Anbieterkennzeichnung

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) = Xⁿ + p_n-1 X^n-1 + ... + p₀ 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 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 n zusätzliche, 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 z⁽ⁱ⁾ = (z⁽ⁱ⁾₁ , ..., z⁽ⁱ⁾_n ) wird das Verschwindungspolynom sowie dessen Ableitung g_z⁽ⁱ⁾ '(X) zugeordnet. Es gelten

g_z⁽ⁱ⁾ (z⁽ⁱ⁾_k ) = 0 und .

Aus p(X) und der Ableitung g_z⁽ⁱ⁾ '(X) werden die Weierstraß-Korrekturen , k = 1, ..., n bestimmt und das korrigierte Tupel z^{(i + 1)} = z⁽ⁱ⁾ + w⁽ⁱ⁾ = (z⁽ⁱ⁾₁ + w⁽ⁱ⁾₁ , ..., z⁽ⁱ⁾_n + w⁽ⁱ⁾_n ) 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 x³ - 3x² + 3x - 5 = 0. Als Starttupel werde (z₁ , z₂ , z₃ ) = (a⁰ , a¹ , a² ) mit dem komplexen Parameter gewählt. Es ergeben sich die folgenden ersten Iterationsschritte

In den ersten 4 Iterationen wird das Tripel (z₁ , z₂ , z₃ ) 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) 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

.

Da die Polynome auf beiden Seiten normiert sind, 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 w = (w₁ , ..., w_n ) in jedem Schritt der Newton-Iteration ergibt sich aus der Forderung, dass

in erster Ordnung in w erfüllt sei. Aus der Taylor-Entwicklung erster Ordnung ergibt sich die in w lineare Gleichung

.

Jede einzelne Korrektur w_k kann daraus durch Einsetzen von X = z_k zu

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) 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

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) = 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.

Ein Mathematiker ist eine Maschine, die Kaffee in Theoreme verwandelt.

Paul Erdös

Druckansicht     

Amazon.de empfiehlt:

Numerik für Ingenieure und Naturwissenschaftler

Wolfgang Dahmen

Numerik für Ingenieure, Physiker und Informatiker: für Bache...

Günter Bärwolff

Numerik-Algorithmen: Verfahren, Beispiele, Anwendungen, 2CD-...

Gisela Engeln-Müllges

Numerische Mathematik

Hans Rudolf Schwarz

Numerische Mathematik: Eine beispielorientierte Einführung

Michael Knorrenschild

Numerische Mathematik: Eine beispielorientierte Einführung (...

Michael Knorrenschild

Bücher zum Thema Numerik auf
• bol.de
• buch.de
• buecher.de
• libri.de