From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) Subject: Re: integration error Date: 12 Dec 1999 16:34:15 -0500 Newsgroups: sci.math.num-analysis Keywords: comparison of errors from various numerical integration algorithms In article <830apk$9nc$1@ssauraab-i-1.production.compuserve.com>, Jan C. Hoffmann <100550.3643@compuserve.com> wrote: : :Khalid Al-Qurashi schrieb in im Newsbeitrag: :>3853A03C.9A2C2DEF@leeds.ac.uk... :> hello, :> Can anyone tell me please what is the difference between integration :> error calculated from Simpson rule and that calculated from Romberg :> method? :> I will address the reply later. To the question itself: *** (Preamble:) *** Romberg scheme, if we are talking about the same method, is a sequence of successive refinements of integral sums, starting with Trapezoidal Rule ("column number zero"), equipped with some stopping criterion. The success of the most frequently quoted error formula for Trapezoidal Rule depends on the boundedness of the second derivative of the integrand. Then the error converges to 0 at the rate bounded by C * h^2 where C is a constant depending on the bound of that second derivative, and h is the stepsize. The bound is sharp, attained at polynomials of degree 2. The success of "column number k" of Romberg scheme depends on the bounedness of the derivative of order (2*k+2) of the integrand, and then the error is bounded by a constant times h^(2*k+2). The bound is sharp, attained at polynomials of degree (2*k+2). *** (End of preamble, beginning of the core of the reply:) *** Simpson's Rule is exactly "column number one" of Romberg Scheme. You need the 4-th derivative bounded, and the error is bounded by C * h^4. And now for the previous reply: >Hi, > >I can give you the difference for Simpson's Rule and Gaussian Quadrature: > >Example: > >Integral[0,1](x^(1/3)) dx > >Analytical solution: 0.75 > >Simpson: 0.7497051 (100 intervals) >Simpson: 0.7499866 (1000 intervals) > The illustration is not informative at all: the integrand f(x) = x^(1/3) has even the first derivative ((1/3)*x^(-2/3)) unbounded, and things get worse for higher order derivatives (orderwise:-). It's like trying to show the qualities of a racing car by testing it in a rough landscape for which tanks are more appropriate. Or trying to fell a tree using razor blades. Given enough time and a good supply of razor blades, one could fell the tree, provided the tree would grow slower than the progress of cutting it. Still, a saw (roughly from the same family of tools) is considered a more efficient choice. (Will I get letters from a Society for Prevention of Cruelty to Plants?:-)= Incidentally, Simpson's Rule for this integrand is just as inefficient as Trapezoidal Rule, and Romberg Scheme would be a waste of effort because of the same lack of improvement; all have order of magnitude of the error about C * h^(4/3) (an exercise in summation estimates). >Gauss: 0.7511323 Gauss what? Gauss method (simple) is specified by the order and the weight. Gauss (composite) does that plus stepsize. If it was used for weight 1 and integrand x^(1/3), it may be just a trifle better than Simpson, but the speed of convergence is not at all good enough. I did not go into the calculations, but the composite rule with stepsize h would still have order h^(4/3). On the other hand, if you had a Gauss formula for weight x^(1/3) and integrand 1, it would give you an exact result by sampling at one point. Here it is: Gauss formula with weight x^(1/3) with 1 node, exact for integrands which are polynomials f of degree 1 or less, is (3/4) * f(4/7) (the beginning of the sequence of orthogonal polynomials with weight x^(1/3) over [0,1] is 1, x-4/7, ...) so that the integral will come out as 3/4, no improvement needed. >With Romberg and Simpson you can adjust the error by the number of >integration steps. Taking into account the agonizing slowness of convergence, since the integrand fails to have the required bounds on derivatives. Cheers, ZVK(Slavek). > >-- >Jan C. Hoffmann (c/o MTEC) >http://ourworld.compuserve.com/homepages/MTEC/ ============================================================================== From: David Wilkinson Subject: Re: integration error Date: Sun, 12 Dec 1999 21:07:27 +0000 Newsgroups: sci.math.num-analysis Simpson's rule is usually used in its composite form: I = h/3{f(x0)+4f(x1)+2f(x2)+4f(x3)+2f(x4)+..+2f(xn-2)+4f(xn-1)+f(xn)) where xi = a+ih (i=0,...,n) if the 4th derivative f4 is continuous on [a,b] a bound on the error estimate is |E(h)|<=1/180*h^4(b-a)M where |f4(x)|<=M for all x in [a,b]. So, if you can find the 4th derivative of the integrand you can estimate an upper bound for the error. If the integrand is a cubic polynomial or less then f4 is zero and Simpson is exact, but in the general case there is an error. Obviously by taking more points and reducing h you can make the error as small as you like, subject to rounding errors, and at the expense of more computation, since the error is proportional to h^4. Romberg's method allows you to specify the error you will accept. It then repeatedly doubles, or triples, the number of points at which the integrand is evaluated and uses Richardson extrapolation to estimate the integral and its error, stopping when the error estimate is less than that specified. In principle Romberg requires less evaluations than Simpson for a given accuracy. Hope this helps. In article <3853A03C.9A2C2DEF@leeds.ac.uk>, Khalid Al-Qurashi writes >hello, >Can anyone tell me please what is the difference between integration >error calculated from Simpson rule and that calculated from Romberg >method? > >Thanks > -- David Wilkinson ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: integration error Date: 13 Dec 1999 10:52:06 GMT Newsgroups: sci.math.num-analysis In article <3853A03C.9A2C2DEF@leeds.ac.uk>, Khalid Al-Qurashi writes: |> hello, |> Can anyone tell me please what is the difference between integration |> error calculated from Simpson rule and that calculated from Romberg |> method? assume that the integrand f is as often differentibal as you wish (there are error expressions without that strong assumption, but this would yield much more involved expressions) then error of iterated Simpson rule with knot distance h (equidistant) is -(1/180)*(b-a)*h^4*f^{4}(ksi) fro some ksi in {a,b} the integration interval simpsons rule gives the _second_ column in Rombergs scheme. Fist column is the Trapezoidal rule with -(1/12)*(b-a)*h^2*f^{2}(ksi) where again the knot istance is h whereas the k-th column in Rombergs scheme gives in row i, where knot distance is h_i=(b-a)/(2^i) -(b-a)^(2k+3)*(B_{2k+2}/((2k)!) * (1/ 2^((i-k)*(2k+2)+k(k+1))) * f^{2k+2}(ksi) B_{2k} are the Bernoulli numbers. hope that helps peter