Block 2INTERPOLATION
Structure Page Nos.
2.0Introduction
2.1Objectives
2.2operators
2.3Newton Form of the Interpolating Polynomial
2.4Interpolation at Equally Spaced Points
2.4.1Differences – Forward and Backward Differences
2.4.2Newton’s Forward-Difference and Backward-Difference Formulas
2.5Summary
2.6Solutions/Answers
2.2 operators
Let us suppose that values of a function y = f (x) are known at (n + 1) points, say x = xi,
i = 0(1) n and that x0 < x1 < x2 . . . < xn. The function f(x) may or may not be known explicitly. That is, we are given (n + 1) pair of values (x0, y0), (x1, y1), . . . (xn, yn) and the problem is to find the value of y at some intermediate point x in the interval [xo, xn]. The process of computing/determining this value is known as ‘interpolation’. There are several methods of interpolation when the abscissas xi, i = 0(1)n, known as tabular points, are equidistant i.e.
xi – xi-1 = h, i = 1(1)n is same throughout. Before discussing these methods we need to introduce some operators.
Unit 1 : Operators
i)Forward difference (FD) operator: (Delta)
f(x) = f(x+h) – f(x)
ii)Backward Difference (BD) operator : (Inverted Delta)
f(x) = f(x) – f(x – h)
iii)Central Difference (CD) operator : (Small Delta)
iv)Averaging operator : (mew)
v)Shift operator : E
Ef(x) = f(x+h)
vi)Differential Operator : D
The operators can be applied repeatedly. For example, in case of FD operator we may have,
, etc.
Similarly we can express BD and CD respectively as follows:
, etc.
, etc.
In case of shift operator we can have,
Epf(x) = f(x+ph)
where p may be +ve or –ve and integer or fractional.
Interrelation between Operators
The operators are interrelated as one operator can be expressed in terms of the other. For example, , and can be expressed in terms of E as follows:
f(x) = f(x+h) – f(x) = (E–1) f(x) or E – 1
or 1 – E–1
or
We can derive other relationships among various operators as shown in Table 1.
Table 1: Interrelations between various operators
Application of on polynomial functions
i)f(x) = c, a constant
f(x) = cx0 = cx0 = c{(x + h) 0 – x0} = c (1 – 1) = 0
ii)f(x) =x
f(x) =x = (x+h) –x =h
iii)f(x)=
Proceeding in this manner it can be shown that if f(x)=xnthen It can be further extended when f(x) is a polynomial of degree n, say Then
, as rest of differences will be zero.
Similar results hold for BD and CD operators.
Unit2; Interpolation with equal interval
Difference Table
Adifference table is central to all interpolation formulas (see Table 2).Suppose we are given the data (xi, yi), i =0,1,2…where or and represents value of y corresponding to x==x0 +ih. We can express FD of as follows,
; etc.
It will be convenient if we express in terms of E i.e.
E – 1.In that case,
, etc
We can obtain similar expressions for BD and CD. In Table 2,values of x with corresponding value of yare tabulated vertically.
Table 2: Difference Table
0 / –1 / 6.5625
7.5000
1 / 0 / 14.0625 / –15.0000
–7.5000 / 12.0000
2 / 1 / 6.5625 / –3.0000 / 24.0000
–10.5000 / 36.0000
3 / 2 / –3.9375 / 33.0000 / 24.0000
22.5000 / 60.0000
4 / 3 / 18.5625 / 93.0000
115.5000
5 / 4 / 134.0625
Note: Above values are taken from y = Note that fourth differences are constant.
In the next column first differences, yi, i = 0(1)4 are computed and placed as shown in the table. Then second differences third differences , i = 0(1)2 and finally fourth differences are computed.
It is important to note that the difference table is always made in the above manner while the differences may be expressed by FD, BD or CD as required. That is, in the column of first differences we have ,
7.5000 =
–7.5000 =
–15.0000 =
=
=, etc.
Hence the differences in a difference table appear as shown in Table 3, Table 4 and Table 5.
Table 3: Differences express in forward difference notation
i / xi / yi / 1st diff. / 2nd diff. / 3rd diff. / 4th diff.0 / x0 / y0
y0
1 / x1 / y 1 /
2 / x2 / y 2 / /
3 / x3 / y 3 /
4 / x4 / y 4
Table 4: Differences expressed in backward difference notation
i / xi / yi / 1st diff. / 2nd diff. / 3rd diff. / 4th diff.0 / x 0 / y0
1 / x 1 / y1 /
2 / x 2 / y2 / /
3 / x 3 / y3 /
4 / x 4 / y4
Table 5: Differences expressed incentral difference notation
i / xi / yi / 1st diff. / 2nd diff. / 3rd diff. / 4th diff.0 / x 0 / y0
1 / x 1 / y1 /
2 / x2 / y2 / /
3 / x3 / y3 /
4 / x4 / y4
It must be observed that in Table 3 y0 and its differences appear sloping downwards, in Table 4, y4 and its differences appear in an upward slope while in Table 5, yi and its even differences appear in a straight line (see y2).
Interpolation Formulas
We shall now discuss some interpolation formulas using FD, BD and CD. Let us suppose we have to compute the value of y corresponding to x = xp, denoted by yp. We have xp = x0 + ph or . Expressing E in terms of we get FD and BD interpolation formulas respectively. We choose x0 so as to include more terms in the formula.
i)Newton’s FD Formula
=
This formula is used to compute the value of y near the upper end of the table such that 0<p<1.
ii)Newton’s BD Formula
=
This formula is used near the lower end of the table choosing x0 such that –1<p<0. The CD formulas are used to find the value in the middle of the table. We can derive several CD formulas with tedius mathematical manipulations. Two popular CD formulas are given below:
i)Stirlings Formula
=
+
This formula should be used for –0.25 p0.25.
ii)Bessels’ Formula
This formula is used for –0.25 0.75.
Example1
From Table 2, find the value of y for x = 0.5 using appropriate formula.
Solution
Since is near upper end of the table we use FD formula. Choose so that
=14.0625 – 3.750 + 0.3750 + 2.2500 – 0.9375 = 12.0000
Example 2
From Table 2, find the value of y when x =3.5 using an appropriate formula.
Solution
Since = 3.5 is near the lower end of the table we use BD formula choosing , hence
Example3
From Table 2, find the value of y, when x = 1.75, using a central difference stirling’s formula.
Solution
Using stirling’s formula , taking= 2.0 so that p =
The differences used are as follows,
Example 4
From Table 2, find the value of y for using Bessel’s formula.
Solution
We choose so that
Bessel’s formula is given by,
The differences used in the formula are as follows,
+
=
= –1.3125 – 2.625 – 1.40625 – 0.28125 + 0.41015625
= – 2.58984375
Note: Usually the computations are required to be done up to second or third differences and at the most fourth differences and an approximate value of y is obtained.
Unit3:- Interpolation with unequal intervals
Let us suppose we have pair of values , where denotes a value corresponding to . We assume that and that the interval between two successive values of x is not necessarily same i.e., may or may not be same all over. We shall now discuss interpolation methods with unequal intervals.
Lagrange’s Method
In Lagrange’s method a polynomial is fitted passing through all the given points. Obviously, if points , are given, a polynomial of highest degree n can be fitted which is represented as,
where
are known as Lagrange’s coefficients and each of them is a polynomial of degree n. It should be noted that they satisfy a property,
,
,
The Lagrange’s method can be used for inverse interpolation i.e. we can express x as function of y as,
where
Example5
Using Lagrange’s method find the value of y when from the following data:
Compute upto four places of decimal only.
Solution
From Lagrange’s method
=
=
=
Divided Difference (DD) Table
Let us suppose that values of a function f(x) are provided for x = x0, x1, x2, … etc. which are not necessarily equi-distant. We define the divided difference (DD) as follows:
First DD:
etc.
Second DD:
Third DD:
and so on
We form a DD Table as follows
Table 6: Divided Difference (DD) Table
x / f(x) / 1st DD / 2nd DD / 3rd DD / 4th DDx0 / f(x0)
f(x0, x1)
x1 / f(x1) / f(x0, x1, x2)
f(x1, x2) / f(x0, x1, x2, x3)
x2 / f(x2) / f(x1, x2, x3) / f(x0, x1, x2, x3, x4)
f(x2, x3) / f(x1, x2, x3, x4)
x3 / f(x3) / f(x2, x3, x4)
f(x3, x4)
x4 / f(x4)
Newton’s Divided Difference (DD) Formula
The Newton’s DD formula is given as follow:
+
Example 6
Prepare a DD table for the following data
x:–030134
f(x)–28243270
Find f(2) using Newton’s DD formula.
Solution
I / xi / / 1st DD / 2nd DD / 3rd DD / 4th DD0 / –3 / –28 /
1 / 0 / 2 /
2 / 1 / 4 / / / 0
3 / 3 / 32 / /
4 / 4 / 70 /
Newton’s DD formula is given by
+
y(2) = –28 + (2+3) × 10 + (2+3) × (2 – 0) (–2) + (2+3) (2–0)(2–1)×1
= –28 + 50 – 20 + 10 = 12
Supplementary reading
2.2LAGRANGE’S FORM
2.2.1Problem of Interpolation
We are here concerned with a real-valued function f(x) defined on the interval [a, b] such that the analytical formula representing the function is unknown, but the values of the function f(x) are given for a given set of n + 1 distinct values of x = x0, x1, x2, …, xn where x0 < x1 < x2, …, < xn lying in the interval [a, b]. We denote f(xk) by fk. The technique of determining an approximate value of f(x) for a non-tabular value of x which lies in the interval is called interpolation. The process of determining the value of f(x) for a value of x lying outside the interval [a, b] is called extrapolation. However, we shall assume that f(x) is defined in (─,) in which it is continuously differentiable a sufficient number of times.
2.2.2Lagrange’s Form of Interpolating Polynomial
In this section, we derive a polynomial P(x) of degree n which agrees with values of f at the given (n + 1) distinct points, called the nodes or abscissas. In other words, we can find a polynomial P(x) such that P(xi) = fi, i = 0, 1, 2, …, n. Such a polynomial P(x) is called the interpolating polynomial of f(x).
First we prove the existence of an interpolating polynomial by actually constructing one such polynomial having the desired property. The uniqueness of the interpolating polynomial is proved by invoking the corollary of the fundamental theorem of algebra. Then we derive a general expression for error in approximating the function by the interpolating polynomial at a point and this allows us to calculate a bound on the error over an interval.
In polynomial interpolation the approximating function is taken to be a polynomial of degree n such that
)…..n(2.2.1)
Let . Then, by conditions (4.3.1) we have
i = 0, 1, 2…, n.
This is a system of n + 1 linear equations in n + 1 unknowns a0, a1, …, an. Since the determinant of the co-efficients
as xo, x1…….xn are distinct points/nodes, the values of a0, a1, …, an can be uniquely determined so that the polynomial Pn(x) exists and is unique. But this does not give us the explicit form of Pn(x). Hence in the following we first show the existence of Pn(x) by constructing one such polynomial and then prove its uniqueness.
Theorem 1:Let x0, x1, …, xn be n + 1 distinct points on the real line and let f(x) be a real-valued function defined on some interval I = [a, b] containing these points. Then, there exists exactly one polynomial Pn(x) of degree n, which interpolates f(x) at xo, x1, …, xn, that is, i = 0, 1, 2, …, n.
Proof: Consider the problem of determining a polynomial of degree 1 that passes through the distinct points and. That is, we are approximating the function f by means of a first degree polynomial interpolating f(x) at x = x0 and x1.
Consider the polynomial
Then P1(x0) = f0 and P1(x1) = f1. Hence P1(x) has the required properties. Let
L0(x) and L1(x) , then P1(x) = L0(x) f0 + L1(x) f1.
Also we note that and L1(x1) = 1.
For the general case, let the required polynomial be written as
(2.2.2)
Setting x = xj, we get
fj =
Since the polynomial fits the data exactly,
we must have
The polynomial Li(x) which are of degree n are called the Lagrange fundamental polynomials. It is easily verified that these polynomials are given by
= i = 0, 1, 2, …, n. (2.2.3)
Substitution of (4.3.2) in (4.3.1) gives the required Lagrange form of the interpolating polynomial. The uniqueness of the interpolating polynomial can be established easily with the help of following results.
Lemma 1. If x1, x2 , …, xk are distinct zeros of the polynomial P(x), then
P(x) = (x – x1) (x – x2) … (x – xk) R(x)
for some polynomial R(x)
Corollary. If Pk(x) and Qk(x) are two polynomials of degree k which agree at the
k +1 distinct points then Pk(x) = Qk(x) identically.
Example 1: Find the Lagrange’s interpolating polynomial for the following data:
X / / / 1f(x) / –1 / 2 / 7
Solution:
Hence P2 (x) = L0 (x) (-1) + L1 (x) (2) + L2 (x) (7)
Example 2: If f(1) = –3, f(3) = 9, f(4) = 30 and f(6) = 132, find the Lagrange’s interpolation polynomial of f(x). Also find the value of f when x = 5.
Solution: We have x0 = 1, x1 = 3, x2 = 4, x3 = 6 and
f0 = –3, f1 = 9, f2 = 30, f3 = 132.
The Lagrange’s interpolating polynomial P3(x) is given by
P3(x) =L0(x)(2.2.4)
Where
Substituting these in (2.2.4) we have:
which gives on simplification
P3(x) = x3 – 3x2 + 5x – 6.
You may now solve the following exercises
E1)Prove the uniqueness of the interpolating polynomial using corollary of Lemma 1.
E2)Find Lagrange’s interpolating polynomial for the data. Hence obtain f(2).
x / 0 / 1 / 4 / 5f(x) / 8 / 11 / 68 / 123
E3)Using the Lagrange’s interpolation formula, find the value of y when x=10
x / 5 / 6 / 9 / 11f(x) / 12 / 13 / 14 / 16
2.2.3Inverse Interpolation
In inverse interpolation in a table of values of x find y = f(x), one is given a number and wishes to find the point so that f= , where f(x) is the tabulated function. For this, we naturally assume that the function y = f(x) has a unique inverse x = g(y) in the range of the table. The problem of inverse interpolation simply reduces to interpolation with x-row and y-row in the given table interchanged so that the interpolating points now become y0, y1, …, yn (same as f0, f1, …, fn i.e. f(xi) = fi = yi) and the corresponding function values are x0, x1, …, xn where the function is x = g(y). Since the points y0, y1, …, yn are invariably unequally spaced, this interpolation can be done by Lagrange’s form of interpolation (also by Newton’s divided difference form discussed later). By Lagrange’s formula
Pn(y) = and
. This process is called inverse interpolation
Example 3: Find the value of x when y = 3 from the following table of values
x / 4 / 7 / 10 / 12y / –1 / 1 / 2 / 4
Solution: The Lagrange’s interpolation polynomial of x is given by
So
You may now solve the following exercises
E4)Using Lagranges interpolation formula, find the value of f(4) from the following data:
x / 1 / 3 / 7 / 13f(x) / 2 / 5 / 12 / 20
E5)From the following table, find the Lagrange’s interpolating polynomial, which agrees with the values of x at the given value of y. Hence find the value of x when y = 2.
x / 1 / 19 / 49 / 101y / 1 / 3 / 4 / 5
E6)Using the inverse Lagrange interpolation, find the value of x when y = 3 from the following table of values:
x / 36 / 54 / 72 / 144y / – 2 / 1 / 2 / 4
2.2.4General Error Term
The next step is to estimate/calculate a remainder term or bound for the error involved in approximating a function by an interpolating polynomial.
Let En(x) = f(x) – Pn(x) be the error involved in approximating the function f(x) by an interpolating polynomial. We derive an expression for En(x) in the following theorem. We shall just indicate the proof. This result helps us in estimating a useful bound on the error as explained through an example.
Theorem 2:Let x0, x1, ..., xn be distinct numbers in the interval [a, b] and f has (continuous) derivatives up to order (n + 1) in the open interval (a, b). If Pn(x) is the interpolating polynomial of degree n, which interpolating f(x) at the points x0, x1,…, xn, then for each x [a, b], a numberin (a, b) exists such that
En(x) = f(x) – Pn(x).
Proof (Indication): If x for any k = 0, 1, 2, …, n, define the function g for t in [a, b] by g(t) = f(t) – Pn(t) – [f(x) – Pn(x)] .
g(t) has continuous derivatives up to (n + 1) order. Now, for k = 0, 1, 2, …, n, we have g(xk) = 0 and g(x) = 0.
Thus, g has continuous derivatives up to order (n + 1) and g vanishes at the (n + 2) distinct points x, x0, x1, …, xn. By generalized Rolle’s Theorem stated below, there exists in (a, b) for which g(n+1) = 0. That is
0 = g(n+1)
= f(n+1)( ) – (n+1)!
where the differentiation is with respect to t.
Simplifying above we get the error at x =
En= f – Pn = (2.2.5)
By repeated application of Rolle’s Theorem the following theorem can be proved.
Theorem 3(Generalized Rolle’s Theorem):
Let f be a real-valued function defined on [a, b] which is n times differentiable on (a, b). If f vanishes at the (n + 1) distinct prints x0, x1, …, xn, in [a, b] then a number
c in (a, b) exists such that f(n) (c) = 0.
The error formula derived above, is an important theoretical result and error formula and interpolating polynomial will be used in deriving important formula for numerical differentiation and numerical integration
It is to be noted that = depends on the point at which error estimate is required. This error formula is of limited utility since f(n+1) (x) is not known (when we are given a set of data at specific nodes) and the point is hardly known. But the formula can be used to obtain a bound on the error of interpolating polynomial as illustrated below:
Example 4: The following table given the values of f(x) = ex, .1 x 2. If we fit an interpolating polynomial of degree four to the data given below, find the magnitude of the maximum possible error in the computed value of f(x) when
x = 1.25.
x / 1.2 / 1.3 / 1.4 / 1.5 / 1.6f(x) / 3.3201 / 3.6692 / 4.0552 / 4.4817 / 4.9530
Solution: From Equation, the magnitude of the error associated with the 4th degree polynomial approximation is given by
and = e1.6 = 4.9530
Since f(x) = ex is increasing in [1.2, 1.6]. Hence
When nodes are equipspaced, we shall get another bound later.
2.3NEWTON FORM OF THE INTERPOLATING POLYNOMIAL
The Lagrange’s form of the interpolating polynomial discussed in previous section has certain drawbacks. One generally calculates a linear polynomial P1(x), a quadratic polynomial P2(x) etc. by increasing the number of interpolating points, until a satisfactory approximation Pk(x) to f(x) has been found. In such a situation, Lagrange form does not take any advantage of the availability of Pk-1(x) in calculating Pk(x). In Newton form, this advantage is taken care of.
Before deriving Newton’s general form of interpolating polynomial, we introduce the concept of divided difference and the tabular representation of divided differences. Also the error term of the interpolating polynomial in this case is derived in terms of divided differences. Using the two different expressions for the error term we establish a relationship between nth order divided difference and the nth order derivative.
Suppose we have determined a polynomial Pk-1(x) of degree k – 1 which interpolates f(x) at the points x0, x1,…, xk–1. In order to make use of Pk–1(x) in calculating Pk(x) we consider the following problem. What function g(x) should be added to Pk–1(x) to get Pk(x)? Let g(x) = Pk(x) – Pk–1(x). Now, g(x) is a polynomial of degree k and for = 0, 1, …, k – 1.
Hence g(x) can be written as
Where Ak is a constant depending on x0, x1, …, xk–1.
Suppose that is the Lagrange polynomial of degree at most n that agrees with the function f at the distinct numbers x0, x1, …, xn. The divided difference of f with respect to x0, x1, …, xn can be obtained by proving that Pn has the representation, called Newton form.
(2.3.1)
for appropriate constants A0, A1,…..An.
Evaluating Pn(x) [Equation (4.4.1)] at xo we get A0 = Pn(x0) = f(x0).
Similarly when Pn(x) is evaluated at x1, we get Let us introduce the notation for divided differences and define it at this stage. The divided difference of the function f, with respect to xi, is denoted by f[xi] and is simply the evaluation f at xi, that is, f[xi]=f(xi). The first divided difference of f with respect to xi and xi+1 is denoted by f[xi, xi+1] and defined as
f[xi, xi+1]
The remaining divided differences of higher orders are defined inductively as follows. The kth divided differences relative to xi, xi+1, …, xi+k is defined as follows:
where the (k –1)st divided differences f[xi,…, xi+k–1] and f[xi+1,…, xi+k] have been determined. This shows that the kth divided difference is the divided differences of
(k –1)st divided differences justifying the name. It can be shown that the divided difference f[x0, x1–1, xk] is invariant under all permutations of argument x0, x1,…, xk.
The constant A2, A3, …, An can be consecutively obtained in similar manner like the evaluation of A0 and A1. As shown in the evaluation of A0 and A1 , the required constants Ak=f[x0, x1,…xk].
This shows that Pn(x) can be constructed step by step with the addition of the next term in Equation (4.4.1), as one constructs the sequence P0(x), P1(x) with Pk(x) obtained from in the form
(2.3.2)
That is, g(x) is a polynomial of degree k having (at least) k distinct zeros x0,…..xk–1. This constant Ak is called the kth divided difference of f(x) at the points x0, x1, …, xk and is denoted by f[x0, x1…, xk]. This coefficient depends only on the values of f(x) at the points x0, x1, …, xk. The following expressions can be proved for f[x0, x1, …..xk].
(2.3.3)
and
(2.3.4)
Equation (4.4.2) can now be rewritten as
(2.3.5)
Using Equation (4.4.5), Equation (4.4.1) can be rewritten as
(2.3.6)
This can be written compactly as follows
(2.3.7)
This is Newton’s form of interpolating polynomial or Newton’s interpolatory divided-difference formula.
Methods for determining the explicit representation of an interpolating polynomial from tabulated data are known as divided-difference methods. These methods can be used to derive techniques for approximating the derivatives and integrals of functions, as well as for (approximating the solutions) to differential equations.
2.3.1Table of Divided Differences
Suppose we denote, for convenience, a first order divided difference of f(x) with any two arguments by f[., .], a second order divided difference with any three arguments by f[., ., .] and so on. Then the table of divided difference can be written as follows:
Table 1
Xf[.]f[., .]f[., ., .]f[[., ., ., .] f[[., ., ., .,.]
x0f0
f[x0, x1]
x1f1f[x0, x1, x2]
f[x1, x2]f[x0, x1, x2, x3]
x2f2f[x1, x2, x3] f[x0, x1, x2, x3, x4]
f[x2, x3] f[x1, x2, x3, x4]
x3f3 f[x2, x3, x4]
f[x3, x4]
x4f4
Example:If f(x) = x3, find the value of f[a ,b, c].
Solution:f[a, b] =
Similarly f[b, c] = b2 + bc + c2
Hence f[a, b, c] =
= a + b + c
You may now solve the following exercises
E7)If f(x)=, show that f[a, b, c, d] = – .
E8)Using divided difference show that the following data
x / 1 / 2 / 3 / 5 / 6f(x) / 1 / 3 / 7 / 21 / 31
represents a second degree polynomial. Obtain this polynomial. Hence, find the approximate value of f(4).
Example 5: Form the following table of values, find the Newton’s form of interpolating polynomial approximating f(x).
x / –1 / 0 / 3 / 6 / 7f(x) / 3 / –6 / 39 / 822 / 1611
Also find the approximate value of the function f(x) at x = 2.
Solution: We note that the value of x, that is xi are not equally spaced. To find the desired polynomial, we form the table of divided differences of f(x)
Table 2
xf[.] f[., .]f[., ., .]f[[., ., ., .] f[[., ., ., .,.]
x0 –1 3
─9
x1 0 –6 6
15 5
x2 3 39 41 1
261 13
x3 6 822 132
789
x4 7 1611
Newton’s interpolating polynomial P4(x) is given by
+(x – x0)(x – x1)(x – x2)f[x0, x1 ,x2, x3] +
(x – x0)(x – x1) (x – x2) (x – x3)f[x0, x1, x2, x3] (2.3.8)
The divided differences f[x0], f[x0, x1], f[x1, x1, x2], f[x0, x1, x2, x3], f[x0, x1, x2, x3] are those which lie along the diagonal at f(x0) as shown by the dotted line. Substituting the values of xi and the values of the divided differences in Equation (4.4.8), we get
P4(x) =3 + (x + 1)( –9) + (x + 1)(x – 0)(6) + (x + 1)(x – 0)(x –3)(5)
+(x +1)(x– 0)(x – 3)(x – 6)(1)
This on simplification gives
P4(x) = x4 – 3x3 + 5x2 – 6