Brent-Verfahren
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
Problem: Gesucht ist die Nullstelle einer stetigen Funktion
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 existiert.
![{\displaystyle f\colon [a,b]\to \mathbb {R} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c5ab61178bf5349838758ffe3d96135406ed0245)
![{\displaystyle [a,b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c4b788fc5c637e26ee98b45f89a5c08c85f7935)
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
Drei Punkte gehören zu jedem Iterationsschritt:
- ist der aktuelle Iterationswert
- ist der gegenüberliegende Punkt, d. h. ein Punkt, so dass und unterschiedliches Vorzeichen besitzen, so dass das Intervall die Nullstelle enthält. Außerdem sollte noch folgendes gelten: , damit eine bessere Näherung ist als .
- ist der vorherige Iterationswert (im ersten Iterationsschritt setzten wir ).
![{\displaystyle \left[a_{k},b_{k}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eedb8388cc57cd9f3cc1409c0152f2345016382a)
Für jeden Iterationsschritt werden zwei vorläufige Werte ermittelt. Der erste durch das Sekantenverfahren:
und der zweite durch die Bisektion:
Wenn der Wert des Sekantenverfahrens zwischen und liegt, dann wird das der neue Iterationswert , ansonsten der Mittelpunkt nach Bisektion (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{k+1}=m} ).
Der neue Punkt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{k+1}} wird so gewählt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(a_{k+1})} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(b_{k+1})} unterschiedliche Vorzeichen besitzen, dies geschieht folgendermaßen: wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(a_k)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(b_{k+1})} unterschiedliche Vorzeichen haben, dann wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{k+1}=a_k} . Ansonsten müssen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(b_{k+1})} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(b_k)} unterschiedliche Vorzeichen haben, so dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{k+1}=b_k} .
Schlussendlich muss Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{k+1}} die bessere Näherung sein, also es muss gelten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |f(b_{k+1})|\le|f(a_{k+1})|} , wenn nicht, werden einfach beide Variablen getauscht.
Damit ist 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_k} nur sehr langsam konvergieren. Insbesondere Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |b_k-b_{k-1}|} kann beliebig klein werden, d. h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{k-1}} liegt sehr nah bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a, b} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a, b} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c} unterschiedliche Funktionswerte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(a), f(b)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{k+1}=b_k+d} größer sein als ein gewisser Toleranzwert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle tol} , welcher aus der gewünschten Genauigkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} und der Maschinengenauigkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon} berechnet wird. Sollte der Schritt kleiner sein, ändert man den Punkt b um diesen Toleranzschritt, um wenigstens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |b_k-b_{k-1}|\geq tol} zu gewährleisten, also man rechnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{k+1}=b_k\pm tol} . Nach so einem kleinen Schritt um Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N^2} Iterationsschritte benötigte, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N} die Anzahl der Iterationsschritte für die Bisektion ist. Wenn die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 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
Für die bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = 1} gelegene Nullstelle der Funktion
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x) = e^{-x} \ln(x)}
erhält man mit den Startwerten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a=0{,}05} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b=1{,}7} und der gewünschten Genauigkeit von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 des 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++.
