Estimating Error in a Quadrature

[Teg Veece]

Hey,
I'm using a quadrature to estimate the integral of a function.
Intuitively, I know that if the function is a very smooth function, the quadrature will perform well at a low order (few samples).
If however, the function in more complex, I'll need to sample it more frequently for the quadrature to be as accurate.

I'm wondering if there's some equation that expresses this intuition. Something that I can point to and use to explain why more complex functions require a higher order quadrature for the same level of accuracy.

I think the expression should contain some reference to the function's derivative.

Thanks.

 

[Robert1986]

Well, Gaussian Quadrature, is (i'm pretty sure) order 2n accurate, meaning that the error is less than

\frac{k}{(2n)!}||f^{2n}||_{\infty}

where f is the function being interpolated, and k is constant. So, if f is a degree 2n-1 polynomial, then Gaussian Quadrature is exact.

Does this help?

 

[Teg Veece]

It does actually. Thanks for that.

Do you know what the error is for a Clenshaw-Curtis quadrature?

 

[Robert1986]

Not off hand, but google probably does :) .

 

[Teg Veece]

I found something on the wikipedia page saying it's error is bounded by
O([2N]^{-k}/k) for a k-times differentiable integrand.

I'm not sure what a k-times differentiable integrand is exactly but, at a guess, is a function like x^2+2x+5 differentiable 3 times and x^9+2 differentiable 10 times so it's a proxy to complexity?The function I'm trying to integrate is exp(-x^2/L) with respect to x between the limits, -1 and 1.
I'm finding though that the smaller I make L, the worse the quadrature gets. I don't think I'm changing the number of times it can be differentiated, so why does the approximation get worse?
My intuition is that by making L smaller, the width of this function (Gaussian) becomes smaller and a higher order quadrature is needed to accurately probe it but I'm not sure if any equation backs this up.

 

[Robert1986]

As a side note, one of the drawbacks of Gaussian Quadrature is that it is kind of difficult to get a good grasp on the error. For this reason, people estimate the error by I_m - I_n where m > n and I_n is the estimated integral with n nodes.

Now, I think that the problem is that as L gets bigger and bigger, the meaty portion of the function bunches up around 0, right? So, if you are using a few nodes, you probably aren't getting much sampling from the real "meaty" part of this function.

I'd keep increasing the number of nodes until I_{n+2} - I_n is within your tolerance. This will give you better than necessary accuracy, which isn't all that bad.

 

[Robert1986]

I found something on the wikipedia page saying it's error is bounded by
O([2N]^{-k}/k) for a k-times differentiable integrand.

I'm not sure what a k-times differentiable integrand is exactly but, at a guess, is a function like x^2+2x+5 differentiable 3 times and x^9+2 differentiable 10 times so it's a proxy to complexity?

You are sort of right. But, x^9 + 2 is infinitely times differentiable since the trivial ploynomial p(x) = 0 is differentiable.