Das Dekker-Brent-Verfahren

Dekker-Brent-Verfahren
- Problem:
  - Sekantenverfahren und IQI schnell, aber (zumindest am Anfang) unzuverlässig
  - Bisektion langsam, aber sicher
- Lösung: kombiniere die Verfahren geschickt mit Hilfe dreier Werte a, b, c, wobei
  - a und b liegen auf verschiedenen Seiten der Nullstelle, sie bilden immer das kleinste bisher gefundene Intervall
  - b ist immer der beste bisher gefundene Wert, d.h. der mit dem betragsmäßig kleinsten Funktionswert
  - c ist der vorherige Wert von b
- konkreter
  - ```
  Ausgangssituation: Startintervall [a b] mit 
     f(a) f(b) < 0
     |f(b)| ≤ |f(a)|  (ggf. a, b vertauschen)
  finde neuen Wert c aus [a b] mit Sekantenschritt
  sortiere a, b, c um
  wiederhole bis Intervallbreite < delta
     wenn (c ≠ a) und (c ≠ b)
        probiere IQI-Schritt
     sonst
        probiere Sekantenschritt
     end		  
     wenn neuer Wert im alten Intervall [a b]
       nimm ihn als neues c
     sonst
       bestimme neues c mit Bisektion
     end
     sortiere a, b, c um
```
- einige komplexere Details des Verfahrens fehlen ([12])
  - Kontrolle möglicher numerischer Probleme
  - Methode zur Beschleunigung bei "bösartigen" Funktionen
  - Programmiertricks zur allgemeinen Beschleunigung
- genaueres Abbruchverfahren
  - bestimme Ergebnis x₀ = (a + b)/2
  - bestimme absoluten Fehler ε_abs = |b - a|/2 und relativen Fehler ε_rel = ε_abs/|x₀|
  - Abbruch, wenn ε_rel < δ
- Verfahren ist so zuverlässig wie Bisektion, aber in der Regel deutlich schneller
Matlab-Routine fzero:
- basiert auf Dekker-Brent-Verfahren
- falls nur ein Startwert x₀ (kein Intervall):
  - suche Intervall mit Vorzeichenwechsel durch allmähliches Vergrößern um x₀ herum
- das kann schiefgehen, vor allem in der Nähe von Polstellen (mit Standardbeispiel 1)
  - fzero(f1, 4.8)
    ans = 4.712388980384693
- fzero wird gesprächig bei Angabe einer entsprechenden Option
  - options = optimset("Display", "iter");
    fzero(@cos, [1 3], options)
Aufgaben:
- Aufgabe 7