Mathematical background

Brent method is an iterative scheme used to obtain one root of the equation $F(x)=0$ within an interval $[x_1,x_2]$. It assumes that $F(x_1)F(x_2)<0$. Let $x_3$ be the mid-point of the interval $[x_1,x_2]$. A new estimate of the root is $x_4$ with:

$$x_4=x_3+\frac{P}{Q}$$

with:

$$\begin{eqnarray*} R&=& \frac{F(x_3)}{F(x_2)}~~~~S=\frac{F(X_3)}{F(x_1)}~~~~~T=\f... ...\\ P&=&S[T(R-T)(x_2-x_3)-(1-R)(x_3-x_1)]\\ Q&=&(T-1)(R-1)(S-1) \end{eqnarray*}$$

In this method $x_3$ is considered to be the current estimate of the solution. The term $P/Q$ is a correction factor: when this factor leads to a new estimate of the solution outside the interval we use a bisection method to compute a new interval $[x_1,x_2]$. In other words if $F(x_1)F(x_3)<0$ the new interval is $[x_1,x_3]$ and if $F(x_2)F(x_3)<0$ the new interval is $[x_3,x_2]$. Therefore Brent method is a cross between a bisection method and a super-linear method which insure that the estimate of the solution always lie within the interval $[x_1,x_2]$.