Editing Brent's method (section)

== Dekker's method ==

The idea to combine the bisection method with the secant method goes back to {{Harvtxt|Dekker|1969}}.

Suppose that one wants to solve the equation ''f''(''x'') = 0. As with the bisection method, one needs to initialize Dekker's method with two points, say ''a''<sub>0</sub> and ''b''<sub>0</sub>, such that ''f''(''a''<sub>0</sub>) and ''f''(''b''<sub>0</sub>) have opposite signs. If ''f'' is continuous on [''a''<sub>0</sub>, ''b''<sub>0</sub>], the [[intermediate value theorem]] guarantees the existence of a solution between ''a''<sub>0</sub> and ''b''<sub>0</sub>.

Three points are involved in every iteration:
* ''b''<sub>''k''</sub> is the current iterate, i.e., the current guess for the root of ''f''.
* ''a''<sub>''k''</sub> is the "contrapoint", i.e., a point such that ''f''(''a''<sub>''k''</sub>) and ''f''(''b''<sub>''k''</sub>) have opposite signs, so the interval [''a''<sub>''k''</sub>, ''b''<sub>''k''</sub>] contains the solution. Furthermore, |''f''(''b''<sub>''k''</sub>)| should be less than or equal to |''f''(''a''<sub>''k''</sub>)|, so that ''b''<sub>''k''</sub> is a better guess for the unknown solution than ''a''<sub>''k''</sub>.
* ''b''<sub>''k''&minus;1</sub> is the previous iterate (for the first iteration, one sets ''b''<sub>''k''&minus;1</sub> = ''a''<sub>0</sub>).

Two provisional values for the next iterate are computed. The first one is given by linear interpolation, also known as the secant method:
::<math> s = \begin{cases}  b_k - \frac{b_k-b_{k-1}}{f(b_k)-f(b_{k-1})} f(b_k), & \mbox{if }  f(b_k)\neq f(b_{k-1})  \\ m & \mbox{otherwise } \end{cases} </math>

and the second one is given by the bisection method
::<math> m = \frac{a_k+b_k}{2}. </math>
If the result of the secant method, ''s'', lies strictly between ''b''<sub>''k''</sub> and ''m'', then it becomes the next iterate (''b''<sub>''k''+1</sub> = ''s''), otherwise the midpoint is used (''b''<sub>''k''+1</sub> = ''m'').

Then, the value of the new contrapoint is chosen such that ''f''(''a''<sub>''k''+1</sub>) and ''f''(''b''<sub>''k''+1</sub>) have opposite signs. If ''f''(''a''<sub>''k''</sub>) and ''f''(''b''<sub>''k''+1</sub>) have opposite signs, then the contrapoint remains the same: ''a''<sub>''k''+1</sub> = ''a''<sub>''k''</sub>. Otherwise, ''f''(''b''<sub>''k''+1</sub>) and ''f''(''b''<sub>''k''</sub>) have opposite signs, so the new contrapoint becomes ''a''<sub>''k''+1</sub> = ''b''<sub>''k''</sub>.

Finally, if |''f''(''a''<sub>''k''+1</sub>)| < |''f''(''b''<sub>''k''+1</sub>)|, then ''a''<sub>''k''+1</sub> is probably a better guess for the solution than ''b''<sub>''k''+1</sub>, and hence the values of ''a''<sub>''k''+1</sub> and ''b''<sub>''k''+1</sub> are exchanged.

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

Dekker's method performs well if the function ''f'' is reasonably well-behaved. However, there are circumstances in which every iteration employs the secant method, but the iterates ''b''<sub>''k''</sub> converge very slowly (in particular, |''b''<sub>''k''</sub> &minus; ''b''<sub>''k''&minus;1</sub>| may be arbitrarily small). Dekker's method requires far more iterations than the bisection method in this case.