Reelle Nullstellen beliebiger reeller Polynome

• Um alle reellen Nullstellen eines reellen Polynoms p(x) zu identifizieren, (auch wenn es daneben komplexe gibt), wird der Graph der Polynoms systematisch abgetastet. An einer Stelle x wird ein Schritt h > 0 gewählt und p wird je nach Vorzeichen von p(x) auf dem Intervall [x,x+h] durch eine Parabel zweiter Ordnung nach unten bzw. oben abgeschätzt. Dazu dient die vollständige Taylorentwicklung mit einer Abschätzung der Terme höherer als zweiter Ordnung:
  Für x in [x₀,x₀+h] gilt p(x) in
  p(x₀)+p'(x₀)*(x-x₀)+(x-x₀)²*(p''(x₀)/2+(-)sum_k=3ⁿ |p^(k)(x₀)|*h^k-2/(k!))
  
  Liegt eine Parabelnullstelle in diesem Intervall, definiert sie den nächsten Testpunkt, andernfalls ist dies x₀+h. Ist eine Nullstelle gefunden (d.h. der Polynomwert liegt im Bereich der Rundungsfehler oder der Schritt wird zu klein), dann wird sie mit dem Horner-Schema abgespalten und der Vorgang wiederholt sich, nachdem der Startpunkt etwas nach links zurückverlegt wurde. So sollen auch mehrfache Nullstellen gefunden werden. Das wird solange fortgesetzt, bis alle reellen Nullstellen gefunden sind oder das vorgegebene Intervall ausgeschöpft ist.

Die Eingaben

• Der Grad n des Polynoms ist anzugeben.
• Sie haben nun die Wahl, sich die Polynomkoeffizienten aus Nullstellen erzeugen zu lassen oder die Koeffizienten direkt einzugeben. Im ersteren Fall können Sie auch komplexe Nullstellen benutzen, müssen aber dann die konjugiert komplexe direkt danach eingeben. Oder
• Die n+1 Koeffizienten a_n, ... ,a₀ des Polynoms (in dieser Reihenfolge). Wichtig: Der Höchstkoeffizient a_n ungleich 0.
• Ein Intervall, in dem die Nullstellen gesucht werden sollen, bzw. die Angabe, daß alle Nullstellen gesucht sind. Dann definiert die Schranke von Marden das Intervall (symmetrisch zu null).

Die Ausgaben

• Die gefundenen Nullstellen.
• Ein (png)-Bild des Graphen des normierten Polynoms p(x)/a_n mit den Abtastpunkten.

Fragen ?

• Welche lokale Konvergenzordnung hat das Verfahren ?
• Wie steht es um die Genauigkeit und die Konvergenzgeschwindigkeit bei mehrfachen Nullstellen ? Warum ?
• Warum wird hier wohl mit expliziter Nullstellenabspaltung gearbeitet ?

Das Eingabeformular

Zurück: Nichtlineare Gleichungssysteme