BRANCH-E&TC ENGINEERING
SEM -3RD
SUBJECT-MATH -3
CHAPTER-06
TOPIC-finite difference and interpolation
FACULTY-tapas ranjan si
歐亞書局 P
Interpolation
A standard idea in interpolation now is to find a polynomial pn(x) of degree n (or less) that assumes the given values; thus
(1)
We call this pn(x) an interpolation polynomial and x0, ‥‥, xn the nodes. And if ƒ(x) is a mathematical function, we call pn(x) a polynomial approximation of ƒ.
We use pn(x) to get (approximate) values of ƒ for x’s between x0 and xn (“interpolation”) or sometimes outside this interval (“extrapolation”).
continued
797
歐亞書局 P
Lagrange Interpolation
Linear interpolation is interpolation by the straight line through (x0, ƒ0), (x1, ƒ1); see Fig. 428. Thus the linear Lagrange polynomial p1 is a sum p1 = L0ƒ0 + L1ƒ1 with L0 the linear polynomial that is 1 at x0 and 0 at x1; similarly, L1 is 0 at x0 and 1 at x1. Obviously,
This gives the linear Lagrange polynomial
(2)
continued
798
歐亞書局 P
E X A M P L E 1 Linear Lagrange Interpolation
Compute a 4D-value of ln 9.2 from ln 9.0 = 2.1972, ln 9.5 = 2.2513 by linear Lagrange interpolation and determine the error, using ln 9.2 = 2.2192 (4D).
Solution. x0 = 9.0, x1 = 9.5, ƒ0 = ln 9.0, ƒ1 = ln 9.5. In (2) we need
and obtain the answer
continued
798
歐亞書局 P
The error is ε = a – a = 2.2192 – 2.2188 = 0.0004.
Hence linear interpolation is not sufficient here to get 4D-accuracy; it would suffice for 3D-accuracy.
continued
798
歐亞書局 P
Quadratic interpolation
The interpolation of given (x0, ƒ0), (x1, ƒ1), (x2, ƒ2) by a second-degree polynomial p2(x), which by Lagrange’s idea is
(3a)
with L0(x0) = 1, L1(x1) = 1, L2(x2) = 1, and L0(x1) = L0(x2) = 0, etc. We claim that
(3b)
continued
799
歐亞書局 P
E X A M P L E 2 Quadratic Lagrange Interpolation
Compute ln 9.2 by (3) from the data in Example 1 and the additional third value ln 11.0 = 2.3979.
Solution. In (3),
so that (3a) gives, exact to 4D,
continued
799
歐亞書局 P
General Lagrange Interpolation Polynomial
For general n we obtain
(4a)
where Lk(xk) = 1 and Lk is 0 at the other nodes, and the Lk are independent of the function ƒ to be interpolated. We get (4a) if we take
(4b)
We can easily see that pn(xk) = ƒk.
continued
800
歐亞書局 P
Newton’s Divided Difference Interpolation
The kth divided difference, recursively denoted and defined as follows:
and in general
(8)
802
歐亞書局 P
歐亞書局 P
With p0(x) = ƒ0 by repeated application with k = 1, ‥‥, n this finally gives Newton’s divided difference interpolation formula
(10)
802
歐亞書局 P
Table 19.2 Newton’s Divided Difference Interpolation
continued
803
歐亞書局 P
803
歐亞書局 P
E X A M P L E 4 Newton’s Divided Difference� Interpolation Formula
Compute ƒ(9.2) from the values shown in the first two columns of the following table.
continued
803
歐亞書局 P
Solution
We compute the divided differences as shown. Sample computation:
The values we need in (10) are circled. We have
The value exact to 6D is ƒ(9.2) = ln 9.2 = 2.219 203. Note that we can nicely see how the accuracy increases from term to term:
continued
804
歐亞書局 P
Equal Spacing: Newton’s Forward Difference Formula
Newton’s formula (10) is valid for arbitrarily spaced nodes as they may occur in practice in experiments or observations.
However, in many applications the xj’s are regularly spaced—for instance, in measurements taken at regular intervals of time. Then, denoting the distance by h, we can write
(11)
We can show how (8) and (10) now simplify considerably!
continued
804
歐亞書局 P
Let us define the first forward difference of ƒ at xj by
and the second forward difference of ƒ at xj by
and, continuing in this way, the kth forward difference of ƒ at xj by
(12)
804
歐亞書局 P
Formula (10) becomes Newton’s (or Gregory–Newton’s) forward difference interpolation formula
(14)
where the binomial coefficients in the first line are defined by
(15)
and s! = 1 • 2 ‥‥ s.
continued
805
歐亞書局 P
Error
From (5) we get, with x – x0 = rh, x – x1 = (r – 1)h, etc.,
(16)
with t as characterized in (5).
805
歐亞書局 P
E X A M P L E 5 Newton’s Forward Difference � Formula. Error Estimation
Compute cosh 0.56 from (14) and the four values in the following table and estimate the error.
continued
806
歐亞書局 P
Solution
We compute the forward differences as shown in the table. The values we need are circled. In (14) we have r = (0.56 – 0.50)/0.1 = 0.6, so that (14) gives
continued
806
歐亞書局 P
Error estimate. From (16), since the fourth derivative is cosh(4) t = cosh t,
where A = –0.000 003 36 and 0.5 ≤ t ≤ 0.8. We do not know t, but we get an inequality by taking the largest and smallest cosh t in that interval:
continued
806
歐亞書局 P
Since
this gives
Numeric values are
The exact 6D-value is cosh 0.56 = 1.160 941. It lies within these bounds. Such bounds are not always so tight. Also, we did not consider roundoff errors, which will depend on the number of operations.
806
歐亞書局 P
Equal Spacing: Newton’s Backward Difference Formula
A formula similar to (14) but involving backward differences is Newton’s (or Gregory–Newton’s) backward difference interpolation formula
(18)
807
歐亞書局 P
E X A M P L E 6 Newton’s Forward and Backward � Interpolations
Compute a 7D-value of the Bessel function J0(x) for x = 1.72 from the four values in the following table, using (a) Newton’s forward formula (14), (b) Newton’s backward formula (18).
continued
807
歐亞書局 P
Solution. The computation of the differences is the same in both cases. Only their notation differs.
(a) Forward. In (14) we have r = (1.72 – 1.70)/0.1 = 0.2, and j goes from 0 to 3 (see first column). In each column we need the first given number, and (14) thus gives
which is exact to 6D, the exact 7D-value being 0.386 4185.
continued
807
歐亞書局 P
(b) Backward. For (18) we use j shown in the second column, and in each column the last number. Since r = (1.72 – 2.00)/ 0.1 = –2.8, we thus get from (18)
808
歐亞書局 P
歐亞書局 P