Methods

• General Methodology
• Binary Search
• False Position
• Muller
• Dekker
• Brent
• Chandrupatla
• Quadratic Safe
• Chandrupatla Mixed

General Methodology

Next Computed Point

Each method returns t, which is used to compute the next point with the formula

x = x₂ + t ( x₁ - x₂ )

If t = 0.5 is set, then Binary Search is used instead.

Tolerance

Finally, an adjustment is made so that searching over intervals smaller than the desired error is avoided. This is done by rounding towards the midpoint of the interval.

x = x + 0.25 ( error_abs + error_rel | x | ) sign( ( x₁ - x ) + ( x₂ - x ) )

Guaranteed Convergence

At the end of each iteration, a new value of t is chosen. To guarantee convergence, several additional measures are checked. The bracketing interval is said to fail to bisect if

• x / y < 1/8 where | x | < | y | are the bracketing points.
• Binary search is not used and | x - y | does not decrease by a factor of 1/2.
• Geometric Mean is used and | x - y | does not decrease by a factor of 3/4.

Otherwise the bracketing interval succeeds to bisect. If the bracketing interval fails to bisect for:

• 3 iterations, then
  • The Illinois method is tried by using 0.5 f ( x₁ ).
  • If a quarter of the limit of iterations for the given method are used up, or the Illinois method has no effect, then t is doubled.
    • If t ≥ 1, then t is decreased by 1.
  • If t > 0.5, then t = 0.5 to avoid going too far.
• More than 3 iterations, or t is out of bounds, then
  • t = 0.5 is forced.

Binary Search

a.k.a. bisection

order = 1.000

A midpoint of the bracketing interval is used to halve either the absolute or relative errors. To halve the absolute error, the traditional arithmetic mean is used. To halve the relative error, the geometric mean is used. To ensure both are eventually halved, the two types of means used are alternated. See Binary Search for more details.

return t = 0.5

False Position

a.k.a. Regula Falsi and Secant

order = 1.414

The root is estimated using a secant line through x₁ and x₂.

return t = f ( x₂ ) / ( f ( x₂ ) - f ( x₁ ) )

Muller

a.k.a. Quadratic

order = 1.731

The root is estimated using a quadratic interpolation through x₁, x₂, and x₃. The root of the interpolating quadratic is computed with 2 iterations of Newton's method from the side of [ x₁, x₂] that is guaranteed to converge to the bracketed root.

a = ( f ( x₁ ) - f ( x₂ ) ) / ( x₁ - x₂ )

c = ( f ( x₃ ) - f ( x₂ ) ) / ( x₃ - x₂ )

b = ( a - c ) / ( x₁ - x₃ )

if b is 0:

• return t = f ( x₂ ) / ( f ( x₂ ) - f ( x₁ ) )

if b and f ( x₁ ) have the same sign:

• r = x₁

else:

• r = x₂

repeat two times:

• r -= ( f ( x₂ ) + a ( r - x₁ ) + b ( r - x₁ ) ( r - x₂ ) ) / ( a + b ( ( r - x₁ ) + ( r - x₂ ) ) )

return t = ( r - x₂ ) / ( x₁ - x₂ )

Dekker

order = 1.618

The root is estimated using a secant line through x₂ and either x₁ or x₃. If x₁ is closer to x₂ than x₁ or f ( x₂ ) = f ( x₃ ), then x₁ is used. Otherwise x₃ is used.

if f ( x₂ ) = f ( x₃ ) or t ≥ 0.5: return t = f ( x₂ ) / ( f ( x₂ ) - f ( x₁ ) )

else: return t = ( f ( x₂ ) / ( f ( x₂ ) - f ( x₃ ) ) ) ( ( x₂ - x₃ ) / ( x₂ - x₁ ) )

Brent

a.k.a. Brent-Dekker and fzeroin

order = 1.731

When possible, inverse quadratic interpolation through x₁, x₂, and x₃ is used. If division by zero would occur, a secant line through x₁ and x₂ is used instead. Some conditions are then checked to use binary search instead if interpolation does not appear to be converging fast enough.

l = ( x₃ - x₂ ) / ( x₁ - x₂ )

a = f ( x₂ ) / ( f ( x₁ ) - f ( x₂ ) )

b = f ( x₃ ) / ( f ( x₁ ) - f ( x₃ ) )

c = f ( x₂ ) / ( f ( x₃ ) - f ( x₂ ) )

d = f ( x₁ ) / ( f ( x₃ ) - f ( x₁ ) )

t = a b + c d l

if division by zero occurs:

• t = f ( x₂ ) / ( f ( x₂ ) - f ( x₁ ) )

if t < 0 or t > 1 or either

1. (binary search was last used and t | x₁ - x₂ | > 0.5 | x₂ - x₃ | )

2. (interpolation was last used and t | x₁ - x₂ | > 0.5 | x₃ - x₄ |)

• t = 0.5

return t

Chandrupatla

order = 1.731

Chandrupatla's method is very similar to Brent's method. The main difference is its more intelligent attempt at deciding when to use interpolation or binary search. Often Chandrupatla's method will be found to be more robust than Brent's method because it requires the three points ( x₁, x₂, x₃ ) to be close to a straight line in order to use inverse quadratic interpolation. This is done by first rescaling x and y so that the points lie in the unit square:

x = ( x₂ - x₁ ) / ( x₃ - x₁ )

y = ( f ( x₂ ) - f ( x₁ ) ) / ( f ( x₃ ) - f ( x₁ ) )

• If x² < y and ( 1 - x )² < 1 - y, then inverse quadratic interpolation is used.
• Otherwise t = 0.5 is used to indicate binary search should be used.

The closer the points ( x₁, x₂, x₃ ) form a straight line, the closer the point ( x, y ) will be to the straight line y = x. Chandrupatla's method accepts interpolation if ( x, y ) lies in the shaded region in the graph below.

Quadratic Safe

a.k.a. Chandrupatla quadratic, Chandrupatla Muller, and Muller safe

order = 1.731

The Quadratic Safe method is a modification of Chandrupatla's method to fit Muller's method. The same rescaling is used, but instead of testing for inverse quadratic inequalities, quadratic inequalities are used.

x = ( x₂ - x₁ ) / ( x₃ - x₁ )

y = ( f ( x₂ ) - f ( x₁ ) ) / ( f ( x₃ ) - f ( x₁ ) )

• If y² < x and ( 1 - y )² < 1 - x, then quadratic interpolation is used. Unlike Muller's method, an additional iteration of Newton's method is used because it is more likely that the quadratic root is accurate.
• Otherwise t = 0.5 is used to indicate binary search should be used.

The closer the points ( x₁, x₂, x₃ ) form a straight line, the closer the point ( x, y ) will be to the straight line y = x. The Quadratic Safe method accepts interpolation if ( x, y ) lies in the shaded region in the graph below.

Chandrupatla Mixed

order = 1.731

The Chandrupatla Mixed method is a combination of Chandrupatla's method with Quadratic Safe. This is done by diagonally dividing the unit square into 4 diagonal quadrants, and then choosing the method which is most accepting in that quadrant.

x = ( x₂ - x₁ ) / ( x₃ - x₁ )

y = ( f ( x₂ ) - f ( x₁ ) ) / ( f ( x₃ ) - f ( x₁ ) )

• If y ( 1 - y ) < x ( 1 - x ), then Quadratic Safe is used.

• Otherwise Chandrupatla's method is used.

Like with Quadratic Safe, 3 iterations of Newton's methods is used to find the root of the interpolating quadratic because it can be expected that the root is accurate.

The region of acceptance for interpolation is shown as an overlap of Chandrupatla's and Quadratic Safe's. It can be seen that Chandrupatla's method is used when on the left or right sides, while Quadratic Safe is used when on the upper and lower sides of the unit square.