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 |μ| 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 | 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) 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 KThe 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 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).