next up previous contents
Next: Implementation Up: Brent method for solving Previous: Brent method for solving   Contents

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:

\begin{displaymath}
x_4=x_3+\frac{P}{Q}
\end{displaymath}

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]$.



Jean-Pierre Merlet 2012-12-20