jagomart
digital resources
picture1_Methods Of Integration Pdf 87270 | 9 2 191


 167x       Filetype PDF       File size 0.89 MB       Source: academic.oup.com


File: Methods Of Integration Pdf 87270 | 9 2 191
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 ...

icon picture PDF Filetype PDF | Posted on 14 Sep 2022 | 3 years ago
Partial capture of text on file.
          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
The words contained in this file might help you see if this file matches what you are looking for:

...Series methods for integration by k wright some of using chebyshev and legendre polynomial are compared mainly from an empirical point view the evaluation both definite indefinite integrals is considered also advisability dividing a range separate in each part instead covering whole with one downloaded https academic oup com comjnl article guest on september introduction convenience since this does not cause any restrictions as clenshaw curtis suggested method long b finite finding certain sets points particularly convenient function expanding integrand corresponding polynomials exist satisfying integrating it main idea that size orthogonal summation relations over them coefficients gives estimate enables to be determined very simply t x there accuracy obtained allows further action n taken automatically then various alterations two property zeros cos l r j modifications scheme have been put forward maxima minima end here hoped make critical assessment these possibilities along slight ...

no reviews yet
Please Login to review.