Accelerated Convergence Techniques

[this page | pdf | references | back links]

The term accelerated convergence appears in a number of different guises in mathematics and finance.


1.            In the context of numerical integration (also called quadrature), accelerated convergence can relate to approaches that aim to converge more rapidly to the correct answer as the number of evaluations, , of the underlying function increases.


Perhaps the most important example is what is more classically known as Simpson’s rule. The theory can be developed as follows. The simplest and perhaps most obvious way of evaluating an integral numerically is the so-called trapezoidal rule. Suppose we are trying to evaluate  and the abscissas (i.e. the points at which the function is evaluated) are equally spaced, say at  for  (so  and ), with the values of  there being . The trapezoidal rule involves approximating the integral by the following formula:



The accuracy of this approximation can be expressed as follows:



By  we mean that the true answer differs from the estimate by an amount that is the product of some numerical coefficient times  times the value of the second derivative of the function somewhere in the interval of the integration (assuming that the function is sufficiently smooth and actually has a second derivative).


Repeated application of the above over each of the   parts of the overall integration results in the extended trapezoidal rule, namely:



Here we have written the error estimate in terms of the overall interval size  and  rather than  as usually  will be fixed and  varied to achieve a desired level of accuracy. This highlights that the accuracy of the trapezoidal rule improves by a factor of  as  increases (if the function being integrated is sufficiently smooth).


The trapezoidal rule is a two point formula (in the sense that each underlying interval involves just two points,  and ) and is exact for polynomials up to and including degree 1, i.e.  (i.e. straight lines). We might therefore expect that there is a three point formula that is exact up to polynomials of degree two (i.e. quadratics). This is indeed the case, and it involves Simpson’s rule (here we use the convention that , ,  etc.



Classically, a variety of other formulae were developed that fitted higher and higher order polynomials, e.g. Simpson’s 3/8 rule, Bode’s rule etc., but in practice the (extended) trapezoidal rule has some subtle but important facets which make it the starting point for many different numerical integration techniques, see e.g. Press et al. (2007). In particular, the error of the approximation which begins with a term of order  is entirely even when expressed in powers of .


Suppose, therefore, that we evaluate the trapezoidal rule with  steps (i.e.  abcissae) and come up with an answer . Suppose we repeat it with  steps (i.e. the   abcissae previously used plus  further ones equally spaced between them) and come up with an answer . Then, if the function is sufficiently smooth, the leading error term in the second evaluation will be one-quarter of the size of the leading error in the first evaluation. We should therefore be able to test for convergence by repeatedly doubling the number of terms evaluated, and we should be able cancel out entirely the leading order error term using the combination:



The residual error term is of order , the same as Simpson’s rule; indeed it should not take long to realise that  is exactly the same as Simpson’s rule.


Various other refinements of this idea can be used to improve convergence further, e.g. Romberg integration.


2.            Alternatively, accelerated convergence can relate to other more general methods of improving the convergence properties of a series, i.e. where we approach the same end answer but with fewer evaluations of the series.


For example, suppose we have two convergent series, say:






with the property that



Then Kummer’s transformation indicates that a series with a more rapid convergence to the same value is given by the following, see Abramowitz and Stegun (1972):



This becomes particularly helpful if  is known already; useful cases include:



and more generally:



Other examples of convergence improvement are given in e.g. Weisstein (2015).


Desktop view | Switch to Mobile