Fixed interval methods
The integration algorithms in this category divide the integration interval into an equal number of intervals. A weighted average of the function values at these points gives an approximation for the integral.
Left and Right Rectangle Rules
One way to compute an integral is to approximate the area using rectangles. This is what the rectangle rules do. The integration interval is divided into a large number of subintervals. On each interval, the function is approximated by a constant value. For the left point rule, it is the lower bound of the subinterval. For the right point rule it is the upper bound of the subinterval. These rules are implemented by the LeftPointIntegrator and RightPointIntegrator classes.
These algorithms are only of order one, meaning that any linear function is integrated exactly, but quadratic functions are not. This makes the algorithm not suitable for general problems. However, there is one property that still makes them useful. For certain functions, the resulting approximation is guaranteed to be an upper or lower bound for the true value of the integral. For monotonically increasing functions, the left-point rule gives a lower bound. For monotonically decreasing functions, it gives an upper bound. The right-point rule gives the opposite bounds.
The Mid-Point and Trapezoid Rules
The mid-point rule, implemented by the MidpointIntegrator class, is another variation of the rectangle rule. It approximates the function on each subinterval by its value in the middle of the subinterval. The trapezoid rule approximates the function on each interval by a straight line through the function at the left and right points of the subinterval. The trapezoid rule is implemented by the TrapezoidIntegrator class.
These algorithms are also only of order one. They are equally ill-suited for general problems. Once again, however, the resulting approximation is guaranteed to be an upper or lower bound for the true value of the integral of certain functions. For convex functions, the mid-point rule gives a lower bound. For concave functions, it gives an upper bound. The trapezoid rule gives the opposite bounds.
Simpson's Rule
One of the simplest integration algorithms is Simpson's rule, implemented by the SimpsonIntegrator class. This algorithm is of order 3. In each iteration, the number of points is doubled. The difference between successive approximations is taken as the estimate for the integration error. Because the order of the algorithm is so low, use of this algorithm is not recommended. It is here more for historical reasons than for its practical application.
The following example evaluates the integral of the Sine function over the interval [0,5] using Simpson's rule.
SimpsonIntegrator simpson = new SimpsonIntegrator();
simpson.RelativeTolerance = 1e-5;
simpson.ConvergenceCriterion = ConvergenceCriterion.WithinRelativeTolerance;
double result = simpson.Integrate(Math.Sin, 0, 2);
Console.WriteLine("sin(x) on [0,2]");
Console.WriteLine("Simpson integrator:");
Console.WriteLine(" Value: {0}", simpson.Result);
Console.WriteLine(" Status: {0}", simpson.Status);
Console.WriteLine(" Estimated error: {0}", simpson.EstimatedError);
Console.WriteLine(" Iterations: {0}", simpson.IterationsNeeded);
Console.WriteLine(" Function evaluations: {0}", simpson.EvaluationsNeeded);Romberg Integration
Romberg integration is an enhancement of the basic trapezoid rule. It is implemented by the RombergIntegrator class. Once again, the number of points is doubled in each iteration. This time, however, the successive approximations are used to extrapolate the exact value of the integral as the width of each subinterval approaches zero. Romberg integration has an effective order of 2k after k steps of the algorithm. Even though the number of function evaluations is still fairly high, it is a major improvement over Simpson's rule, and a reasonable choice for target functions that are sufficiently smooth.
RombergIntegrator romberg = new RombergIntegrator();
romberg.RelativeTolerance = 1e-5;
romberg.ConvergenceCriterion = ConvergenceCriterion.WithinRelativeTolerance;
double result = romberg.Integrate(Math.Sin, 0, 2);
Console.WriteLine("sin(x) on [0,2]");
Console.WriteLine("Romberg integrator:");
Console.WriteLine(" Value: {0}", result);
Console.WriteLine(" Status: {0}", romberg.Status);
Console.WriteLine(" Estimated error: {0}", romberg.EstimatedError);
Console.WriteLine(" Iterations: {0}", romberg.IterationsNeeded);
Console.WriteLine(" Function evaluations: {0}", romberg.EvaluationsNeeded);The method does have its limits, however. Nothing beats the robustness of the adaptive Gauss-Kronrod integrator discussed in the next section.
References
S.D. Conte and Carl de Boor, Elementary Numerical Analysis: An Algorithmic Approach, McGraw-Hill, 1972.