Skip to content

Error and Convergence

SimpleArt edited this page Oct 30, 2021 · 6 revisions

Absolute Error

There are two main types of error. The absolute error is defined as the distance from the root and is bounded by | x - y |. This gives one way to terminate and is often the type of error a user wants. To guarantee this error is halved, the arithmetic mean (AM) is used.

Relative Error

Although absolute error is simple to understand, it does not actually match the structure of floating point numbers and misses the concept of significant figures. The relative error is defined as the absolute error divided by the absolute value of the root and is estimated by | x1 - x2 | / (0.5 | x1 + x2 |). There are several interpretations of the relative error. One interpretation is it measures the number of significant figures to which the root is found. Another intuitive interpretation is it measures how close the ratio x1 / x2 is to 1. To guarantee this error is halved, the geometric mean (GM) is used.

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 Root of
Bisection 1.000 x - 1
False Position 1.414 x 2 - 2
Newton* 2.000 x - 2
Muller 1.731 x 12 - 9 x 8 + 1
Dekker 1.618 x 2 - x - 1
Brent 1.731 x 12 - 9 x 8 + 1
Chandrupatla 1.731 x 12 - 9 x 8 + 1

*Note: Newton's method requires the derivative fprime.

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.

Clone this wiki locally