Troger
[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

Müller-Verfahren

Das Müller-Verfahren ist eine Verallgemeinerung des Sekanten-Verfahrens. Anstatt eines linearen Modells für f wird hier ein quadratisches Modell (eine quadratische Parabel) verwendet.

Beim Sekanten-Verfahren wird der Schnittpunkt der Geraden, die durch die Punkte

$(x^{(k-1)},f(x^{(k-1)}))$ und (x$^{(k)},f(x^{(k)}))$

gegeben ist, mit der X-Achse als nächster Punkt x(k+1) der Iterationsfolge verwendet. Beim Müller-Verfahren verwendet man nun eine Parabel und diese wird durch die drei Punkte

$(x^{(k-2)},f(x^{(k-2)})),(x^{(k-1)},f(x^{(k-1)}))$ und $(x^{(k)},f(x^{(k)}))$

mit der X-Achse zum Schnitt gebracht. Da man nun zwei mögliche Nachfolgerpunkte (die 2 Schnittpunkte) für x(k+1) erhält, nimmt man jenen Punkt der näher bei x(k) liegt.

Da man eine quadratische Parabel als Modellfunktion verwendet, können die Lösungen für die Schnittpunkte auch komplex werden. Sind nur reelle Lösungen gesucht, müssen solche komplexe Lösungen algorithmisch unterdrückt werden.

Wenn jedoch komplexe Nullstellen gesucht werden, hat man beim Müller-Verfahren den Vorteil, daß man mit reellen Startwerten beginnen kann und den Algorithmus mit komplexen Näherungen fortsetzen kann. Diese Möglichkeit hat man weder beim Newton-Verfahren noch beim Sekanten-Verfahren.


Konvergenz (Müller-Verfahren):

Bei diesem Verfahren handelt es sich um ein Dreischrittverfahren der Form

$x^{(k+1)}=t(x^{(k)},x^{(k-1)},x^{(k-2)})$

und es gilt folgende Beziehung:

$e_{k+1}\approx \frac 16\left| \frac{f^{\prime \prime \prime }(x^{*})}{f^\prime(x^{*})}\right| e_ke_{k-1}e_{k-2}$

Die Konvergenzordnung ist p=1.839. Daraus folgt daß das Müller-Verfahren überlinear reagiert und somit schneller ist als das Sekanten-Verfahren.

[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]