Interpolation and polynomial approximation

Theorem: (Weierstrass approximation theorem)

If f(x) is defined and continuous on [a, b] , then there exists a polynomial p(x) defined
on [a, b], with the property that

f (x) −P(x)   x[a,b],  0

One of the most useful and well-known classes of functions mapping the set of R into R is the class of algebraic polynomials

p(x) = a0 +ax
1 +a2x +..... +anx
2 n
 Example: According the following table, Find f(4) by using quadratic and cubic interpolation respectively
X 1 3 5 6

F(x) 0 4 12 19

let p(x) = a0 +a1x +a2x2

Then P(1) = f (1) = 0 = a0 +a1 +a2
P(3) = f (3) = 4 = a0 +3a1 +9a2
P(5) = f (5) =12 = a0 +5a1 +25a2

Using Gauss elimination we have a0 =−0.5, a1 =0, a2 =0.5

Hence P(x) =−0.5+0.5x  f (4) = P(4) =7.5
2
Secondly, let p(x) = a0 +ax
1 +a2x2
+a3x3

P(1) = f (1) =0 = a0 +a1 +a2 +a3

P(3) = f (3) = 4 = a0 +3a1 +9a2 +27a3
Then

P(5) = f (5) =12 = a0 +5a1 +25a2 +125a3

P(6) = f (6) =19 = a0 +6a1 +36a2 +216a3
Using Gauss elimination we have a0 =−2, a1 = 2.3, 2
a2 =− , a3 =0.1
5
Hence P(x) =−2+2.3x−0.4x2 +0.1x3
 Lagrange interpolating polynomial

Theorem: If x0, x1,....xn are (n+1) distinct numbers and f(x) is the function whose values are given at these

numbers, then there exists a unique polynomial P(x) of degree at most n with the property that f (xk ) = P(xk ),  k =0,1,...,n
This polynomial is given by P(x) = L0(x) f (x0) +L1(x) f (x1) +.... +Ln(x) f (xn)
=Lk (x) f (xk )
n

k=0
where

Lk (x) = (x − x0 )( x − x1)....(x − xk−1)(x − xk+1)...(x − xn )

(xk −x0)(xk −x1)....(xk −xk−1)(xk −xk+1)...(xk −xn)
=
n
(x − xi )
ik (xk − xi )
i=0
Example: Using the following table and Lagrange polynomial to find f(3)
x 2 2.5 4

F(x) 0.5 0.4 0.25

L ( x) = ( x − x1)(x − x2 ) = (x −2.5)(x −4)  L (3) =−0.5

Solution: 0
(x0 −x1)(x0 −x2) (2−2.5)(2−4) 0

L1(x) = (x − x0 )( x − x2 ) = (x − 2)(x − 4)  L1(3) = 4

(x1 −x0)(x1 −x2) (2.5−2)(2.5−4) 3
L2(x) = ( x − x0 )(x − x1) = (x − 2)(x − 2.5)  L2(3) =0.1667
(x2 −x0)(x2 −x1) (4−2)(4−2.5)
P(x) = L0(x) f (x0) +L1(x) f (x1) +L2(x) f (x2)
7
=−0.5(0.5) + (0.4) +0.1667(0.25) = 0.325
6
Exercises: Using Lagrange interpolating polynomials to approximate the following

1] Find f(2.5) x 2 2.2 2.4 2.6 2.8

F(x) 0.52 0.63 0.85 1.1 1.3

2] find cosh (1.1) x 1 1.2 1.3 1.4 1.5

Cosh(x) 1.543 1.811 1.971 2.151 2.352

x 1.7 1.9 2 2.1 2.3

3] find 𝑒 2.2 𝑒𝑥 5.474 6.686 7.389 8.166 9.974
Divided Differences Method

Methods for determining the explicit representation of an interpolating polynomial from

tabulated data are known as divided-differences method. The divided-differences of f(x)
with respect to 𝑥0 , 𝑥1 ,…., 𝑥𝑛 are divided by showing P(x) as follows

P(x) = a0 +a1(x−x0) +a2(x−x0)(x−x1) +...+an(x−x0)....(x−xn−1)

For appropriate constants 𝑎0 , 𝑎,…., 𝑎𝑛
At x=𝑥0 in P(x), we have a0 = P(x0) = f (x0) = f [x0]
Similarly, at x=𝑥1 in P(x), we have f (x1) = P(x1) = a0 +a1(x1 − x0)
f (x1) = f (x0) +a1(x1 − x0)
a1 = f (x1) − f (x0 ) = f [x0, x1]
(x1 − x0)
Similarly, at x=𝑥2 in P(x), we have

f (x2) = P(x2) = a0 +a1(x2 − x0) +a2(x2 − x0)(x2 −x1)

f (x2) = f (x0) + f [x0, x1](x2 −x0) +a2(x2 −x0)(x2 −x1)
f (x2) − f (x0) − f [x0, x1](x2 −x0) = a2(x2 −x0)(x2 −x1)
a2 = [ f ( x 2 ) − f ( x 1) + f ( x 1) − f ( x 0 )] − f [ x0 , x1](x2 − x0 )
(x2 − x0)(x2 − x1)
a2 = f [x 1 , x 2 ] + f [ x0 , x1 ]( x 1 − x 0 ) − f [x0 , x1]( x 2 − x0 )
(x2 − x0) (x2 − x0)(x2 − x1)
a2 = f [ x1 , x 2 ] + f [ x0 , x1 ]( x 1 − x 2 )
(x2 − x0) (x2 − x0)(x2 − x1)
a2 = f [ x 1, x 2 ] − f [x 0 , x 1] = f [x0, x1, x2]
(x2 − x0)
 In general Newton’s interpolating divided difference formula is the following polynomial

P(x) = f [x0]+ f [x0, x1](x −x0) + f [x0, x1, x2] (x −x0)(x −x1) +... + f [x0, x1, x2,..., xn] (x −x0)....(x −xn−1)
(1)
𝒙𝟎 F(𝒙𝟎 )

F[𝒙𝟎 , 𝒙𝟏 ]

𝒙𝟏 F(𝒙𝟏 ) F[𝒙𝟎 , 𝒙𝟏 , 𝒙𝟐 ]

F[𝒙𝟏 , 𝒙𝟐 ] F[𝒙𝟎 , 𝒙𝟏 , 𝒙𝟐 , , 𝒙𝟑 ]

𝒙𝟐 F(𝒙𝟐 ) F[𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 ]

F[𝒙𝟐 , 𝒙𝟑 ]

𝒙𝟑 F(𝒙𝟑 )
Example: Using the following table to find f(1.5) by using Newton’s divided difference formula

x 1 1.3 1.7 1.9

F(x) 2.56 3.42 5.76 6.88
Solution: 1 2.56
43
15
1.3 3.42 179
42

5.85 −655
126

1.7 5.76 −5
12

5.6

1.9 6.88
 43 179 655
P(x) = 2.56+ (x−1) + (x−1)(x−1.3) − (x−1)(x−1.3)(x−1.7)
15 42 126
f (1.5) = P(1.5) = 4.52349
Differences:
Forward-Differences operator ∆
f (xn ) = f (xn+1) − f (xn)
f (x0) = f (x1) − f (x0)
2 f (x0) =f (x1) −f (x0)
3 f (x0) =2 f (x1) −2 f (x0)
Newton’s forward divided difference
When 𝑥0 , 𝑥1 , … . . , 𝑥𝑛 are arranged consecutively with equal spacing, that is
x1 = x0 +h, x2 = x1 +h ,......, xn+1 = xn +h
 And so on we have
n f (x0) =n−1 f (x1) −n−1 f (x0)
f [x0, x1] = f (x1 ) − f (x 0 ) 1
= f (x0)
Then x1 −x0 h
f [x0, x1, x2] = f [ x1, x2 ] − f [x0, x1] 1 1 1 1
= [ f (x1) − f (x0)] = 2 2 f (x0)
x2 −x0 2h h h 2h
f [x0, x1, x2, x3] = 1
3  f (x0)
3
Similarly we can prove
3!h
f [x0, x1, x2, x3,..., xn] = 1 n
f (x0)
n
n!h
Substituting from above equations in the following Newton’s interpolating divided
difference formula
P(x) = f [x0]+ f [x0, x1](x−x0) + f [x0, x1, x2](x−x0)(x−x1) +...+ f [x0, x1, x2,..., xn](x−x0)....(x−xn−1)
Then we have
P(x) = f [x0]+ 1  f (x0)(x−x0) + 1 2 2 f (x0)(x−x0)(x−x1) +...+ 1 n n f (x0)(x−x0)....(x−xn−1) (2)
h 2!h n!h
Assume 𝑥 = 𝑥0 + s h then 𝑥 − 𝑥0 = s h. Also we can prove that
x − x1 = x0 +sh− x1 = x0 − x1 +sh =−h+sh = h(s −1)
x − x2 = x0 +sh− x2 = x0 − x2 +sh =−2h+sh = h(s −2)
x − xn−1 = x0 +sh− xn−1 = x0 − xn−1 +sh =−(n−1)h+sh = h(s −(n−1))
Substituting in (2) we have
P(x) = f [x0]+ 1  f (x0)(sh) + 1 2 2 f (x0) s(s −1)h2 +...+ 1 n n f (x0) s(s −1)....(s −(n−1))hn
h 2!h n!h
Hence we have the following polynomial which is known Newton’s forward divided difference

1 1
P(x) = f (x0) + f (x0)s +  f (x0)s(s −1) +...+ n f (x0) s(s −1)....(s −(n−1)) (3)
2
2! n!
f(𝒙𝟎 )
∆ f(𝒙𝟎 )
f(𝒙𝟏 ) ∆2 f(𝒙𝟎 )
∆ f(𝒙𝟏 ) ∆3 f(𝒙𝟎 )

f(𝒙𝟐 ) ∆2 f(𝒙𝟏 ) ∆4 f(𝒙𝟎 )

∆ f(𝒙𝟐 ) ∆3 f(𝒙𝟏 )

f(𝒙𝟑 ) ∆2 f(𝒙𝟐 )
∆ f(𝒙𝟑 )

f(𝒙𝟒 )
 Example I: Using Newton’s forward divided difference interpolation to find f(1.5) according to the following
table
x 1 3 5 7 9
F(x) 4 5 8 11 16

Solution: since h=2, x=1.5, 𝑥0 =1 , x= 𝑥0 +s h, then 1.5=1+s(2) , hence s=0.25

4
1
5 2
3 -2
8 0 4
3 2
11 2
5
16
 Since

P(x) = f (x0) + f (x0)s + 1 2 f (x0) s(s −1) + 1 3 f (x0) s(s −1)(s −2) + 1 4 f (x0) s(s −1)(s −2)(s −3)
2! 3! 4!

Then
1 1 1
P(1.5) = 4+(1)(0.25) + (2)(0.25)(0.25−1) + (−2)(0.25)(0.25−1)(0.25−2) + (4)(0.25)(0.25−1)(0.25−2)(0.25−3)
2! 3! 4!
backward-Differences operator ∇

f (xn) = f (xn) − f (xn−1)

2 f (xn) =f (xn) −f (xn−1)

Newton’s backward divided difference

If the interpolating nodes are reordered as 𝑥𝑛 , 𝑥𝑛−1 , … . . , 𝑥0 then

Newton’s interpolating divided difference formula (1) can be written as follows

P(x) = f [xn]+ f [xn−1, xn](x−xn) + f [xn, xn−1, xn−2](x−xn)(x−xn−1) +...+ f [x0, x1,..., xn](x−xn)....(x−x1) (4)
Similarly as forward difference we can say

f [xn−1, xn] = f (xn) − f (xn−1) = 1f (xn)

xn −xn−1 h
f [xn−2, xn−1, xn] = 1 2 2 f (xn)
2!h
f [x0,...., xn−1, xn] = 1 n
f (xn)
n
n!h
Substituting from above equations in Newton’s interpolating divided difference formula (4)
Then we have
1 1 1
P(x) = f (xn) + f (xn)(x−xn) + 2  f (xn)(x−xn)(x−xn−1) +...+ n 2 f (xn)(x−xn)....(x−x1) (5)
2
h 2!h n!h

Assume 𝑥 = 𝑥𝑛 + s h then 𝑥 − 𝑥𝑛 = s h. Also we can prove that

 x − xn−1 = xn +sh− xn−1 = xn − xn−1 +sh = h+sh = h(s +1)
x − xn−2 = xn +sh− xn−2 = xn − xn−2 +sh = 2h+sh = h(s +2)

Substituting in (5) we have

P(x) = f (xn) + 1f (xn)(sh) + 1 2 2 f (xn)(sh)(s +1)h+...+ 1 n 2 f (xn)(s)(s +1)(s +2)...(s +n−1)hn
h 2!h n!h
Hence we have the following polynomial which is known Newton’s backward divided difference

1 1
P(x) = f (xn) +f (xn)(s) +  f (xn)(s)(s +1)+...+ 2 f (xn)(s)(s +1)(s +2)...(s +n−1)
2
(6)
2! n!
f(𝒙𝟒 )
∇f(𝒙𝟒 )
f(𝒙𝟑 ) ∇2 f(𝒙𝟒 )
∇f(𝒙𝟑 ) ∇3 f(𝒙𝟒 )

f(𝒙𝟐 ) ∇2 f(𝒙𝟑 ) ∇4 f(𝒙𝟒 )

∇f(𝒙𝟐 ) ∇3 f(𝒙𝟑 )

f(𝒙𝟏 ) ∇2 f(𝒙𝟐 )

∇f(𝒙𝟏 )

f(𝒙𝟎 )
 Example II: Using Newton’s backward divided difference interpolation to find f(8) according to the following table

x 1 3 5 7 9
F(x) 4 5 8 11 16

Solution: Since h=2, x=8, 𝑥4 =9 , x= 𝑥4 +s h, then 8=9+s(2) , hence s= - 0.5

16
5
11 2
3 2
8 0 4
3 -2
5 2
1
4
Since
P(x) = f (x4) +f (x4)(s) + 1 2 f (x4)(s)(s +1)+ 1 3 f (x4)(s)(s +1)(s +2) + 1 4 f (x4)(s)(s +1)(s +2)(s +3)
2! 3! 4!
Then
P(8) =16+(5)(−0.5) + 1 (2)(−0.5)(−0.5+1)+ 1 (2)(−0.5)(−0.5+1)(−0.5+2) + 1 (4)(−0.5)(−0.5+1)(−0.5+2)(−0.5+3)
2! 3! 4!

Example: Find f(1.5) and f(8) using the following table

x 1 3 5 7 9

F(x) 4 5 8 11 16

Solution: Using one table only to find f(1.5) and f(8) as follows
 4
1
5 2
3 -2
8 0 4
3 2
11 2
5
16

To find f(1.5), we follow the same steps in Example I

and to find f(8) we follow the same steps in Example II
 Example: Using Newton’s method and the following table to find
tan(4.9) and tan(5.9)

x 0.8 1.1 1.4 1.7 2

tan(x+4) -11.385 -2.449 -1.218 -0.66 -0.291

Solution: To find tan(4.9), x+4=4.9, then x=0.9 and hence 0.9=0.8+s(0.3) where h=0.3. That
1
is s=
3
1 −7.705 1 −2 −7.032 1 −2 −5 −6.548 10 −8
tan(4.9)=-11.385+8.936( )+ ( ) ( )+ ( ) ( ) ( )+ ( )( )
3 2! 3 3 3! 3 3 3 4! 27 3

1
To find tan(5.9), x+4=5.9, then x=1.9 and hence 1.9=2+s(0.3) where h=0.3. That is s=-
3
−1 −0.189 −1 2 0.484 −1 2 5 −6.548 −10 8
tan(5.9)=-0.291+0.369( )+ ( ) ( )+ ( ) ( ) ( )+ ( )( )
3 2! 3 3 3! 3 3 3 4! 27 3
-11.385

8.936

-2.449 -7.705

1.231 7.032

-1.218 -0.673 -6.548

0.558 0.484

-0.66 -0.189

0.369

-0.291
Exercises: Using Newton’s interpolation method to evaluate the following

x 1.7 1.9 2 2.1 2.3

1] find 𝑒 1.8 𝑒𝑥 5.474 6.686 7.389 8.166 9.974

x 1.1 1.2 1.5 1.7 1.8 2

2] Find f(1.3) and f(1.95) f(x) 1.112 1.219 1.636 2.054 2.323 3.011

x -1 0 2 4 7
3] Find f(2.5) f(x) 2 1 11 117 666

x 8.1 8.3 8.6 8.7

4] Find f(8.35)
f(x) 16.9441 17.56492 18.50515 18.82091
5] Find f(0.05) and f(0.75) x 0 0.2 0.4 0.6 0.8
f(x) 1 1.2214 1.4918 1.8221 2.2255

x 1 1.05 1.1 1.15 1.3

6] Find 1.03 & 1.23
𝑥 1 1.0247 1.0488 1.0724 1.0954

x 2 2.2 2.4 2.6 2.8 3

ln(x+2) 1.3863 1.4351 1.4816 1.5261 1.5686 1.6094

7] Find ln(4.1)& ln(4.9)

x 0.1 0.3 0.5 0.7 0.9

8] Find sin(1.2)& sin(1.85) Sin(x+1) 0.8912 0.9636 0.9975 0.9917 0.9463

 Applications
1]You measure the voltage drop V across a resistor for a number of different values of
current i. The results are
i 0.25 0.75 1.25 1.5 2

v -0.45 -0.6 0.7 1.88 6

Use Newton’s interpolation to estimate the voltage drop for i = 1.15.

2] The current in a wire is measured with great precision as a function of time:

t 0 0.1250 0.2500 0.3750 0.500

i 0 6.24 7.75 4.85 0.000

Determine i at t = 0.23.