Dr. Anita Pal Assistant Professor

by

Dr. Anita Pal Assistant Professor

Department of Mathematics

National Institute of Technology Durgapur Durgapur-713209

email: anita.buie@gmail.com

Chapter 2 Interpolation

Module No. 2

Newton’s Interpolation Methods

In Lagrange’s interpolation lots of arithmetic calculations are involved. But, this method is applicable for both equal and unequal spaced points. In this module, we discussed about new kind of interpolation methods based on finite differences known as Newton’s interpolations. In these methods, we assumed that the values of x’s are equispaced.

2.1 Newton’s forward difference interpolation formula

Suppose the explicit form of the functiony=f(x) is unknown, but the values ofy at some equispaced points x₀, x₁, . . . , x_n are known. Lety_i be the value of f(x) atx=x_i and it is known for alli= 0,1,2, . . . , n. If the function is given, then one can calculate such values.

Since the values of x’s are equispaced, thereforexi=x0+ih, i= 0,1, . . . , n, whereh is called the spacing. Thus, we have a set ofn+ 1 points (x_i, y_i), i= 0,1,2, . . . , n.

Now, the problem is to construct a polynomial, say,φ(x) of degree less than or equal tonwhich passes through the points

yi=φ(xi), i= 0,1, . . . , n. (2.1) Let the polynomialφ(x) be the following form

φ(x) =a₀+a₁(x−x₀) +a₂(x−x₀)(x−x₁) +a₃(x−x₀)(x−x₁)(x−x₂) +· · ·+an(x−x0)(x−x1)· · ·(x−xn−1), (2.2) where a₀, a₁, . . . , a_n are constants and their values are to be determined using (2.1).

Now, our problem is to find the values ofa_i’s. To find these values, substitutex=x_i in (2.2) according to the order i= 0,1,2, . . . , n.

When x=x₀, then φ(x₀) =a₀, i.e. a₀ =y₀. When x=x1, then φ(x1) =a0+a1(x1−x0)

i.e. y1 =y0+a1h. Thus, the value of a1 is a1 = y1−y0

h = ∆y0

h . When x=x₂,φ(x₂) =a₀+a₁(x₂−x₁) +a₂(x₂−x₀)(x₂−x₁)

i.e. y2 =y0+y₁−y₀

h .2h+a2(2h)(h).

Therefore, a₂= y₂−2y₁+y₀

2!h² = ∆²y₀ 2!h² .

In this way, all ai’s can be determined. In general,an= ∆ⁿy₀ n!hⁿ.

By substituting all the values ofai in (2.2), the polynomial φ(x) becomes φ(x) =y0+ (x−x0)∆y0

h + (x−x0)(x−x1)∆²y0

2!h² +(x−x0)(x−x1)(x−x2)∆³y₀

3!h³

+· · ·+ (x−x₀)(x−x₁)· · ·(x−xn−1)∆ⁿy0

n!hⁿ. (2.3)

This is the interpolating polynomial, but it can be simplified by using the equispaced condition and introducing a suitable variable discussed below.

Let the new variable u be defined as x = x₀ +uh. Since x_i = x₀+ih, therefore, x−xi = (u−i)hfori= 0,1,2, . . . , n.

Using these values the equation (2.3) reduced to φ(x) =y0+ (uh)∆y0

h + (uh)(u−1)h∆²y0

2!h² + (uh)(u−1)h(u−2)h∆³y0

3!h³ +· · ·+ (uh)(u−1)h(u−2)h· · ·(u−n−1)h∆ⁿy₀

n!hⁿ

=y0+u∆y0+u(u−1)

2! ∆²y0+u(u−1)(u−2) 3! ∆³y0

+· · ·+ u(u−1)(u−2)· · ·(u−n−1)

n! ∆ⁿy0. (2.4)

The value of uis obtained by u= x−x0

h for a given value ofx.

This is known as Newton or Newton-Gregory forward difference interpolating polynomial.

Obviously, this interpolation formula also contains some error, and the error is esti- mated in the following.

Error in Newton’s forward interpolation formula

In previous module, it is seen that the error in polynomial interpolation is E(x) = (x−x0)(x−x1)· · ·(x−xn)f⁽ⁿ⁺¹⁾(ξ)

(n+ 1)!

=u(u−1)(u−2)· · ·(u−n)hⁿ⁺¹f⁽ⁿ⁺¹⁾(ξ)

(n+ 1)! (using x=x0+uh)

where ξ is a value of x and it lies between min{x₀, x1, . . . , xn, x} and max{x₀, x1, . . . , x_n, x}.

In terms of forward difference, the value of f⁽ⁿ⁺¹⁾(ξ) is approximately equal to hⁿ⁺¹∆ⁿ⁺¹y0.

Thus, the error in terms of forward difference is E(x)' u(u−1)(u−2)· · ·(u−n)

(n+ 1)! ∆ⁿ⁺¹y0. Let us consider a particular case:

If 0< u <1 then

|u(u−1)|= (1−u)u=u−u² = 1 4−

1 2 −u

2

≤ 1 4 and

|(u−2)(u−3)· · ·(u−n)| ≤ |(−2)(−3)· · ·(−n)|=n!.

Thus,

|E(x)| ≤ 1 4

n!

(n+ 1)!|∆ⁿ⁺¹y₀|= 1

4(n+ 1)|∆ⁿ⁺¹y₀|.

Again,|∆ⁿ⁺¹y₀| ≤9 in the last significant figure.

Hence,|E(x)| ≤ 9

4(n+ 1) <1 forn >2 and 0< u <1.

This is a very interesting result and indicates that the maximum error in Newton’s forward interpolation is 1, provided u=|(x−x₀)/h|<1, i.e. |x−x₀|< h.

Example 2.1 Given below is a table of values of the probability integral

y= 2 π

Z x

0

e^−x2 dx.

Determine the value of y when the value of x is 0.456.

x : 0.45 0.46 0.47 0.48 0.49

y : 0.475482 0.484656 0.497452 0.502750 0.511668

Solution. Let us first construct the forward difference table as follows:

x y ∆y ∆²y ∆³y 0.45 0.475482

0.009174

0.46 0.484656 0.003622

0.012796 –0.011120

0.47 0.497452 –0.007498

0.005298 0.011118

0.48 0.502750 0.003620

0.008918 0.49 0.511668

For this problem, x₀ = 0.45, x= 0.456, h= 0.01, u= x−x₀

h = 0.456−0.45 0.01 = 0.6.

Now,

y(0.456) =y₀+u∆y₀+u(u−1)

2! ∆²y₀+u(u−1)(u−2) 3! ∆³y₀

= 0.475482 + 0.6×0.009174 + 0.6(0.6−1)

2 ×0.003622

+0.6(0.6−1)(0.6−2)

6 ×(−0.011120)

= 0.475482 + 0.0055044−0.0008693−0.0006227

= 0.4794944.

Hence, the value ofy when x= 0.456 is 0.479494.

Note 2.1 In general, Newton’s forward difference formula is used to compute the ap- proximate value of f(x) when the value of x is near tox₀ of the given table. But, if the value of x is at the end of the table, then this formula gives more error. In this case, Newton’s backward formula is used, discussed below.

2.2 Newton’s backward difference interpolation formula

This is another form of Newton’s interpolation. Let the set of values (xi, yi), i = 0,1,2, . . . , n be given, where y_i=f(x_i) and x_i =x₀+ih,h is the spacing.

We have to construct a polynomial of degree less than or equal to n, which passes through the given points.

Letφ(x) be such a polynomial and it is consider as follows:

φ(x) =a₀+a₁(x−x_n) +a₂(x−x_n)(x−xn−1) +a₃(x−x_n)(x−xn−1)(x−xn−2)

+· · ·+a_n(x−x_n)(x−xn−1)· · ·(x−x₁). (2.5) Here a_i’s are constants and their values are to be determined using the conditions

yi =φ(xi), i= 0,1, . . . , n. (2.6) To find the values ofai’s, we substitute x=xn, nn−1, . . . , x1 in (2.5).

Forx=x_n,

φ(xn) =a0, i.e. a0 =yn. For x=xn−1,

φ(xn−1) =a₀+a₁(xn−1−x_n), i.e. yn−1=y_n+a₁(−h). This givesa₁ = y_n−yn−1

h = ∇y_n

h . When x=xn−2,

φ(xn−2) =a₀+a₁(xn−2−x_n) +a₂(xn−2−x_n)(xn−2−xn−1)

=yn+yn−yn−1

h (−2h) +a2(−2h)(−h)

That is, yn−2= 2yn−1−y_n+a₂.2!h². Hence,a₂ = yn−2yn−1+yn−2

2!h² = ∇²yn

2!h² . In this manner, all a_i’s can be determined. In general,

a_k = ∇^kyn

k!h^k .

Using these values,φ(x) becomes φ(x) =y_n+ (x−x_n)∇y_n

h + (x−x_n)(x−xn−1)∇²y_n 2!h² +(x−x_n)(x−xn−1)(x−xn−2)∇³y_n

3!h³ +· · · +(x−xn)(x−xn−1)(x−xn−2)· · ·(x−x1)∇ⁿyn

n!hⁿ. (2.7)

Since the values of xi’s are equispaced, further simplification is possible. Let v be a new variable defined byx=x_n+vh. Note that v is unit less quantity.

Thus,xi=x0+ihandx=xn+vh. Therefore,x−xn−i= (xn+vh)−(x₀+n−ih) = (x_n−x₀) + (v−n−i)h= (v+i)h, i= 0,1, . . . , n.

Using these results, (2.7) reduces to φ(x) =y_n+vh∇y_n

h +vh(v+ 1)h∇²y_n

2!h² +vh(v+ 1)h(v+ 2)h∇³y_n 3!h³ +· · · +vh(v+ 1)h(v+ 2)h· · ·(v+n−1)h∇ⁿyn

n!hⁿ

=y_n+v∇y_n+v(v+ 1)

2! ∇²y_n+v(v+ 1)(v+ 2)

3! ∇³y_n+· · · +v(v+ 1)(v+ 2)· · ·(v+n−1)

n! ∇ⁿy_n. (2.8)

This is well known Newton’s backward or Newton-Gregory backward inter- polation formula.

Note 2.2 The Newton’s backward difference interpolation formula is used to compute the value of f(x) whenx is near to x_n, i.e. whenx is at the end of the table.

Error in Newton’s backward interpolation formula

The error occur in backward difference interpolation formula is given by E(x) = (x−xn)(x−xn−1)· · ·(x−x1)(x−x0)f⁽ⁿ⁺¹⁾(ξ)

(n+ 1)!

=v(v+ 1)(v+ 2)· · ·(v+n)hⁿ⁺¹f⁽ⁿ⁺¹⁾(ξ)

(n+ 1)! , (2.9)

wherev= x−x_n

h andξ lies between min{x₀, x₁, . . . , x_n, x} and max{x₀, x₁, . . . , x_n, x}.

Example 2.2 The following table of values of x and f(x) is given.

x : 0.25 0.30 0.35 0.40 0.45 0.50

f(x) : 2.6754 2.8765 2.9076 3.2876 3.3451 3.7139 Use Newton’s backward interpolation formula to determine the value of f(0.48).

Solution. The backward difference table is

x f(x) ∇f(x) ∇²f(x) ∇³f(x) ∇⁴f(x) 0.25 2.6754

0.30 2.8765 0.2011

0.35 2.9076 0.0311 –0.1700

0.40 3.2876 0.3800 0.3489 0.5189

0.45 3.3451 0.0575 –0.3225 –0.6714 –1.1903 0.50 3.7139 0.3688 0.3113 0.6338 1.3052 In this problem, xn= 0.50, x= 0.48, h= 0.05, v= x−xn

h = 0.48−0.50

0.05 =−0.4.

Then,

f(0.48) =f(x_n) +v∇f(x_n)+v(v+ 1)

2! ∇²f(x_n)+v(v+ 1)(v+ 2)

3! ∇³f(x_n) +v(v+ 1)(v+ 2)(v+ 3)

4! ∇⁴f(xn)+· · ·

= 3.7139−0.4×0.3688 + −0.4(−0.4 + 1)

2 ×0.3113

+−0.4(−0.4 + 1)(−0.4 + 2)

6 ×0.6338

+−0.4(−0.4 + 1)(−0.4 + 2)(−0.4 + 3)

24 ×1.3052

= 3.7139−0.14752−0.037356−0.040563−0.054296

= 3.43416'3.4342.

Thus,f(0.48) = 3.4342.

Example 2.3 The following table gives the value of x and y.

x : 2 3 4 5 6

f(x) : 5 8 12 20 37

Calculate the value of y at x = 5.5 by considering third degree Newton’s backward in- terpolation polynomial. Again, find the same value by considering the fourth degree polynomial.

Solution. To find a third degree polynomial, we consider last four data and the corre- sponding backward difference table is

x y ∇y ∇²y ∇³y

3 8

4 12 4

5 20 8 4

6 37 17 9 5

In this problem, x_n= 6, x= 5.5, h= 1, v= x−x_n

h = 5.5−6

1 =−0.5.

y(5.5) =yn+v∇y_n+v(v+ 1)

2! ∇²yn+v(v+ 1)(v+ 2) 3! ∇³yn

= 37−0.5×17 +−0.5(−0.5 + 1)

2 ×9

+−0.5(−0.5 + 1)(−0.5 + 2)

6 ×5

= 37−8.5−1.125−0.3125

= 27.0625.

Now, we consider fourth degree polynomial to calculatey(5.5). The difference table is shown below. The additional calculations are marked by red colour.

x y ∇y ∇²y ∇³y ∇⁴y 2 5

3 8 3

4 12 4 1

5 20 8 4 3

6 37 17 9 5 2

The value of y(5.5) can be determined by the following formula. Note that there is only one term we have to calculate, other terms are already determined in previous step.

f(0.48) =yn+v∇y_n+v(v+ 1)

2! ∇²yn+v(v+ 1)(v+ 2)

3! ∇³yn+v(v+ 1)(v+ 2)(v+ 3) 4! ∇⁴yn. The value of the last term is

v(v+ 1)(v+ 2)(v+ 3)

4! ∇⁴yn

= −0.5(−0.5 + 1)(−0.5 + 2)(−0.5 + 3)

4! ×2 =−0.078125.

Thus, the value ofy(5.5) is 27.0625−0.078125 = 26.984375.

Example 2.4 The upward velocity of a rocket is given below:

t(sec) : 0 10 15 20 25 30

v(t) (m/sec) : 0 126.75 350.50 510.80 650.40 920.25

Determine the value of the velocity att= 26sec using Newton’s backward and forward formulae and compare the results.

Solution. The velocity at t = 0 is zero, and hence it does not give any information.

Therefore, we discard this data.

Using Newton’s backward formula The backward difference table is

t v(t) ∇v ∇²v ∇³v ∇⁴v

10 126.75

15 350.50 223.75

20 510.80 160.30 –63.45

25 650.40 139.60 –20.70 42.45

30 920.25 269.85 130.25 150.95 108.50 Here,t_n= 30, t= 26, h= 5, v= t−t_n

h = 26−30

5 =−0.8.

By Newton’s backward formula

v(26) =y_n+v∇y_n+v(v+ 1)

2! ∇²y_n+v(v+ 1)(v+ 2) 3! ∇³y_n +v(v+ 1)(v+ 2)(v+ 3)

4! ∇⁴yn

= 920.25−0.8×269.85 +−0.8(−0.8 + 1)

2 ×(130.25)

+−0.8(−0.8 + 1)(−0.8 + 2)

6 ×150.95

+−0.8(−0.8 + 1)(−0.8 + 2)(−0.8 + 3)

24 ×108.50

= 687.21.

Thus the velocity of the rocket att= 16 sec is 687.21 m/s.

By Newton’s forward formula

Since the Newton’s forward interpolation formula is used when the given value is at the beginning of the table. For this purpose the table is written in reverse order as

t(sec) : 30 25 20 15 10 0 v(t) (m/s) : 920.25 640.40 510.80 350.50 126.75 0 Here also we discard the last data as it has no importance.

The forward difference table is

t v(t) ∇v ∇²v ∇³v ∇⁴v

30 920.25

–269.85

25 650.40 130.25

–139.60 –150.95

20 510.80 –20.70 108.50

–160.30 –42.45

15 350.50 –63.45

–223.75 10 126.75

Here t₀= 30, t= 26, h=−5, u= t−t₀

h = 26−30

−5 = 0.8.

Then

v(26) =y₀+u∆v₀+u(u−1)

2! ∆²v₀+u(u−1)(u−2) 3! ∆³v₀ +u(u−1)(u−2)(u−3)

4! ∆⁴v0

= 920.25 + 0.8×(−269.85) + 0.8(0.8−1)

2 ×(130.25) +0.8(0.8−1)(0.8−2)

6 ×(−150.95) +0.8(0.8−1)(0.8−2)(0.8−3)

24 ×108.50

= 687.21.

Thus, the value of v(16) obtained by Newton’s forward formula is 687.21 which is same as the value obtained by Newton’s backward formula.

From the above example one can conclude that if a problem is solved by Newton’s forward formula, then it can be solved by Newton’s backward formula also.

In the following section, we discuss another interpolation formula called Newton’s divided difference interpolation formula.

2.3 Divided differences and their properties

Newton’s forward and backward interpolation formulae are deduced from forward and backward difference operators. In this section, another type of difference called divided difference is defined and based on this difference, Newton’s divided interpolation formula is derived.

Lety =f(x) be a function whose explicit form is unknown, but it is known at some values of x, say at x0, x1, . . . , xn. Suppose (xi, yi), where yi = f(xi), i = 0,1, . . . , n are known at n+ 1 points x₀, x₁, . . . , x_n. Like Lagrange’s interpolation, the points x₀, x₁, . . . , x_n are not necessarily equispaced.

The divided differences of different orders are defined below:

Zeroth order divided difference

The zeroth order divided difference for the argument x₀ is denoted by f[x₀] and is defined by

f[x₀] =f(x₀).

First order divided difference

The first order divided difference for two arguments x₀ and x₁ is denoted by f[x₀, x₁].

This is defined below:

f[x₀, x₁] = f(x0)−f(x1) x₀−x₁ .

In general, for the arguments xi and xj, the first order divided difference is f[x_i, x_j] = f(x_i)−f(x_j)

xi−xj

. Second order divided difference

For the arguments x₀, x₁ and x₂ the second order divided difference is denoted by f[x0, x1, x2] and is defined below:

f[x0, x1, x2] = f[x0, x1]−f[x1, x2] x0−x2

.

In general, f[x_i, x_j, x_k] = f[x_i, x_j]−f[x_j, x_k] xi−xk

.

nth order divided differences

For then+1 argumentsx0, x1, . . . , xnthe divided difference is denoted byf[x0, x1, . . . , xn], which is defined as

f[x0, x1, . . . , xn] = f[x₀, x₁, . . . , xn−1]−f[x₁, x₂, . . . , x_n] x0−xn

.

From the definition of first order divided difference it is seen that if the two arguments are equal, then it does not give any definite value. But, there is a meaning, which is discussed below.

2.3.1 Divided differences for equal arguments or divided differences for confluent argu- ments

In the following, it is shown by limiting process, that there is a definite value of divided difference when the arguments are equal. The divided differences for equal arguments is known asconfluent divided differences.

f[x0, x0] = lim

ε→0f[x0, x0+ε] = lim

ε→0

f(x0+ε)−f(x0)

ε =f⁰(x0),

provided f(x) is differentiable. Thus, f[x₀, x₀] is nothing but the first order derivative of f(x) at x=x0.

For three arguments, the confluent divided difference is determined as follows:

f[x₀, x₀, x₀] = lim

ε→0f[x₀+ε, x₀, x₀] = lim

ε→0

f[x₀+ε, x₀]−f[x₀, x₀] ε

= lim

ε→0

f(x0+ε)−f(x₀)

ε −f⁰(x₀) ε

= lim

ε→0

f(x0+ε)−f(x0)−εf⁰(x0) ε²

0 0 form

= lim

ε→0

f⁰(x0+ε)−f⁰(x0)

2ε (by L’Hospital rule)

= f⁰⁰(x₀) 2! . We obtained second order derivative.

Similarly, the confluent divided difference of four arguments isf[x₀, x₀, x₀, x₀] = f⁰⁰⁰(x₀) 3! . In general, for (k+ 1) arguments the confluent divided difference is given by

f[

(k+1) times

z }| {

x0, x0, . . . , x0] = f^k(x0)

k! . (2.10)

For this relation we can write

d^k

dx^kf(x₀) =k!f[

(k+1) times

z }| {

x₀, x₀, . . . , x₀]. (2.11) Some interesting properties of divided difference are presented below.

2.3.2 Properties of divided differences

(i) Divided difference of a constant is zero

Letf(x) =c, wherec is an arbitrary constant.

Then f[x₀, x₁] = f(x₀)−f(x₁)

x₀−x₁ = c−c x₀−x₁ = 0.

(ii) Divided difference of cf(x), c is constant, is the divided difference of f(x) multi- plied by c, i.e. if g(x) =cf(x), then g[x0, x1] =cf[x0, x]

Letg(x) =cf(x).

Therefore,

g[x₀, x₁] = g(x₀)−g(x₁)

x₀−x₁ = cf(x₀)−cf(x₁)

x₀−x₁ =cf(x₀)−f(x₁)

x₀−x₁ =cf[x₀, x₁].

(iii) Divided difference is linear Letf(x) =ap(x) +bq(x).

Now,

f[x₀, x₁] =f(x₀)−f(x₁)

x₀−x₁ = ap(x₀) +bq(x₀)−ap(x₁)−bq(x₁) x₀−x₁

=ap(x₀)−p(x₁)

x₀−x₁ +bq(x₀)−q(x₁) x₀−x₁

=ap[x₀, x₁] +bq[x₀, x₁].

This shows that divided difference is a linear operator.

(iv) Divided differences are symmetric The first order divided difference is

f[x0, x1] = f(x0)−f(x1) x0−x1

= f(x1)−f(x0) x1−x0

=f[x1, x0].

So, it is symmetric. This expression can be written as Also, f[x₀, x₁] = 1

x₀−x₁f(x₀) + 1

x₁−x₀f(x₁).

The second order difference can also be expressed to the above form. For three arguments

f[x0, x1, x2] = f[x0, x1]−f[x1, x2] x₀−x₂

= 1

x₀−x₂

hn 1

x₀−x₁f(x₀) + 1

x₁−x₀f(x₁)o

−n 1 x1−x2

f(x₁) + 1 x2−x1

f(x₂)oi

= 1

(x₀−x₂)(x₀−x₁)f(x0)

+ 1

(x1−x0)(x1−x2)f(x1) + 1

(x2−x0)(x2−x1)f(x2).

In this manner, the divided differences for (n+ 1) arguments is written as f[x0, x1, . . . , xn] = 1

(x₀−x₁)(x₀−x₂)· · ·(x₀−x_n)f(x0)

+ 1

(x1−x0)(x1−x2)· · ·(x1−xn)f(x1) +· · ·

+ 1

(xn−x0)(xn−x1)· · ·(xn−xn−1)f(xn)

=

n

X

i=0

f(x_i)

(x_i−x₀)· · ·(x_i−xi−1)(x_i−x_i+1)· · ·(x_i−x_n). (2.12) Thus, it is easy to conclude that the divided differences are symmetric.

(v) For equispaced arguments, the divided differences can be expressed in terms of forward differences, i.e.

f[x₀, x₁, . . . , x_n] = 1

hⁿ.n!∆ⁿy₀. (2.13)

Since the arguments are equispaced, therefore x_i =x₀+ih, i= 0,1, . . . , n.

Therefore, the first order divided difference is given by f[x₀, x₁] = f(x₁)−f(x₀)

x₁−x₀ = y₁−y₀

x₁−x₀ = ∆y₀

h . (2.14)

Again, the second order difference is

f[x0, x1, x2] =f[x0, x1]−f[x1, x2] x₀−x₂ = 1

−2h ∆y0

h − ∆y1

h

= ∆y₁−∆y₀

2h² = ∆²y₀

2!h² . (2.15)

Now, we use mathematical induction to prove the result. The result (2.13) is true forn= 1,2. Suppose the result be true for

n=k. Therefore, f[x0, x1, . . . , x_k] = ∆^ky0

k!h^k. Now,

f[x₀, x₁, . . . , x_k, x_k+1] = f[x₀, x₁, . . . , x_k]−f[x₁, x₂, . . . , x_k+1] x0−xk+1

= 1

−(x_k+1−x₀) h∆^ky0

k!h^k −∆^ky1

k!h^k i

= 1

(k+ 1)k!h^k+1[∆^ky1−∆^ky0]

= ∆^k+1y₀ (k+ 1)!h^k+1. Hence, by mathematical induction we conclude that

f[x₀, x₁, . . . , x_n] = 1

hⁿ.n!∆ⁿy₀. (2.16)

(vi) The nth order divided difference of a polynomial of degree n is constant

Letf(x) =a0xⁿ+a1xⁿ⁻¹+a2xⁿ⁻²+· · ·+an−1x+an,(a06= 0) be a polynomial of degree n.

Then

f[x, x0] = f(x)−f(x0) x−x₀

=a₀xⁿ−xⁿ₀

x−x₀ +a₁xⁿ⁻¹−xⁿ⁻¹₀

x−x₀ +a₂xⁿ⁻²−xⁿ⁻²₀

x−x₀ +· · ·+an−1

x−x₀ x−x₀

=a₀[xⁿ⁻¹+xⁿ⁻²x₀+xⁿ⁻³x²₀+· · ·+xxⁿ⁻²₀ +xⁿ⁻¹₀ ]

+a₁[xⁿ⁻²+xⁿ⁻³x₀+xⁿ⁻⁴x²₀+· · ·+xxⁿ⁻³₀ +xⁿ⁻²₀ ] +· · ·+an−1

=a₀xⁿ⁻¹+ (a₀x₀+a₁)xⁿ⁻²+ (a₀x²₀+a₁x₀+a₂)xⁿ⁻³+· · ·+an−1

=b₀xⁿ⁻¹+b₁xⁿ⁻²+b₂xⁿ⁻³+· · ·+bn−1,

whereb₀ =a₀, b₁ =a₀x₀+a₁, b₂=a₀x²₀+a₁x₀+a₂, . . . , bn−1=an−1.

Thus, the first order divided difference of a polynomial of degreenis a polynomial of degree n−1.

In this manner, one can prove that thenth order divided difference of a polynomial is constant.

2.4 Newton’s fundamental interpolation formula

Based on divided difference, one can construct another type of interpolation formula called Newton’s fundamental interpolation formula. From this formula, Newton’s for- ward and backward difference and also Lagrange’s interpolation formulae can be derived.

So, in this context, this formula is highly importance.

Let the functiony=f(x) be known at the argumentsx₀, x₁, . . . , x_nand lety_i=f(x_i), i= 0,1, . . . , n. The points xi,i= 0,1, . . . , nare not necessary equispaced.

The first order divided difference for the argumentsx₀, xis f[x0, x] = f(x)−f(x0)

x−x₀ . This can be written asf(x) =f(x0) + (x−x0)f[x0, x].

For the argumentsx₀, x₁ and x, the divided difference is f[x0, x1, x] = f[x0, x1]−f[x0, x]

x₁−x

i.e., f[x0, x] =f[x0, x1] + (x−x1)f[x0, x1, x]

i.e., f(x)−f(x₀)

x−x₀ =f[x₀, x₁] + (x−x₁)f[x₀, x₁, x]

Thus, f(x) =f(x₀) + (x−x₀)f[x₀, x₁] + (x−x₀)(x−x₁)f[x₀, x₁, x].

Similarly, for the arguments x0, x1, x2, x,

f(x) =f(x₀) + (x−x₀)f[x₀, x₁] + (x−x₀)(x−x₁)f[x₀, x₁, x₂] + (x−x₀)(x−x₁)(x−x₂)f[x₀, x₁, x₂, x]

In this way, for the arguments x₀, x₁, x₂, . . . , x_n and x, we get

f(x) =f(x0) + (x−x0)f[x0, x1] + (x−x0)(x−x1)f[x0, x1, x2] + (x−x0)(x−x1)(x−x2)f[x0, x1, x2, x3] +· · ·

+ (x−x0)(x−x1)· · ·(x−xn)f[x0, x1, x2, . . . , xn, x]. (2.17) This formula is known as Newton’s fundamentalor Newton’s generalinterpo- lation formula. The last term (x−x0)(x−x1)· · ·(x−xn)f[x0, x1, x2, . . . , xn, x] is the error term.

The divided differences of different order are shown in Table 2.1.

x ... f(x) First Second Third

x0 ... f(x0)

x0−x1 ... f[x0, x1]

x₀−x₂ x₁ ... f(x₁) f[x₀, x₁, x₂]

x0−x3 x1−x2 ... f[x1, x2] f[x0, x1, x2, x3] x1−x3 x2 ... f(x2) f[x1, x2, x3]

x₂−x₃ ... f[x₂, x₃] x₃ ... f(x₃)

Table 2.1: Divided difference table.

Error term

The error term is

E(x) = (x−x₀)(x−x₁)· · ·(x−x_n)f[x₀, x₁, . . . , x_n, x]

= (x−x0)(x−x1)· · ·(x−xn)fⁿ⁺¹(ξ)

(n+ 1)!,[using (2.10)] (2.18)

where min{x₀, x1, . . . , xn, x}< ξ <max{x₀, x1, . . . , xn, x}.

It is very interesting that the Newton’s fundamental interpolation formula gives both the interpolating polynomial as well as error term simultaneously.

Example 2.5 Using Newton’s divided difference formula, find the value off(1.2)from the following table:

x : 0 2 5 7 11

f(x) : 2.153 3.875 4.279 4.891 5.256 Solution. The divided difference table is

x f(x) 1st 2nd 3rd 4th

0 2.153

–2 0.8610

–5 2 3.875 –0.1453

–7 –3 0.1346 0.0257

–11 –5 5 4.279 0.0343 –0.0030

–9 –2 0.3060 –0.0078

–6 7 4.891 –0.0358

–4 0.0912

11 5.256

Here x= 1.2, x0= 0, x1 = 2, x2 = 5, x3= 7, x4 = 11, f[x0] = 2.153, f[x0, x1] = 0.8610, f[x0, x1, x2] =−0.1453, f[x₀, x₁, x₂, x₃] = 0.0257, f[x₀, x₁, x₂, x₃, x₄] =−0.0030.

The Newton’s divided difference formula is

f(1.2) =f[x₀] + (x−x₀)f[x₀, x₁] + (x−x₀)(x−x₁)f[x₀, x₁, x₂] +(x−x₀)(x−x₁)(x−x₂)f[x₀, x₁, x₂, x₃]

+(x−x0)(x−x1)(x−x2)(x−x3)f[x0, x1, x2, x3, x4]

= 2.153 + 1.0332 + 0.1399 + 0.0938 + 0.0635

= 3.4834.

Hence,f(1.2) = 3.4834.

2.5 Deductions of other interpolation formulae from Newton’s divided difference formula

Theoretically, Newton’s divided difference formula is very powerful because from this formula several interpolation formulae can be derived.

2.6 Newton’s forward difference interpolation formula

Let the arguments be equispaced, i.e. x_i = x₀ +ih, i = 0,1, . . . , n. Then the kth order divided difference is (from (2.16))

f[x0, x1, . . . , xk] = ∆^kf(x0) k!h^k , fork= 1,2, . . . , n.

Using this assumption the formula (2.17) reduces to

φ(x) =f(x0) + (x−x0)∆f(x0)

1!h + (x−x0)(x−x1)∆²f(x0) 2!h² + (x−x0)(x−x1)(x−x2)∆³f(x0)

3!h³ +· · · + (x−x0)(x−x1)· · ·(x−xn−1)∆ⁿf(x0)

n!hⁿ + (x−x0)(x−x1)· · ·(x−xn) ∆ⁿ⁺¹f(ξ) (n+ 1)!hⁿ⁺¹. The last term is the error term.

To convert it to usual form of Newton’s forward difference formula, let u= x−x₀

h ,

i.e. x=x0+uh. Sincexi=x0+ih,i= 0,1,2, . . . , n.

Therefore, x−x_i= (u−i)h.

Then

φ(x) =f(x₀) +u∆f(x₀) +u(u−1)

2! ∆²f(x₀) +· · · + u(u−1)(u−2)· · ·(u−n+ 1)

n! ∆ⁿf(x0)

+u(u−1)(u−2)· · ·(u−n)fⁿ⁺¹(ξ)

(n+ 1)!. (2.19)

The value of ξ lies between min{x, x₀, x₁, . . . , x_n} and max{x, x₀, x₁, . . . , x_n}.

This is the well known Newton’s forward difference interpolation formula including error term.

2.7 Newton’s backward difference interpolation formula

In this case also, we assumed that x_i =x₀+ih,i= 0,1, . . . , n.

Let

φ(x) =f(x_n) + (x−x_n)f[x_n, xn−1] + (x−x_n)(x−xn−1)f[x_n, xn−1, xn−2] +· · ·+ (x−x_n)(x−xn−1)· · ·(x−x₁)f[x_n, xn−1, . . . , x₁, x₀]

+E(x), (2.20)

where

E(x) = (x−xn)(x−xn−1)· · ·(x−x1)(x−x0)f[x, xn, xn−1, . . . , x1, x0].

From the arguments x_n, xn−1, . . . , xn−k, the relation (2.16) becomes f[x_n, xn−1, . . . , x_n−k] = ∆^kf(xn−k)

k!h^k . Again,

∆^kf(xn−k)

k!h^k = ∇^kf(x_n) k!h^k . Thus,

f[x_n, xn−1, . . . , xn−k] = ∇^kf(x_n) k!h^k . With this notation (2.20) reduces to

φ(x) =f(xn) + (x−xn)∇f(xn)

1!h + (x−xn)(x−xn−1)∇²f(xn) 2!h² +· · · + (x−x_n)(x−xn−1)· · ·(x−x₁)(x−x₀)∇ⁿf(x_n)

n!hⁿ +E(x), where

E(x) = (x−xn)(x−xn−1)· · ·(x−x1)(x−x0) ∇ⁿ⁺¹f(ξ) (n+ 1)!hⁿ⁺¹, where min{x, x₀, x₁, . . . , x_n}< ξ <max{x, x₀, x₁, . . . , x_n}.

This is the Newton’s backward difference interpolation formula with error termE(x).

2.8 Lagrange’s interpolation formula

Let x₀, x₁, . . . , x_n be the (n+ 1) arguments, not necessarily equispaced. For these arguments the norder divided difference is

f[x0, x1, . . . , xn] =

n

X

i=0

f(xi)

(xi−x0)(xi−x1)· · ·(xi−xi−1)(xi−xi+1)· · ·(xi−xn). Similarly, for the (n+ 2) argumentsx, x₀, . . . , x_n, the (n+ 1) order divided difference is

f[x, x₀, x₁, . . . , x_n] = f(x)

(x−x0)(x−x1)· · ·(x−xn) +

n

X

i=0

f(xi)

(x_i−x₀)· · ·(x_i−xi−1)(x_i−x_i+1)· · ·(x_i−x_n)

= f(x) w(x) +

n

X

i=0

f(x_i) (xi−x)w⁰(xi), where w(x) = (x−x0)(x−x1)· · ·(x−xn).

Thus,

f(x) =

n

X

i=0

w(x)f(xi)

(x−xi)w⁰(xi) +w(x)f[x, x0, x1, . . . , xn]

=

n

X

i=0

L_i(x)f(x_i) +w(x)fⁿ⁺¹(ξ)

(n+ 1)! [using (2.16)]

where min{x₀, x1, . . . , xn, x}< ξ <max{x₀, x1, . . . , xn, x} and Li(x) = w(x)

(x−xi)w⁰(xi),theith Lagrange’s function.

This is the Lagrange’s interpolation formula for unequal spacing with error term.

Note that both Lagrange’s and Newton’s divided difference interpolation formulae are applicable for unequal spaced arguments. Also, they are equivalent proved in the next section.

2.9 Equivalence of Lagrange’s and Newton’s divided difference formulae

Let (x_i, y_i), i = 0,1, . . . , n be the given set of points. The arguments x_i’s are not necessarily equispaced.

The Lagrange’s interpolation polynomial for these points is

φ(x) =

n

X

i=0

Li(x)yi, (2.21)

whereLi(x) = (x−x₀)(x−x₁)· · ·(x−xi−1)(x−x_i+1)· · ·(x−x_n)

(xi−x0)(xi−x1)· · ·(xi−xi−1)(xi−xi+1)· · ·(xi−xn). (2.22) Again the Newton’s divided difference interpolation formula for these points is

φ(x) =f(x₀) + (x−x₀)f[x₀, x₁] + (x−x₀)(x−x₁)f[x₀, x₁, x₂] +· · · +(x−x₀)(x−x₁)· · ·(x−xn−1)f[x₀, x₁,· · ·, x_n]

=f(x0) + (x−x0)

f(x0)

x₀−x₁ + f(x1) x₁−x₀

+(x−x0)(x−x1)× f(x₀)

(x0−x1)(x0−x2)+ f(x₁)

(x1−x0)(x1−x2) + f(x₂) (x2−x0)(x2−x1)

+· · ·+ (x−x₀)(x−x₁)· · ·(x−xn−1)× f(x0)

(x₀−x₁)· · ·(x₀−x_n)+· · ·+ f(xn)

(x_n−x₀)· · ·(x_n−xn−1)

. (2.23)

The coefficient of f(x₀) in the above expression is 1 + x−x₀

x0−x1

+ (x−x₀)(x−x₁)

(x0−x1)(x0−x2) +· · ·+ (x−x₀)(x−x₁)· · ·(x−xn−1) (x0−x1)(x0−x2)· · ·(x0−xn)

= (x−x₁) (x0−x1)

1 + x−x₀ x0−x2

+ (x−x₀)(x−x₂) (x0−x2)(x0−x3) + +· · ·+ (x−x0)(x−x2)· · ·(x−xn−1)

(x0−x2)(x0−x3)· · ·(x0−xn)

= (x−x₁) (x₀−x₁)

x−x₂

x₀−x₂ + (x−x₀)(x−x₂) (x₀−x₂)(x₀−x₃) + +· · ·+ (x−x₀)(x−x₂)· · ·(x−xn−1)

(x0−x2)(x0−x3)· · ·(x0−xn)

= (x−x1)(x−x2) (x0−x1)(x0−x2)

1 + x−x0

x0−x3

+· · ·+ (x−x0)(x−x3)· · ·(x−xn−1) (x0−x3)(x0−x4)· · ·(x0−xn)

= (x−x1)(x−x2) (x₀−x₁)(x₀−x₂)

x−x3

x₀−x₂ +· · ·+ (x−x0)(x−x3)· · ·(x−xn−1) (x₀−x₃)(x₀−x₄)· · ·(x₀−x_n)

=· · · ·

= (x−x1)(x−x2)· · ·(x−xn−1) (x0−x1)(x0−x2)· · ·(x0−xn−1)

1 + x−x0

x0−xn

= (x−x1)(x−x2)· · ·(x−xn−1)(x−xn) (x0−x1)(x0−x2)· · ·(x0−xn−1)(x0−xn)

=L₀(x).

By similarly process, it can be shown that the coefficient of f(xi) is Li(x) for i = 2,3, . . . , n.

Hence, (2.23) becomes

φ(x) =L0(x)f(x0) +L1(x)f(x1) +· · ·+Ln(x)f(xn) =

n

X

i=1

Li(x)f(xi) =

n

X

i=1

Li(x)yi. Thus the Lagrange’s and the Newton’s divided difference interpolation formulae are equivalent.

Example 2.6 For the following table of data, find the interpolating polynomial using (i) Lagrange’s formula and (ii) Newton’s divided difference formula.

x : 0 3 8 10

y : 12 21 1 0 Also, compare the results.

Solution. (i) The Lagrange’s interpolation polynomial is φ(x) = (x−3)(x−8)(x−10)

(0−3)(0−8)(0−10) ×12 +(x−0)(x−8)(x−10) (3−0)(3−8)(3−10) ×8 +(x−0)(x−3)(x−10)

(8−0)(8−3)(8−10) ×1 + (x−0)(x−3)(x−8) (10−0)(10−3)(10−8)×0

= x³−21x²+ 134x−240

−240 ×12 +x³−18x²+ 80x

105 ×21

+x³−13x²+ 30x

−80 ×1 + 0

= 1

80[11x³−191x²+ 714x+ 960].

(ii) The divided difference table is

x f(x) 1st div. 2nd div. 3rd div.

diff. diff. diff.

0 12

3 21 3

8 1 –4 –7/8

10 0 –1/2 1/2 11/80

Newton’s divided difference polynomial is

φ(x) = 12 + (x−0)×3 + (x−0)(x−3)×(−7 8) +(x−0)(x−3)(x−8)× 11

80

= 12 + 3x−7

8(x²−3x) +11

80(x³−11x²+ 24x)

= 1

80[11x³−191x²+ 714x+ 960].

See that both the polynomials are same. It is expected because interpolating poly- nomial is unique.

Note 2.3 From the above calculations it is obvious that the Newton’s divided difference interpolation formula needs less computation than Lagrange’s interpolation formula. So, it is suggested to use Newton’s divided difference interpolation formula when the argu- ments are unequal spaced.