Householder-Verfahren

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Householder-Verfahren sind eine Gruppe von numerischen Verfahren zur Bestimmung von Nullstellen einer skalaren reellen Funktion. Sie sind nach Alston Scott Householder benannt.

Beschreibung des Verfahrens

[Bearbeiten | Quelltext bearbeiten]

Sei eine natürliche Zahl und eine mindestens -fach stetig differenzierbare Funktion, die im Intervall eine einfache Nullstelle besitze, d. h. . Sei ein Startwert nahe genug an . Dann konvergiert die durch die Iteration

erzeugte Folge sukzessiver Approximationen mit Konvergenzordnung gegen . Das heißt, es gibt eine Konstante mit

.

Für ergibt sich das Newton-Verfahren, für das Halley-Verfahren.

Hat eine einfache Nullstelle in , so gibt es eine -fach stetig differenzierbare Funktion mit und . Die reziproke Funktion hat einen Pol der Ordnung in . Liegt nahe , so wird die Taylorentwicklung von in von diesem Pol dominiert,

Betrachtet man als sich langsam ändernd bis nahezu konstant zu , dann sind die Taylorkoeffizienten umgekehrt proportional zu den Potenzen von , also

für

Die von Newton zur Demonstration seines Verfahrens benutzte Polynomgleichung war . In einem ersten Schritt wurde beobachtet, dass es eine Nullstelle nahe geben muss. Durch Einsetzen von erhält man erst

und anschließend durch Invertieren dieses Polynoms als Taylorreihe

Das Ergebnis des ersten Schritts des Householder-Verfahrens einer gegebenen Ordnung erhält man auch, indem man den Koeffizienten des Grades durch seinen linken Nachbarn in dieser Entwicklung teilt. Dies ergibt folgende Näherungen aufsteigender Ordnung

d x1=2+
1 0,100000000000000000000000000000000
2 0,094339622641509433962264150943396
3 0,094558429973238180196253345227476
4 0,094551282051282051282051282051282
5 0,094551486538216154140615031261963
6 0,094551481438752142436492263099119
7 0,094551481543746895938379484125813
8 0,094551481542336756233561913325371
9 0,094551481542324837086869382419375
10 0,094551481542326678478801765822985

Es ergeben sich also in diesem Beispiel etwas mehr als gültige Dezimalstellen für den ersten Schritt im Verfahren der Ordnung