Skip to content

Methods

SimpleArt edited this page Oct 22, 2020 · 19 revisions

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

x = x2 + t ( x1 - x2 )

Bisection

a.k.a. binary search

The midpoint of the bracketing interval is used.

return t = 0.5

Plot of bisection

False Position

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

Plot of false position

Muller

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 )

Plot of Muller's method

Dekker

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

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