Lagrange and Apline Interpolation - Numerical Analysis, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

 Page 1


Numerical Analysis
Chapter 4 Interpolation and Approximation
4.1 Polynomial Interpolation
Goal Given n+1 data points
(x
0
,y
0
), (x
1
,y
1
), ···(x
n
,y
n
),
to ?nd the polynomial of degree less than or equal to n that passes through these points.
Remark There is a unique polynomial of degree less than or equal to n passing through n+1 given
points. (Give a proof for n = 2.)
Linear Interpolation Giventwo points (x
0
,y
0
) and (x
1
,y
1
), the linear polynomial passing through the
two points is the equation of the line passing through the points. One way to write its formula is
P
1
(x)= y
0
x
1
-x
x
1
-x
0
+y
1
x
-
x
0
x
1
-x
0
.
Example For the data points (2,3) and (5,7) ?nd P
1
(x).
Solution:
P
1
(x)=3
5-x
5-2
+7
x-2
5-2
=(5-x)+
5
3
(x-2)
Example For the data points (0.82,2.270500) and (0.83,2.293319), ?nd P
1
(x) and evaluate P
1
(0.826).
Solution:
P
1
(x)=2.270500
.83-x
.83-.82
+2.293319
x-.82
.83-.82
= 227.0500 (.83-x) + 229.3319(x-.82)
and hence
P
1
(.826) = 2.2841914.
Remark. If f(x)= e
x
, then f(.82) ˜ 2.270500, f(.83) ˜ 2.293319, and f(.826)˜ 2.2841638. Note then
that P
1
(x) is an approximation of f(x)= e
x
for x? [.82,.83].
In general, if y
0
= f(x
0
) and y
1
= f(x
1
) for some function f, then P
1
(x) is a linear approximation of f(x)
for all x? [x
0
,x
1
].
Page 2


Numerical Analysis
Chapter 4 Interpolation and Approximation
4.1 Polynomial Interpolation
Goal Given n+1 data points
(x
0
,y
0
), (x
1
,y
1
), ···(x
n
,y
n
),
to ?nd the polynomial of degree less than or equal to n that passes through these points.
Remark There is a unique polynomial of degree less than or equal to n passing through n+1 given
points. (Give a proof for n = 2.)
Linear Interpolation Giventwo points (x
0
,y
0
) and (x
1
,y
1
), the linear polynomial passing through the
two points is the equation of the line passing through the points. One way to write its formula is
P
1
(x)= y
0
x
1
-x
x
1
-x
0
+y
1
x
-
x
0
x
1
-x
0
.
Example For the data points (2,3) and (5,7) ?nd P
1
(x).
Solution:
P
1
(x)=3
5-x
5-2
+7
x-2
5-2
=(5-x)+
5
3
(x-2)
Example For the data points (0.82,2.270500) and (0.83,2.293319), ?nd P
1
(x) and evaluate P
1
(0.826).
Solution:
P
1
(x)=2.270500
.83-x
.83-.82
+2.293319
x-.82
.83-.82
= 227.0500 (.83-x) + 229.3319(x-.82)
and hence
P
1
(.826) = 2.2841914.
Remark. If f(x)= e
x
, then f(.82) ˜ 2.270500, f(.83) ˜ 2.293319, and f(.826)˜ 2.2841638. Note then
that P
1
(x) is an approximation of f(x)= e
x
for x? [.82,.83].
In general, if y
0
= f(x
0
) and y
1
= f(x
1
) for some function f, then P
1
(x) is a linear approximation of f(x)
for all x? [x
0
,x
1
].
Quadratic Interpolation If (x
0
,y
0
), (x
1
,y
1
), (x
2
,y
2
), are given data points, then the quadratic
polynomial passing through these points can be expressed as
P
2
(x)= y
0
L
0
(x)+ y
1
L
1
(x)+ y
2
L
2
(x)
where
L
0
(x)=
(x-x
1
)(x-x
2
)
(x
0
-x
1
)(x
0
-x
2
)
L
1
(x)=
(x-x
0
)(x-x
2
)
(x
1
-x
0
)(x
1
-x
2
)
L
2
(x)=
(x-x
0
)(x-x
1
)
(x
2
-x
0
)(x
2
-x
1
)
The polynomial P
(
x) given by the above formula is called Lagrange’s interpolating polynomial and
the functions L
0
,L
1
,L
2
are calledLagrange’s interpolating basis functions.
Remark Note that deg(P
2
)=2 and that
L
i
(x
j
)= d
ij
=
(
0 i6= j
1 i= j
d
ij
is called the Kronecker delta function.
Example Construct P
2
from the data points (0,-1),(1,-1),(2,7).
Solution:
P
2
(x)=(-1)
(x-1)(x-2)
2
+(-1)
x(x-2)
-1
+7
x(x-1)
2
=
-1
2
(x-1)(x-2) + x(x-2) +
7
2
x(x-1)
Example See Example 4.1.4 on page 122 of the text.
Higher-Degree Interpolation Given n+1 data points
(x
0
,y
0
), (x
1
,y
1
), ···(x
n
,y
n
),
the n Lagrange interpolating polynomial is given by
P
n
(x)= y
0
L
0
(x)+ y
1
L
1
(x)+ y
2
L
2
(x)+ y
n
L
n
(x)
where
L
0
(x)=
(x-x
1
)(x-x
2
)(x-x
3
)···(x-x
n
)
(x
0
-x
1
)(x
0
-x
2
)(x
0
-x
3
)···(x
0
-x
n
)
L
1
(x)=
(x-x
0
)(x-x
2
)(x-x
3
)···(x-x
n
)
(x
1
-x
0
)(x
1
-x
2
)(x
1
-x
3
)···(x
1
-x
n
)
L
2
(x)=
(x-x
0
)(x-x
1
)(x-x
3
)···(x-x
n
)
(x
2
-x
0
)(x
2
-x
1
)(x
2
-x
3
)···(x
2
-x
n
)
.
.
.
L
n
(x)=
(x-x
0
)(x-x
1
)(x-x
2
)···(x-x
n-1
)
(x
n
-x
0
)(x
n
-x
1
)(x
n
-x
3
)···(x
n
-x
n-1
Page 3


Numerical Analysis
Chapter 4 Interpolation and Approximation
4.1 Polynomial Interpolation
Goal Given n+1 data points
(x
0
,y
0
), (x
1
,y
1
), ···(x
n
,y
n
),
to ?nd the polynomial of degree less than or equal to n that passes through these points.
Remark There is a unique polynomial of degree less than or equal to n passing through n+1 given
points. (Give a proof for n = 2.)
Linear Interpolation Giventwo points (x
0
,y
0
) and (x
1
,y
1
), the linear polynomial passing through the
two points is the equation of the line passing through the points. One way to write its formula is
P
1
(x)= y
0
x
1
-x
x
1
-x
0
+y
1
x
-
x
0
x
1
-x
0
.
Example For the data points (2,3) and (5,7) ?nd P
1
(x).
Solution:
P
1
(x)=3
5-x
5-2
+7
x-2
5-2
=(5-x)+
5
3
(x-2)
Example For the data points (0.82,2.270500) and (0.83,2.293319), ?nd P
1
(x) and evaluate P
1
(0.826).
Solution:
P
1
(x)=2.270500
.83-x
.83-.82
+2.293319
x-.82
.83-.82
= 227.0500 (.83-x) + 229.3319(x-.82)
and hence
P
1
(.826) = 2.2841914.
Remark. If f(x)= e
x
, then f(.82) ˜ 2.270500, f(.83) ˜ 2.293319, and f(.826)˜ 2.2841638. Note then
that P
1
(x) is an approximation of f(x)= e
x
for x? [.82,.83].
In general, if y
0
= f(x
0
) and y
1
= f(x
1
) for some function f, then P
1
(x) is a linear approximation of f(x)
for all x? [x
0
,x
1
].
Quadratic Interpolation If (x
0
,y
0
), (x
1
,y
1
), (x
2
,y
2
), are given data points, then the quadratic
polynomial passing through these points can be expressed as
P
2
(x)= y
0
L
0
(x)+ y
1
L
1
(x)+ y
2
L
2
(x)
where
L
0
(x)=
(x-x
1
)(x-x
2
)
(x
0
-x
1
)(x
0
-x
2
)
L
1
(x)=
(x-x
0
)(x-x
2
)
(x
1
-x
0
)(x
1
-x
2
)
L
2
(x)=
(x-x
0
)(x-x
1
)
(x
2
-x
0
)(x
2
-x
1
)
The polynomial P
(
x) given by the above formula is called Lagrange’s interpolating polynomial and
the functions L
0
,L
1
,L
2
are calledLagrange’s interpolating basis functions.
Remark Note that deg(P
2
)=2 and that
L
i
(x
j
)= d
ij
=
(
0 i6= j
1 i= j
d
ij
is called the Kronecker delta function.
Example Construct P
2
from the data points (0,-1),(1,-1),(2,7).
Solution:
P
2
(x)=(-1)
(x-1)(x-2)
2
+(-1)
x(x-2)
-1
+7
x(x-1)
2
=
-1
2
(x-1)(x-2) + x(x-2) +
7
2
x(x-1)
Example See Example 4.1.4 on page 122 of the text.
Higher-Degree Interpolation Given n+1 data points
(x
0
,y
0
), (x
1
,y
1
), ···(x
n
,y
n
),
the n Lagrange interpolating polynomial is given by
P
n
(x)= y
0
L
0
(x)+ y
1
L
1
(x)+ y
2
L
2
(x)+ y
n
L
n
(x)
where
L
0
(x)=
(x-x
1
)(x-x
2
)(x-x
3
)···(x-x
n
)
(x
0
-x
1
)(x
0
-x
2
)(x
0
-x
3
)···(x
0
-x
n
)
L
1
(x)=
(x-x
0
)(x-x
2
)(x-x
3
)···(x-x
n
)
(x
1
-x
0
)(x
1
-x
2
)(x
1
-x
3
)···(x
1
-x
n
)
L
2
(x)=
(x-x
0
)(x-x
1
)(x-x
3
)···(x-x
n
)
(x
2
-x
0
)(x
2
-x
1
)(x
2
-x
3
)···(x
2
-x
n
)
.
.
.
L
n
(x)=
(x-x
0
)(x-x
1
)(x-x
2
)···(x-x
n-1
)
(x
n
-x
0
)(x
n
-x
1
)(x
n
-x
3
)···(x
n
-x
n-1
Newton’s Divided Di?erence Givendistinctpoints x
0
and x
1
inthe domain of a function f, wede?ne
f[x
0
,x
1
]=
f(x
1
)-f(x
0
)
x
1
-x
0
.
This is called the ?rst-order divided di?erence of f(x).
Remark. Note that if f is di?erentiable on [x
0
,x
1
], then by Mean Value Theorem, there exists a
c? (x
0
,x
1
) such that f[x
0
,x
1
]= f
0
(c). Furthermore, if x)0 and x
1
are close to each other, then we have
f[x
0
,x
1
]˜ f
0
(d) with d =
x
0
+x
1
2
.
Example Consider f(x) =cosx, x
0
=0.2, and x
1
=0.3. Compute f[x
0
,x
1
].
Solution:
f[x
0
,x
1
]=
cos(0.3)-cos(0.2)
0.3-0.2
˜-0.2473009
Note that
f
0

x
0
+x
1
2

=-sin(0.25)˜-0.247404
De?nition Higher order divided di?erences are de?ned recursively using the lower-order ones.
Suppose x
0
,x
1
,x
2
are distinct point in the domain of f. Then the second-order divided di?erence is
given by
f[x
0
,x
1
,x
2
]=
f[x
1
,x
2
]-f[x
0
,x
1
]
x
2
-x
0
Suppose x
0
,x
1
,x
2
,x
3
are distinct points in the domain of f. Then thethird-order divided di?erenceis
given by
f[x
0
,x
1
,x
2
,x
3
]=
f[x
1
,x
2
,x
3
]-f[x
0
,x
1
,x
2
]
x
3
-x
0
Ingeneral,ifx
0
,x
1
,x
2
···x
n
aredistinctpointsinthedomainof f,thenthenth-orderdivideddi?erence
is given by
f[x
0
,x
1
,x
2
,···x
n
]=
f[x
1
,x
2
,···x
n
]-f[x
0
,x
1
,c...,x
n-1
]
x
n
-x
0
Theorem Suppose x
0
,x
1
,x
2
,...,x
n
are distinct points in [a,b] and suppose f is n times continuously
di?erentiable. Then there exists a point c between the smallest and largest of x
0
,x
1
,···,x
n
such that
f[x
0
,x
1
,···,x
n
]=
f
(n)
(c)
n!
.
Page 4


Numerical Analysis
Chapter 4 Interpolation and Approximation
4.1 Polynomial Interpolation
Goal Given n+1 data points
(x
0
,y
0
), (x
1
,y
1
), ···(x
n
,y
n
),
to ?nd the polynomial of degree less than or equal to n that passes through these points.
Remark There is a unique polynomial of degree less than or equal to n passing through n+1 given
points. (Give a proof for n = 2.)
Linear Interpolation Giventwo points (x
0
,y
0
) and (x
1
,y
1
), the linear polynomial passing through the
two points is the equation of the line passing through the points. One way to write its formula is
P
1
(x)= y
0
x
1
-x
x
1
-x
0
+y
1
x
-
x
0
x
1
-x
0
.
Example For the data points (2,3) and (5,7) ?nd P
1
(x).
Solution:
P
1
(x)=3
5-x
5-2
+7
x-2
5-2
=(5-x)+
5
3
(x-2)
Example For the data points (0.82,2.270500) and (0.83,2.293319), ?nd P
1
(x) and evaluate P
1
(0.826).
Solution:
P
1
(x)=2.270500
.83-x
.83-.82
+2.293319
x-.82
.83-.82
= 227.0500 (.83-x) + 229.3319(x-.82)
and hence
P
1
(.826) = 2.2841914.
Remark. If f(x)= e
x
, then f(.82) ˜ 2.270500, f(.83) ˜ 2.293319, and f(.826)˜ 2.2841638. Note then
that P
1
(x) is an approximation of f(x)= e
x
for x? [.82,.83].
In general, if y
0
= f(x
0
) and y
1
= f(x
1
) for some function f, then P
1
(x) is a linear approximation of f(x)
for all x? [x
0
,x
1
].
Quadratic Interpolation If (x
0
,y
0
), (x
1
,y
1
), (x
2
,y
2
), are given data points, then the quadratic
polynomial passing through these points can be expressed as
P
2
(x)= y
0
L
0
(x)+ y
1
L
1
(x)+ y
2
L
2
(x)
where
L
0
(x)=
(x-x
1
)(x-x
2
)
(x
0
-x
1
)(x
0
-x
2
)
L
1
(x)=
(x-x
0
)(x-x
2
)
(x
1
-x
0
)(x
1
-x
2
)
L
2
(x)=
(x-x
0
)(x-x
1
)
(x
2
-x
0
)(x
2
-x
1
)
The polynomial P
(
x) given by the above formula is called Lagrange’s interpolating polynomial and
the functions L
0
,L
1
,L
2
are calledLagrange’s interpolating basis functions.
Remark Note that deg(P
2
)=2 and that
L
i
(x
j
)= d
ij
=
(
0 i6= j
1 i= j
d
ij
is called the Kronecker delta function.
Example Construct P
2
from the data points (0,-1),(1,-1),(2,7).
Solution:
P
2
(x)=(-1)
(x-1)(x-2)
2
+(-1)
x(x-2)
-1
+7
x(x-1)
2
=
-1
2
(x-1)(x-2) + x(x-2) +
7
2
x(x-1)
Example See Example 4.1.4 on page 122 of the text.
Higher-Degree Interpolation Given n+1 data points
(x
0
,y
0
), (x
1
,y
1
), ···(x
n
,y
n
),
the n Lagrange interpolating polynomial is given by
P
n
(x)= y
0
L
0
(x)+ y
1
L
1
(x)+ y
2
L
2
(x)+ y
n
L
n
(x)
where
L
0
(x)=
(x-x
1
)(x-x
2
)(x-x
3
)···(x-x
n
)
(x
0
-x
1
)(x
0
-x
2
)(x
0
-x
3
)···(x
0
-x
n
)
L
1
(x)=
(x-x
0
)(x-x
2
)(x-x
3
)···(x-x
n
)
(x
1
-x
0
)(x
1
-x
2
)(x
1
-x
3
)···(x
1
-x
n
)
L
2
(x)=
(x-x
0
)(x-x
1
)(x-x
3
)···(x-x
n
)
(x
2
-x
0
)(x
2
-x
1
)(x
2
-x
3
)···(x
2
-x
n
)
.
.
.
L
n
(x)=
(x-x
0
)(x-x
1
)(x-x
2
)···(x-x
n-1
)
(x
n
-x
0
)(x
n
-x
1
)(x
n
-x
3
)···(x
n
-x
n-1
Newton’s Divided Di?erence Givendistinctpoints x
0
and x
1
inthe domain of a function f, wede?ne
f[x
0
,x
1
]=
f(x
1
)-f(x
0
)
x
1
-x
0
.
This is called the ?rst-order divided di?erence of f(x).
Remark. Note that if f is di?erentiable on [x
0
,x
1
], then by Mean Value Theorem, there exists a
c? (x
0
,x
1
) such that f[x
0
,x
1
]= f
0
(c). Furthermore, if x)0 and x
1
are close to each other, then we have
f[x
0
,x
1
]˜ f
0
(d) with d =
x
0
+x
1
2
.
Example Consider f(x) =cosx, x
0
=0.2, and x
1
=0.3. Compute f[x
0
,x
1
].
Solution:
f[x
0
,x
1
]=
cos(0.3)-cos(0.2)
0.3-0.2
˜-0.2473009
Note that
f
0

x
0
+x
1
2

=-sin(0.25)˜-0.247404
De?nition Higher order divided di?erences are de?ned recursively using the lower-order ones.
Suppose x
0
,x
1
,x
2
are distinct point in the domain of f. Then the second-order divided di?erence is
given by
f[x
0
,x
1
,x
2
]=
f[x
1
,x
2
]-f[x
0
,x
1
]
x
2
-x
0
Suppose x
0
,x
1
,x
2
,x
3
are distinct points in the domain of f. Then thethird-order divided di?erenceis
given by
f[x
0
,x
1
,x
2
,x
3
]=
f[x
1
,x
2
,x
3
]-f[x
0
,x
1
,x
2
]
x
3
-x
0
Ingeneral,ifx
0
,x
1
,x
2
···x
n
aredistinctpointsinthedomainof f,thenthenth-orderdivideddi?erence
is given by
f[x
0
,x
1
,x
2
,···x
n
]=
f[x
1
,x
2
,···x
n
]-f[x
0
,x
1
,c...,x
n-1
]
x
n
-x
0
Theorem Suppose x
0
,x
1
,x
2
,...,x
n
are distinct points in [a,b] and suppose f is n times continuously
di?erentiable. Then there exists a point c between the smallest and largest of x
0
,x
1
,···,x
n
such that
f[x
0
,x
1
,···,x
n
]=
f
(n)
(c)
n!
.
Example Let f(x)=cosx, x
0
=0.2,x
1
=0.3,x
2
=0.4. Compute f[x
0
,x
1
,x
2
].
Solution: From the previous example, we have f[x
0
,x
1
]˜-0.2473009 and
f[x
1
,x
2
]=
cos(0.4)-cos(0.3)
0.4-0.3
˜-0.3427550
Thus
f[x
0
,x
1
,x
2
]=
f[x
1
,x
2
]-f[x
0
,x
1
]
x
2
-x
0
˜
-0.3427550-(-0.2473009)
0.4-0.2
˜-0.4772705.
With n = 2 and c=0.3 ( a point between 0.2 and 0.3) we have
f
00
(c)
2
=-
1
2
cos(0.3)˜-0.4776682
which is very close to f[x
0
,x
1
,x
2
] as claimed in the theorem.
Basic Properties of Divided di?erences
1) f[x
0
,x
1
]= f[x
1
,x
0
]and f[x
0
,x
1
,x
2
]= f[x
1
,x
0
,x
2
]= f[x
1
,x
2
,x
0
]=···. Ingeneralif{i
0
,i
2
, ···,i
n
}
is a permutation of {0,1,2,···n}, then
f[x
0
,x
1
,···,x
n
]= f[x
i
0
,x
i
1
,···,x
in
]
2)
f[x
0
,x
1
,x
2
]=
f(x
0
)
(x
0
-x
1
)(x
1
-x
2
)
+
f(x
1
)
(x
1
-x
2
)(x
1
-x
2
)
+
f(x
2
)
(x
2
-x
0
)(x
2
-x
1
)
3) From the de?nition we have
lim
x
1
?x
0
f[x
0
,x
1
] = lim
x
1
?x
0
f(x
1
)-f(x
0
)
x
1
-x
0
= f
0
(x
0
).
The we can de?ne
f[x
0
,x
0
]= f
0
(x
0
)
In general, if x
0
= x
1
= x
2
=··· = x
n
, then
f[x
0
,x
0
,···,x
0
]=
f
(n)
n!
.
4) If x
0
= x
2
6= x
1
, then
f[x
0
,x
1
,x
0
]= f[x
0
,x
0
,x
1
]=
f[x
0
,x
1
]-f[x
0
,x
0
]
x
1
-x
0
Page 5


Numerical Analysis
Chapter 4 Interpolation and Approximation
4.1 Polynomial Interpolation
Goal Given n+1 data points
(x
0
,y
0
), (x
1
,y
1
), ···(x
n
,y
n
),
to ?nd the polynomial of degree less than or equal to n that passes through these points.
Remark There is a unique polynomial of degree less than or equal to n passing through n+1 given
points. (Give a proof for n = 2.)
Linear Interpolation Giventwo points (x
0
,y
0
) and (x
1
,y
1
), the linear polynomial passing through the
two points is the equation of the line passing through the points. One way to write its formula is
P
1
(x)= y
0
x
1
-x
x
1
-x
0
+y
1
x
-
x
0
x
1
-x
0
.
Example For the data points (2,3) and (5,7) ?nd P
1
(x).
Solution:
P
1
(x)=3
5-x
5-2
+7
x-2
5-2
=(5-x)+
5
3
(x-2)
Example For the data points (0.82,2.270500) and (0.83,2.293319), ?nd P
1
(x) and evaluate P
1
(0.826).
Solution:
P
1
(x)=2.270500
.83-x
.83-.82
+2.293319
x-.82
.83-.82
= 227.0500 (.83-x) + 229.3319(x-.82)
and hence
P
1
(.826) = 2.2841914.
Remark. If f(x)= e
x
, then f(.82) ˜ 2.270500, f(.83) ˜ 2.293319, and f(.826)˜ 2.2841638. Note then
that P
1
(x) is an approximation of f(x)= e
x
for x? [.82,.83].
In general, if y
0
= f(x
0
) and y
1
= f(x
1
) for some function f, then P
1
(x) is a linear approximation of f(x)
for all x? [x
0
,x
1
].
Quadratic Interpolation If (x
0
,y
0
), (x
1
,y
1
), (x
2
,y
2
), are given data points, then the quadratic
polynomial passing through these points can be expressed as
P
2
(x)= y
0
L
0
(x)+ y
1
L
1
(x)+ y
2
L
2
(x)
where
L
0
(x)=
(x-x
1
)(x-x
2
)
(x
0
-x
1
)(x
0
-x
2
)
L
1
(x)=
(x-x
0
)(x-x
2
)
(x
1
-x
0
)(x
1
-x
2
)
L
2
(x)=
(x-x
0
)(x-x
1
)
(x
2
-x
0
)(x
2
-x
1
)
The polynomial P
(
x) given by the above formula is called Lagrange’s interpolating polynomial and
the functions L
0
,L
1
,L
2
are calledLagrange’s interpolating basis functions.
Remark Note that deg(P
2
)=2 and that
L
i
(x
j
)= d
ij
=
(
0 i6= j
1 i= j
d
ij
is called the Kronecker delta function.
Example Construct P
2
from the data points (0,-1),(1,-1),(2,7).
Solution:
P
2
(x)=(-1)
(x-1)(x-2)
2
+(-1)
x(x-2)
-1
+7
x(x-1)
2
=
-1
2
(x-1)(x-2) + x(x-2) +
7
2
x(x-1)
Example See Example 4.1.4 on page 122 of the text.
Higher-Degree Interpolation Given n+1 data points
(x
0
,y
0
), (x
1
,y
1
), ···(x
n
,y
n
),
the n Lagrange interpolating polynomial is given by
P
n
(x)= y
0
L
0
(x)+ y
1
L
1
(x)+ y
2
L
2
(x)+ y
n
L
n
(x)
where
L
0
(x)=
(x-x
1
)(x-x
2
)(x-x
3
)···(x-x
n
)
(x
0
-x
1
)(x
0
-x
2
)(x
0
-x
3
)···(x
0
-x
n
)
L
1
(x)=
(x-x
0
)(x-x
2
)(x-x
3
)···(x-x
n
)
(x
1
-x
0
)(x
1
-x
2
)(x
1
-x
3
)···(x
1
-x
n
)
L
2
(x)=
(x-x
0
)(x-x
1
)(x-x
3
)···(x-x
n
)
(x
2
-x
0
)(x
2
-x
1
)(x
2
-x
3
)···(x
2
-x
n
)
.
.
.
L
n
(x)=
(x-x
0
)(x-x
1
)(x-x
2
)···(x-x
n-1
)
(x
n
-x
0
)(x
n
-x
1
)(x
n
-x
3
)···(x
n
-x
n-1
Newton’s Divided Di?erence Givendistinctpoints x
0
and x
1
inthe domain of a function f, wede?ne
f[x
0
,x
1
]=
f(x
1
)-f(x
0
)
x
1
-x
0
.
This is called the ?rst-order divided di?erence of f(x).
Remark. Note that if f is di?erentiable on [x
0
,x
1
], then by Mean Value Theorem, there exists a
c? (x
0
,x
1
) such that f[x
0
,x
1
]= f
0
(c). Furthermore, if x)0 and x
1
are close to each other, then we have
f[x
0
,x
1
]˜ f
0
(d) with d =
x
0
+x
1
2
.
Example Consider f(x) =cosx, x
0
=0.2, and x
1
=0.3. Compute f[x
0
,x
1
].
Solution:
f[x
0
,x
1
]=
cos(0.3)-cos(0.2)
0.3-0.2
˜-0.2473009
Note that
f
0

x
0
+x
1
2

=-sin(0.25)˜-0.247404
De?nition Higher order divided di?erences are de?ned recursively using the lower-order ones.
Suppose x
0
,x
1
,x
2
are distinct point in the domain of f. Then the second-order divided di?erence is
given by
f[x
0
,x
1
,x
2
]=
f[x
1
,x
2
]-f[x
0
,x
1
]
x
2
-x
0
Suppose x
0
,x
1
,x
2
,x
3
are distinct points in the domain of f. Then thethird-order divided di?erenceis
given by
f[x
0
,x
1
,x
2
,x
3
]=
f[x
1
,x
2
,x
3
]-f[x
0
,x
1
,x
2
]
x
3
-x
0
Ingeneral,ifx
0
,x
1
,x
2
···x
n
aredistinctpointsinthedomainof f,thenthenth-orderdivideddi?erence
is given by
f[x
0
,x
1
,x
2
,···x
n
]=
f[x
1
,x
2
,···x
n
]-f[x
0
,x
1
,c...,x
n-1
]
x
n
-x
0
Theorem Suppose x
0
,x
1
,x
2
,...,x
n
are distinct points in [a,b] and suppose f is n times continuously
di?erentiable. Then there exists a point c between the smallest and largest of x
0
,x
1
,···,x
n
such that
f[x
0
,x
1
,···,x
n
]=
f
(n)
(c)
n!
.
Example Let f(x)=cosx, x
0
=0.2,x
1
=0.3,x
2
=0.4. Compute f[x
0
,x
1
,x
2
].
Solution: From the previous example, we have f[x
0
,x
1
]˜-0.2473009 and
f[x
1
,x
2
]=
cos(0.4)-cos(0.3)
0.4-0.3
˜-0.3427550
Thus
f[x
0
,x
1
,x
2
]=
f[x
1
,x
2
]-f[x
0
,x
1
]
x
2
-x
0
˜
-0.3427550-(-0.2473009)
0.4-0.2
˜-0.4772705.
With n = 2 and c=0.3 ( a point between 0.2 and 0.3) we have
f
00
(c)
2
=-
1
2
cos(0.3)˜-0.4776682
which is very close to f[x
0
,x
1
,x
2
] as claimed in the theorem.
Basic Properties of Divided di?erences
1) f[x
0
,x
1
]= f[x
1
,x
0
]and f[x
0
,x
1
,x
2
]= f[x
1
,x
0
,x
2
]= f[x
1
,x
2
,x
0
]=···. Ingeneralif{i
0
,i
2
, ···,i
n
}
is a permutation of {0,1,2,···n}, then
f[x
0
,x
1
,···,x
n
]= f[x
i
0
,x
i
1
,···,x
in
]
2)
f[x
0
,x
1
,x
2
]=
f(x
0
)
(x
0
-x
1
)(x
1
-x
2
)
+
f(x
1
)
(x
1
-x
2
)(x
1
-x
2
)
+
f(x
2
)
(x
2
-x
0
)(x
2
-x
1
)
3) From the de?nition we have
lim
x
1
?x
0
f[x
0
,x
1
] = lim
x
1
?x
0
f(x
1
)-f(x
0
)
x
1
-x
0
= f
0
(x
0
).
The we can de?ne
f[x
0
,x
0
]= f
0
(x
0
)
In general, if x
0
= x
1
= x
2
=··· = x
n
, then
f[x
0
,x
0
,···,x
0
]=
f
(n)
n!
.
4) If x
0
= x
2
6= x
1
, then
f[x
0
,x
1
,x
0
]= f[x
0
,x
0
,x
1
]=
f[x
0
,x
1
]-f[x
0
,x
0
]
x
1
-x
0
Newton’s Divided Di?erence Interpolating Polynomial Or Newton’s Form
De?ne
P
1
(x)= f(x
0
)+f[x
0
,x
1
](x-x
0
)
P
2
(x)= f(x
0
)+f[x
0
,x
1
](x-x
0
)+f[x
0
,x
1
,x
2
](x-x
1
)
= P
1
(x)+f[x
0
,x
1
,x
2
](x-x
0
)(x-x
1
)
P
3
(x)= f(x
0
)+f[x
0
,x
1
](x-x
0
)+f[x
0
,x
1
,x
2
](x-x
1
)+f[x
0
,x
1
,x
2
,x
3
](x-x
0
)(x-x
1
)(x-x
2
)
= P
2
(x)+f[x
0
,x
1
,x
2
,x
3
](x-x
0
)(x-x
1
)(x-x
2
)
.
.
.
P
n
(x)= P
n-1
(x)+f[x
0
,x
1
,···,x
n-1
](x-x
0
)(x-x
1
)···(x-x
n-1
)
The polynomial P
n
is calledNewton’sdivideddeferenceformula for the interpolatingpolynomial
or Newton’s form for the interpolating polynomial. Note that P
n
(x
i
)= f(x
i
).
—Example DeterminetheNewtonformfortheinterpolatingpolynomialforthedataset{(-1,5),(0,1),(1,1),(2
Then use this polynomial to approximate y if x=1.5.
Solution
ix
i
f[x
i
]= f(x
i
) f[x
i
,x
i+1
] f[x
i
,x
i+1
,x
i+2
] f[x
0
,x
1
,x
2
,x
3
]
0-1 5
-4
10 1 2
01
21 1 5
10
32 11
Therefore
P
3
(x)= f[x
0
]+f[x
0
,x
1
](x-x
0
)+f[x
0
,x
1
,x
2
](x-x
0
)(x-x
1
)+f[x
0
,x
1
,x
2
,x
3
](x-x
0
)(x-x
1
)(x-x
2
)
=5-4(x-(-1))+2(x-(-1))(x-0)+1(x-(-1))(x-0)(x-2)
=5-4(x+1)+2x(x+1)+x(x+1)(x-1)
And so P
3
(1.5)=4.375.