www.wikidata.de-de.nina.az

Brent Verfahren Das ist ein Verfahren der numerischen Mathematik zur iterativen Bestimmung einer Nullstelle welches die

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 Bearbeiten

Problem: Gesucht ist die Nullstelle einer stetigen Funktion
Gegeben sind zwei Startwerte und , deren Funktionswerte und unterschiedliches Vorzeichen besitzen, d. h. , so dass nach Zwischenwertsatz eine Nullstelle im Intervall 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:

  • 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 ).

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 ().

Der neue Punkt wird so gewählt, dass und unterschiedliche Vorzeichen besitzen, dies geschieht folgendermaßen: wenn und unterschiedliche Vorzeichen haben, dann wird . Ansonsten müssen und unterschiedliche Vorzeichen haben, so dass .

Schlussendlich muss die bessere Näherung sein, also es muss gelten , 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 nur sehr langsam konvergieren. Insbesondere kann beliebig klein werden, d. h. liegt sehr nah bei . 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 und 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 und unterschiedliche Funktionswerte und 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 liegt, sonst führt man einen Bisektionsschritt durch. Außerdem soll die Änderung des Punktes größer sein als ein gewisser Toleranzwert , welcher aus der gewünschten Genauigkeit und der Maschinengenauigkeit berechnet wird. Sollte der Schritt kleiner sein, ändert man den Punkt b um diesen Toleranzschritt, um wenigstens zu gewährleisten, also man rechnet . Nach so einem kleinen Schritt um 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 Iterationsschritte benötigte, wobei die Anzahl der Iterationsschritte für die Bisektion ist. Wenn die Funktion 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 gelegene Nullstelle der Funktion

erhält man mit den Startwerten und und der gewünschten Genauigkeit von 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 Bearbeiten

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

Weblink Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 fruheren Algorithmus von Theodorus Dekker 1969 Inhaltsverzeichnis 1 Grundidee 2 Verfahren von Dekker 3 Verfahren von Brent 4 Algorithmus von Brent fur Matlab 5 Beispiel 6 Literatur 7 WeblinkGrundidee BearbeitenProblem Gesucht ist die Nullstelle f x 0 displaystyle f x 0 nbsp einer stetigen Funktion f a b R displaystyle f colon a b to mathbb R nbsp Gegeben sind zwei Startwerte a displaystyle a nbsp und b displaystyle b nbsp deren Funktionswerte f a displaystyle f a nbsp und f b displaystyle f b nbsp unterschiedliches Vorzeichen besitzen d h f a f b lt 0 displaystyle f a cdot f b lt 0 nbsp so dass nach Zwischenwertsatz eine Nullstelle im Intervall a b displaystyle a b nbsp existiert Zur Losung dieses Problems kann man nun unterschiedliche Losungsansatze verwenden Allgemein wird man mit der Bisektion immer zu einer Naherung kommen Aber es gibt auch Verfahren die fur glatte Funktionen schneller konvergieren konnen wie das Sekantenverfahren mit superlinearer Konvergenz Es gibt aber Beispiele wo das Sekantenverfahren gar nicht konvergiert da dieses Verfahren nur lokal konvergent ist das heisst es hangt davon ab wie die Startwerte gewahlt sind Die Dekker Methode vereinigt nun die beiden Vorteile der zwei Verfahren Verfahren von Dekker BearbeitenDrei Punkte gehoren zu jedem Iterationsschritt b k displaystyle b k nbsp ist der aktuelle Iterationswert a k displaystyle a k nbsp ist der gegenuberliegende Punkt d h ein Punkt so dass f a k displaystyle f a k nbsp und f b k displaystyle f b k nbsp unterschiedliches Vorzeichen besitzen so dass das Intervall a k b k displaystyle left a k b k right nbsp die Nullstelle enthalt Ausserdem sollte noch folgendes gelten f b k f a k displaystyle f b k leq f a k nbsp damit b k displaystyle b k nbsp eine bessere Naherung ist als a k displaystyle a k nbsp b k 1 displaystyle b k 1 nbsp ist der vorherige Iterationswert im ersten Iterationsschritt setzten wir b k 1 a 0 displaystyle b k 1 a 0 nbsp Fur jeden Iterationsschritt werden zwei vorlaufige Werte ermittelt Der erste durch das Sekantenverfahren s b k b k b k 1 f b k f b k 1 f b k displaystyle s b k frac b k b k 1 f b k f b k 1 f b k nbsp und der zweite durch die Bisektion m a k b k 2 displaystyle m frac a k b k 2 nbsp Wenn der Wert des Sekantenverfahrens s displaystyle s nbsp zwischen b k displaystyle b k nbsp und m displaystyle m nbsp liegt dann wird das der neue Iterationswert b k 1 s displaystyle b k 1 s nbsp ansonsten der Mittelpunkt nach Bisektion b k 1 m displaystyle b k 1 m nbsp Der neue Punkt a k 1 displaystyle a k 1 nbsp wird so gewahlt dass f a k 1 displaystyle f a k 1 nbsp und f b k 1 displaystyle f b k 1 nbsp unterschiedliche Vorzeichen besitzen dies geschieht folgendermassen wenn f a k displaystyle f a k nbsp und f b k 1 displaystyle f b k 1 nbsp unterschiedliche Vorzeichen haben dann wird a k 1 a k displaystyle a k 1 a k nbsp Ansonsten mussen f b k 1 displaystyle f b k 1 nbsp und f b k displaystyle f b k nbsp unterschiedliche Vorzeichen haben so dass a k 1 b k displaystyle a k 1 b k nbsp Schlussendlich muss b k 1 displaystyle b k 1 nbsp die bessere Naherung sein also es muss gelten f b k 1 f a k 1 displaystyle f b k 1 leq f a k 1 nbsp wenn nicht werden einfach beide Variablen getauscht Damit ist ein Iterationsschritt durchgefuhrt Verfahren von Brent BearbeitenDie Dekker Methode konvergiert schnell wenn die Funktion gutartig ist Es gibt aber Beispiele bei denen in jedem Iterationsschritt das Sekantenverfahren verwendet wird aber die b k displaystyle b k nbsp nur sehr langsam konvergieren Insbesondere b k b k 1 displaystyle b k b k 1 nbsp kann beliebig klein werden d h b k 1 displaystyle b k 1 nbsp liegt sehr nah bei b k displaystyle b k nbsp In diesem Fall benotigt Dekkers Methode weit mehr Iterationsschritte als die Bisektion Um dies zu vermeiden hat Brent das Verfahren leicht modifiziert indem zur Berechnung der neuen Naherung gegebenenfalls drei Punkte a b displaystyle a b nbsp und c displaystyle c nbsp verwendet werden die drei Punkte umfassen die Naherung des letzten Iterationsschrittes und den dazugehorigen gegenuberliegenden Punkt dessen Funktionswert ein anderes Vorzeichen besitzt und eine altere Naherung aus einem vorherigen Schritt Ausserdem werden noch mehr Voraussetzungen verlangt bevor uberhaupt eine Interpolation durchgefuhrt wird so dass ein zu langsames Konvergieren ausgeschlossen werden kann und das Verfahren nicht viel langsamer als die Bisektion konvergiert Ausserdem verwendet Brent nicht nur die lineare Interpolation sondern auch die inverse quadratische Interpolation wenn die drei Punkte a b displaystyle a b nbsp und c displaystyle c nbsp unterschiedliche Funktionswerte f a f b displaystyle f a f b nbsp und f c displaystyle f c nbsp besitzen Dies verspricht eine etwas bessere Effizienz bei der Annaherung an die Nullstelle Die Interpolation wird durchgefuhrt wenn der dadurch neu berechnete Punkt s in dem Intervall 3 4 c b c b b displaystyle left tfrac 3 4 c b c b b right nbsp liegt sonst fuhrt man einen Bisektionsschritt durch Ausserdem soll die Anderung des Punktes b k 1 b k d displaystyle b k 1 b k d nbsp grosser sein als ein gewisser Toleranzwert t o l displaystyle tol nbsp welcher aus der gewunschten Genauigkeit t displaystyle t nbsp und der Maschinengenauigkeit e displaystyle varepsilon nbsp berechnet wird Sollte der Schritt kleiner sein andert man den Punkt b um diesen Toleranzschritt um wenigstens b k b k 1 t o l displaystyle b k b k 1 geq tol nbsp zu gewahrleisten also man rechnet b k 1 b k t o l displaystyle b k 1 b k pm tol nbsp Nach so einem kleinen Schritt um t o l displaystyle tol nbsp wird spatestens im ubernachsten Iterationsschritt eine Bisektion durchgefuhrt um so das Verfahren nicht viel langsamer konvergieren zu lassen als die Bisektion an sich Brent zeigt dass seine Methode hochstens N 2 displaystyle N 2 nbsp Iterationsschritte benotigte wobei N displaystyle N nbsp die Anzahl der Iterationsschritte fur die Bisektion ist Wenn die Funktion f displaystyle f nbsp 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 fur Matlab BearbeitenFolgender Algorithmus liegt dem Brent Verfahren zugrunde fa f a fb f b if fa fb gt 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 lt maxiter iter iter 1 if fb fc gt 0 c a fc fa d b a e d end if abs fc lt 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 gt tol amp amp abs fb gt 0 Verfahren muss noch durchgefuhrt werden if abs e lt tol abs fa lt 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 gt 0 q q else p p end s e e d if 2 p lt 3 m q abs tol q amp amp p lt abs s q 2 d p q else d m e m end end a b fa fb if abs d gt tol b b d else if m gt 0 b b tol else b b tol end end else break end fb f b end xs b Beispiel BearbeitenFur die bei x 1 displaystyle x 1 nbsp gelegene Nullstelle der Funktion f x e x ln x displaystyle f x e x ln x nbsp erhalt man mit den Startwerten a 0 05 displaystyle a 0 05 nbsp und b 1 7 displaystyle b 1 7 nbsp und der gewunschten Genauigkeit von t 10 20 displaystyle t 10 20 nbsp fur die drei Verfahren folgende Ergebnisse Verfahren Anzahl der Iterationsschritte Fehler nach Ende der IterationBrent 9 0Sekantenverfahren konvergiert nicht in 1000 Schritten entfalltBisektion 31 1 164153 10 10Die Iterationsschritte des Brent Verfahrens genauer betrachtet Iterationsschritt angewendeter Schritt aktuelle Naherung x 1 Lineare Interpolation 1 64572 Bisektion 0 847858892515063 Lineare Interpolation 1 186048314575574 Lineare Interpolation 1 042534522281175 Quadratische Interpolation 0 995909466515326 Lineare Interpolation 1 000267180466347 Lineare Interpolation 1 000001635540398 Quadratische Interpolation 0 999999999994369 Lineare Interpolation 1Literatur BearbeitenRichard Brent Algorithms for Minimization without Derivatives Dover 2002 Press et al Numerical Recipes in C Cambridge University Press 1991Weblink BearbeitenJohn Burkardt BRENT Algorithms for Minimization Without Derivatives Programmbibliothek in C Abgerufen von https de wikipedia org w index php title Brent Verfahren amp oldid 231051172