Description
1 Introduction
The goal of this project is to apply Brent’s method for solving root-finding
problem f(x) = 0. We know that given an interval [a, b] with f(a)f(b) < 0,
the Bisection method generates a sequence {pn}∞
n=1 converging to a zero on
[a, b], say p.
We also know that for Newton’s method (also for its variant Secant
method), only if the initial guess x0 is “sufficiently close” to p, it converges. If
it converges, and f
0
(p) 6= 0, it converges quadratically (super-linearly for Secant method)– much faster than Bisection method (usually linear convergence).
However in practice it is very difficult to find a “good” initial guess. Brent’s
method attempts to solve this problem. In every iteration, it chooses between
Secant method (or in some cases inverse quadratic interpolation) and Bisection
method.
The convergence is guaranteed given the same initial condition as Bisection method. While in the worst case, the performance of Brent’s method
is worse than Bisection method, it is usually as good as Secant method. See
Figure 1 for an illustration of convergence rate.
0 10 20 30 40 50 60
10−16
10−14
10−12
10−10
10−8
10−6
10−4
10−2
100
Brent Method
Bisection Method
Figure 1: Comparison of convergence rate between Brent’s method and Bisection method for finding a root of f(x) = cos(x
2
) − x
3 on [0, 1]. x axis is the
number of iterations, and y axis is the quantity |pn − p| plotted in log-scale.
1
2 Description of Brent’s Method
Like Bisection method, Brent’s method initially requires an interval [l, r] such
that f(l)f(r) < 0. Brent’s methods attempts to find a root p of f on [l, r] in an
iterative way.
During the iterations, it keeps a record of three variables a, b, c: b
is the current approximation of p, a is a point such that f(a)f(b) < 0, and c is
the previous approximation of p. In each iteration, the algorithm chooses from
the following three candidates (denoted by s) the next approximation of p:
1. (inverse quadratic interpolation)
s =
af(b)f(c)
(f(a) − f(b))(f(a) − f(c)) +
bf(a)f(c)
(f(b) − f(a))(f(b) − f(c))
+
cf(a)f(b)
(f(c) − f(a))(f(c) − f(b));
(1)
2. (secant method)
s = b −
f(b)(b − a)
f(b) − f(a)
; (2)
3. (bisection method)
s = b + (b − a)/2. (3)
The condition for choosing which candidate is technical. Roughly speaking,
choosing inverse quadratic interpolation requires that f(a), f(b), f(c) are all
distinct, and both inverse quadratic interpolation and secant method require
that s is between a and b but not too close to b. The specific algorithm is
described in the table of Algorithm 1.
3 Application
We test Brent’s method on two root finding problems:
1. f(x) = (x + 3)(x − 1)4 on [−4, 4/3];
2. f(x) = cos(x
2
) −
1
2
x on [0, 2].
In both these two cases, we choose = 10−15
.
4 What to submit
Submit a zip file containing both MATLAB/Octave codes for Brent’s method
and a PDF report including the following
1. Documentation for MATLAB/Octave functions, including a description
of what they do, what the variables in the input and output represent,
and how to use the code (calling syntax).
2
Algorithm 1 Brent’s method
input: function f, end points a, b such that f(a) · f(b) < 0, some small
threshold
output: solution p
if |f(a)| < |f(b)| then swap a, b end if c ← a flag ← true . flag denotes whether the previous iteration is bisection δ ← max(1, |b|); while |f(b)| > or |b − a| > δ do
if |f(a) − f(c)| > and |f(b) − f(c)| >
then
calculate s by inverse quadratic interpolation . see Equation (1)
else
calculate s by secant method . see Equation (2)
end if
if (s −
3a+b
4
)(s − b) > 0 or
(flag = true and |s − b| ≥ |b − c|/2) or
(flag = false and |s − b| ≥ |c − d|/2) or
(flag = true and |b − c| < δ) or
(flag = false and |c − d| < δ)
then
calculate x by bisection method . see Equation (3)
flag = true
else
flag = false
end if
calculate f(s)
d ← c
c ← b
if f(a)f(s) < 0 then b ← s
else
a ← s
end if
if |f(a)| < |f(b)| then swap a, b
end if
δ ← max(1, |b|);
end while
p ← b
return p
3
2. Report the results for solving the two problems in “Applications” section.
In particular, list the values of a, b, c in each iteration in a table. You may
need to modify the algorithm a little to record a, b, c in each iteration.
3. Use MATLAB/Octave function fzero to compute a “ground truth” solution ˆp for each problem. For each root-finding problem, use function
semilogy to plot |b − pˆ| versus the iteration number. You will observe a
curve similar to the blue line in Fig. 1.
4. An implementation of Bisection method (bisection) is provided. The
output of bisection is a sequence {pn} of approximate values for p. Solve
each root-finding problem using bisection and plot by semilogy the
graph |pn − pˆ| versus the iteration number n. You will see a curve similar
to the red dots in Fig. 1.
4