Most effective non uniform mesh, composite trapezoidal rule. help pleaseee

[aerot89]

Hi guys, I'm using a composite trapezoidal rule to approximate the integral of functions. Up till now I have been using a uniform composite mesh, ie, there are J intervals, each interval being 1/J wide (since the integral is between 0 and 1).

How do I find the most efficient non-uniform mesh that will reduce the error while keeping the number of intervals J the same? eg ((0:J)/J)^x

Any help would be greatly appreciated, I have looked through all my lecture notes, and done some pretty thorough online searching but to no avail.

Thanks
Edit/Delete Message

 

[mathman]

As long as the integrand's properties are completely undefined, uniform is the best you can do.

 

[aerot89]

Hey, thanks for your response, the integrals we are dealing with are actually well defined though.

I wrote a MATLAB program that would take the uniform mesh over [0,1] and raise it to a power eg
mesh = ((0:J)/J)^x, so that the points were more concentrated at the start or end depending on the choice of x.

it then calculated the value of x that minimised the error in the numerical estimate of the integral.

Is there anyway of proving why this value of x produced the most efficient mesh?

Thanks

 

[uart]

Hey, thanks for your response, the integrals we are dealing with are actually well defined though.

I wrote a MATLAB program that would take the uniform mesh over [0,1] and raise it to a power eg
mesh = ((0:J)/J)^x, so that the points were more concentrated at the start or end depending on the choice of x.

it then calculated the value of x that minimised the error in the numerical estimate of the integral.

Is there anyway of proving why this value of x produced the most efficient mesh?

Thanks

In general you would want to pack the samples more closely where the absolute value of the second derivative is large and more sparsely where it (the second derivative) is small.

However wouldn't the effort be better spent in applying a higher order integrator such as Simpsons rule?

 

[aerot89]

Ah thanks, that's pretty helpful. I guess it makes sense because the rate of change of the gradient is greatest! Yeah but I've got an assignment that is all based around the composite trapezoidal rule and developments on it..

Thanks again.

 

[mikeph]

Taking the problem to extremes, say you have a curve y=x^2 in the domain [0,1], and you are allowed three samples, one at (0,0), one at (1,1). Where do you put the third to minimise the error?

If your point is at the value a (for 0<a<1), then your estimation of the area is:

trapezium 1 = a*(0 + a^2)/2 = a^3/2
trapezium 2 = (1 - a)(a^2 + 1)/2

so the estimate function is f(a) = [a^3 + (1 - a)(a^2 + 1)]/2
f(a) = (a^2 - a + 1)/2

The error is then the real value minus this estimate, and the real area is 1/3.

err(a) = 1/3 - (a^2 - a + 1)/2

to minimise this we differentiate and set equal to zero,

err'(a) = a - 1/2 = 0
a = 1/2.

ie. an even mesh. (in line with post #4 and your reply since the 2nd derivative of x^2 is constant).

This is my interpretation of your discussion about the composite trapezoidal rule... is it correct? Basically summing all the trapeziums for variable sample points and using the error to optimise the location of the points. Try it with y=x^3 and I would put money on a not being equal to 1/2.