MATH/APPM 4650
Class notes, February 23

Numerical integration (basic)

Most of today's notes will be on the board. Here are the basic ideas.

Main idea:
Suppose we are trying to approximate an integral over a small interval numerically.
(If the interval is not small, we will use composite integration, discussed in the next section.)

Suppose we have function values at some points f(x₀), f(x₁), f(x₂), . . ., f(x_n) and we want to use these to approximate the integral.

The easiest thing to do is construct the interpolating polynomial (which has degree n), then integrate that.

For example, if we have three points f(a)=p, f((a+b)/2)=q, and f(b)=r, then the interpolating polynomial is P(x) = 1/(b-a)²[ (2r-4q+2p) x² + (-3ra-rb+4qa+4qb-pa-3pb)x + (pb²+ra²+rba-4qba+pba) ] which is rather complicated, but if we integrate this from x=a to x=b, we get the simple formula which you might recognize from calculus as Simpson's rule.

We can generalize this to any degree pretty easily.

---

General formulas:
Closed Newton-Cotes:
For any positive integer n, we set h = (b-a)/n (the spacing between the points). We set x_k = a+kh, so x₀=a and x_n=b.

The following formulas all come from integrating the corresponding Lagrange interpolating polynomial.

• n=1, h=b-a: (trapezoid rule) Integral ≈ h/2 [ f(x₀) + f(x₁) ]
• n=2, h=(b-a)/2: (Simpson's rule) Integral ≈ h/3 [ f(x₀) + 4f(x₁) + f(x₂) ]
• n=3, h=(b-a)/3: Integral ≈ 3h/8 [ f(x₀) + 3f(x₁) + 3f(x₂) + f(x₃) ]
• n=4, h=(b-a)/4: Integral ≈ 2h/45 [ 7f(x₀) + 32f(x₁) + 12f(x₂) + 32f(x₃) + 7f(x₄) ]

Open Newton-Cotes:
This is the same as the closed Newton-Cotes, except we omit the endpoint values.
For any nonnegative integer n, we set h = (b-a)/(n+2) (the spacing between the points). We set x_k = a+(k+1)h, so x_-1=a and x_n+1=b.

• n=0, h=(b-a)/2: (midpoint rule) Integral ≈ 2hf(x₀)
• n=1, h=(b-a)/3: Integral ≈ 3h/2 [ f(x₀) + f(x₁) ]
• n=2, h=(b-a)/4: Integral ≈ 4h/3 [ 2f(x₀) - f(x₁) + 2f(x₂) ]
• n=3, h=(b-a)/5: Integral ≈ 5h/24 [ 11f(x₀) + f(x₁) + f(x₂) + 11f(x₃) ]

---

When to use open Newton-Cotes or closed Newton-Cotes?

• Open Newton-Cotes may be more useful if if the integrand is singular at the endpoints, but the integral is known to exist. For example,
• If the (n+1)st derivative is nowhere zero on the interval, then closed Newton-Cotes degree n and open Newton-Cotes degree (n-1) will bound the actual integral. (See below.)
  For example, if the function has no inflection points, then the midpoint rule and the trapezoid rule bound the integral.

---

How to derive an error formula (example for Simpson's Rule):

On a small interval, we can approximate a function by its Taylor series: Integrate from x=a to x=a+2h:
Compare to Simpson's Rule:
Observe the first time they are different is at the h⁵ term. So the error is h⁵/90 f⁽⁴⁾(ξ).

The first error term comes from the first power of x that Simpson's Rule fails to get exactly right.

In this case Simpson's Rule is exact on everything up to x³, so the error comes from the integral of x⁴, and is thus proportional to h⁵.


In general, any integration rule that involves symmetrically placed points and is accurate up to x^2m will be accurate up to x^2m+1.
We always get the next odd term for free by symmetry (but we have to work for the next even term).