167x 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.