Repository navigation
Methods
Each method returns t, which is used to compute the next point with the formula
x = x1 + t ( x2 - x1 )
a.k.a. binary search
The midpoint of the bracketing interval is used.
return t = 0.5
a.k.a. Regula Falsi and Secant
The root is estimated using a secant line through x1 and x2.
return t = f ( x2 ) / ( f ( x2 ) - f ( x1 ) )
a.k.a. Quadratic
The root is estimated using a quadratic interpolation through x1, x2, and x3. The root of the interpolating quadratic is computed with 2 iterations of Newton's method from the side of [ x1, x2] that is guaranteed to converge to the bracketed root.
a = ( f ( x1 ) - f ( x2 ) ) / ( x1 - x2 )
c = ( f ( x3 ) - f ( x2 ) ) / ( x3 - x2 )
b = ( a - c ) / ( x1 - x3 )
if b is 0:
- return t = f ( x2 ) / ( f ( x2 ) - f ( x1 ) )
if b and f ( x1 ) have the same sign:
- r = x1
else:
- r = x2
repeat two times:
- r -= ( f ( x2 ) + a ( r - x1 ) + b ( r - x1 ) ( r - x2 ) ) / ( a + b ( ( r - x1 ) + ( r - x2 ) ) )
return t = ( r - x2 ) / ( x1 - x2 )
The root is estimated using a secant line through x2 and either x1 or x3. If x3 is closer to x2 than x1 and f ( x2 ) ≠ f ( x3 ), then x3 is used. Otherwise x1 is used.
if f ( x2 ) = f ( x3 ) or t ≥ 0.5: return t = f ( x2 ) / ( f ( x2 ) - f ( x1 ) )
else: return t = ( f ( x2 ) / ( f ( x2 ) - f ( x3 ) ) ) ( ( x2 - x3 ) / ( x2 - x1 ) )
a.k.a. Brent-Dekker and fzeroin
When possible, inverse quadratic interpolation through x1, x2, and x3 is used. If division by zero would occur, a secant line through x1 and x2 is used instead. Some conditions are then checked to use bisection instead.
l = ( x3 - x2 ) / ( x1 - x2 )
a = f ( x2 ) / ( f ( x1 ) - f ( x2 ) )
b = f ( x3 ) / ( f ( x1 ) - f ( x3 ) )
c = f ( x2 ) / ( f ( x3 ) - f ( x2 ) )
d = f ( x1 ) / ( f ( x3 ) - f ( x1 ) )
t = a b + c d l
if division by zero occurs:
- t = f ( x2 ) / ( f ( x2 ) - f ( x1 ) )
if t < 0 or t > 1 or either
-
(bisection was last used and t | x1 - x2 | > 0.5 | x2 - x3 | )
-
(interpolation was last used and t | x1 - x2 | > 0.5 | x3 - x4 |)
- t = 0.5
return t




