Skip to content

Methods

SimpleArt edited this page Nov 5, 2020 · 19 revisions

General Methodology

Next Computed Point

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

x = x2 + t ( x1 - x2 )

Three edge cases are considered.

  1. If x1 - x2 leads to overflow, t = 0.5 is set to indicated binary search is used, and x = 0 is set.

  2. If f ( x ) is infinite, t = 0.5 is set to indicate binary search is used because interpolation is unreliable in this situation.

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

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 + 10-14 | x | ) sign( ( x1 - x ) + ( x2 - x ) )

Guaranteed Convergence

At the end of each iteration, a new value of t is chosen. To guarantee convergence, several additional measures are checked.

  • If the bracketing interval fails to halve for 3 iterations, then
    • The Illinois method is tried by using 0.25 f ( x1 ).
    • 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 quadrupled.
    • If t > 0.5, then t = 0.5 to avoid going too far.
  • If the bracketing interval fails to halve for 4 iterations, or t is out of bounds, then
    • t = 0.5 is forced.
    • This may be run twice in a row if the geometric mean is used first but the interval does not halve.

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

Plot of binary search

False Position

a.k.a. Regula Falsi and Secant

order = 1.414

The root is estimated using a secant line through x1 and x2.

return t = f ( x2 ) / ( f ( x2 ) - f ( x1 ) )

Plot of false position

Muller

a.k.a. Quadratic

order = 1.731

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 )

Plot of Muller's method

Dekker

order = 1.618

The root is estimated using a secant line through x2 and either x1 or x3. If x1 is closer to x2 than x1 or f ( x2 ) = f ( x3 ), then x1 is used. Otherwise x3 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 ) )

Plot of Dekker's method

Brent

a.k.a. Brent-Dekker and fzeroin

order = 1.731

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 binary search instead if interpolation does not appear to be converging fast enough.

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

  1. (binary search was last used and t | x1 - x2 | > 0.5 | x2 - x3 | )

  2. (interpolation was last used and t | x1 - x2 | > 0.5 | x3 - x4 |)

  • t = 0.5

return t

Plot of Brent's method

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 ( x1, x2, x3 ) 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 = ( x2 - x1 ) / ( x3 - x1 )

y = ( f ( x2 ) - f ( x1 ) ) / ( f ( x3 ) - f ( x1 ) )

The closer the points ( x1, x2, x3 ) 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.

Plot of Chandrupatla's acceptance region

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 = ( x2 - x1 ) / ( x3 - x1 )

y = ( f ( x2 ) - f ( x1 ) ) / ( f ( x3 ) - f ( x1 ) )

  • If y2 < x and ( 1 - y )2 < 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 ( x1, x2, x3 ) 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.

Plot of Quadratic Safe's acceptance region

Chandrupatla Mixed

order = 1.731

The Chandrupatla Mixed method is a combination of Chandrupatla's method with Quadratic Safe. Both the quadratic and inverse quadratic inequalities are tested to see if any interpolation is possible. If both interpolations are possible, the one which is closer to being an equality is used.

  • If only inverse quadratic interpolation can be used, then it is used.
  • If only quadratic interpolation can be used, then it is used.
  • If both can be used:
    • inverse quadratic interpolation is used if ( x - y2) ( 1 - x - ( 1 - y )2 ) < 1.5 ( y - x2) ( 1 - y - ( 1 - x )2 ).
    • quadratic interpolation is used otherwise.
  • If no interpolation can be used, t = 0.5 is used to indicate binary search should be 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.

Clone this wiki locally