Brent-Verfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Brent-Verfahren ist ein Verfahren der numerischen Mathematik zur iterativen Bestimmung einer Nullstelle, welches die Bisektion, das Sekantenverfahren (bzw. Lineare Interpolation) und die inverse quadratische Interpolation miteinander kombiniert. Das Verfahren wurde von Richard P. Brent 1973 entwickelt und ist eine Modifizierung des früheren Algorithmus von Theodorus Dekker (1969).

Grundidee[Bearbeiten]

Problem: Gesucht ist die Nullstelle f(x)=0 einer stetigen Funktion f:[a,b] \to \mathbb{R}
Gegeben sind zwei Startwerte a und b, deren Funktionswerte f(a) und f(b) unterschiedliches Vorzeichen besitzen, so dass nach Zwischenwertsatz eine Nullstelle im Intervall [a,b] existiert.

Zur Lösung dieses Problems kann man nun unterschiedliche Lösungsansätze verwenden. Allgemein wird man mit der Bisektion immer zu einer Näherung kommen. Aber es gibt auch Verfahren, die für glatte Funktionen schneller konvergieren können, wie das Sekantenverfahren mit superlinearer Konvergenz. Es gibt aber Beispiele, wo das Sekantenverfahren gar nicht konvergiert, da dieses Verfahren nur lokal konvergent ist, das heißt es hängt davon ab, wie die Startwerte gewählt sind.

Die Dekker-Methode vereinigt nun die beiden Vorteile der zwei Verfahren.

Verfahren von Dekker[Bearbeiten]

Drei Punkte gehören zu jedem Iterationsschritt:

  • bk ist der aktuelle Iterationswert
  • ak ist der gegenüberliegende Punkt, d. h. ein Punkt, so dass f(ak) und f(bk) unterschiedliches Vorzeichen besitzen, so dass das Intervall [ak, bk] die Nullstelle enthält. Außerdem sollte noch folgendes gelten: |f(bk)| ≤ |f(ak)|, damit bk eine bessere Näherung ist als ak.
  • bk−1 ist der vorherige Iterationswert (im ersten Iterationsschritt setzten wir bk−1 = a0).

Für jeden Iterationsschritt werden zwei vorläufige Werte ermittelt. Der erste durch das Sekantenverfahren:

 s = b_k - \frac{b_k-b_{k-1}}{f(b_k)-f(b_{k-1})} f(b_k),

und der zweite durch die Bisektion:

 m = \frac{a_k+b_k}{2}.

Wenn der Wert des Sekantenverfahrens s zwischen bk und m liegt, dann wird das der neue Iterationswert (bk+1 = s), ansonsten der Mittelpunkt nach Bisektion (bk+1 = m).

Der neue Punkt ak+1 wird so gewählt, dass f(ak+1) und f(bk+1) unterschiedliche Vorzeichen besitzen, dies geschieht folgendermaßen: wenn f(ak) und f(bk+1) unterschiedliche Vorzeichen haben, dann wird ak+1 = ak. Ansonsten müssen f(bk+1) und f(bk) unterschiedliche Vorzeichen haben, so dass ak+1 = bk.

Schlussendlich muss bk+1 die bessere Näherung sein, also es muss gelten |f(bk+1)| ≤ |f(ak+1)|, wenn nicht werden einfach beide Variablen getauscht.

Damit ist ein Iterationsschritt durchgeführt.

Verfahren von Brent[Bearbeiten]

Die Dekker-Methode konvergiert schnell, wenn die Funktion gutartig ist. Es gibt aber Beispiele, bei denen in jedem Iterationsschritt das Sekantenverfahren verwendet wird, aber die bk nur sehr langsam konvergieren. Insbesondere | bkbk−1 | kann beliebig klein werden, d. h. bk−1 liegt sehr nah bei bk. In diesem Fall benötigt Dekkers Methode weit mehr Iterationsschritte als die Bisektion.

Um dies zu vermeiden hat Brent das Verfahren leicht modifiziert, in dem zur Berechnung der neuen Näherung gegebenenfalls drei Punkte a, b und c verwendet werden, die drei Punkte umfassen die Näherung des letzten Iterationsschrittes und den dazugehörigen gegenüberliegenden Punkt, dessen Funktionswert ein anderes Vorzeichen besitzt, und eine „ältere“ Näherung aus einem vorherigen Schritt. Außerdem werden noch mehr Voraussetzungen verlangt, bevor überhaupt eine Interpolation durchgeführt wird, so dass ein zu langsames Konvergieren ausgeschlossen werden kann und das Verfahren nicht viel langsamer als die Bisektion konvergiert. Außerdem verwendet Brent nicht nur die Lineare Interpolation, sondern auch die Inverse Quadratische Interpolation, wenn die drei Punkte a, b und c unterschiedliche Funktionswerte f(a), f(b) und f(c) besitzen. Dies verspricht eine etwas bessere Effizienz bei der Annäherung an die Nullstelle.

Die Interpolation wird durchgeführt, wenn der dadurch neu berechnete Punkt s in dem Intervall [\tfrac{3}{4}(c-b), b] liegt, sonst führt man einen Bisektionsschritt durch. Außerdem soll die Änderung des Punktes bk+1=bk+d größer sein als ein gewisser Toleranzwert tol, welcher aus der gewünschten Genauigkeit \delta und der Maschinengenauigkeit \varepsilon berechnet wird. Sollte der Schritt kleiner sein, ändert man den Punkt b um diesen Toleranzschritt, um wenigstens | bkbk−1 | \geq tol zu gewährleisten, also man rechnet bk+1=bk\pm tol. Nach so einem kleinen Schritt um tol wird spätestens im übernächsten Iterationsschritt eine Bisektion durchgeführt, um so das Verfahren nicht viel langsamer konvergieren zu lassen als die Bisektion an sich.

Brent zeigt, dass seine Methode höchstens N² Iterationsschritte benötigte, wobei N die Anzahl der Iterationsschritte für die Bisektion ist. Wenn die Funktion f gutartig ist, dann wird die Brent-Methode in der Regel die inverse quadratische oder die lineare Interpolation verwenden und somit superlinear konvergieren.

Algorithmus von Brent für Matlab[Bearbeiten]

Folgender Algorithmus liegt dem Brent-Verfahren zugrunde:

fa=f(a); fb=f(b);
 
if fa*fb>0
    error('f(a) und f(b) sollten unterschiedliche Vorzeichen haben');
end
 
c=a; fc=fa;   %Zu Beginn ist c = a
 
c=a; fc=fa; d=b-a; e=d;
 
iter=0;
maxiter=1000
 
while iter<maxiter
    iter=iter+1
 
    if fb*fc>0
        c=a; fc=fa; d=b-a; e=d;
    end
 
    if abs(fc)<abs(fb)
        a=b; b=c; c=a;
        fa=fb; fb=fc; fc=fa;
    end
 
    tol=2*eps*abs(b)+t; m=(c-b)/2; %Toleranz
 
    if (abs(m)>tol) && (abs(fb)>0) %Verfahren muss noch durchgeführt werden
 
        if (abs(e)<tol) || (abs(fa)<=abs(fb))
            d=m; e=m;
        else
            s=fb/fa;
            if a==c
                p=2*m*s; q=1-s;
            else
                q=fa/fc; r=fb/fc;
                p=s*(2*m*q*(q-r)-(b-a)*(r-1));
                q=(q-1)*(r-1)*(s-1);
            end
            if p>0
                q=-q;
            else
                p=-p;
            end
            s=e; e=d;
            if ( 2*p<3*m*q-abs(tol*q) ) && (p<abs(s*q/2))
                d=p/q;
            else
                d=m; e=m;
            end
        end
 
        a=b; fa=fb;
 
        if abs(d)>tol
            b=b+d
        else
            if m>0
                b=b+tol;
            else
                b=b-tol;
            end
        end
    else
        break;
    end
 
    fb=f(b);
 end
 
 xs=b;

Beispiel[Bearbeiten]

Für die bei x = 1 gelegene Nullstelle der Funktion

f(x) = e^{-x} \ln(x)

erhält man mit den Startwerten a=0{,}05 und b=1{,}7 und der gewünschten Genauigkeit von t=10^{-20} für die drei Verfahren folgende Ergebnisse:

Verfahren Anzahl der Iterationsschritte Fehler nach Ende der Iteration
Brent 9 0
Sekantenverfahren konvergiert nicht in 1000 Schritten entfällt
Bisektion 31 1.164153*10−10

Die Iterationsschritte des Brent-Verfahrens genauer betrachtet:

Iterationsschritt angewendeter Schritt aktuelle Näherung x\approx
1 Lineare Interpolation 1.6457
2 Bisektion 0.84785889251506
3 Lineare Interpolation 1.18604831457557
4 Lineare Interpolation 1.04253452228117
5 Quadratische Interpolation 0.99590946651532
6 Lineare Interpolation 1.00026718046634
7 Lineare Interpolation 1.00000163554039
8 Quadratische Interpolation 0.99999999999436
9 Lineare Interpolation 1

Literatur[Bearbeiten]

  • Richard Brent: Algorithms for Minimization without Derivatives. Dover 2002
  • Press et al: Numerical Recipes in C. Cambridge University Press, 1991