Brent's Method - Dekker's Method

Dekker's Method

The idea to combine the bisection method with the secant method goes back to Dekker.

Suppose that we want to solve the equation f(x) = 0. As with the bisection method, we need to initialize Dekker's method with two points, say a₀ and b₀, such that f(a₀) and f(b₀) have opposite signs. If f is continuous on, the intermediate value theorem guarantees the existence of a solution between a₀ and b₀.

Three points are involved in every iteration:

• b_k is the current iterate, i.e., the current guess for the root of f.
• a_k is the "contrapoint," i.e., a point such that f(a_k) and f(b_k) have opposite signs, so the interval contains the solution. Furthermore, |f(b_k)| should be less than or equal to |f(a_k)|, so that b_k is a better guess for the unknown solution than a_k.
• b_k−1 is the previous iterate (for the first iteration, we set b_k−1 = a₀).

Two provisional values for the next iterate are computed. The first one is given by linear interpolation, also known as the secant method:

and the second one is given by the bisection method

If the result of the secant method, s, lies strictly between b_k and m, then it becomes the next iterate (b_k+1 = s), otherwise the midpoint is used (b_k+1 = m).

Then, the value of the new contrapoint is chosen such that f(a_k+1) and f(b_k+1) have opposite signs. If f(a_k) and f(b_k+1) have opposite signs, then the contrapoint remains the same: a_k+1 = a_k. Otherwise, f(b_k+1) and f(b_k) have opposite signs, so the new contrapoint becomes a_k+1 = b_k.

Finally, if |f(a_k+1)| < |f(b_k+1)|, then a_k+1 is probably a better guess for the solution than b_k+1, and hence the values of a_k+1 and b_k+1 are exchanged.

This ends the description of a single iteration of Dekker's method.