Rate Of Convergence In Numerical Analysis

In numerical analysis, the speed at which a convergent sequence approaches its limit is called the rate of convergence. Strictly speaking, a limit does not give information about any finite first part of the sequence; this concept is of practical importance if we deal with a sequence of successive approximations for a iterative method, as typically fewer iterations are needed to output a useful approximation if the rate of convergence is higher. This may even make the difference between needing ten or a million iterations.

Similar concepts are used for discretization methods. The solution of the discretized problem converges to the solution of the continuous problem as the grid size goes to zero, and the speed of convergence is one of the factors of the efficiency of the method. However, the terminology in this case is different from the terminology for iterative methods.

Convergence speed for iterative methods

Basic definition

Suppose that the sequence {xk} converges to the number L.

We say that this sequence converges linearly to L, if there exists a number μ ∈ (0, 1) such that

The number μ is called the rate of convergence.

If the above holds with μ = 0, then the sequence is said to converge superlinearly. One says that the sequence converges sublinearly if it converges, but μ=1.

The next definition is used to distinguish superlinear rates of convergence. We say that the sequence converges with order q for q > 1 to L if

In particular, convergence with order 2 is called quadratic convergence, and convergence with order 3 is called cubic convergence.

This is sometimes called Q-linear convergence, Q-quadratic convergence, etc., to distinguish it from the definition below. The Q stands for “quotient,” because the definition uses the quotient between two successive terms.

Extended definition

The drawback of the above definitions is that these do not catch some sequences which still converge reasonably fast, but whose “speed” is variable, such as the sequence {bk} below. Therefore, the definition of rate of convergence is sometimes extended as follows.

Under the new definition, the sequence {xk} converges with at least order q if there exists a sequence {εk} such that

and the sequence {εk} converges to zero with order q according to the above “simple” definition. To distinguish it from that definition, this is sometimes called R-linear convergence, R-quadratic convergence, etc.

Examples

Consider the following sequences:

The sequence {ak} converges linearly to 0 with rate 1/2. More generally, the sequence Cμk converges linearly with rate μ if |μ| < 1. The sequence {bk} also converges linearly to 0 with rate 1/2 under the extended definition, but not under the simple definition. The sequence {ck} converges superlinearly. In fact, it is quadratically convergent. Finally, the sequence {dk} converges sublinearly.

Get Help With Your Essay

If you need assistance with writing your essay, our professional essay writing service is here to help!
Find out more about our Essay Writing Service

CONVERGENCE SPEED FOR DISCRETIZATION METHODS

A similar situation exists for discretization methods. Here, the important parameter is not the iteration number k but the number of grid points, here denoted n. In the simplest situation (a uniform one-dimensional grid), the number of grid points is inversely proportional to the grid spacing.

In this case, a sequence xn is said to converge to L with order p if there exists a constant C such that

| xn − L | < Cn − p for all n.

This is written as |xn – L| = O(n-p) using the big O notation.

This is the relevant definition when discussing methods for numerical quadrature or the solution of ordinary differential equations.

Examples

The sequence {dk} with dk = 1 / (k+1) was introduced above. This sequence converges with order 1 according to the convention for discretization methods.

The sequence {ak} with ak = 2-k, which was also introduced above, converges with order p for every number p. It is said to converge exponentially using the convention for discretization methods. However, it only converges linearly (that is, with order 1) using the convention for iterative methods.

RATE OF CONVERGENCE OF BISECTION METHOD

If f is a continuous function on the interval [a, b] and f(a)f(b) < 0, then the bisection method converges to a root of f. In fact, the absolute error is halved at each step. Thus, the method converges linearly, which is quite slow. On the other hand, the method is guaranteed to converge if f(a) and f(b) have different signs.

The bisection method gives only a range where the root exists, rather than a single estimate for the root’s location. Without using any other information, the best estimate for the location of the root is the midpoint of the smallest bracket found. In that case, the absolute error after n steps is at most

If either endpoint of the interval is used, then the maximum absolute error is

the entire length of the interval.

These formulas can be used to determine in advance the number of iterations that the bisection method would need to converge to a root to within a certain tolerance. For, using the second formula for the error, the number of iterations n has to satisfy

to ensure that the error is smaller than the tolerance ε.

If f has several simple roots in the interval [a,b], then the bisection method will find one of them.

RATE OF CONVERGENCE OF FALSE-POSITION METHOD

If the initial end-points a0 and b0 are chosen such that f(a0) and f(b0) are of the opposite signs, then one of the end-points will converge to a root of f. The other end-point will remain fixed for all subsequent iterations while the converging endpoint becomes updated. Unlike the bisection method, the width of the bracket does not tend to zero. As a consequence, the linear approximation to f(x), which is used to pick the false position, does not improve in its quality.

One example of this phenomenon is the function,

f(x) = 2×3 − 4×2 + 3x

on the initial bracket [−1,1]. The left end, −1, is never replaced and thus the width of the bracket never falls below 1. Hence, the right endpoint approaches 0 at a linear rate.

While it is false to think that the method of false position is a good method, it is equally a mistake to think that it is unsalvageable. The failure mode is easy to detect and easily remedied by next picking a modified false position, such as

or

down-weighting one of the endpoint values to force the next ck to occur on that side of the function. There are other ways to pick the rescaling which give even better convergence rates.

RATE OF CONVERGENCE OF SECANT METHOD

The iterates xn of the secant method converge to a root of f, if the initial values x0 and x1 are sufficiently close to the root. The order of convergence is α, where

is the golden ratio. In particular, the convergence is superlinear.

This result only holds under some technical conditions, namely that f be twice continuously differentiable and the root in question be simple (i.e., with multiplicity 1).

If the initial values are not close to the root, then there is no guarantee that the secant method converges.

The right-most quantity above may be expressed as

since . Then, from a Taylor expansion of about one finds

for some . Similarly

Placing these quantities into Equation 4.9 will result in some cancellation,

or

The approximation expressed in Equation 4.11 can be explicitly quantified by recognizing that for some . Hence

This completes the analysis of the final term in Equation 4.8. The first term in Equation 4.8 can be analyzed similarly, to obtain

Hence, the error given in the secant method is roughly given as

A more careful investigation and analysis produces the exact expression

for some .

To generate a complete convergence analysis, assume that f”(x) is bounded and in some neighborhood of . These assumptions imply that sufficiently close to . Further, assume that the initial values and are chosen sufficiently close to to satisfy

for some K<1. Then,

The exponents on K form the Fibonacci sequence, . The Fibonacci sequence is defined inductively, as

The general error term is then given to be

The Fibonacci number have an explicit formula, namely

with . Note that , and since K < 1 we have .

At this point, we have

While somewhat complex-looking, the equation above actually produces the convergence rate that we seek.

RATE OF CONVERGENCE OF NEWTON RAPHSON METHOD

Suppose that the function ƒ has a zero at α, i.e., ƒ(α) = 0.

If f is continuously differentiable and its derivative is nonzero at α, then there exists a neighbourhood of α such that for all starting values x0 in that neighbourhood, the sequence {xn} will converge to α.

If the function is continuously differentiable and its derivative is not 0 at α and it has a second derivative at α then the convergence is quadratic or faster. If the second derivative is not 0 at α then the convergence is merely quadratic. If the third derivative exists and is bounded in a neighbourhood of α, then:

where

If the derivative is 0 at α, then the convergence is usually only linear. Specifically, if Æ’ is twice continuously differentiable, Æ’ ‘(α) = 0 and Æ’ ”(α) ≠ 0, then there exists a neighbourhood of α such that for all starting values x0 in that neighbourhood, the sequence of iterates converges linearly, with rate log10 2 (Süli & Mayers, Exercise 1.6). Alternatively if Æ’ ‘(α) = 0 and Æ’ ‘(x) ≠ 0 for x ≠ 0, x in a neighbHYPERLINK “http://en.wikipedia.org/wiki/Topological_neighborhood”ourhood U of α, α being a zero of multiplicity r, and if Æ’ ∈ Cr(U) then there exists a neighbourhood of α such that for all starting values x0 in that neighbourhood, the sequence of iterates converges linearly.

However, even linear convergence is not guaranteed in pathological situations.

In practice these results are local and the neighbourhood of convergence are not known a priori, but there are also some results on global convergence, for instance, given a right neighbourhood U+ of α, if f is twice differentiable in U+ and if , in U+, then, for each x0 in U+ the sequence xk is monotonically decreasing to α.

Proof of quadratic convergence for Newton’s iterative method

According to TaylorHYPERLINK “http://en.wikipedia.org/wiki/Taylor’s_theorem”‘HYPERLINK “http://en.wikipedia.org/wiki/Taylor’s_theorem”s theorem, any function f(x) which has a continuous second derivative can be represented by an expansion about a point that is close to a root of f(x).