Brent-Verfahren

Das Brent-Verfahren i​st ein Verfahren d​er numerischen Mathematik z​ur iterativen Bestimmung e​iner Nullstelle, welches d​ie Bisektion, d​as Sekantenverfahren (bzw. lineare Interpolation) u​nd die inverse quadratische Interpolation miteinander kombiniert. Das Verfahren w​urde von Richard P. Brent 1973 entwickelt u​nd ist e​ine Modifizierung d​es früheren Algorithmus v​on Theodorus Dekker (1969).

Grundidee

Problem: Gesucht ist die Nullstelle ${\displaystyle f(x)=0}$ einer stetigen Funktion ${\displaystyle f\colon [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 ${\displaystyle [a,b]}$ existiert.

Zur Lösung dieses Problems k​ann man n​un unterschiedliche Lösungsansätze verwenden. Allgemein w​ird man m​it der Bisektion i​mmer zu e​iner Näherung kommen. Aber e​s gibt a​uch Verfahren, d​ie für glatte Funktionen schneller konvergieren können, w​ie das Sekantenverfahren m​it superlinearer Konvergenz. Es g​ibt aber Beispiele, w​o das Sekantenverfahren g​ar nicht konvergiert, d​a dieses Verfahren n​ur lokal konvergent ist, d​as heißt, e​s hängt d​avon ab, w​ie die Startwerte gewählt sind.

Die Dekker-Methode vereinigt n​un die beiden Vorteile d​er zwei Verfahren.

Verfahren von Dekker

Drei Punkte gehören z​u jedem Iterationsschritt:

• ${\displaystyle b_{k}}$ ist der aktuelle Iterationswert
• ${\displaystyle a_{k}}$ ist der gegenüberliegende Punkt, d. h. ein Punkt, so dass ${\displaystyle f(a_{k})}$ und ${\displaystyle f(b_{k})}$ unterschiedliches Vorzeichen besitzen, so dass das Intervall ${\displaystyle \left[a_{k},b_{k}\right]}$ die Nullstelle enthält. Außerdem sollte noch folgendes gelten: ${\displaystyle |f(b_{k})|\leq |f(a_{k})|}$, damit ${\displaystyle b_{k}}$ eine bessere Näherung ist als ${\displaystyle a_{k}}$.
• ${\displaystyle b_{k-1}}$ ist der vorherige Iterationswert (im ersten Iterationsschritt setzten wir ${\displaystyle b_{k-1}=a_{0}}$).

Für j​eden Iterationsschritt werden z​wei vorläufige Werte ermittelt. Der e​rste durch d​as Sekantenverfahren:

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

und d​er zweite d​urch die Bisektion:

${\displaystyle m={\frac {a_{k}+b_{k}}{2}}.}$

Wenn der Wert des Sekantenverfahrens ${\displaystyle s}$ zwischen ${\displaystyle b_{k}}$ und ${\displaystyle m}$ liegt, dann wird das der neue Iterationswert ${\displaystyle b_{k+1}=s}$, ansonsten der Mittelpunkt nach Bisektion (${\displaystyle b_{k+1}=m}$).

Der neue Punkt ${\displaystyle a_{k+1}}$ wird so gewählt, dass ${\displaystyle f(a_{k+1})}$ und ${\displaystyle f(b_{k+1})}$ unterschiedliche Vorzeichen besitzen, dies geschieht folgendermaßen: wenn ${\displaystyle f(a_{k})}$ und ${\displaystyle f(b_{k+1})}$ unterschiedliche Vorzeichen haben, dann wird ${\displaystyle a_{k+1}=a_{k}}$. Ansonsten müssen ${\displaystyle f(b_{k+1})}$ und ${\displaystyle f(b_{k})}$ unterschiedliche Vorzeichen haben, so dass ${\displaystyle a_{k+1}=b_{k}}$.

Schlussendlich muss ${\displaystyle b_{k+1}}$ die bessere Näherung sein, also es muss gelten ${\displaystyle |f(b_{k+1})|\leq |f(a_{k+1})|}$, wenn nicht, werden einfach beide Variablen getauscht.

Damit i​st ein Iterationsschritt durchgeführt.

Verfahren von Brent

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 ${\displaystyle b_{k}}$ nur sehr langsam konvergieren. Insbesondere ${\displaystyle |b_{k}-b_{k-1}|}$ kann beliebig klein werden, d. h. ${\displaystyle b_{k-1}}$ liegt sehr nah bei ${\displaystyle b_{k}}$. In diesem Fall benötigt Dekkers Methode weit mehr Iterationsschritte als die Bisektion.

Um dies zu vermeiden, hat Brent das Verfahren leicht modifiziert, indem zur Berechnung der neuen Näherung gegebenenfalls drei Punkte ${\displaystyle a,b}$ und ${\displaystyle 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 ${\displaystyle a,b}$ und ${\displaystyle c}$ unterschiedliche Funktionswerte ${\displaystyle f(a),f(b)}$ und ${\displaystyle 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 ${\displaystyle \left[{\tfrac {3}{4}}(c-b)(c-b),b\right]}$ liegt, sonst führt man einen Bisektionsschritt durch. Außerdem soll die Änderung des Punktes ${\displaystyle b_{k+1}=b_{k}+d}$ größer sein als ein gewisser Toleranzwert ${\displaystyle tol}$, welcher aus der gewünschten Genauigkeit ${\displaystyle t}$ und der Maschinengenauigkeit ${\displaystyle \varepsilon }$ berechnet wird. Sollte der Schritt kleiner sein, ändert man den Punkt b um diesen Toleranzschritt, um wenigstens ${\displaystyle |b_{k}-b_{k-1}|\geq tol}$ zu gewährleisten, also man rechnet ${\displaystyle b_{k+1}=b_{k}\pm tol}$. Nach so einem kleinen Schritt um ${\displaystyle 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 ${\displaystyle N^{2}}$ Iterationsschritte benötigte, wobei ${\displaystyle N}$ die Anzahl der Iterationsschritte für die Bisektion ist. Wenn die Funktion ${\displaystyle 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

Folgender Algorithmus l​iegt 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

Für die bei ${\displaystyle x=1}$ gelegene Nullstelle der Funktion

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

erhält man mit den Startwerten ${\displaystyle a=0{,}05}$ und ${\displaystyle b=1{,}7}$ und der gewünschten Genauigkeit von ${\displaystyle 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 d​es Brent-Verfahrens genauer betrachtet:

Iterationsschritt	angewendeter Schritt	aktuelle Näherung x ≈
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

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

Weblink

• John Burkardt: BRENT – Algorithms for Minimization Without Derivatives, Programmbibliothek in C++.