Interpolation and Approximation: Numerical Differentiation and Regression

INTERPOLATION

Introduction

• The process of estimating intermediate values between given data points is called Interpolation .
• The most common method used for this purpose is Polynomial Interpolation.

Find the functional value for 𝑥 = 2.5 , i.e. 𝑓 2.5 = ? Is this a problem of Interpolation or extrapolation??

𝑥	1	3	4	6	9
𝑓(𝑥)	4	16	43	67	23

Solution:
Step 1: Obtain the polynomial equation using tabular data points.
Suppose we got our polynomial as,
𝑓 𝑥 = 4𝑥
4 + 3𝑥
2 + 2
Step 2 : Now, put 𝑥 = 2.5 in the above expression of 𝑓 𝑥 which gives the desired answer

Note: The number of data points minus one defines the order of interpolation. If n number of data points are given, the order of the polynomial will be n-1.

Linear Interpolation

• Connecting two data points with a straight line.
• Suppose we are given two data points (𝑥₁, 𝑓 𝑥₁ ) and (𝑥₂, 𝑓 𝑥₂ ) .
• We are going to derive the formula which helps to calculate 𝑓 𝑥 for the given 𝑥 where 𝑥₁ ≤ 𝑥 ≤ 𝑥₂ .

Let us find the equation of straight line from the given two points (𝑥₁, 𝑓 𝑥₁ ) and (𝑥₂, 𝑓 𝑥₂ ) .

Demerits of Linear Interpolation

• Linear Interpolation uses first order polynomial (i.e. straight line) to approximate the function.
• To reduce this error, we need to use higher order polynomial.

Lagrange Interpolation Polynomial

• Let 𝑥₀, 𝑓₀ , 𝑥₁, 𝑓₁ , and 𝑥₂, 𝑓₂ are the given data points.

x	𝑥0	𝑥1	𝑥2
f	𝑓0	𝑓1	𝑓2

Here, number of data points = 3 , so the polynomial will be of the order 2.

• Let us consider a second order polynomial of the form 𝑝₂ 𝑥 = 𝑏₁ 𝑥 − 𝑥₀ 𝑥 − 𝑥₁ + 𝑏₂ 𝑥 − 𝑥₁ 𝑥 − 𝑥₂ + 𝑏₃ 𝑥 − 𝑥₂ 𝑥 − 𝑥₀ ………………..[1] where 𝑏₁, 𝑏₂ 𝑎𝑛𝑑 𝑏₃ 𝑎𝑟𝑒 𝑡ℎ𝑒 𝑐𝑜𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑠 𝑜𝑓 𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙.
• Given points 𝑥₀, 𝑓₀ , 𝑥₁, 𝑓₁ , and 𝑥₂, 𝑓₂ should satisfy the equation 1.
• At 𝑥 = 𝑥_𝑜, 𝑝₂ 𝑥₀ = 𝑓_𝑜,

Similarly, for 𝑥 = 𝑥₁, 𝑝₂ 𝑥₁ = 𝑓₁  

Example 2.1
For the following data ,use Lagrange interpolation polynomial to find 𝑦 𝑎𝑡 𝑥 = 3.2.

x	1	2	4	5
y	4	9	61	120

Solution: Here, 𝑥₀ = 1, 𝑥₁ = 2, 𝑥2 = 4, 𝑥₃ = 5 , 𝑓₀ = 4, 𝑓₁ = 9, 𝑓₂ = 61, 𝑓₃ = 120

Now,

Newton Interpolation Polynomial

• The Newton form of polynomial is 𝒑_𝒏 (𝒙) = 𝒂_𝟎+ 𝒂_𝟏𝒙 − 𝒙_𝟎 + 𝒂_𝟐 𝒙 − 𝒙_𝟎 𝒙 − 𝒙_𝟏 + 𝒂_𝟑 𝒙 − 𝒙_𝟎 𝒙 − 𝒙_𝟏 𝒙 − 𝒙_𝟐… … … … … . . +𝒂_𝒏 𝒙 − 𝒙_𝟎 𝒙 − 𝒙_𝟏 … . . (𝒙 − 𝒙_𝒏−𝟏)
• For given 𝑥₀, 𝑓₀ , 𝑥₁, 𝑓₁ , 𝑥₂, 𝑓₂ … … … (𝑥_𝑛, 𝑓_𝑛), we need to find the value of coefficients 𝑎₀, 𝑎₁, 𝑎₂, 𝑎₃ … … … . . 𝑎_𝑛.

✓ If only two data points 𝑥0, 𝑓0 , 𝑥1, 𝑓1 are given, 𝒑𝟏 𝒙 = 𝒂𝟎+ 𝒂𝟏 𝒙 − 𝒙𝟎 → 𝟏𝒔𝒕 𝒐𝒓𝒅𝒆𝒓 𝒑𝒐𝒍𝒚𝒏𝒐𝒎𝒊𝒂𝒍 ✓ If three data points 𝑥0, 𝑓0 , 𝑥1, 𝑓1 , 𝑥2, 𝑓2 are given 𝒑𝟐 𝒙 = 𝒂𝟎 + 𝒂𝟏 𝒙 − 𝒙𝟎 + 𝒂𝟐 𝒙 − 𝒙𝟎 𝒙 − 𝒙𝟏 → 𝟐𝒏𝒅 𝒐𝒓𝒅𝒆𝒓 𝒑𝒐𝒍𝒚𝒏𝒐𝒎𝒊𝒂𝒍 ✓ Similarly, for four data points 𝑥0, 𝑓0 , 𝑥1, 𝑓1 , 𝑥2, 𝑓2 𝑥3, 𝑓3 , 𝒑𝟑 𝒙 = 𝒂𝟎 + 𝒂𝟏 𝒙 − 𝒙𝟎 + 𝒂𝟐 𝒙 − 𝒙𝟎 𝒙 − 𝒙𝟏 + 𝒂𝟑(𝒙 − 𝒙𝟎)(𝒙 − 𝒙𝟏)(𝒙 − 𝒙𝟐) → 𝟑𝒓𝒅 𝒐𝒓𝒅𝒆𝒓 𝒑𝒐𝒍𝒚𝒏𝒐𝒎𝒊𝒂𝒍

• For 𝑥 = 𝑥₀, 𝑝_𝑛 (𝑥₀ )= 𝑓₀ , we will get 𝑓₀ = 𝑎₀ . 𝑎₀ = 𝑓₀
• For 𝑥 = 𝑥₁, 𝑝_𝑛 (𝑥₁ ) = 𝑓₁ 

or,  𝑓₁ = 𝑎₀ + 𝑎₁ 𝑥₁ − 𝑥₀

or, 𝑓1 = 𝑓₀ + 𝑎₁ 𝑥₁ − 𝑥₀ [since 𝑎₀ = 𝑓₀]

𝑓₂ = 𝑎₀ + 𝑎₁ 𝑥₂ − 𝑥₀ + 𝑎₂(𝑥₂ − 𝑥₀)(𝑥₂ − 𝑥₁) which gives

Newton Divide Difference Table

The alternative way of finding the coefficients (𝑎0, 𝑎1, 𝑎2 𝑎𝑛𝑑 𝑠𝑜 𝑜𝑛) value is to use Newton divided difference table. For given 𝑥₀, 𝑓₀ , 𝑥₁, 𝑓₁ , 𝑥₂, 𝑓₂ , 𝑥₃, 𝑓₃ 𝑎𝑛𝑑 (𝑥₄, 𝑓₄)

Example 2.2

Find the functional value for 𝑥 = 7 using Newton interpolation polynomial.

x	5	6	9	11
𝑓(𝑥)	12	13	14	16

Solution: Since 4 data points are given, the required polynomial will be of the order 3.

 𝒑_𝟑 (𝒙) = 𝒂_𝟎 + 𝒂_𝟏 𝒙 − 𝒙_𝟎 + 𝒂_𝟐 𝒙 − 𝒙_𝟎 𝒙 − 𝒙_𝟏 + 𝒂_𝟑 𝒙 − 𝒙_𝟎𝒙 − 𝒙_𝟏 𝒙 − 𝒙_𝟐

To get the value of 𝑎₀, 𝑎₁, 𝑎₂, 𝑎₃ 𝑎𝑛𝑑 𝑎₄ , we are going to use Newton divided difference table.

Newton Forward Difference /Newton Backward Difference [Interpolation with equidistant points]

• Particularly used when the functional values are given at a sequence of equally spaced points.
• Also called as Newton Gregory technique.

Scenario 1:

x	5	6	9	11
𝑓(𝑥)	12	13	14	16

𝐻𝑒𝑟𝑒, 𝑥₁ − 𝑥₀ = 6 − 5 = 1 𝑤ℎ𝑒𝑟𝑒𝑎𝑠, 𝑥₂ − 𝑥₁ = 9 − 6 = 3 Not equally spaced. We can’t use Newton Forward/Backward Difference. Rather, we need to rely on Lagrange or Newton Interpolation polynomial.

Scenario 2:

x	10	20	30	40	50
𝑓(𝑥)	0	7	26	63	124

Here, 𝒙 values are equally spaced. In this case we can use Newton forward difference or Newton backward difference.
𝑠𝑡𝑒𝑝 𝑠𝑖𝑧𝑒 ℎ = 10

• If required point is close to the start of the table, use Newton forward difference. 𝐴𝑡 𝑥 = 15, 𝑓 (𝑥) = ? 𝑜𝑟 𝐴𝑡 𝑥 = 25, 𝑓 𝑥 = ? [ First value of 𝒙 (𝐢. 𝐞. 𝑥₀) acts as a reference point ]
• If required point is close to the end of the table , use Newton backward difference. 𝐴𝑡 𝑥 = 48, 𝑓 𝑥 =? 𝑜𝑟 𝐴𝑡 𝑥 = 35, 𝑥 = ? [ Last value of 𝒙 (𝐢. 𝐞. 𝑥_𝑛) acts as a reference point ]
• Simple difference is used here rather than divided difference which was used in Newton divided difference table. 𝑓₁ − 𝑓₀ = 1𝑠𝑡 𝑜𝑟𝑑𝑒𝑟 𝑠𝑖𝑚𝑝𝑙𝑒 𝑑𝑖𝑓𝑓𝑒𝑟𝑒𝑛𝑐𝑒

Newton Forward Difference

Let us create a forward difference table for given 𝑥₀, 𝑓₀ , 𝑥₁, 𝑓₁ , 𝑥₂, 𝑓₂ , 𝑥₃, 𝑓₃ 𝑎𝑛𝑑 (𝑥₄, 𝑓₄)

Then, the Newton forward difference formula is given by,

Example 2.3:

Estimate the value of 𝑠𝑖𝑛𝜃 𝑎𝑡 𝜃 = 25⁰ using Newton-Gregory forward difference formula.

𝜃	10	20	30	40	50
sin(𝜃)	0.1736	0.3420	0.5000	0.6428	0.7660

Solution: Let us draw a Newton forward difference table to find the value of coefficients

𝒇_𝟎 = 𝟎. 𝟏𝟕𝟑𝟔 , ∆𝒇_𝟎 = 𝟎. 𝟏𝟔𝟖𝟒, ∆ ^𝟐𝒇_𝟎 = −𝟎. 𝟎𝟏𝟎𝟒 , ∆ ^𝟑𝒇_𝟎 = −𝟎. 𝟎𝟎𝟒𝟖, ∆ ^𝟒𝒇_𝟎 = 𝟎. 𝟎𝟎𝟎4

Newton forward difference formula is given by,

= 0.422665625

Newton Backward Difference

Let us create a forward difference table for given 𝑥₀, 𝑓₀ , 𝑥₁, 𝑓₁ , 𝑥₂, 𝑓₂ , 𝑥₃, 𝑓₃ 𝑎𝑛𝑑 (𝑥₄, 𝑓₄)

Then, the Newton backward difference formula is given by,

Example 2.4
Estimate the value of 𝑠𝑖𝑛𝜃 𝑎𝑡 𝜃 = 45 ⁰using Newton-Gregory backward difference formula.

𝜃	10	20	30	40	50
sin(𝜃)	0.1736	0.3420	0.5000	0.6428	0.7660

Solution: Let us draw a Newton backward difference table to find the value of coefficients

From table, 𝑓₄ = 0. 7660, 𝛻𝑓₄ = 0.1232, 𝛻 ² 𝑓₄ = −0. 0196, 𝛻 ³ 𝑓₄ = −0.0044, 𝑎𝑛𝑑 𝛻 ⁴ 𝑓₄ = 0.0004

Newton backward difference formula is given by

= 0.707509

NUMERICAL DIFFERENTIATION

Numerical Differentiation

• Numerical differentiation is the process of computing the value of the derivative of an explicitly unknown function, with given discrete set of points(𝑥_𝑖 , 𝑓_𝑖) .
• To differentiate a function numerically, we first determine an interpolating polynomial and then compute the approximate derivative at the given point.
• If 𝑥_𝑖 ’s are equispaced use Newton’s forward/backward interpolation formula to find the derivative.
• If 𝑥_𝑖 ’s are not equispaced, we may find using Newton’s divided difference method or Lagrange’s interpolation formula and then differentiate it as many times as required.

Problem Scenario: The following table gives the displacement, x (cm) of an object at various of time ,t(seconds). Find the velocity and acceleration of the object at t=1.2 sec. Use suitable interpolation method. t 1.0 1.2 1.4 1.6 1.8 x 9.0 9.5 10.2 11.0 13.2

Numerical Derivatives using Newton Forward Interpolation

Newton forward interpolation formula is given by,

Numerical Derivatives using Newton Backward Interpolation

For given 𝑥₀, 𝑓₀ , 𝑥₁, 𝑓₁ , 𝑥₂, 𝑓₂ , 𝑥₃, 𝑓₃ 𝑎𝑛𝑑 (𝑥₄, 𝑓₄) , Newton backward interpolation formula is given by

Example 2.5

x	0	1	2	3
y	5	6	3	8

Solution:

Newton difference table,

Formula for Newton forward interpolation is given by,

Example 2.6 Following table gives the census population of a state for the 1961 to 2001.

Year	1961	1971	1981	1991	2001
Population(million)	19.96	36.65	58.81	77.21	94.61

Find the rate of growth of the population in the year 2001.
Solution: since given table is equi-spaced (h=10) and rate of growth is asked for 2001, we have to
use Newton backward interpolation.

𝑓₄ = 94.61, ∇ 𝑓₄ = 17.40, ∇ ₂ 𝑓₄ = −1, ∇ ₃ 𝑓₄ = 2.76, ∇ ₄ 𝑓₄ = 11.99

Newton Backward Interpolation formula is give by,

Example 2.7 Compute f ’(3.5) and f ’’(4) given that f(0)=2, f(1)=3, f(2)=12, and f(5)=147

Solution:

x	0	1	2	5
y	2	3	12	147

Since 𝑥𝑖 ′s values are not equally spaced, we have to use either Lagrange or Newton divided difference formula.

Let us draw Newton divide difference table,

From table, 𝑎₀ = 2, 𝑎₁ = 1, 𝑎₂ = 4, 𝑎₃ = 1

Newton interpolation formula is given by,

 𝑓( 𝑥) = 𝑝₃( 𝑥 )= 𝑎₀ + 𝑎₁ 𝑥 − 𝑥₀ + 𝑎₂ 𝑥 − 𝑥₀ 𝑥 − 𝑥₁ + 𝑎₃(𝑥 − 𝑥₀)(𝑥 − 𝑥₁)(𝑥 − 𝑥₂)

Substituting the value of coefficients,

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

 𝑓 (𝑥) = 𝑥 ³ + 𝑥 ² − 𝑥 + 2