Unit - 3
Polynomial interpolation
Interpolation
Definition:
Interpolation is a technique of estimating the value of a function for any intermediate value of the independent variable while the process of computing the value of the function outside the given range is called extrapolation.
Let be a function of x.
The table given below gives corresponding values of y for different values of x.
X |
| …. | |||
y= f(x) | …. |
The process of finding the values of y corresponding to any value of x which lies between is called interpolation.
If the given function is a polynomial it is polynomial interpolation and given function is known as interpolating polynomial.
Note- The process of computing the value of the function outside the given range is called extrapolation.
Thus interpolation is the “art of reading between the lines of a table.”
Conditions for Interpolation
1) The function must be a polynomial of independent variable.
2) The function should be either increasing or decreasing function.
3) The value of the function should be increase or decrease uniformly.
Finite Difference
Let be a function of x.The table given below gives corresponding values of y for different values of x.
X |
| …. | |||
y= f(x) | …. | ||||
|
|
|
|
|
|
There are three types of differences are useful-
a) Forward Difference:
The are called differences of y, denoted by
The symbol is called the forward difference operator. Consider the forward difference table below:
Where
And third forward difference so on.
b) Backward Difference:
The difference are called first backward difference and is denoted by Consider the backward difference table below:
Where
And third backward differences so on.
Example: Construct a backward difference table for y = log x, given-
X | 10 | 20 | 30 | 40 | 50 |
y | 1 | 1.3010 | 1.4771 | 1.6021 | 1.6990 |
Sol. The backward difference table will be-
10
20
30
40
50
| 1
1.3010
1.4771
1.6021
1.6990
|
0.3010
0.1761
0.1250
0.0969
|
-0.1249
-0.0511
-0.0281
|
0.0738
0.0230 |
-0.0508
|
Divided Difference:
In the case of interpolation, when the value of the arguments are not equi-spaced (unequal intervals) we use the class of differences called divided differences.
Definition: The difference which are defined by taking into consideration the change in the value of the argument are known as divided differences.
Let be a function defined as
……. | ||||
………… |
Where are unequal i.e. it is case of unequal interval.
The first order divided differences are:
And so on.
The second order divided difference is:
And so on.
Similarly the nth order divided difference is:
With the help of these we construct the divided difference table:
X | f(x) | ||
|
|
|
|
Newton’s Divided difference Formula:
Let be a function defined as
……. | ||||
………… |
Where are unequal i.e. it is case of unequal interval.
.
Example1: By means of Newton’s divided difference formula, find the values of from the following table:
x | 4 | 5 | 7 | 10 | 11 | 13 |
f(x) | 48 | 100 | 294 | 900 | 1210 | 2028 |
We construct the divided difference table is given by:
x | f(x) | First order divide difference | Second order divide difference | Third order divide difference | Fourth order divide difference |
4
5
7
10
11
13 | 48
100
294
900
1210
2028 |
|
|
|
0
0 |
By Newton’s Divided difference formula
.
Now, putting in above we get
.
Example2: The following values of the function f(x) for values of x are given:
Find the value of and also the value of x for which f(x) is maximum or minimum.
We construct the divide difference table:
x | f(x) | First order divide difference | Second order divide difference | Third order divide difference |
1
2
7
8 | 4
5
5
4 |
|
|
0 |
By Newton’s divided difference formula
.
Putting in above we get
For maximum and minimum of , we have
Or
Example3: Find a polynomial satisfied by
, by the use of Newton’s interpolation formula with divided difference.
x | -4 | -1 | 0 | 2 | 4 |
F(x) | 1245 | 33 | 5 | 9 | 1335 |
Here
We will construct the divided difference table:
x | F(x) | First order divided difference | Second order divided difference | Third order divided difference | Fourth order divided difference |
-4
-1
0
2
4 | 1245
33
5
9
1335 |
|
|
|
|
By Newton’s divided difference formula
.
This is the required polynomial.
Lagrange’s Interpolation of polynomial:
Let , be defined function we get
X | ….. | ||||
f(x) | …… |
Where the interval is not necessarily equal. We assume f(x) is a polynomial od degree n. Then Lagrange’s interpolation formula is given by
Example1: Deduce Lagrange’s formula for interpolation. The observed values of a function are respectively 168,120,72 and 63 at the four position3,7,9 and 10 of the independent variable. What is the best estimate you can for the value of the function at the position6 of the independent variable.
We construct the table for the given data:
X | 3 | 6 | 7 | 9 | 10 |
Y=f(x) | 168 | ? | 120 | 72 | 63 |
We need to calculate for x = 6, we need f(6)=?
Here
We get
By Lagrange’s interpolation formula, we have
Hence the estimated value for x=6 is 147.
Example2: By means of Lagrange’s formula, prove that
We construct the table:
X | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
Y=f(x) |
Here x = 3, f(x)=?
By Lagrange’s formula for interpolation
Hence proved.
Example3: Find the polynomial of fifth degree from the following data
X | 0 | 1 | 3 | 5 | 6 | 9 |
Y=f(x) | -18 | 0 | 0 | -248 | 0 | 13104 |
Here
We get
By Lagrange’s interpolation formula
Key takeaways-
- The difference which are defined by taking into consideration the change in the value of the argument are known as divided differences.
- Newton’s Divided difference Formula
.
Error in interpolation:
We know that, the interpolation means to estimate a missing function value by taking a weighted average of known function value at neighbouring points.
Let y = f(x) is the known function at (n + 1) points.
A polynomial of degree n. is known as the interpolating polynomial when passes through these (n + 1) points.
can be constructed using only the numerical values and and does not need any order derivatives of f (x). The approximation is known as interpolated value when and extrapolated value when or .
Note- Error increases when the number of interpolation is increased.
The error of the polynomial is obtained by the generalized Rolle’s theorem,
It is given as-
Here contains {x, }
Note- that the error term given above is same for Lagrange polynomial and interpolating polynomial obtained from divide difference table
Central differences:
The central difference operator is defined by the relations,
...................
|
|
|
|
|
|
|
Averaging operator (:
It is defined as-
Shift operator E:
It is the operation of increasing the argument x by h so that
Ef(x) = f(x + h)
f(x) = f(x + 2h) and so on.
The inverse operator is defined by
Note:
1.
2.
3.
4.
5.
6.
Example: Prove that
Sol.
By taking left hand side, we get-
Example: Prove that-
Sol.
From (1)-
Hence proved.
Example: Prove that
Sol.
R.H.S
Gauss forward difference formula-
- Gauss forward difference formula-
2. Gauss backward difference formula-
Example: By using Gauss forward difference formula obtain f(32) given that-
f(25) = 0.2707 f(35) = 0.3386
f(30) = 0.3027 f(40) = 0.3794
Sol.
Here
Let us take the origin at 30, a = 30 then we get-
u = 0.4
The forward difference table-
u | x | F(x) | |||
-1
0
1
2
| 25
30
35
40 | 0.2707
0.3027
0.3386
0.3794 |
0.032
0.359
0.408 |
0.0039
0.0049 |
0.0010 |
By using Gauss forward difference formula, we get-
Example: Find by using Gauss forward formula if-
Sol.
Let a = 8, h = 4,
We have
a + hu = 9
And we get-
u = 0.25
The forward difference table-
u | X | F(x) | ||||
-2
-1
0
1
2
| 0
4
8
12
16 | 14
24
32
35
40
|
10
8
3
5 |
-2
-5
2
|
-3
7
|
10 |
By using Gauss forward difference formula, we get-
Hence
Example: Using Gauss’s backward interpolation formula, find the population for the year 1936 given that-
Year | 1901 | 1911 | 1921 | 1931 | 1941 | 1951 |
Population(in thousands) | 12 | 15 | 20 | 27 | 39 | 52 |
Sol.
Let origin is at 1941 and h = 10
Then-
Which gives-
The backward difference table-
u | F(u) | |||||
-4
-3
-2
-1
0
1
| 12
15
20
27
39
52 |
3
5
7
12
13 |
2
2
5
1
|
0
3
-4
|
3
-7 |
-10
|
By using Gauss backward formula, we get-
thousands
Hence the pop. Of the year 1936 is 32625
Key takeaways-
1. Gauss forward difference formula-
2. Gauss backward difference formula-
Hermite’s interpolation formula-
The Hermite’s interpolation formula is defined as-
Example: Find the cubic polynomial by using Hermite’s interpolation formula, given-
0 | 0 | 0 |
1 | 1 | 1 |
Sol.
We know that Hermite’s interpolation formula-
..........(1)
Now
And
Hence
From equation (1)-
and
Spline interpolation-
The approximation of arbitrary functions on a closed interval becomes oscillatory for higher-degree polynomials. By dividing the given interval into a collection of subintervals, piecewise polynomial approximation consists of constructing a different approximating polynomial on each subinterval. Cubic spline interplation is the most common piecewise approximation using cubic polynomial, known as spline function, connecting each pair of data points. Cubic splines are third-order curves employed to connect each pair of data points.
Linear splines-
This type of spline defined by a function that is the linear function.
Linear splines are called first order splines.
Consider a set of (n + 1) data points, (
The set of linear functions defining linear splines in n intervals are-
………………………………………….
………………………………………….
………………………………………….
………………………………………….
is the slope if the line connects the data points .
is given as-
Quadratic splines:
These are called the second order splines.
For each interval, we fit a parabola give by-
For n + 1 data points we have n intervals. So we should determine 3 × n unknown constants. The 3n condition to find the 3n unknowns are given by the following equations.
- At the interior knots, the function values must be-
For i = 2, n giving raise to 2(n − 1) = 2n – 2 conditions.
2. The first and last functions must pass through the two end points
Giving two conditions.
3. At the interior knots, the first derivatives f (x) = 2ax + b must be equal.
For i = 2 to n giving n − 1 conditions
4. Assume that the second derivative is zero at the first point. Then the first two points are connected by a straight line, so
Thus solving (2n − 2) + 2 + (n − 1) + 1 = 3n conditions above we obtain the 3n unknown constants a, b and c.
Cubic splines-
Let us fit a third order polynomial,
For each of the n intervals between the (n + 1) data points (knots) (i = 0, 1, 2, . . . n). The problem is to find the 4 × n = 4n unknown constants
We have the following conditions-
- 2n − 2 conditions since the function values must be equal at the (n − 1) interior knots.
- 2 conditions since the first and last functions must pass through the two end points x0 and xn.
- (n − 1) conditions since the first derivatives must be equal at the (n − 1) interior points.
- (n − 1) conditions since the second derivatives must be equal at the (n − 1) interior knots.
The above conditions are summed to (2n − 2) + (2) + (n − 1) + (n − 1) = 4n − 2, thus short of 2 more conditions to solve the 4n unknown constants.
Natural spline for which the end point constraints are assumed as “second derivatives at the end knots are zero”.
Natural splines are more frequently used in which the end cubic approach linearity at their extremities.
The cubic spline for each interval (, ) is given by
There are only two unknowns
Therefore the second derivatives at the end points of the interval can be find by the following equations,
This equation written for the (n -1) interior points results in (n −1) simultaneous equations for the second derivatives.
Example: Fit a linear spline of the data given below:
X | 1 | 3 | 6 | 8 |
F(x) | 4 | 5.5 | 7 | 9.5 |
Sol.
Here we have, n = 4 and there are 3 intervals.
Let us assume that-
, , ,
, , ,
And the slope,
Similarly we can find,
As we know that the
The three splines will be-
Example: Fit quadratic splines for the following data.
X | 1 | 3 | 6 | 8 |
F(x) | 4 | 5.5 | 7 | 9.5 |
Sol.
For the 4 data points in 3 intervals, we fix three splines of the form-
We need to find 9 unknown (3 * 3 = 9).
We need 9 conditions to determine 9 unknowns.
There are 2 interior points .
- Function value must be equal at the two interior points, giving rise to four equations.
For i=2 to 3
For i=2
For
2. The first and last function must pass through the end points and giving rise to two equations-
Or
3. The third derivative at the interior knots must be equal-
For i=2,3
4. Assume that the second derivative is zero at the first point i.e.,
Using (9), in (1) and(5)-
We get-
By solving second and third equation, we get-
By solving 4 and 6, we get-
So that we get the values of 9 coefficients-
Now-
The three quadratic splines will be-
References:
- E. Kreyszig, “Advanced Engineering Mathematics”, John Wiley & Sons, 2006.
- P. G. Hoel, S. C. Port and C. J. Stone, “Introduction to Probability Theory”, Universal Book Stall, 2003.
- S. Ross, “A First Course in Probability”, Pearson Education India, 2002.
- W. Feller, “An Introduction to Probability Theory and Its Applications”, Vol. 1, Wiley, 1968.
- N.P. Bali and M. Goyal, “A Text Book of Engineering Mathematics”, Laxmi Publications, 2010.
- B.S. Grewal, “Higher Engineering Mathematics”, Khanna Publishers, 2000.