Filetype PDF | Posted on 14 Sep 2022 | 3 years ago
Authentication
digital resources
173x Filetype PDF File size 0.89 MB Source: academic.oup.com
Series methods for integration
By K. Wright*
Some methods of integration using Chebyshev and Legendre polynomial series are compared,
mainly from an empirical point of view. The evaluation of both definite and indefinite integrals
is considered, and also the advisability of dividing a range of integration using separate series in
each part instead of covering the whole range with one series. Downloaded from https://academic.oup.com/comjnl/article/9/2/191/623440 by guest on 14 September 2022
1. Introduction convenience since this does not cause any restrictions as
Clenshaw and Curtis (1960) suggested a method of long as a and b are finite.
finding both the definite and indefinite integrals of a Certain sets of points are particularly convenient since
function by expanding the integrand as a Chebyshev corresponding sets of polynomials exist satisfying
series and integrating it. The main idea is that the size orthogonal summation relations over them, and this
of the series coefficients gives a convenient estimate of enables the series coefficients to be determined very
simply. For the Chebyshev polynomials T (x) there are
the accuracy obtained and this allows further action to n
be taken automatically. Since then, various alterations two sets of n points with this property: the zeros of
T {x) X-, = cos (2/ + l)7r/«, j = 0, . . . n — 1, and the
and modifications to this scheme have been put forward. n
maxima and minima of T _ (x) with the end points
Here it is hoped to make a critical assessment of these n x
possibilities, along with some further slight variations, x, = cosjir/in - 1), j = 0, . . . n - 1.
mainly from an empirical point of view though some Elliott (1965) considers both these sets of points for
theoretical work is also considered. Examples are given interpolation and integration. He calls the first set the
which illustrate the properties of the method and which "classical" points, as they correspond to a general
either verify or show some limitations to the theoretical property of orthogonal polynomials. The other points
work. Naturally the conclusions are not very clear-cut, Elliott calls the "practical" set, and these are the points
but certain general properties are discernible and some that Clenshaw and Curtis use. They have the useful
doubts are raised about the validity of previous views. property that the points for m — 2n — 1 contain those
for n. Both sets of points were used by Lanczos (1938,
2. Methods considered 1957).
All the methods considered here can be put in the It is clearly not necessary to restrict this method to
following general form: for the integral Chebyshev series, for other sets of orthogonal poly-
nomials satisfy orthogonality relations over their zeros.
An obvious choice is to use Legendre polynomials—
ff(x)dx or \f{x)dx then for the definite integral the method reduces to the
Gauss formula. It suffers from the defect that the points
(i) suppose {<£,(*)} is a complete set of functions on are no longer simple cosines, but these numbers can be
(a, by, stored if necessary.
(ii) obtain an approximation to the integrand in the Since the Gauss-Legendre method does not seem to
form have been given explicitly before, we state it here.
Suppose the Gauss points and weights of order n are
{Xj} and {w,}. Then the approximation to f(x) is
o f{x) ~ S a P (x) where
n-l ;) =/(*;) r r
by making 2 a,
o
at n points x
h a = (r (1)
r
(iii) integrate this interpolating function.
The method is characterized by (a) the choice of the This assumes the usual normalization of the Legendre
polynomial so that P (l)=l- The series is then
functions { (x)}, (b) the choice of the points {*,}. r
r integrated using
Here (x) is taken as some polynomial of degree r and
r
consequently the values of the integral only depend on P,(x)dx = {P ,(x) - P _ 1). (2)
the choice of {*,}, at least apart from rounding effects. r+ r
The series coefficients will naturally still depend on the
(x) and they can be used to estimate the accuracy. Filippi (1964) suggests a slightly different idea which
r obtains the indefinite integral as a Chebyshev series, but
The range of integration will be taken as (—1,1) for
University of Newcastle upon Tyne Computing Laboratory, 1 Kensington Terrace, Newcastle upon Tyne 2.
191
Series methods for integration
this time by expanding the integrand in terms of the 3. Error estimates using series
derivatives of Chebyshev polynomial T' (x), which
n Classical error estimates using derivatives can be used
consequently eliminates the integration step. He uses with series formulae, but they are not of great practical
points similar to the "practical" ones but not including value since the derivatives are not usually available.
the end points. That is x} = cosjir/(n -f l),j = 1, . . . n. Similarly, newer methods such as that given by Davis
There is an orthogonality relation which makes these and Rabinowitz (1954), though more convenient, still
points also convenient, and they have a property similar involve additional knowledge of the integral, such as
to the practical points that the points for m = In + 1 some norm, which may be difficult to estimate accurately.
contain those for n. The series methods, on the other hand, give a very
These are the four methods considered here. The simple means of estimating the error, but as compensa- Downloaded from https://academic.oup.com/comjnl/article/9/2/191/623440 by guest on 14 September 2022
advantage of using a Chebyshev expansion is that the tion they are more difficult to justify rigorously.
corresponding series is usually rapidly convergent. The Though the methods require the consideration only of
choice of Legendre polynomials seems reasonable on a finite series approximating the integral it is often con-
account of their connection with Gauss quadrature. venient to compare this with the corresponding infinite
The naive justification of the choice of Chebyshev zeros series expansion. They should differ little if the series is
is that the error has a factor I1(JC — jc ) = KT {x\ and
y n rapidly convergent, and then the next term in the series
this factor has smallest maximum modulus for this will form the dominant term in the error. As this is
choice of points. not known the last term found can be used instead, and
The usual method of use of these formulae is to this would normally be expected to be larger than the
increase the number of points until sufficient accuracy is error. It is probably safest, as Clenshaw and Curtis
obtained. This is clearly particularly convenient if suggest, to take the largest of the last two or three terms
function values already found can be used again, but in the integrated series as an estimate, in the hope that
even so it is not obviously the best strategy. Hence the this procedure will take care of any spuriously small
possibility of splitting the range using two or even more coefficients caused, for example, by the function being
series is considered, as well as the straightforward use. odd or even. This estimate can be applied to both the
This corresponds to the normal use of finite-difference definite and indefinite integrals.
type methods, and clearly needs consideration. For the Gauss-Legendre method definite integral the
These methods, unlike high-order Newton-Cotes error is considerably smaller than would be predicted
formulae, are convergent as the number of points by this estimate. Suppose the infinite series expansion
increases for any continuous function. All the weights 00
effectively used by the methods for definite integrals can of the integral is fix) = 2 A PAx) and the cor-
be shown to be positive, and so using a theorem in r
Krylov (1962) p. 265 the methods are convergent. responding coefficients obtained by collocation are
{a }, r = 0 . . . n — 1. Then the definite integral is
Consider now what is required of a method of inte- r
just 2A since
gration. It should be efficient in some sense—giving 0
high accuracy for little work. To make this more J_P (x) = 0, r # 0,
precise we find two separate problems: for the definite r
integral we want to minimize the error in just one value; so the error is
for the indefinite integral we want to minimize the E = 2(A — a ).
largest error in the range considered. These are clearly 0 0
not the same problem and it would be surprising if they Now using (1)
had the same answer. Even the separate problems as
stated do not obviously have a solution, since they may a = i S w,f(x,) = * 2 w, 2
depend on the nature of the integral as well as the 0
method of integration. However, it may still be possible 1=1 (=1 r=0
to choose a set of points which though not always Changing the order of summation gives
optimum are generally better than others in some way.
For the definite integral we have the precise result r=0 1=1
that the Gauss points give an integral value exact for as .1
high a degree polynomial as possible, and this leads to but 2 w,PAx,) = \ PAx)dx if r < :
the conclusion that the Gauss formula will generally be i=l J-l
better for smooth functions, though not being exact for = 0 if 0 < r < In.
every function of this type it cannot be the optimum For other r
choice for every function.
Another separate important point needing considera-
tion is the practical usefulness of possible error estimates, and if r is odd X 1S an
either if one wants to know the accuracy obtained by a function. /) = 0 since PA )
particular formula or wants to make it the basis of an So a - A = i 2 A 2 w,P Ax,)
automatic integration procedure. 0 o lr 2
192
Series methods for integration
Table 1
1
Series coefficients of indefinite integral I (t + 3)" dt
CLASSICAL PRACTICAL GAUSS FILIPPI
+0-752905650 +0-752905604 +0-386294361 +0-752905544
+0-343145751 +0-343145750 +0-341116917 +0-343145751
-0 029437252 -0 029437251 -0038917917 -0-029437252 Downloaded from https://academic.oup.com/comjnl/article/9/2/191/623440 by guest on 14 September 2022
+0-003367089 +0 003367087 +0005334194 +0-003367089
-0-000433276 -0-000433265 -0-000783747 -0-000433276
+0-000059472 +0000059419 +0000119456 +0 000059471
-0000008510 -0000008511 -0-000018637 -0 000008503
+0000001287 +0000001326 +0 000003024 +0000001249
-0000000188 -0000000193 -0 000000470 -0000000182
and \A \ (3) Table 2
2r 9 1
Errors (xlO ) in indefinite integral J (t + 3)" dt
So for rapid convergence 2A can be taken as an
2n
estimate of the error in the integral. This is rather t CLASSICAL PRACTICAL GAUSS FILIPPI
limited in its application unless some knowledge of the
behaviour of the series coefficients is assumed, but it is —0-8 57 +23 -43 +9
interesting to remember when examining empirical -0-6 +47 + 127 + 33 + 56
results. -0-4 -3 -39 + 16 +58
For more slowly convergent series Clenshaw and -0-2 -78 -145 -42 + 13
Curtis give an estimate of the error in the definite 0 -15 +3 -2 +40
integral using the "practical" points, and Elliott con- 0-2 -46 + 143 +37 +65
siders this further for both the "practical" and "classical" 0-4 -15 +58 -10 + 29
cases. 0-6 -52 -62 -23 + 30
As an example illustrating some of these points the 0-8 + 12 + 1 +25 + 59
results for the integral 10 -18 + 16 0 +61
are given using 8 points. The series representing the examples will be considered. Most of the functions
indefinite integral are given in Table 1 and the errors considered were well behaved, having singularities of
in the integral at various points in the range in Table 2. different types at varying distances from the range of
It is illustrated quite clearly that the Gauss-Legendre integration. Various numbers of points (usually less
method gives a better value for the definite integral than 20) were taken for all examples. The superiority
(t = 1) than the indefinite integral. This is perhaps even of the Gauss points for the indefinite integral appears
more marked for the 6-point formula where the definite remarkably consistent, though I know of no explana-
9
integral has error 1 X 10~ while the indefinite for tion. Similarly the practical points consistently gave the
9
Gauss has error 1,859 x 10~ , and for the practical worst maximum error for the indefinite integral. Both
9
points 8,183 x 10~ . The practical and classical points the classical and practical points have comparatively
give about the same accuracy for the definite integral small errors at the end of the range, while for the Filippi
while the Filippi value is appreciably worse. For the method the error is usually near its maximum there.
indefinite integral the Gauss method, quite surprisingly The size of the last term seems only reliable as an upper
is best, followed by Filippi, classical and practical points. error estimate if the series is very rapidly convergent.
The last term in the integrated series is a fairly close 9
upper bound of the largest error in all cases, though (The order of this is that a should be about 10~ a0,
quite considerably larger, as expected, for the Gauss though this is quite variable.)
points. As an exceptional example the results using 8 points
for J V0 + t)dt are given in Tables 3 and 4. The
Clearly no reliable conclusions can be drawn from one integrand has a slowly convergent series on account of
integration or even from a small number of examples. the branch point at t = —1. Here the Gauss points no
Since it would be impracticable to give a large number longer show a more accurate value for the definite
of numerical results, properties which appeared con- integral than for the indefinite integral. This is still,
sistent will be mentioned and later some exceptional however, consistent with the estimate of 2a where a
i6 r
193
Series methods for integration
are the coefficients of the series for the integral (not Table 3
shown). The value for ai6 using 20 points is ~000095
which is larger than half the error ~0-00024. This is a Series coefficients of \ -\/(l + t)dt,
consequence of the way the series converges, which will Range (—1,1) 8 points
be considered in more detail later.
The Gauss points still give the best indefinite integral
followed by classical, Filippi and practical methods. CLASSICAL PRACTICAL GAUSS FILTPPI
Similar behaviour occurs for 4, 6, 10, and 20 points.
The uniformity of sign of the error in the Filippi method + 1-60003 + 1-59856 +0-75473 + 1-60277
though consistent for all numbers of points taken with +0-96026 +0-96050 +0-96973 +0-96039 Downloaded from https://academic.oup.com/comjnl/article/9/2/191/623440 by guest on 14 September 2022
this function, does not occur with all functions, and does +0-13727 +0-13703 +0-17961 +0-13713
not have any obvious significance. -001533 -001506 -0-02290 -001518
+0-00426 +0-00395 +0-00685 +0-00409
4. Comments on other work on series -000171 -000136 -0-00285 -000153
4.1 Elliott's comparisons +O-OOO88 +0-00140 +0-00148 +0-00066
Elliott (1965) considers the comparison of the practical -0-00056 -000171 -0-00093 -0-00030
and classical points more generally, considering inter- +0-00022 +0-00071 +0 00038 +000011
polation as well as integration. He also discusses the
properties of some particular types of series in detail, Table 4
relating these to the singularities of the functions. In
particular he considers the infinite Chebyshev series with s
a = t" which corresponds to the function Errors in f V(l + *) dt X 10
n
1 - t2 -0-8 +76 + 147 -23
JKJ 2 -101
2{\+t~2tz) -0-6 0 -145 -58 -116
2
which has one simple pole at z = (1 + t )/2t. He shows -0-4 +23 + 131 -54 -118
that the maximum error for interpolation will be smaller -0-2 +55 +279 -38 -108
for the classical points if / < \/2 — 1, and the practical 0 + 33 + 114 -47 -113
ones otherwise (/ real). He then considers even and 0-2 + 14 -27 -55 -117
odd functions of the form 0-4 +31 +48 -46 -112
0-6 +41 + 149 -44 -112
and shows that the practical points are always best for 0-8 +25 + 100 -52 -115
these functions. These correspond to series of the form 1-0 +32 +89 -48 -115
a = f, a , = 0, or a = 0, a , = r. If, however,
r 2r+ 2r 2r+ 2 2
one considers a function of the form l/(a + z ), it M
appears by similar arguments that the classical points J - JN- I (4)
are always superior. This casts some doubt on Elliott's
conclusion that the practical points are generally pre- and for the classical points
ferable for any odd or even function. Probably more
significant is his other conclusion that the differences in (5)
maximum error are always very small, and this continues m=[
where z are the positions of the poles, g , h are
to hold. m m m
Elliott also produces error estimates for the definite associated with the singularities and are dependent on
integral using the two methods and then considers their N the number of points. Putting t = cos 6, x = cos a
asymptotic properties. He shows that for the practical and integrating by parts gives
3 3 sin a sin no.
points the error is O(l/« ) or more precisely O(£ t"/n ),
2 r 2
and for the classical points it is O(l/« ) or O(2 t"/n ), so Now if a = 0 this first term vanishes giving
r
that the practical points should usually be better. Two
reservations need to be made however: (a) the theory but for a ^= 0 this term stays giving only O(l/iV). For
applies to n large, (b) it does not apply to the indefinite the definite integral there is further cancellation when
integral. the Js are subtracted for the practical points, but again
Similar analysis can be performed for the indefinite this does not occur for the indefinite integral for
integral. Following Elliott closely, with the notation
that J {z) = fT (t)/(t - z)dt instead of the definite
n n ^^ in - 1)« C7)
J-i — sin (« + l)a},
integral, we have the estimate of the error using the which may add instead of cancelling.
practical points as
194
no reviews yet
Please Login to review.
