Numerical integration

Numerical integration is the first algorithm of this part that a reader can check against a formula, which makes it the right place to measure something: the error of a quadrature rule falls at a rate that its order predicts, and the rate is visible in a table of five lines. This lesson writes the trapezoid rule and Simpson's rule for a function passed as an argument, prints the error against the exact value, and reads the ratios.

The trapezoid rule

The interval is cut into n pieces of width h and the area under each piece is a trapezoid: h * (f(x_i) + f(x_i+1)) / 2. Summing them gives h * (f(a)/2 + f(x_1) + ... + f(x_n-1) + f(b)/2), which is the form the code uses: one half of each endpoint and the whole of every interior point, then multiply by h.

The file integ.f90:

module quadrature implicit none private public :: square, expo, trapezoid, simpson abstract interface pure function fun_iface(x) result(y) real, intent(in) :: x real :: y end function fun_iface end interface contains pure function square(x) result(y) real, intent(in) :: x real :: y y = x * x end function square pure function expo(x) result(y) real, intent(in) :: x real :: y y = exp(x) end function expo function trapezoid(f, a, b, n) result(s) procedure(fun_iface) :: f real, intent(in) :: a, b integer, intent(in) :: n real :: s, h integer :: i h = (b - a) / real(n) s = 0.5 * (f(a) + f(b)) do i = 1, n - 1 s = s + f(a + real(i) * h) end do s = s * h end function trapezoid function simpson(f, a, b, n) result(s) procedure(fun_iface) :: f real, intent(in) :: a, b integer, intent(in) :: n real :: s, h integer :: i h = (b - a) / real(n) s = f(a) + f(b) do i = 1, n - 1 if (mod(i, 2) == 1) then s = s + 4.0 * f(a + real(i) * h) else s = s + 2.0 * f(a + real(i) * h) end if end do s = s * h / 3.0 end function simpson end module quadrature program integdemo use quadrature implicit none integer :: n real :: exact, et, es, pt, ps logical :: first exact = exp(1.0) - 1.0 pt = 0.0 ps = 0.0 first = .true. print '(a,es12.4)', 'simpson on x*x, n = 8, error = ', abs(simpson(square, 0.0, 1.0, 8) - 1.0 / 3.0) print '(a,f9.7)', 'integral of exp on [0,1], exact = ', exact print '(a)', ' n trap error ratio simpson error ratio' n = 8 do while (n <= 128) et = abs(trapezoid(expo, 0.0, 1.0, n) - exact) es = abs(simpson(expo, 0.0, 1.0, n) - exact) if (first) then print '(i5,2es13.4)', n, et, es first = .false. else print '(i5,es13.4,f8.2,es13.4,f8.2)', n, et, ratio(pt, et), es, ratio(ps, es) end if pt = et ps = es n = 2 * n end do contains function ratio(prev, now) result(r) real, intent(in) :: prev, now real :: r if (now > 0.0) then r = prev / now else r = 0.0 end if end function ratio end program integdemo

gfortran -Wall -Wextra -std=f2018 integ.f90 -o integ
./integ

simpson on x*x, n = 8, error = 0.0000E+00
integral of exp on [0,1], exact = 1.7182817
n trap error ratio simpson error ratio
8 2.2367E-03 2.3842E-06
16 5.5933E-04 4.00 1.1921E-07 20.00
32 1.4007E-04 3.99 1.1921E-07 1.00
64 3.5167E-05 3.98 3.5763E-07 0.33
128 8.5831E-06 4.10 3.5763E-07 1.00

Simpson's rule

Simpson's rule fits a parabola through three points and weights them 1, 4, 1; summed over pairs of intervals it gives weights 4 for the odd points and 2 for the even ones, which is the loop in the code. For a smooth function it is far more accurate than the trapezoid for the same number of function evaluations, and the first line of the output is the extreme case: on x*x the rule is exact, and the error at eight intervals is zero to the last printed digit.

That is not a numerical accident. Simpson's rule integrates every polynomial of degree three exactly, so a quadratic has no error at any n. The rule is the first of the Newton-Cotes family, and the family continues with weights that are exact for higher degrees and less stable at the ends; for production work the Gaussian rules with a weight function are the ones numerical libraries use.

A function as an argument

Both rules take the function as a dummy procedure, which is what makes them reusable: one quadrature routine integrates anything with the shape of fun_iface. That is the mechanism of lesson 070, and this is the use it was designed for. The module makes the interface explicit, so a call with a function of the wrong shape is a compile error rather than a wrong answer.

The two functions are pure and so is the interface, which is a promise the compiler can use: a pure function may not change a module variable, so the integrand cannot quietly count its calls in a global. If a program needs that count, the interface must drop pure and the optimiser loses a little freedom with it.

The measured table

The table integrates exp(x) from zero to one, whose exact value is e - 1 = 1.7182817, and prints the absolute error for n = 8, 16, 32, 64 and 128. The third and fifth columns are the ratio of the previous error to the current one, which is how a rate is measured: a method whose error falls like h^2 shows a ratio near four when h is halved, and one that falls like h^4 shows sixteen.

Reading the ratios

The trapezoid column is the textbook result: 4.00, 3.99, 3.98 and 4.10, four within the noise of single precision. The rule is second order, the number of function evaluations doubles, and the error quarters. That is a measured convergence order, and it is the kind of number a report should quote rather than the word "convergent".

The Simpson column has no such pattern, and the reason is in its own values: 2.4e-07, 1.2e-07, 3.6e-07. Simpson is so accurate on this function that the error is at the resolution of a single-precision real near 1.7, which is about 1.2e-07. The ratios are then a record of rounding, not of the method. Wall-clock time would have shown the same thing at a different cost: both rules evaluate a hundred and twenty-nine points at n = 128, and Simpson gets an answer a thousand times closer.

This is the practical lesson of the page. A convergence table is read for the slope before the roundoff floor, and a method that reaches the floor at n = 8 has to be measured in double precision or on a function with a bigger derivative. A table of ratios that jumps between 0.33 and 20 is not a broken program; it is a program measuring noise.

Where the error stops falling

Every quadrature rule has the same shape of error curve: it falls like a power of h, then flattens when the rounding error of the sum is larger than the truncation error, and then rises as the number of additions grows. The flat part is the precision of the type, and the rise is the accumulation of roundoff.

So the right step is not the smallest one. For a real function with a few derivatives, the useful range is where the ratio is still the predicted one, and a program that keeps halving the step past that point pays twice the work for a worse answer. In double precision the floor is a thousand million times lower, which is why a serious quadrature routine declares its accumulator as real64 even when the integrand is single.

Exercises

  1. Integrate sin(x) from zero to pi and compare with the exact value two. Which rule reaches the single-precision floor first?
  2. Change the accumulator of trapezoid to real64 and rerun the table. Where does the trapezoid ratio stop being four?
  3. Write a rule that uses the midpoint of each interval instead of the endpoints. What is its order, measured the same way?
  4. Integrate x**7 from zero to one with Simpson at n = 8. Is the answer exact, and why is that the last polynomial degree for which it is?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What is the error of the trapezoid rule proportional to?

    Answer

    h squared, so it quarters when h halves

    The measured ratio of four is the evidence.

  2. Why is Simpson&#39;s rule exact for x*x?

    Answer

    It integrates every polynomial of degree three exactly

    The parabola through three points matches a quadratic.

  3. What does this program print? program p implicit none real :: h, s integer :: i h = 0.5 s = 0.0 do i = 1, 3 s = s + h h = h / 2.0 end do print *, s end program p

    Answer

    0.875

    Half plus a quarter plus an eighth is seven eighths.

  4. What does a ratio of about four in the table mean?

    Answer

    Halving h divided the error by four: a second-order method

    The ratio of two errors is the measured order.

  5. Why does the Simpson column stop showing a pattern?

    Answer

    Its error reached the single-precision floor, so the numbers are rounding noise

    About 1e-07 is the resolution near 1.7 in real32.

  6. Why is the integrand passed as a procedure argument?

    Answer

    So one routine integrates any function of the right shape

    It is the design lesson 070 prepared for.

  7. What does the pure on the interface promise?

    Answer

    The integrand does not change anything outside itself

    A pure function may not touch a module variable.

  8. What is the useful step size for a quadrature rule?

    Answer

    Where the error still falls at the predicted rate

    Past the roundoff floor more work buys a worse answer.

  9. Which accumulator should a serious quadrature routine use?

    Answer

    real64, even for a single-precision integrand

    The sum is where the rounding accumulates.

  10. How many function evaluations does the trapezoid rule use for n intervals?

    Answer

    n + 1 points

    Both endpoints and every interior point.

The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev