CSC475: Numerical Computing

Tanveer Ahmed Siddiqui

Department of Computer Science

COMSATS University, Islamabad
 Question Answer Session

Week 08

Department of Computer Science 2

 Today Covered
,

After completing this lecture you should be able to

know
 Lagrange Interpolating Polynomials
 Newton’s Divided-Difference Interpolating
Polynomials
 Spline Interpolation

Department of Computer Science

 Interpolation

Department of Computer Science 4

 Interpolation

Department of Computer Science 5

 Interpolation

Department of Computer Science 6

 Interpolation

 For two points the polynomial is of first order

(a straight line connecting the points).
 For three points the polynomial is of second
order (a parabola that connects the points), and
so on.

Department of Computer Science 7

 Upshot

 Now suppose that the functional values are

given in tabular form such as

Department of Computer Science 8

 How to write these polynomial?

 The polynomial can be written in different

mathematical forms.
 Standard Form
 Fitting power series

 Lagrange interpolating functions

 Newton forward or backward interpolation
 The resulting polynomial will always be the
same!
 The different forms are suitable for use in
different circumstances.
Department of Computer Science 9
 Observation

 In practice, solving the system of equations,

especially for higher-order polynomials, is not
efficient
 It is possible to write the polynomial in other
forms that may be easier to use.
 Two such forms:
 The Lagrange forms
 The Newton forms

Department of Computer Science 15

 Lagrange Interpolating Polynomials

 Lagrange interpolating polynomials are a

particular form of polynomials that can be
written to fit a given set of data points by using
the values at the points.
 The polynomials can be written right away and
do not require any preliminary calculations for
determining coefficients.

Department of Computer Science 16

 Lagrange functions

n x  xj
Li ( x)  
j 0 xi  x j
j i

x x0 x1
y= f(x) y0 y1
Department of Computer Science 17
 Lagrange functions

 The Lagrange function is given below.

 n x  xj i=0,1,……n
Li ( x)  
j 0 xi  x j
j i
 Solution:
 Since we have two points, therefore we have to
find the Lagrange function(polynomial) of first
degree from given points.
 Here i = 0 and 1, so we find L0(x) and L1(x)

Department of Computer Science 18

 Lagrange functions

 These polynomials have the following properties:

 L0(x0)=1 L0(x1)=0
 L1(x0)=0 L1(x1)=1
 i.e.

 the Kronecker delta function.

Department of Computer Science 19

 Example

 Determine L0(x) and L1(x) using the points (2, 4)

and (5, 1).
 Solution: We are given the following data
points:
x x0 = 2 x1 = 5
y= f(x) y0 = 4 y1 = 1

Department of Computer Science 20

 Lagrange functions

 Assume three data points (x0, y0),(x1, y1),(x2, y2),

with x0, x1, x2 distinct. Construct the Lagrange
interpolation basis functions
 Solution: Since we have three points, therefore
we have to find the Lagrange
function(polynomial) of 2nd degree(quadratic)
from given points.
 Here i = 0, 1 and 2, so we find L0(x), L1(x) and
L2(x)

Department of Computer Science 21

 Lagrange functions

 The formula for Lagrange interpolation basis

functions is given by
n x  xj i =0,1,2
Li ( x)  
j 0 xi  x j
j i

Each Li(x) has degree 2

Department of Computer Science 22
 Example

 Use the numbers (called nodes) x0 = 2, x1 =

2.75 and x2 = 4 to find the second Lagrange
polynomial
 Solution: We have to compute L0(x), L1(x), and
L2(x) which are given by

Department of Computer Science 23

 Example

 Solution: We have to compute the following

x0 = 2, x1 = 2.75 and x2 = 4

Department of Computer Science 24

 General Lagrange functions

 The basic Lagrange polynomial of degree n is given by.

 The key thing to notice is that the numerator

of Lk(x) contains the entire sequence of factors (x – x1), (x –
x2), (x – x3), ……………….. (x – xn), with the exception of the
single factor (x – xk).
 Likewise, the denominator contains the entire sequence of
factors (xk – x1), (xk – x2), (xk – x3), ... (xk – xn), with the
exception of the single factor (xk – xk).

Department of Computer Science 25

The Lagrange Polynomial: The Linear Case

Department of Computer Science 26

The Lagrange Polynomial: The Linear Case

Department of Computer Science 29

 Example

Department of Computer Science 30

 Example

Department of Computer Science 31

 Your Turn

 For the data points (2, 3) and (5, 7) find P1(x).

Department of Computer Science 32

 Upshot

 For two points, (x0, y0), and (x1, y1), the first-
order Lagrange polynomial that passes through
the points has the form:

Department of Computer Science 33

The Lagrange Polynomial: The Quadratic Case

 For three data points the interpolating

polynomial is taken to be a quadratic

 P(x) = f0L0(x) + f1L1(x) + f2L2(x)

Department of Computer Science 34

 Example

 P(x) = f0L0(x) + f1L1(x) + f2L2(x)

Department of Computer Science 35

 Your Turn

 Construct P2 from the data points (0,−1), (1,−1),

(2, 7).

Department of Computer Science 36

The Lagrange Polynomial: The Cubic Case

 For four data points the interpolating polynomial

is taken to be a cubic

 P(x) = f0L0(x) + f1L1(x) + f2L2(x) + f3L3(x)

Department of Computer Science 37

 Your Turn

 Find the polynomial P(x) passing through the

points (0, 2), (1, 3), (2, 12), (5, 147) and
compute P (3) and P (4).

 P(x) = f0L0(x) + f1L1(x) + f2L2(x) + f3L3(x)

Department of Computer Science 38

The Lagrange Polynomial: The General Case

 Then P(x) =f0L0(x)+f1L1(x)+…fnLn(x)

 We would have P(xk)=fk for k=0,…,n.
 P(x) is called the nth Lagrange interpolating
polynomial.
 The above equation can be written in a compact
form using summation and product notation as:

 Where are called the Lagrange

functions.
Department of Computer Science 39
The Lagrange Polynomial: The General Case

Department of Computer Science 40

 Excercise

Department of Computer Science 41

 Excercise

Department of Computer Science 42

 Remark

 The application of the Lagrange formula

becomes quite lengthy and difficult if number of
values in the data is more than four.
 It can be seen that inclusion of a point in the
data list leads to add one more term in the
formula and the numerator and denominator of
each term get changed.
 Hence, it is not advisable to use Lagrange
formula for more than four points in the data
set.
 To overcome this problem, we prefer to use the
Newton’s divided difference formula
Department of Computer Science 43
 Divided Differences

 When the arguments are not equi-spaced, we

use divided differences.
 Let y = f(x) be a function whose functional form
is not known but its values at (n+1) points,
namely, x0 , x1, … xn are known.
 The divided difference of first order for the
points x0, x1 is defined as:

 This is the discrete version of the derivative of a

function f(x).
Department of Computer Science 44
 2nd Divided Differences

 For the points x0, x1, x2 the divided difference of

second order is defined as

Department of Computer Science 45

 nth Divided Differences

 In the similar manner, the divided difference of

nth order for the points x0, x1 , … xn is defined
as:

Department of Computer Science 46

 Divided Difference Table

 The divided difference tables with 6 arguments

are as follows:

Department of Computer Science 47

 Divided Difference Table

 The divided difference tables with 5 arguments

are as follows:

Department of Computer Science 48

 Example

 Obtain the divided difference table for the

function y = f(x) given by

 Solution: The divided difference tables with 4

arguments are as follows:

Department of Computer Science 49

 Your Turn

Department of Computer Science 50

 Your Turn

 Obtain the divided difference table for the

function y = f(x) given by

Department of Computer Science 51

 NDD Interpolation

 Newton’s Divided Difference Interpolating

Polynomial Or Newton’s Form

Department of Computer Science 52

 NDD Interpolation

 The polynomial Pn is called Newton’s divided

deference formula for the interpolating
polynomial or Newton’s form for the
interpolating polynomial.
 Note that Pn(xi) = f(xi).

Department of Computer Science 53

 Example

 Determine the Newton form for the interpolating

polynomial for the data set {(−1, 5), (0, 1), (1,
1),
 Then use this polynomial to approximate y if x =
1.5.
 Solution

Department of Computer Science 54

 Example

Department of Computer Science 55