Skip to content

Methods

SimpleArt edited this page Oct 19, 2020 · 19 revisions

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

x = x1 + t ( x2 - x1 )

Bisection

a.k.a. binary search

The midpoint of the bracketing interval is used.

Plot of bisection

Formula

t = 0.5

False Position

a.k.a. Regula Falsi and Secant

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

Plot of false position

Formula

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

Dekker

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

Plot of Dekker's method

Formula

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

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.

Plot of Brent's method

Formula

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

Clone this wiki locally