Section 9.4 How fzero works
Matlab command fzero implements Brent's method (1973). It builds on earlier Dekker's method (1969) which is easier to describe:
- Start with a bracketing interval.
- Try the secant method.
- Accept the result of secant method if it “looks right”, which means: it lies between the midpoint and the endpoint with smaller value of \(|f|\text{.}\)
- Otherwise use bisection instead.
- Identify a new bracketing interval. Repeat until it is small enough.
Brent's method replaces secant lines with parabolas: instead of drawing a line through two points on the graph \(y=f(x)\text{,}\) we draw a parabola through three points on the graph.
But a parabola of the form \(y=Ax^2+Bx+C\) may intersect the \(x\)-axis twice, or not at all. This would not work for our purpose. So, Brent's method uses parabolas of the form \(x=Ay^2+By+C\) because they cross the \(x\)-axis once, at \(x=C\text{.}\) This is called “inverse quadratic interpolation”. We will study interpolation in detail in Part IV of the course.
Brent's method can be summarized as:
- Start with a bracketing interval.
- Try inverse quadratic interpolation
- Accept the result of IQI if it “looks right” (the condition is more complicated than in Dekker's method)
- Otherwise use bisection instead.
- Identify a new bracketing interval. Repeat until it is small enough.
Several other variations of this approach were proposed over the years, but Brent's method became entrenched in libraries for numerical computation, from Matlab (fzero) to R (uniroot) to Python (SciPy optimize library) and others.
To see how Brent's method works inside fzero, use an option for displaying each iteration.
options = optimset('Display', 'iter');
fzero(@(x) exp(x)-1, 7, options)
The steps shown by this code include the preliminary process of finding a bracketing interval. These steps can be avoided if such an interval is given to fzero as its second argument [a b], instead of an initial guess.
fzero(@(x) exp(x)-1, [-5 5], options)