0% found this document useful (0 votes)
47 views

Unit 6 (Interpolation)

This document summarizes key points about interpolation from a lecture on numerical methods. It discusses: - Linear interpolation using a first-order polynomial to connect two points - Quadratic interpolation using a second-order polynomial to connect three points - Newton's divided difference method for constructing polynomials of any order (n) to interpolate (n+1) data points - Examples are given of linear, quadratic, and cubic interpolation using Newton's method

Uploaded by

ebrahim5936
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
47 views

Unit 6 (Interpolation)

This document summarizes key points about interpolation from a lecture on numerical methods. It discusses: - Linear interpolation using a first-order polynomial to connect two points - Quadratic interpolation using a second-order polynomial to connect three points - Newton's divided difference method for constructing polynomials of any order (n) to interpolate (n+1) data points - Examples are given of linear, quadratic, and cubic interpolation using Newton's method

Uploaded by

ebrahim5936
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 36

Numerical Methods (CISE-301)

Unit-6
(Interpolation)
Dr. Muhammad Majid Gulzar (CIE-KFUPM)
Contents (Unit-6):
1) Newton’s Divided Difference Interpolating Polynomials (Sec 18.1)

2) Lagrange Interpolating Polynomials (Sec 18.2)

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Interpolation:

Data Set Regression Interpolation


Dr. Muhammad Majid Gulzar (CIE-KFUPM)
Interpolation:
 Interpolation was used for long time to provide an estimate of a tabulated function at
values that are not available in the table.

 What is sin(0.15)? 𝑥𝑥 𝑠𝑠𝑠𝑠𝑠𝑠(𝑥𝑥)


0 0.0000
 Using Linear Interpolation: sin(0.15) ≈ 0.1493
0.1 0.0998
 True Value: sin(0.15) = 0.1494
0.2 0.1987
0.3 0.2955
0.4 0.3894

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Interpolation:
 Linear Interpolation: Given any two points, there is
one polynomial of order ≤ 1 that passes through the
two points.

 Quadratic Interpolation: Given any three points there


is one polynomial of order ≤ 2 that passes through the
three points.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Interpolation:
 General formula for 𝑛𝑛𝑡𝑡𝑡 order polynomial is 𝑓𝑓 𝑥𝑥 = 𝑎𝑎0 + 𝑎𝑎1 𝑥𝑥 + 𝑎𝑎2 𝑥𝑥 2 + ⋯ + 𝑎𝑎𝑛𝑛 𝑥𝑥 𝑛𝑛 . For
(𝑛𝑛 + 1) data points, there is one and only one polynomial of order 𝑛𝑛 that passes through
all the points.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Interpolation:
 There is only one straight line (1𝑠𝑠𝑠𝑠 −order polynomial) that connects
two points.

 There is only one parabola (2𝑛𝑛𝑛𝑛 −order polynomial) connects a set of


three points.

 Polynomial interpolation consists of determining the unique


𝑛𝑛𝑡𝑡𝑡 −order polynomial that fits (𝑛𝑛 + 1) data points. This polynomial
then provides a formula to compute intermediate values.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Newton’s Divided Difference Interpolating
Polynomials (Sec 18.1)
Newton’s Divided Difference:
 Newton’s divided-difference interpolating polynomial is among the most popular and
useful forms
 Linear Interpolation

 Quadratic Interpolation

 General Form of Newton’s Interpolating Polynomials

 Errors of Newton’s Interpolating Polynomials

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Linear Interpolation:
 The simplest form of interpolation is to connect two data points with a straight line,
known as linear interpolation.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Linear Interpolation (Example):
Estimate the natural logarithm of 2 using linear interpolation. First, perform the computation by
interpolating between 𝑙𝑙𝑙𝑙 1 = 0 and 𝑙𝑙𝑙𝑙 6 = 1.791759. Then, repeat the procedure, but use a smaller
interval from 𝑙𝑙𝑛𝑛 1 = 0 to 𝑙𝑙𝑛𝑛 4 = 1.386294.
Note: The true value of 𝑙𝑙𝑙𝑙 2 is 0.6931472.

𝑙𝑙𝑙𝑙 1 −→ 𝑙𝑙𝑙𝑙 6

𝑙𝑙𝑙𝑙 1 −→ 𝑙𝑙𝑙𝑙 4

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Newton’s Divided Difference:
 Newton’s divided-difference interpolating polynomial is among the most popular and
useful forms
 Linear Interpolation

 Quadratic Interpolation

 General Form of Newton’s Interpolating Polynomials

 Errors of Newton’s Interpolating Polynomials

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Quadratic Interpolation:
 If three data points are available, means to introduce some curvature into the line, this
can be accomplished with a 2𝑛𝑛𝑛𝑛 −order polynomial (also called a quadratic/parabola).

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Quadratic Interpolation (Example):
Estimate the natural logarithm of 2 using second-order polynomial.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Quadratic Interpolation (Example):

b0 b1
b2
0.2027325

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Quadratic Interpolation (Example):

𝑥𝑥 𝑓𝑓[ ] 𝑓𝑓[ , ] 𝑓𝑓[ , , ]


0 -5 2 -4
xi yi
1 -3 6
-1 -15 0 −5

1 −3
−3 − (−5)
=2
1−0
−1 −15

𝑓𝑓(𝑥𝑥1 ) − 𝑓𝑓(𝑥𝑥0 )
𝑓𝑓[𝑥𝑥0 , 𝑥𝑥1 ] =
𝑥𝑥1 − 𝑥𝑥0

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Quadratic Interpolation (Example):

𝑥𝑥 𝑓𝑓[ ] 𝑓𝑓[ , ] 𝑓𝑓[ , , ]


0 -5 2 -4
xi yi
1 -3 6
-1 -15 0 −5

1 −3
−15 − (−3)
=6
−1 − 1
−1 −15

𝑓𝑓(𝑥𝑥2 ) − 𝑓𝑓(𝑥𝑥1 )
𝑓𝑓[𝑥𝑥1 , 𝑥𝑥2 ] =
𝑥𝑥2 − 𝑥𝑥1

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Quadratic Interpolation (Example):

𝑥𝑥 𝑓𝑓[ ] 𝑓𝑓[ , ] 𝑓𝑓[ , , ]


0 -5 2 -4
xi yi
1 -3 6
-1 -15 0 −5

1 −3
6−2
= −4
−1 − 0
−1 −15

𝑓𝑓[𝑥𝑥1 , 𝑥𝑥2 ] − 𝑓𝑓[𝑥𝑥0 , 𝑥𝑥1 ]


𝑓𝑓[𝑥𝑥0 , 𝑥𝑥1 , 𝑥𝑥2 ] =
𝑥𝑥2 − 𝑥𝑥0

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Quadratic Interpolation (Example):

𝑥𝑥 𝑓𝑓[ ] 𝑓𝑓[ , ] 𝑓𝑓[ , , ]


0 -5 2 -4
xi yi
1 -3 6
-1 -15 0 −5

1 −3

𝑓𝑓2 (𝑥𝑥) = −5 + 2(𝑥𝑥 − 0) − 4(𝑥𝑥 − 0)(𝑥𝑥 − 1) −1 −15

𝑓𝑓2 𝑥𝑥 = 𝑓𝑓 𝑥𝑥0 + 𝑓𝑓[𝑥𝑥0 , 𝑥𝑥1 ](𝑥𝑥 − 𝑥𝑥0 ) + 𝑓𝑓[𝑥𝑥0 , 𝑥𝑥1 , 𝑥𝑥2 ](𝑥𝑥 − 𝑥𝑥0 )(𝑥𝑥 − 𝑥𝑥1 )

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Quadratic Interpolation (Example):
𝑥𝑥 𝑦𝑦 xi yi 𝑥𝑥 𝑦𝑦 xi yi
1 0 3 1 1 0 2 3 3 1 2 3
2 3 5 2 3 1 0 4 1 0
3 8 3 8 3 8 3 8

𝑃𝑃2 (𝑥𝑥) = 0 + 3(𝑥𝑥 − 1) + 1(𝑥𝑥 − 1)(𝑥𝑥 − 2) 𝑃𝑃2 (𝑥𝑥) = 3 + 3(𝑥𝑥 − 2) + 1(𝑥𝑥 − 2)(𝑥𝑥 − 1)
𝑃𝑃2 (𝑥𝑥) = 𝑥𝑥 2 − 1 𝑃𝑃2 (𝑥𝑥) = 𝑥𝑥 2 − 1

𝑓𝑓[𝑥𝑥0 , 𝑥𝑥1 , 𝑥𝑥2 ] = 𝑓𝑓[𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥0 ] = 𝑓𝑓[𝑥𝑥2 , 𝑥𝑥1 , 𝑥𝑥0 ]

Ordering the points should not affect the interpolating polynomial

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Newton’s Divided Difference:
 Newton’s divided-difference interpolating polynomial is among the most popular and
useful forms
 Linear Interpolation

 Quadratic Interpolation

 General Form of Newton’s Interpolating Polynomials

 Errors of Newton’s Interpolating Polynomials

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


General Form:
 If 𝑛𝑛 + 1 data points are available, this can be accomplished with a 𝑛𝑛𝑡𝑡𝑡 − order
polynomial.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


General Form (Example):
Estimate the natural logarithm of 2 using third-order polynomial.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


General Form (Example):
Estimate the natural logarithm of 2 using third-order polynomial.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


General Form (Example):

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Newton’s Divided Difference:
 Newton’s divided-difference interpolating polynomial is among the most popular and
useful forms
 Linear Interpolation

 Quadratic Interpolation

 General Form of Newton’s Interpolating Polynomials

 Errors of Newton’s Interpolating Polynomials

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Errors:
 The equation of interpolating polynomial is similar to the Taylor series expansion in the
sense that terms are added sequentially to capture the higher-order behavior of the
underlying function.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Errors (Example):
Estimate error for natural logarithm of 2 using second-order polynomial.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


General Form (Class Activity):
Find a polynomial to interpolate the data.
𝑥𝑥 𝑓𝑓(𝑥𝑥)
𝑥𝑥 𝑓𝑓(𝑥𝑥) 𝑓𝑓[ , ] 𝑓𝑓[ , , ] 𝑓𝑓[ , , , ] 𝑓𝑓[ , , , , ] 2 3
2 3 1 −1.6667 1.5417 −0.6750 4 5
4 5 −4 4.5 −1.8333 5 1
5 1 5 −1 6 6
6 6 3
7 9
7 9

𝑓𝑓4 = 3 + 1(𝑥𝑥 − 2) − 1.6667(𝑥𝑥 − 2)(𝑥𝑥 − 4) + 1.5417(𝑥𝑥 − 2)(𝑥𝑥 − 4)(𝑥𝑥 − 5) − 0.6750(𝑥𝑥 − 2)(𝑥𝑥 − 4)(𝑥𝑥 − 5)(𝑥𝑥 − 6)

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Lagrange Interpolating Polynomials
(Sec 18.2)
Lagrange Interpolating Polynomials:
 The Lagrange interpolating polynomial is simply a reformulation of the Newton
polynomial that avoids the computation of divided differences.

Newton Interpolating Polynomial

Lagrange Interpolating Polynomial

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Lagrange Interpolating Polynomials:
 The Lagrange interpolating polynomial is simply a reformulation of the Newton
polynomial that avoids the computation of divided differences.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Lagrange Interpolation (Class Activity):
Estimate the natural logarithm of 2 for first and second-order
using Lagrange interpolating polynomial.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Lagrange Interpolation (Example):
 Each of the three terms passes through one of the data points and
is zero at the other two.
 The summation of the three terms must, therefore, be the unique
second-order polynomial that passes exactly through the three
points.

Dr. Muhammad Majid Gulzar (CIE-KFUPM)


Lagrange Interpolation (Class Activity):
Estimate the 𝑓𝑓(4) using
𝑥𝑥 𝑓𝑓(𝑥𝑥)
1) Lagrange Interpolating Polynomial
2 3
4 5
5 1
2) Newton’s Interpolating Polynomial 6 6
7 9

𝑓𝑓4 = 3 + 1(𝑥𝑥 − 2) − 1.6667(𝑥𝑥 − 2)(𝑥𝑥 − 4) + 1.5417(𝑥𝑥 − 2)(𝑥𝑥 − 4)(𝑥𝑥 − 5) − 0.6750(𝑥𝑥 − 2)(𝑥𝑥 − 4)(𝑥𝑥 − 5)(𝑥𝑥 − 6)

Dr. Muhammad Majid Gulzar (CIE-KFUPM)

You might also like