Repository navigation
Methods
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 |
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.
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.
-
If x1 - x2 leads to overflow, t = 0.5 is set to indicated bisection is used, and x = 0 is set.
-
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. If t = 0.5, then an alternation of arithmetic and geometric means is used. Swap x1 and x2 so that they are sorted by absolute value.
- If arithmetic mean is used and
- 2 x2 does not overflow then x = 0.5 ( x1 + x2 ) is set.
- Otherwise x = 0.5 x1 + 0.5 x2 is set.
- If geometric mean is used and
- x1 and x2 have different signs, x12 doesn't underflow, x22 doesn't overflow, then x = sign( x1 ) √( x1 x2 ) is set.
- Otherwise:
- x1 and x2 have different signs, then x1 = sign( x2 ) realmin is set, where realmin is the smallest positive float.
- x = sign( x1 ) √| x1 | √| x2 | set.
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 + 1e-14 | x | ) sign( ( x1 - x ) + ( x2 - x ) )
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.
a.k.a. binary search
order = 1.000
The midpoint of the bracketing interval is used. The midpoint of two real numbers x and y is given by the arithmetic mean, 0.5 ( x + y ). The amount of reals between x and y that are on the left and right sides of the arithmetic mean are equal, but the amount of floats are not. The "middle" float is given by the geometric mean, √( x y ), if x and y are both positive. To ensure a fast search through both reals and floats, arithmetic and geometric means are alternated when t = 0.5. This combination gives convergence in at most 68 iterations when pure bisection is used and at most 408 iterations when other methods are used. The implementation is described above in General Methodology.
return t = 0.5
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 ) )
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 )
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 ) )
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
-
(bisection was last used and t | x1 - x2 | > 0.5 | x2 - x3 | )
-
(interpolation was last used and t | x1 - x2 | > 0.5 | x3 - x4 |)
- t = 0.5
return t




