CS412: Lecture #21
Mridul Aanjaneya
April 9, 2015
Numerical Integration
For the rectangle rule, we have the following local error:
Z xi+1 Z xi+1 Z xi+1
ei = f (xk )dx − f (x)dx = [f (xi ) − f (x)]dx (1)
xi xi xi
We shall seek to obtain an upper bound for the integral in equation (1). Let us
remember Taylor’s formula, applied to f (x) in the vicinity of xi :
f (x) = f (xi ) + f 0 (ci )(x − xi ), where ci ∈ (xi , xi+1 )
Thus,
Z xi+1 Z xi+1
0
ei = − f (ci )(x − xi ) ≤ |f 0 (ci )||x − xi |dx
x xi
Z xi+1i Z xi+1
0 0
⇒ ei ≤ ||f ||∞ |x − xi | dx ≤ ||f ||∞ (x − xi )dx
xi | {z } xi
≥0
xi+1
(x − xi )2
1 0
⇒ ei ≤ ||f 0 ||∞ = ||f ||∞ (xi+1 − xi )2
2 xi 2
1 0
⇒ ei ≤ ||f ||∞ · h2i
2
The global error is defined as:
n−1
X n−1
X n−1
X
e = |Irule − Ianalytic | = [Ii,rule − Ii,analytic ] ≤ |Ii,rule − Ii,analytic | = ei
i=0 i=0 i=0
For example, if h = constant, for the rectangle rule we have:
1
n−1
X 1 b−a 0
e≤ ei = n · ||f 0 ||∞ · h2 ⇒ eglobal ≤ ||f ||∞ h
i=0
2 2
What we observe is that, for the rectangle rule:
• Local error = O(h2 )
• Global error = O(h)
In general, we always get that if the local error is O(hd+1 ) the global will be
O(hd ); additionally, in this case the numerical integration rule is called d-order
accurate (e.g., rectangle rule is 1st order accurate).
Midpoint Rule
xk +xk+1
Here, we approximate f (x) ≈ f 2 . Thus, the integral becomes
Z b
a+b
I= f (x)dx ≈ (b − a)f
a 2
Composite rule, assuming h = constant
2
b n−1 n−1
b−a X
Z X xi + xi+1 xi + xi+1
I= f (x)dx ≈ (xi+1 − xi ) f = f
a i=0
| {z } 2 n i=0 2
=h=(b−a)/n
Local error analysis
We use the (2nd order) Taylor’s formula around the point xm = (xi + xi+1 )/2.
f 00 (ci )
f (x) = f (xm ) + f 0 (xm )(x − xm ) + (x − xm )2 where ci ∈ (xi , xi+1 )
2
xi+1 xi+1 xi+1
f 00 (ci )
Z Z Z
ei = [f (xm ) − f (x)dx] = f (xm ) (x − xm )dx + (x − xm )2
xi xi xi 2
xi+1
R xi+1 (x−xm )2 h2k h2k
Note that xi
(x − xm )dx = 2 = 8 − 8 = 0. Thus,
xi
Z xi+1 Z xi+1
1 1
ei = f 00 (ci )(x − xm )2 ≤ |f 00 (ci )| |x − xm |2 dx
2 xi 2 xi
xi+1 xi+1
(x − xm )3
Z
1 00 1
≤ ||f ||∞ (x − xm )2 dx = ||f 00 ||∞
2 xi 2 3 xi
3
h3
1 00 hi
≤ ||f ||∞ + i
2 24 24
1
⇒ ei ≤ ||f 00 ||∞ h3i
24
Global error
n−1
X b − a 00
eglobal ≤ ei ⇒ eglobal ≤ ||f ||∞ h2
i=0
24
Thus, the midpoint rule is 2nd order accurate.
3
Trapezoidal rule
In this case, f is approximated in [a, b] with the straight line drawn between
(a, f (a)) and (b, f (b)).
f (b)
f (a)
a b
In this case,
Z b
f (a) + f (b)
I= f (x)dx ≈ (b − a) = Itrap
a 2
To generate the corresponding composite rule, we write:
Z xi+1
f (xi ) + f (xi+1 ) f (xi ) + f (xi+1 )
Ii = f (x)dx ≈ (xi+1 − xi ) = hi
xi 2 2
Assuming h = constant, this gives:
n−1 n−1
X X f (xi ) + f (xi+1 )
I = Ii ≈ h
i=0 i=0
2
b−a
= (f (x0 ) + 2f (x1 ) + 2f (x2 ) + . . . + 2f (xn−1 ) + f (xn ))
2n
4
Note that due to the simple formula for the trapezoidal area, we did not have
to write the approximating polynomial
f (b) − f (a)
p(x) = f (a) + (x − a)
b−a
Rb
explicitly.
h Also, the result i of integrating a p(x)dx results in a very simple
formula (b − a) f (a)+f
2
(b)
, even “simpler” than the formula for p itself!
Local error analysis
Estimating the local error can be somewhat delicate with the trapezoidal rule.
We will, in this case, use a formula from the theory of interpolating polynomials
we saw before:
Theorem 1. If P(x) is an n-degree polynomial interpolating (x0 , y0 ), (x1 , y1 ), . . . ,
(xn , yn ), then for every x ∈ [x0 , xn ] we have,
f (n+1) (c)
f (x) − P(x) = (x − x0 )(x − x1 ) . . . (x − xn )
(n + 1)!
Caution: c is not a constant! It depends on the particular x we choose in this
theorem.
For the trapezoidal rule, we effectively use a linear (n = 1) interpolant. When
x ∈ [xi , xi+1 ], we have:
f 00 (ci )
f (x) − Pi (x) = (x − xi )(x − xi+1 ) where ci ∈ (xi , xi+1 )
2
Thus,
xi+1 xi+1
f 00 (ci )
Z Z
ei = [f (x) − pi (x)]dx = (x − xi )(x − xi+1 )
xi xi 2
xi+1
f 00 (ci )
Z
≤ |(x − xi )(x − xi+1 )|dx
xi 2
Z xi+1
1 00
≤ ||f ||∞ |(x − xi )(x − xi+1 )|dx
2 xi
The only reason we can meaningfully continue at this point is to recognize that
(x−xi )(x−xi+1 ) ≤ 0 in [xi , xi+1 ]. Thus, |(x−xi )(x−xi+1 )| = −(x−xi )(x−xi+1 )
and remove in this way the absolute value in the integral above. This is not
the case in general, where we won’t be able to remove the absolute value (see
Simpson’s rule next). We can verify that
5
xi+1 xi+1
h3i
Z Z
|(x − xi )(x − xi+1 )| = − (x − xi )(x − xi+1 ) =
xi xi 6
Putting everything together:
1 00 h3 1
ei ≤ ||f ||∞ i ⇒ ei ≤ ||f 00 ||∞ h3i
2 6 12
For the global error:
n−1
X n 00 nh=b−a b − a 00
e≤ ei ≤ ||f ||∞ h3i −−−−−→ e ≤ ||f ||∞ h2
i=0
12 12
Thus, trapezoidal rule is also 2nd order accurate.
