15.2: How fzero Works

Last updated
Save as PDF

Page ID: 84553

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

According to the MATLAB documentation, fzero uses “a combination of bisection, secant, and inverse quadratic interpolation methods.” (See https://greenteapress.com/matlab/fzero)

To understand what that means, suppose we’re trying to find a root of a function of one variable, \(f(x)\), and assume we have evaluated the function at two places, \(x_1\) and \(x_2\), and found that the results have opposite signs. Specifically, assume \(f(x_1) > 0\) and \(f(x_2) < 0\), as shown in Figure 15.3.

15.3.jpg — Figure 15.3: Initial state of a root-finding search

As long as \(f\) is continuous, there must be at least one root in this interval. In this case we would say that \(x_1\) and \(x_2\) bracket a zero.

If this were all you knew about \(f\), where would you go looking for a root? If you said “halfway between \(x_1\) and \(x_2\),” congratulations! You just invented a numerical method called bisection!

If you said, “I would connect the dots with a straight line and compute the zero of the line,” congratulations! You just invented the secant method!

And if you said, “I would evaluate \(f\) at a third point, find the parabola that passes through all three points, and compute the zeros of the parabola,” congratulations, you just invented inverse quadratic interpolation!

That’s most of how fzero works. The details of how these methods are combined are interesting, but beyond the scope of this book. You can read more at https://greenteapress.com/matlab/brent.