ENGR20005
Numerical Methods in Engineering
Workshop 6 Solutions
6.4 See Q6 4 sol.m for the solution. 6.5 For the function
f(x)= 1 1−x
(a) The zeroth order divided difference is given by f[x0] = 1
1−x0
1−1 f[x0,x1]= 1−x1 1−x0
(1)
And the first order divided difference
(b) Assume that
x1 − x0
= (1−x0)−(1−x1)
1 (1−x0)(1−x1) x1 −x0
=1 (1−x1)(1−x0)
f[x0,x1,…,xn] = 1 (1−x0)(1−x1)···(1−xn)
is true. Then the (n + 1)st divided difference is given by f[x0,x1,…,xn,xn+1]= f[x1,x2,…,xn+1]−f[x0,x1,…,xn]
xn+1 − xn 1−1
= (1−x1)(1−x2)···(1−xn+1) (1−x0)(1−x1)···(1−xn) xn+1 − x0
= (1−x0)−(1−xn+1) 1 (1−x0)(1−x1)(1−x2)···(1−xn+1)xn+1 −x0
=1 (1−x0)(1−x1)(1−x2)···(1−xn+1)
1
This shows us that provided that we know the nth divided difference, then we can construct the (n + 1)st difference.
So, if set the base case using our answer to part (a), we can, in principle, use our result here to obtain the first divided difference, then the second divided difference, and so on until we reach the nth divided difference.
(c) Using the Newton interpolation formula, we may approximate 1/(1 − x) using pn (x) = f [x0 ] + f [x0 , x1 ](x − x0 ) + · · ·
+f[x0,x1,…,xn](x−x0)(x−x1)···(x−xn−1) = 1 + 1 (x−x0)+···
(1−x0) (1−x1)(1−x0)
+ 1 (x−x0)···(x−xn−1)
(1−x0)(1−x1)···(1−xn)
= 1 + x−x0 +···+ (x−x0)···(x−xn−1)
1−x0 (1−x0)(1−x1) (1−x0)···(1−xn)
(d) Letting xi → 0, for i = 0,…,n, we find that pn(x)=1+x+x2 +···+xn
which is also the Taylor series for Eq. (1). This is what we expect, since the divided differences are essentially finite difference approximations of f.
6.6 The error in the Lagrange polynomial of order n is given by
E(t)=f(t)−pn(t)= (t−x0)(t−x1)···(t−xn)f(n+1)(ξ) (2)
(n+1)!
(a) At each nodal point t = xi, i = 0,1,2,…,n., thus
E(xi)= (xi −x0)(xi −x1)···(xi −xn)f(n+1)(ξ) (n+1)!
=0
This result is as expected since the Lagrange interpolation property implies that
f(xi) = pn(xi).
(b) For arbitrary t ̸= xi, where t ∈ [a, b], define the auxiliary function
G(x) = E(x) − Ψ(x)E(t) (3) Ψ(t)
with Ψ(x) = (x−x0)···(x−xn). You can think of Ψ here is the polynomial with roots at each of the interpolation nodes.
Note that this function has no physical meaning, it’s just used to relate something that we know or can easily derive to the rest.
2
i. First, using something we know or can easily derive.
At each of the nodal points x = xi, i = 0,1,…,n, we know from part (a)
that E(xi) = 0, and Ψ(xi) = 0 by definition. Thus, we have G(xi) = E(xi) − Ψ(xi)E(t) = 0
Ψ(t) Similarly, at the point x = t, G is given by
G(t) = E(t) − Ψ(t)E(t) = 0 Ψ(t)
Hence, we may conclude that the set of zeros of G, {x0,x1,x2,…,xn,t}, contains at least n + 2 elements in the interval [a, b].
ii. We’ll first take the set {x0,x1,x2,…,xn,t} and sort the elements so they are in ascending order, call the set Z. (It doesn’t matter whether we know the elements or not, we can always do this as xi, the Lagrange interpolation nodes, are distinct and t ̸= xi).
Suppose that xl is an element of Z and xr is the subsequent element, so that in this interval there are no other elements of Z. (Note that there will be n + 1 of these intervals).
We know by definition of E and Ψ, that the function G has a continuous derivative, which means that we may apply the mean value theorem.
Since part i. showed us that G = 0 for all xl and xr, the mean value theorem tells us that there are at least n+1 points where the gradient vanishes, which shows that there are at least n + 1 roots to G′.
iii. Applying this argument to G′, G′′, . . . , Gj−1, we conclude that G(j) will have n−2−j roots.
iv. The (n + 1)st derivative is given by
G(n+1)(x) = E(n+1)(x) − Ψ(n+1)(x)E(t) (4)
Ψ(t)
Since E(x) = f(x)−pn(x) and pn is the nth order Lagrange polynomial, then
p(n+1)(x) = 0. Thus n
E(n+1) = f(n+1)
3
(d)
holds for all x ∈ [a, b]. i. For the function
f(x) = log10(x) The second derivative is given by
f′′(x) = − 1
x2 log(10)
Hence the error is given by
E(t)= (t−1)(t−2) −1
2! x2 log(10)
≤ (32 −1)(32 −2) −1
2! x2 log(10) =1 −1
8 x2 log(10)
As for the term Ψ(n+1)(x), we have
(n+1) Ψ
dn+1
(x) = dxn+1[(x−x0)(x−x1)···(x−xn)]
dn+1
= dxn+1[xn+1 +···+c0]
dn
= dxn[(n+1)xn +···+c1]
.
= (n+1)!
Hence Eq. (4) becomes
G(n+1)(x) = f(n+1)(x) − (n + 1)!E(t) (5)
Ψ(t)
v. Using our result from part iii. we know that G(n+1) has at least one root,
which we’ll denote ξ. Hence at x = ξ Eq. (5) becomes 0 = f(n+1)(ξ) − (n + 1)!E(t)
Ψ(t)
Rearranging for E(t), we find
E(t) = Ψ(t) f(n+1)(ξ)
(n+1)!
whcih is Eq. (2).
(c) Since part (a) holds for x = xi and part (b) for x ̸= xi, we conclude that Eq. (2)
4
ii. For x > 1, the error is bounded by
E(t) ≤ 0.434 = 0.0542
8
If we were to plot the error
then we would find that the maximum error is |E| ≈ 0.0259 when x ≈ 1.444. So if we evaluate the error there, we would find that
E(t) ≈ 0.434 ≈ 0.026 8(1.4444)2
5