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:




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