Skip to content

Methods

SimpleArt edited this page Oct 25, 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 )

Two edge cases are considered.

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

  2. If f ( x ) is infinite, bisection is used because interpolation is unreliable in this situation.

Except in the first case, when t = 0.5 is set, the formula above is used.

Binary Search

If t = 0.5, then an alternation of arithmetic and geometric means is used.

  • If arithmetic mean is used, then x = 0.5 ( x1 + x2 ) is set.
  • If geometric mean is used, then x = sign( x1 ) √( x1 x2 ) is set.

To avoid under-/over-flow, these formulas are rewritten

  • 0.5 x1 + 0.5 x2
  • sign( x1 ) √| x1 | √| x2 |

when needed. If the geometric mean is used and x1, x2 have different signs, the smaller of the two is replaced by the smallest positive float times the sign of the other before square rooting.

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.

Bisection

a.k.a. binary search

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. This combination gives convergence in at most 68 iterations when pure bisection is used and at most 351 iterations when other methods are used as well. The implementation is described above in General Methodology.

return t = 0.5

Plot of bisection

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 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

  1. (bisection 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

Clone this wiki locally