Numerical Analysis

Math 370  MWF 2:30-3:25
Spring 1997  201 Fowler

(04.07.97) \underline{Newton-Cotes Formulae; Composite Numerical Integration} Newton-Cotes Formulas The official name for the quadrature rules that Trapezoid and Simpson fall under is called the (n + 1)-point closed Newton-Cotes formula. In this case n is the degree of the Lagrange Polynomial used to do the interpolation for f(x) in the integral.

In general, the closed Newton-Cotes formulae look like: If n is even and f ∈ C^{n+2}[a, b]

∫_{a}^{b} f(x) dx = ∑_{i=0}^{n} a_{i}f(x_{i}) + \frac{h^{n+3}f^{(n+2)}(ξ)}{(n + 2)!} ∫_{0}^{n} t^{2}(t − 1) … (t − n) dt

and if n is odd and f ∈ C^{n+1}[a, b]

∫_{a}^{b} f(x) dx = ∑_{i=0}^{n} a_{i}f(x_{i}) + \frac{h^{n+2}f^{(n+1)}(ξ)}{(n + 2)!} ∫_{0}^{n} t(t − 1) … (t − n) dt

where ξ ∈ [a, b] and h = (b − a)/n and a_{i} = ∫_{x_{0}}^{x_{n}} L_{n,i}(x) dx

What is the precision of an (n + 1)-point closed Newton-Cotes formula?

The Midpoint Rule is the first example of an (n + 1)-point open Newton-Cotes formula In the open Newton-Cotes formulas the nodes x_{k} do not necessarily fall within the interval of integration one is interested in. In fact, they are defined saying that h = (b − a)/(n + 2) and x_{k} = x_{0} + kh for k = 0, 1, … n and x_{0} = a + h

EXERCISE: Show that x_{n} = b − h = x_{0} + nh

In general, the open Newton-Cotes formulae look like: If n is even and f ∈ C^{n+2}[a, b]

∫_{a}^{b} f(x) dx = ∑_{i=0}^{n} a_{i}f(x_{i}) + \frac{h^{n+3}f^{(n+2)}(ξ)}{(n + 2)!} ∫_{−1}^{n+1} t^{2}(t − 1) … (t − n) dt

and if n is odd and f ∈ C^{n+1}[a, b]

∫_{a}^{b} f(x) dx = ∑_{i=0}^{n} a_{i}f(x_{i}) + \frac{h^{n+2}f^{(n+1)}(ξ)}{(n + 2)!} ∫_{−1}^{n+1} t(t − 1) … (t − n) dt

where ξ ∈ [a, b] and h = (b − a)/(n + 2), x_{−1} = a, x_{n+1} = b and a_{i} = ∫_{x_{−1}}^{x_{n+1}} L_{n,i}(x) dx

What is the precision of an (n + 1)-point open Newton-Cotes formula?

What’s the difference between the open and closed Newton-Cotes formulae?

EXERCISE: Use the general form of the open Newton-Cotes formula to write down the formula for Midpoint Rule Here are the definitions of the standard numerical quadrature rules that you should know: Midpoint (1-point open Newton-Cotes)

M = (b − a)f (\frac{a + b}{2}) + \frac{h^{3}}{3} f′′(ξ), where h = \frac{b − a}{2}

Trapezoid (2-point closed Newton-Cotes)

T = \frac{(b − a)}{2} [f(a) + f(b)] − \frac{h^{3}}{12}f′′(ξ), where h = b − a

Simpson (3-point closed Newton-Cotes)

S = \frac{(b − a)}{6} [f(a) + 4f(\frac{a + b}{2}) + f(b)] − \frac{h^{5}}{90}f^{(4)}(ξ) where h = \frac{b − a}{2}

Composite Numerical Integration Of course, usually when these rules are used in practice, the interval of integration is split up into N subintervals and the rule is applied repeatedly on each subinterval in order to compute a more accurate approximation to the value of the integral as N increases and the size of each subinterval decreases.

We are interested in looking at what happens to the error formula in each of these cases if we apply them repeatedly on N subintervals.

\underline{EXERCISE} Let’s consider the Trapezoid Rule. Sketch the approximation that using the Trapezoid Rule with N = 2 would look like and write down the approximation T to I the exact value of the

integral ∫_{0}^{1} \sqrt{1 − x^{2}} dx. We’ll denote this by T (2, \sqrt{1 − x^{2}}, 0, 1). Find |I − T (2, f, a, b)|

Repeat the exercise with N = 4 to compute T (4, \sqrt{1 − x^{2}}, −1, 1). Find |I − T (4, f, a, b)|

Does your picture remind you of any topic from interpolation?

Error Term of Composite Trapezoid Starting with the formula for the Trapezoid Rule, we can show that the error formula for the Composite Trapezoid Rule is O(Δx^{2}) and has precision 1.

CT = T(N, f, a, b) = \frac{Δx}{2} [f(a) + 2 ∑_{j=1}^{N−1} f(a + jΔx) + f(b)] − \frac{(b − a)}{12}(Δx)^{2}f′′(μ)

where μ ∈ (a, b) and Δx = (b − a)/N

Similarly, Composite Midpoint Method

CM =M(N, f, a, b) = ∑_{k=1}^{n} f(x_{k})Δx + \frac{(b − a)}{24}(Δx)^{2}f′′(μ)

where μ ∈ (a, b), x_{k} = a+(k−1/2)Δ_{x} and Δx = (b−a)/n and n is the number of subintervals in [a, b] Composite Simpson’s Method

CS = \frac{2}{3}CM + \frac{1}{3}CT − \frac{(b − a)}{2880}(Δx)^{4}f^{(4)}(μ)

where μ ∈ (a, b), Δx = (b − a)/n and n is the number of subintervals in [a, b] \underline{Example} Now that we know expressions for the error terms of these methods we can use this infor-

mation for error control. Consider ∫_{1}^{3} e^{x^{2}} dx. How many N subintervals would we have to split [1,3] into in order to be confident that you have computed the integral to with 10^{−4} of its exact value? Compare how many subsintervals you need using Midpoint versus using Simpson’s.

Effect of Round-Off Error on Composite Numerical Integration Clearly when we do numerical integration we do quite a bit of function evaluation. As we saw in numerical differentiation, everytime we evaluate a function f(x) the computer is using f̃(x) + e(x). Lets consider the Trapezoid Method and try and compute E(Δx) and see what happens as Δx → 0