tags:

views:

289

answers:

5

Hi all,

I'm looking for a library to find the integral of a given set of random data (rather than a function) in C++ (or C, but preferably C++). There is another question asking about integration in C but the answers discuss more how to integrate a function (I think...). I understand that this can be done simply by calculating the area under the line segment between each pair of points from start to finish, but I'd rather not reinvent the wheel if this has already been done. I apologize in advance if this is a duplicate; I searched pretty extensively to no avail. My math isn't as strong as I'd like it so it's entirely possible I'm using the wrong terminology.

Thanks in advance for any help!

Chris

Edit: In case anybody is interested, I feel like an idiot. Even adding in a bunch of OO abstraction to make my other code easier to use, that was maybe 30 lines of code. This is what 3 years away from any sort of math will do to you...thanks for all of the help!

+2  A: 

Yeah sure, it is that simple. Just sum the areas of the trapezoids formed by the data points you have. You cannot make it more complicated than that. Looking for a library to do it is fairly pointless, you'll just write code to whack the data into the format that the library needs. Calculating it yourself will be less code.

Hans Passant
And he might learn something good about integration in the bargain.
duffymo
+8  A: 

This is trivial. If the points are (x0, y0), (x1, y1), ..., (xN, yN), and the points are ordered so that x0 <= x1 <= ... <= xN, then the integral is

  • y0 * (x1 - x0) + y1 * (x2 - x1) + ...

using no interpolation (summing areas of rectangles), and

  • (y0 + y1)/2 * (x1 - x0) + (y1 + y2)/2 * (x2 - x1) + ...

using linear interpolation (summing areas of trapezia).

The problem is especially simple if your data is y0, y1, ..., yN and the corresponding x values are assumed to be 0, 1, ..., N. Then you get

  • y0 + y1 + ...

using no interpolation (summing areas of rectangles), and

  • (y0 + y1)/2 + (y1 + y2)/2 + ...

using linear interpolation (summing areas of trapezia).

Of course, using some simple algebra, the trapezia formulae can be simplified. For instance, in the last case, you get

  • y0/2 + y1 + y2 + ...
Andreas Rejbrand
+1  A: 

Given points (x0, y0), (x1, y1) the area under the trapezoid is (x1 - x0) * (y0 + y1) / 2.

You can calculate the entire area by summing up these.

Paul Hankin
+1  A: 

Your "random data" consists of a set of (x,y) pairs. Before you start the integration, you have to be sure that the pairs are sorted into a list where the values for x increase monotonically. Once you have that, trapezoid integration should be sufficient. (aka Simpson's rule).

duffymo
I believe that Simpson's rules integrates a quadratic spline. The trapezoid rule is simpler. +1 For noting the importance of sorting, but you ought to mention the matter of checking that the data represent a *function* (i.e. no repeated independent coordinates) if you're going this route.
dmckee
+6  A: 

i have just had my numerical exam today :) and i have 3 rules for you

Trapezoidal rule :

integral = h/2 * ( y0 + 2y1 + 2y2 + 2y3 ....... + yn)

Mid-point rule :

integral = h * ( y0.5 + y1.5 + y2.5 + .... y(n-0.5) )

y0.5 means the value of y at the point between x0 and x1

Simpsons Rule :

integral = h/3 * ( y0 + 4y1 + 2y2 + 4y3 + 2y4 ....... + yn)

where h is the step you take which is usually small number ( but not too small to avoid round off error) and n is the number of periods you take

those were the easy to apply ... you can read more about gauss quadrature also

references :

Ahmed Kotb
Did the exam cover which of these rules was most appropriate in what circumstances? Important. Input was: random data.
Hans Passant
we use h as a constant number ... in the first 2 rules you can just get the difference between each two x's (delta x) as in this 2 examples you just get the area of (rectangle or trapezium)... in the third one (simpson) iam not sure this can be done that easily ... but again there is another solution .... we can use Lagrange interpolation from the points given to get the best function that represents the points then do the integeration with fixed h value ...should i add this to the answer ???
Ahmed Kotb
@Ahmed The Simpson Rule uses the Lagrange interpolation for 3 points, so it gives exact results for polynomials up to third order. In fact, the error of the Simpson Rule is proportional to the fourth derivative of the function at some point of the interval.
belisarius