NUMERICAL METHODS

FOR MECHANICAL
ENGINEERS
INTERPOLATION
Dr. Kais Hbaieb
ME 301
Introduction

The most common method for Estimation of

intermediate values between precise data points
is polynomial interpolation. :
f (x)  a0  a1 x  a2 x 2 … an x n

 Polynomial interpolation is used when the point

determined are very precise. The curve
representing the behavior has to pass through
every point.
 There is one and only one nth-order polynomial
that fits n+1 points
Introduction

n=3 n=4
n=2

First order (linear) 2nd order (quadratic) 3rd order (cubic)

Introduction

There are a variety of mathematical formats in

which this polynomial can be expressed:
 The Newton polynomial (sec. 18.1)
 The Lagrange polynomial (sec. 18.2)
 Lagrange Interpolating Polynomials

• The general form for n+1 data points is:

n
f n (x)   Li (x) f (xi )
i0
n x  xj
Li (x)  P
j0 xi  x j
ji

designates the “product of”

Lagrange Interpolating
Polynomials
• Linear version (n = 1):
Used for 2 points of data: (xo,f(xo)) and (x1,f(x1)),

x  x1 x  x0
f1(x)  f (x 0 )  f (x1 )
x0  x1 x1  x0

Lo (x) L1(x)
Lagrange Interpolating
Polynomials

• Second order version (n = 2):

f 2 (x) 
x  x1 x  x2  f (x ) Lo (x) , j ≠ 0
x0  x1 x0 x 2  0

x  x 0 x  x 2 
f (x1) L1 (x) , j ≠1
x1  x0 x1 x 2 
x  x0 xx1 f (x )
 L2 (x) , j ≠ 2
x2  x0 x2 x1 2
Lagrange Interpolating Polynomials - Example

Use a Lagrange interpolating polynomial of the

first and second order to evaluate ln(2) on the
basis of the data:

x0  1 f ( x 0 )  ln(1)  0
x1  4 f ( x1)  ln(4)  1.386294
x2  6 f (x 2)  ln(6)  1.791760
Lagrange Interpolating Polynomials – Example
(cont’d)
• First orderpolynomial:

x  x1 x  x0
f 1(x)  f (x 0 )  f (x1)
x0  x1 x1  x0
24 2 1
f 1(2)  0  1.386294  0.4620981
1 4 4 1
Lagrange Interpolating Polynomials –
Example (cont’d)
• Second order polynomial:

x  x1 x  x2 x  4 x 6
Lo( x)    
xo  x1 xo  x2 0  4 0 6
x  xo  x  x2  x  0 x  6
L1( x) 
x1  xo x1  x2 4  0 4 6
x  xo x  x1 x  0 x  4
L2( x)    
x2  xo x2  x1 6  0 6  4
 Lagrange Interpolating Polynomials – Example
(cont’d)
n n x  xj
f n (x)   Li (x) f (xi ) Li ( x) P ( j ≠ i)
i0 j0 xi  x j
(2  4)(2  6)
f 2 (2)  0
(1 4)(16)
(2 1)(2  6)
 1.386294
(4 1)(4  6)
(2 1)(2  4)
 1.791760  0.5658444
(6 1)(6  4)
Lagrange Interpolating Polynomials
– Example (cont’d)
Pseudocode – Lagrange
interpolation
Coefficients of an Interpolating
Polynomial
• Although “Lagrange” polynomials are well suited for
determining intermediate values between points, they
do not provide a polynomial in conventionalform:

f (x)  a0  a1 x  a2 x 2 … a x x n
• Since n+1 data points are required to determine n+1
coefficients, simultaneous linear systems of equations
can be used to calculate “ a ”s.
Coefficients of an Interpolating
Polynomial (cont’d)

f (x0 )  a0  a1 x0  a2 x02 … an x0n

f (x1 )  a0  a1x1  a x … a x
2
2 1
n
n 1

f (xn )  a0  a1 xn  a 2 xn2 … an xnn

Where “x”s are the knowns and “a”s are the

unknowns.
Possible divergence of an extrapolated
production
Spline Interpolation

• Polynomials are the most common choice of

interpolants.
• There are cases where polynomials can lead to
erroneous results because of round off errorand
overshoot.
• Alternative approach is to apply lower-order
polynomials to subsets of data points. Such
connecting polynomials are called spline functions.
Why Spline Interpolation?

Apply lower-order polynomials to subsets of data points.

Spline provides a superior approximation of the behavior of functions
that have local, abrupt changes.
18
 Spline Interpolation
The concept of spline is using a thin , flexible strip
(called a spline) to draw smooth curves through aset
of points….natural spline(cubic)
Linear Spline

The first order splines for a group of ordered data

points can be defined as a set of linear functions:

f (x)  f (x0 ) m0(x  x0)

f (x)  f (x1)  m1(x  x1)

f (x)  f (xn1)mn1(x xn1)

f (xi1 )  f(xi )
mi 
xi1  xi
Linear spline - Example
Fit the following data with first order splines.
Evaluate the function at x =5.
2.5 1
x f(x) m 0.6
7  4.5
3.0 2.5 f (5)  f (4.5)  m(5  4.5)
4.5 1.0  1.0  0.6 0.5
7.0 2.5
9.0 0.5  1.3
Linear Spline
• The main disadvantage of linear spline is that they are
not smooth. At the data points where 2 splines meets
called (a knot), the slope changesabruptly.

• The first derivative of the function is discontinuousat

these points.

• Using higher order polynomial splines ensure

smoothness at the knots by equating derivatives at
these points.
Quadratic Splines
• Objective: to derive a second order polynomial for each
interval between data points. f i(x)  a i x 2  bi x  ci
• Terms: Interior knots and end points

For n+1 data points:

•i = (0, 1, 2, …n),
• n intervals,
•3n unknown
constants (a’s, b’s and
c’s)
Quadratic Splines
1. The function values of adjacent polynomial
must be equal at the interior knots 2(n-1).
ai1 xi1  bi1 xi1  ci1  f i (xi1 ) i  2, 3, 4,...,n
2

ai xi1  bi xi1  ci  fi (xi 1 )

2
i  2, 3, 4,...,n

2. The first and last functions must pass through

the end points (2).
a1 x0 2  b1 x0  c1  f (x0 )
a x 2  b x  cn  f (xn )
n n n n
Quadratic Splines
• The first derivatives at the interior knots
must be equal (n-1).
f i ' (x)  2ai x  bi
2ai1xi1  bi1  2ai xi1  bi
• Assume that the second derivate is zero at
the first point (1)
a1  0
(The first two points will be connected by a straight line)
Quadratic Splines - Example

Fit the following data with quadratic splines.

Estimate the value at x = 5.
x 3.0 4.5 7.0 9.0
f(x) 2.5 1.0 2.5 0.5

Solutions:
There are 3 intervals (n=3), 9 unknowns.
Quadratic Splines - Example
1. Equal interior points:
For first interior point (4.5, 1.0)
The 1st equation:
x 2 a  x b  c  f (x )
1 1 11 1 1

(4.5)2 a1  4.5b1  c1  f (4.5) 20.25 a1  4.5b1  c1 1.0

The 2nd equation:

x 2a  x b  c  f (x )
1 2 1 2 2 1

(4.5)2 a2  4.5b2  c2  f (4.5) 20.25a2  4.5b2  c2  1.0

Quadratic Splines - Example

For second interior point (7.0, 2.5)

The 3rd equation:

x2 a  x b  c  f (x )
2 2 2 2 2 2

(7)2 a  7b  c  f (7) 49a2  7b2  c2  2.5

2 2 2

The 4th equation:

x 2 a  x b  c  f (x )
2 3 2 3 3 2

(7)2 a  7b  c  f (7) 49a3  7b3  c3  2.5

3 3 3
Quadratic Splines - Example

First and last functions pass the end points

For the start point (3.0, 2.5)

x 2 a  x b  c  f (x ) 9a1  3b1  c1  2.5
0 1 0 1 1 0

For the end point (9, 0.5)

x 2a  x b  c  f (x ) 81a3  9b3  c3 0.5

3 3 3 3 3 3
Quadratic Splines - Example
Equal derivatives at the interior knots.
For first interior point (4.5, 1.0)
2x1 a1  b1  2x1 a2  b2 9a1  b1  9a2 b2

For second interior point (7.0, 2.5)

2x2a2  b2  2x3 a3  b3 14a2  b2  14a3 b3

Second derivative at the first point is 0

f '' (x0 )  a1  0
Quadratic Splines - Example
Quadratic Splines - Example
Quadratic Splines - Example
Solving these 8 equations with 8 unknowns
a1  0, b1  1, c1  5.5 f3(x)
a2  0.64, b2  6.76, c2  18.46 f1(x)
f2(x)

a3  1.6, b3  24.6, c3  91.3

f1(x)  x  5.5, 3.0 x  4.5

f2 (x)  0.64x2  6.76x 18.46, 4.5 x 7.0

f3 (x)  1.6x 2  24.6x  91.3, 7.0 x  9.0

Cubic Splines
Objective: to derive a third order polynomial for
each interval between data points.
Terms: Interior knots and end points
f (x)  a x3  b x2  c x  d
i i i i i

For n+1 data points:

• i = (0, 1, 2, …n),
• n intervals,
• 4n unknown constants (a’s, b’s ,c’s and d’s)
Cubic Splines
• The function values must be equal at the interior knots
(2n-2).
• The first and last functions must pass through the end
points (2).
• The first derivatives at the interior knots must beequal
(n-1).
• The second derivatives at the interior knots must be
equal (n-1).
• The second derivatives at the end knots are zero (2), (the 2nd
derivative function becomes a straight line at the end points)
Alternative technique to get
Cubic Splines
• The second derivative within each interval [ xi-1, xi ] is a straight line. (the 2nd
derivatives can be represented by first order Lagrange interpolating
polynomials.

A straight line
x  xi x  xi1
f i (x)  f i (xi1 )  f i (xi )
'' '' '' connecting the first
xi 1  xi xi  xi1 knot f’’(xi-1) and the
second knot f’’(xi)

The second derivative at any point x within the interval

Cubic Splines
• The last equation can be integrated twice
2 unknown constants of integration can be evaluated by
applying the boundaryconditions:
1. f(x) = f (xi-1) at xi-1
2. f(x) = f (xi) at xi
Unknowns:

f ''(xi )

f ''(x i1 )
i = 0, 1,…, n
 Cubic Splines
• For each interior point xi (n-1): f'(x
i1 i
)  f
i
'
(x )
i

(x  x ) f '' (x )  2(x  x ) f '' (x )

i i1 i1 i1 i1 i

 (x  x ) f '' (x )  6
f (xi1 )  f (xi )
i1 i i1
xi 1  xi


6
f (xi1 )  f (xi )
xi  x i1

This equation result with n-1 unknown second

derivatives where, for boundarypoints:
f”(xo) =f”(xn) = 0
Cubic Splines - Example

Fit the following data with cubic splines

Use the results to estimate the value atx=5.

x 3.0 4.5 7.0 9.0

f(x) 2.5 1.0 2.5 0.5

Solution:
 Natural Spline:
f '' (x )  f '' (3)  0, f '' (x )  f '' (9)  0
0 3
Cubic Splines - Example
 For 1st interior point (x1 =4.5)
x 3.0 4.5 7.0 9.0
f(x) 2.5 1.0 2.5 0.5
- xi  xi1  x1  x0  4.5  3.0  1.5
- xi1  xi 1  x2  x0  7  3.0  4
- xi1  xi  x2  x1  7  4.5  2.5
Apply the following equation:
(x  x ) f '' (x )  2(x  x ) f '' (x )  (x  x ) f ''
(xi1 )
i i1 i1 i1 i1 i i1 i


6
f (x i1 )  f (x i ) 6
f (x i1 )  f (x i )
xi1  xi xi  xi1
Cubic Splines - Example
6 6
1.5 f '' (3)  2 4 f '' (4.5)  2.5 f '' (7)  (2.5 1)  (2.5 1)
2.5 1.5
Since f '' (3)  0
8 f '' (4.5)  2.5 f '' (7)  9.6 .............. (eq.1)

For 2nd interior point (x2 = 7 )

x 3.0 4.5 7.0 9.0

f(x) 2.5 1.0 2.5 0.5
xi  xi1  x2  x1  7  4.5  2.5
xi 1  xi1  x3  x1  9  4.5  4.5

xi 1  xi  x3  x2  9  7 2
Cubic Splines - Example
Apply the following equation:
(x  x ) f '' (x )  2(x  x ) f '' (x )  (x  x ) f '' (x )
i i1 i1 i1 i1 i i1 i i1


6
f (xi1 )  f (xi ) 6
f (x i1 )  f (x i )
xi1  xi xi  xi1
6 6
2.5 f '' (4.5)  2 4.5 f '' (7)  2 f '' (9)  (0.5  2.5)  (1 2.5)
2 2.5
Since f '' (9)  0

2.5 f '' (4.5)  9 f '' (7)  9.6 ............. (equ 2)

Cubic Splines - Example

f1(x)  0.186566(x  3)3 1.6667 (4.5  x)  0.24689(x  3)

Cubic Splines - Example
The 2nd interval (i =2), apply for the equation:
1.67909 1.53308  1  1.67909(2.5) 7  x
f 2 (x)  (7  x) 3  (x  4.5) 3   
6(2.5) 6(2.5) 2.5 6
2.5 1.53308(2.5) 
  (x  4.5)
2.5 6 


f 2 (x)  0.111939(7 x) 3  0.102205 (x  4.5)3  0.29962(7  x) 1.638783(x  4.5)

The 3rd interval (i =3),

f3 (x)  0.127757(9  x) 3 1.761027 (9  x)  0.25(x  7)

For x = 5: f2 (x)  f 2 (5)  1.102886