Skip to content

Methods

SimpleArt edited this page Oct 22, 2020 · 19 revisions

Convergence

Order of Convergence

Let dn be the number of digits accurate on the nth iteration. The order of convergence may be interpreted as

limn → ∞ ( dn / dn-1 ), the ratio of the digits accurate.

For example, if the order of convergence for a method is 1.500, then it can be expected that that method gains 50.0% more digits accurate on every iteration eventually.

All methods have an order of convergence of at least 1.000, meaning they will converge.

Assuming the root is simple, the orders of convergence for each of the methods are as follows:

Method Order
Bisection 1.000
False Position 1.414
Muller 1.731
Dekker 1.618
Brent 1.731
Chandrupatla 1.731

Rate of Convergence

The rate of convergence is a refinement of the order of convergence. While the order of convergence describes the first term in the error, the rate of convergence describes the second term.

dn ~ order dn-1 + log(1/rate), where the base of the log depends on what numbering system is used for dn (e.g. 2 = binary, 10 = base 10).

All methods have an order of at least 1.000, in which case the rate is no greater than 2-1/5, meaning every 5 iterations have to at least give one additional bit of accuracy.

The rate of convergence is often complicated and related to how well the root can be linearly approximated for the given function. Because of this and that it is less interesting than the order of convergence, these are not listed out.

General Methodology

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

order = 1.000

The midpoint of the bracketing interval is used.

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