solution

Introduction to NA, Hw 5 (due 10/22)
Example 1 Prove by induction that in Romberg integration
j−2
Rj1
2X
1
= Rj−1,1 + hj
f (a + (2i − 1)hj )
2
i=1
solution: From the trapezoid rule,


2j−1
X−1
hj 
f (a) + f (a + 2j−1 hj ) + 2
Rj1 =
f (a + ihj ) ,
2
i=1
and
Rj+1,1


j
2X
−1
hj+1 
f (a) + f (a + 2j hj+1 ) + 2
=
f (a + ihj+1 ) .
2
i=1
And we want to show that for any j = 1, 2, . . . t, it holds that
j−1
Rj+1,1
2X
1
f (a + (2i − 1) hj+1 ) .
= Rj1 + hj+1
2
i=1
Case j = 1 we did in class, Now let us consider any j > 2. We can write
Rj+1,1 =
hj+1 f (a) + f (a + 2j hj+1 ) + 2A ,
2
where
A = f (a + hj+1 ) + f (a + 2hj+1 ) + · · · +
+ f a + 2j−1 − 1 hj+1 + f a + 2j−1 hj+1 + f a + 2j − 1 hj+1 ,
can be grouped in even and odd terms as
A=
2j−1
X−1
f (a + 2ihj+1 ) +
i=1
j−1
2X
f (a + (2i − 1) hj+1 ) ,
i=1
where we have adjusted the bounds considering that i ≥ 1 is an integer which in
the first case satisfies
2i ≤ 2j − 1,
i ≤ 2j−1 − 1/2,
i ≤ 2j−1 − 1,
and in the second case
2i − 1 ≤ 2j − 1,
i ≤ 2j−1 .
1
So,

Rj+1,1 =
1 hj 
f (a) + f (a + 2j−1 hj ) + 2
2 2
{z
|
2j−1
X−1

f (a + ihj ) +
i=1
=Rj1
+ hj+1
j−1
2X
}
f (a + (2i − 1) hj+1 )
i=1
j−1
2X
1
= Rj1 + hj+1
f (a + (2i − 1) hj+1 ) ,
2
i=1
which we wanted to show.
R1
Example 2 Apply Romberg integration to find R33 for the integral 0 x2 dx.
Compare with the exact value of this integral. (Hint: this is done numerically,
that is compute the values of entries Rj1 and use them to extrapolate.)
solution: From the trapezoid rule, with h1 = b − a = 1 − 0, we get
h1
1
(f (a) + f (b)) = ,
2
2
1
a+b
3
= R11 + h2 f (
)= ,
2
2
8
1
11
= R21 + h3 [f (a + h3 ) + f (a + 3h3 )] =
,
2
32
R11 =
R21
R31
extrapolating
4R21 − R11
1
= ,
4−1
3
4R31 = R21
1
=
= ,
4−1
3
R22 =
R32
and finally
42 R32 − R22
1
= ,
42 − 1
3
h 3 i1
R1
which is the same as 0 x2 dx = x3
= 13 .
R33 =
0
Example 3 (h = 0.01) Use the two-point forward-difference formula to approximate f 0 (1), and find the approximation error, where f (x) = ln x. Estimate the
error in terms of O notation.
solution: The correct value is f 0 (1) = 1, the approximation is
ln(1 + 0.01) − ln 1
= 0.9950 ,
0.01
therefore the approximation error is e = 0.0050. The error is O(h).
2
Example 4 (h = 0.01) Use the three-point centered-difference formula to approximate f 0 (0), where f (x) = ex . Estimate the error in terms of O notation.
solution: The formula gives
e0.01 − e−0.01
= 1.000016666749992 .
0.02
The error is O(h2 ).
Example 5 (h = 0.01) Use the three-point centered-difference formula for the
second derivative to approximate f 00 (1), where f (x) = x−1 . Estimate the error
in terms of O notation.
solution: The correct value is f 0 (1) = 2, the approximation is
1.01−1 − 2 + 0.99−1
= 2.000200020002563 ,
0.012
therefore the approximation error is e = 0.000200020002563. The error is O(h2 ).
3

Download Report