c) Derive Newton's divided difference formula.
Answers
Answer:
Newton's divided difference interpolation formula is a interpolation technique used when the interval difference is not same for all sequence of values. Divided differences are symmetric with respect to the arguments i.e independent of the order of arguments
NEWTON'S DIVIDED DIFFERENCE FORMULA
Let us assume that the function f(x) is linear then we have
f(xi) - f(xj)
(xi - xj)
where xi and xj are any two tabular points, is independent of xi and xj. This ratio is called the first divided difference of f(x) relative to xi and xj and is denoted by f [xi, xj]. That is
f [xi, xj] =
f(xi) - f(xj)
= f [xj, xi]
(xi - xj)
Since the ratio is independent of xi and xj we can write f [x0, x] = f [x0, x1]
f(x) - f(x0)
=
f [x0, x1]
(x - x0)
f(x) = f(x0) + (x - x0) f [x0, x1]
=
1
| f(x0)
x0 - x
|
f1 - f0
f0x1 - f1x0
=
x +
x - x0
f(x1)
x1 - x
x1 - x0
x1 - x0
So if f(x) is approximated with a linear polynomial then the function value at any point x can be calculated by using f(x) @ P1(x) = f(x0) + (x - x1) f [x0, x1]
where f [x0, x1] is the first divided difference of f relative to x0 and x1.
Similarly if f(x) is a second degree polynomial then the secant slope defined above is not constant but a linear function of x. Hence we have
f [x1, x2] - f [x0, x1]
x2 - x0
is independent of x0, x1 and x2. This ratio is defined as second divided difference of f relative to x0, x1 and x2. The secind divided difference are denoted as
f [x1, x2] - f [x0, x1]
f [x0, x1, x2] =
x2 - x0
Now again since f [x0, x1,x2] is independent of x0, x1 and x2 we have
f [x1, x0, x] = f [x0, x1, x2]
f [x0, x] - f [x1, x0]
= f [x0, x1, x2]
x - x1
f [x0, x] = f [x0, x1] + (x - x1) f [x0, x1, x2]
f [x] - f [x0]
= f [x0, x1] + (x - x1) f [x0, x1, x2]
x - x0
f(x) = f [x0] + (x - x0) f [x0, x1] + (x - x0) (x - x1) f [x0, x1, x2]
This is equivalent to the second degree polynomial approximation passing through three data points
x0
x1
x2
f0
f1
f2
So whenever f(x) is approximated with a second degree polynomial, the value of f(x) at any point x can be computed using the above polynomial.
In the same way if we define recursively kth divided difference by the relation
f [x1, x2, . . ., xk] - f [x0, x1, . . ., xk-1]
f [x0, x1, . . ., xk] =
xk - x0
The kth degree polynomial approximation to f(x) can be written as
f(x) = f [x0] + (x - x0) f [x0, x1] + (x - x0) (x - x1) f [x0, x1, x2]
+ . . . + (x - x0) (x - x1) . . . (x - xk-1) f [x0, x1, . . ., xk].
This formula is called Newton's Divided Difference Formula. Once we have the divided differences of the function f relative to the tabular points then we can use the above formula to compute f(x) at any non tabular point.
Computing divided differences using divided difference table: Let us consider the points (x1, f1), (x2, f2), (x3, f3) and (x4, f4) where x1, x2, x3 and x4