Householder-Verfahren

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 VerfahrensBearbeiten

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.

MotivationBearbeiten

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  

BeispielBearbeiten

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  

QuellenBearbeiten