Chapter 3 : INTERPOLATION & CURVE FITTING

3.1 What is interpolation

3.2 Lagrange Interpolation
3.3 Newton’s divided difference
3.4 Newton’s forward difference
3.5 Newton’s backward difference
3.6 Least square curve fitting method

1
3.1 Interpolation

Aim: To find a function Pn (x) that exactly represents a collection

of data.

10
(a) x3 , f x3 
5 x2 , f x2 

10 5 x10, f x1  5 10
x0 , f x0 
5

10

(b)
n 0 1 ..
xn .. .. ..
f  xn  .. .. ..

(c) f x0   a, f x1   b,..

>> Interpolation rule: Pn ( xi )  f i

2
3.2 Lagrange Polynomial Interpolation

General formula for Lagrange polynomial Interpolation which

passing through all the points

( x0 , f ( x0 )), ( x1 , f ( x1 )),..., ( xn , f ( xn )) ,

is given as:

Pn ( x)  L0 ( x) f ( x0 )  L1 ( x) f ( x1 )  ..  Ln ( x) f ( xn )

where
 
n


x x 

j
L x     
i  
j 0 x x



i j
j i  

is the Lagrange coefficient that satisfies

n
 Li  x   1
i0

3
Example 1

Let x0  1, x1  0.6, x2  0.9, f ( x)  cos( x2 )

a) Find the Lagrange interpolating polynomial.
b) Use a) to approximate f (0.45) and estimate the approximation
error.

Example 2

a) Estimate log4 between log3 and log5 by using linear

Lagrange interpolation. Then compare the result with the
exact solution.

b) The density of a chemical material at three different

temperatures is given below:
Temperature ( 0 C ) 90 200 300
Density ( kg / cm3 ) 950 900 850

i) Write the suitable Lagrange formula for the above data.

ii) Estimate the density of above chemical material when
temperature is 250 0 C .

4
3.3 Newton’s divided - difference formula

General Formula for Newton’s divided- difference that passing

through all the points

( x0 , f ( x0 )), ( x1 , f ( x1 )),..., ( xn , f ( xn )) ,

is given as:

Pn  x   a0  a1  x  x0   a2  x  x0  x  x1 
 ...  an  x  x0  x  x1 ... x  xn1 
The coefficient a0 , a1 , .., an ,  Newton’s divided-difference.

The value of divided-difference for

xi , fi in0
is defined as:

f i[ 0]  f i
[ j 1] [ j 1]
f  f
f i[ j ]  i 1 i , j  1, 2,.., n  1
xi  j  xi
 j
( fi is define as j-th divided - difference), and given in the table
below:

5
Table for Newton’s divided –difference

I x
i f 0 f 1 f 2  f n 1 f n
i i i i  i
1 2  n 1 n 
0 x0 f0 f0 f0 f0 f0
1 f1
2  n1
1 x1 f1 f1 f1
 
1 2 
n2 xn 2 f n 2 f n2 f n2
1
n 1 xn1 f n1 f n1
n xn fn

Given From Newton’s

divided -difference formula

6
We also can write;

0 
a0  f 0  f 0
0  0 
f1  f 0 f1  f 0 1
a1    f0
x1  x0 x1  x0
0  0  0  0 
f 2  f1 f1  f 0 f 2  f1 f1  f 0
 
x2  x1 x1  x0 x2  x1 x1  x0
a2  
x2  x0 x2  x0
1 1
f1  f 0 2 
  f0
x2  x0

Therefore, the Newton’s divided-difference polynomial

interpolation for  xi , f 2

i i 0 (quadratic polynomial)

can be written as:

P2 x   f 0  f 0 x  x0   f 02 x  x0 x  x1 
0 1

7
Generally, Newton’s divided- difference formula, with degree
n is given by;

Pn x   f 0  f 0 x  x0   f 02 x  x0 x  x1   ...

0  1

f 0 x  x0 x  x1 ...x  xn 1 
n 

or
 j  
n j 1
Pn x    f 0   x  xk 
j 0  k 0 

Example 1

Given that e0 1, e0.5  1.6487, e1  2.7183 , use Newton’s Divided

difference formula to estimate the value of e0.25 . Then, compute
the absolute error.

Example 2

For a function f , the Divided Difference table is given by:

x0  0 f [ x0 ]  ?
f [ x0, x1]  ?
x1  0.4 f [ x1]  ? f [ x0 , x1, x2 ]  50
7
f [ x1, x2 ]  10
x2  0.7 f [ x2 ]  6
Determine the missing entries, then approximate f (0.3).

8
3.4 Interpolation for uniform data

Uniform data means the step size, h for xi are all same ie;
( x1  x0 )  ( x2  x1 )  ..  ( xn  xn1 )  h

There several methods to treat uniform data such as;

a) Newton’s forward- difference and

b) Newton’s backward- difference

3.4.1 Newton’s forward difference

Newton’s forward- difference formula

r r  1 2 r r  1r  2 3
Pn x   f 0  rf 0   f0   f 0  ...
2! 3!
r r  1r  2...r  n  n
  f0
n!

x  x0
where r 
h

9
Table for Newton’s forward -difference

x f 2 f i  n 1 f i
i i f
i i n f i
0 x0 f0 f 0 2 f 0 n1 f 0 n f 0
1 x1 f1 f1 2 f1 n1 f1
 
n2 xn 2 f n 2 f n2 2 f n2

n 1 xn1 f n1 f n1

n xn fn

Given from Newton’s forward-

difference formula
k fi  k 1 fi 1  k 1 fi

10
Example 1

By using Newton’s Forward Difference formula, show that the

polynomial interpolating the following data has degree 3.

x -2 -1 0 1 2 3
f (x) 1 4 11 16 13 -4

Example 2

Newton forward difference formula order three can be written as

f x   f 0  Ax  Bx 2  Cx 3 . Find the coefficients A, B and C if you are
given the following data:
f  0  3, f 1  2, f  2  7, f 3  24, f  4  59 and f 5  118 .
Then estimate the value of f  0.1 by using the above formula. Can
you get the Newton forward difference’s formula for the fourth
order from the given data? Explain your answer.

11
3.4.2 Newton’s backward- difference

Newton’s backward- difference formula

r r  1 2 r r  1r  2 3
Pn x   f n  rf n   fn   f n  ...
2! 3!
r r  1r  2...r  n  n
  fn
n!
x  xn
where r
h
Table for Newton’s backward- difference
i xi fi f i  2 fi …
 n 1 f i  n f i
0 x0 f0
1 x1 f1 f 1
2 x2 f2 f 2 2 f2
 
n 1 xn1 f n1 f n1  2 f n1  n1 f n1

n xn fn f n 2 fn  n1 f n  n f n

Given from Newton’s backward-

difference formula
 k f i   k 1 f i   k 1 f i 1

12
Example 1

Given

x 1.0 1.2 1.4 1.6 1.8

f (x) 0.0000 0.1823 0.3365 0.4700 0.5878

Find an approximation of f 1.7  using the Newton’s backward-

difference formula. Do the calculation using 4 decimal places.

Example 2

Given the following data;

x 1 1.2 1.4 1.6 1.8 2.0

f x  0.6570 0.9039 0.9985 0.9407 0.7344 0.4121

By choosing the suitable data, estimate the value of f 1.5 using

cubic interpolation’s formula of:
a) Newton forward difference,
b) Newton backward difference

13
3.5 Least Square Curve Fitting

 For a larger data.

 Is a method of finding a function which ‘best’ fit the data.
(the line not necessarily pass through all points.)
 Rule: the sum of square error must be minimum.
 This method is called Least Squares Method and the curve
that is obtained is called Least Squares Curve.

3.5.1 Least Squares Method

 The easiest method of finding a least squares curve is by

using a polynomial function.

Linear polynomial Quadratic/parabolic

polynomial

a) Linear Least Squares

For a given set of data  xi , y n

i i 0 , we want to find an equation
of a line y  A  Bx which minimize the total of squares error,

n n
S    yi  y xi     yi  A  Bxi 2
2
i 0 i 0

14
 S S
S is minimum when  0 and  0.
A B

These yield:

 2 y
i 0
i  A  Bxi  1  0
n

 2 y
i 0
i  A  Bxi  xi   0

Divide every equation with (-2) and expand it to get normal

equations as follows:

n n n
A1  B  xi   yi
i 0 i 0 i 0
n n n
A xi  B  xi   xi yi
2

i 0 i 0 i 0

or in matrix form:

 n n
  n 
 1  x    y i 
 i 0 i 0
i
 A 
    i 0 
 n n  
2  B   n

  xi  xi   i i 
x y
 i 0 i 0   i 0 

Solve the system above to find a value of A and B and substitute

in y  A  Bx (the least squares line).

15
Example 1

Given:
1  1.4 
   
[ x]   5  , [ y]  1.1
7  0.2
   
Fit a linear least squares to the data.

Example 2

Find the normal equations which arise while fitting the least squares
method of the equation y = c1 + c2 sin x to the set points
(0,0), ( 6,1), ( 2,3), (5 6,2) . Solve them for c1 and c2.

16
b) Parabolic/Quadratic Least Squares

For a given set of data xi , yi in0 , we want to find a parabolic

equation y  A  Bx  Cx which minimize the total least
2

squares error:

 
n n 2

S    yi  yxi    yi  A  Bxi  Cxi

2 2

i 0 i 0

S S S
S is minimum if 0 ,  0 and  0.
A B C

And we get,
n

 2 yi  A  Bx i  Cxi
2
  1  0
i 0
n

 2 yi  A  Bx i  Cxi
2
  x   0
i
i 0
n

 2 yi  A  Bx i  Cxi
2
  x   0
i
2
i 0

Divide every equation with (-2) and expand it to get the normal
equations:

17
 n n n n
A1  B  xi C  xi   yi
2

i 0 i 0 i 0 i 0
n n n n
A xi  B  xi C  xi   xi yi
2 3

i 0 i 0 i 0 i 0
n n n n
A xi  B  xi C  xi   xi yi
2 3 4 2

i 0 i 0 i 0 i 0

or in the matrix form;

 n n n
  n 
 1 x     i 
2
i x i y
 i 0 i 0 i 0  A   i 0 
 n 3    
n n n

  xi  xi    i i 

2
x i  B x y
 in0 i 0
n
i 0
n  C   in0 
 x2 xi   x 2y 
 i x   i i 
3 4
i
 i 0 i 0 i 0   i 0 

Solve the above system for a value of A, B and C to finally obtain

the parabolic equation y  A  Bx  Cx .
2

Example 1

Given the six data points (0, 0.98), (0.1, 1.01), (0.2, 0.99),
(0.3,0.88), (0.4, 0.85), and (0.5, 0.77) which are represent by the
function y( x)  a  bx2 . Apply the least-squares method to find a
and b. Then, compute the total squares error, S.

18
3.5.2 Least Squares Power Function

Let say a set of data xi , yi i 0 is going to be fit into a power
n

function in the form of

y  Ax B
where B is a constant.

Therefore, we need to find A so that the total least squares error, S

is minimum:

 
n 2 n 2

S    yi  yxi    yi  Axi
B

i 0 i 0

S is minimum when
S
  x   0
n
2 yi  Axi
B B
0 i
A i 0

Divide the above equation with (-2) and factorize it to get:

x
B
n n i yi
 xi yi  A xi  0 or A  i 0
B 2B
n
i 0 i 0
x
2B
i
i 0

19
Example:

Recent world records for men’s weight lifting is given as follows:

W (kg) 52 56 60 67.5 75 82.5 90 100 110

L (kg) 252.5 277.5 302.5 345 360 400 415 430 427.5

The higher the weight class, the greater the lift. Accordingly, it is
proposed that lift should be proportional to W 2/3 which arise the
equation L  cW 2/3 . Determine the constant c by the least-squares
method.

20
3.5.3 Data Linearization

Let say a set of data xi , yi i 0 is going to be fit into a power
n

function in the form of

y  Ce Dx
where C and D are constants. Apply ln to both sides to yield

ln  y   ln C   Dx

Y A BX

 linear form: Y = A + BX

Solve for value A and B to get y  Ce Dx .

Example 1:

Given the following data;

V 160 180 200 220 240
T 7 5.5 5.0 3.5 2.0
If VT a  b , (a, b constants), then determine the value of a and b by
the least squares method.

21
 SSE 2393 Numerical Methods

Instructions: Answer all questions. Use 4 decimal places for all calculation

Tutorial 3

1. Given the following table:

x 1.5 1.6 1.7 1.8 1.9
f x  0.0668 0.0548 0.0446 0.0359 0.0287

Estimate the value of f 1.55 and f 1.85 by using the most suitable Newton
interpolation’s formula.

2. Given f x   1 x sin x

a) Form a table for the values xi and f xi  , i = 0, 1, 2, 3, 4 with

x0  1.0 and h  0.2 .
b) By using Newton forward difference’s formula find the polynomial
interpolation P4 x  for the function f x  . Then estimate the value of
f 1.1 and compare the result with the exact solution.

3. Given the table below:

x 1 2 3 4
y 4 -1 0 1

a) Estimate the value of y when x  3.5 by using Newton backward

difference formula.
b) Why the Newton forward difference is not suitable to estimate
the value of y when x  3.5 ?

4. Newton forward difference formula order three can be written as

f x   f 0  Ax  Bx 2  Cx 3 .
Find the coefficients A, B and C if you are given the following data
f 0  3, f 1  2, f 2  7, f 3  24, f 4  59 and f 5  118 .
Then estimate the value of f 0.1 by using the above formula.
Can you get the Newton forward difference’s formula for the fourth
order from the given data? Explain your answer.

5. a) Estimate log4 between log3 and log5 by using linear Lagrange

interpolation. Then compare the result with the exact solution.
 b) The density of a chemical material at three different
temperature are given below:
Temperature ( 0 C ) 90 200 300
Density ( kg / cm )
3
950 900 850

i) Write the suitable Lagrange formula for the above data.

ii) Estimate the density of above chemical material when
temperature is 250 0 C .

6. Given the following data;

x 1 1.2 1.4 1.6 1.8 2.0

f x  0.6570 0.9985 0.9407 0.7344 0.4121

a) Complete the above table by using quadratic Lagrange

interpolation.
b) By choosing the suitable data, estimate the value of f 1.5 using
cubic interpolation’s formula;
i) Newton forward difference, and
ii) Newton backward difference

7. Given the following data,

x 0 1 2 4 6
f x  1 9 23 93 259

Form a Newton divided difference’s table and find the approximation

of f 4.2 by using Newton divided difference polynomial.

8. a) Give two advantages of Newton divided difference method

compared with Newton forward difference or Newton backward
difference method.
b) Given the following data;

x 0.1 0.2 0.3 0.4 0.5

y 0.9950 0.9801 0.9211 0.8776

Estimate y value when x  0.3 and x  0.46 by using Newton divided

difference.
c) Furthermore by using the solution in (b), estimate y when
x  0.46 by Newton backward difference. If the real function is
y  cos x , which method (Newton divided difference or Newton
backward difference) could give the most precise answer y0.46 .
9. a) Given the following data;
x 36 41 42 43 44 45 47 50
y 2.5 2.7 2.8 2.9 3.0 3.2 3.3 3.5

Get the straight line by the least square method. Then find the
approximation of y38 .
b) Fit a parabola by the least squares method to the points (0,0),
(1,1), (3,3) and (4,2). Find the value of total error squares, S for this fit.

10. a) Given the following data;

V 160 180 200 220 240
T 7 5.5 5.0 3.5 2.0

If VT a  b , a, b constants, then
determine the value of a and b by the least squares method.

b) Fit the data below:

x 1.0 1.1 1.4 1.6 2.0
y 3.00 3.03 3.39 3.81 5.00
with the function f x  
A
 Bx 2 by finding the normal equation
x
5
for S    yi  f xi  and then get the value A and B. Hence,
2

i 1

estimate y when x  1.5 .

 I. O. 060> ~ 6· o:s2{

2. 0\) to\pre .I b) ,. q~o3

5· a) 0 '81 Sl>

4· A ~ -2, B:::o, C;=. r

f CO, t)::. 2 . <60 I 0

Go. V\ £1 0+ .
~. ~) D·~~I

b) h) ~ 7 >- .5q. j( ~ fUM ~

,. 10 ) i) o· CJ~O 2

7· f C4 · Z)-= lo4'4-S'1)V'

'/} . b) 0 -q ~ I 0 . 8'"<:; 72 C) D .& 16 I

to .
b) A:;.. '2. .DO l -; I IS ~ o· 9111
~O.s) -;;<. 3'~o .