ASSIGNMENT: 2
NUMERICAL METHODS AND OPTIMIZATION
USING PYTHON
Name: Pankaj Kumar Section: 35/A
UID: 21BCS4385 Subject Code: 21CSH-459
AIM:
To study different types of polynomial interpolation methods (Lagrange and
Newton) and implement them using Python.
SOFTWARE REQUIREMENT:
Any Python IDE e.g., PyCharm, Google Colab
DESCRIPTION:
Polynomial interpolation is a method of estimating values between known data
points. It constructs a polynomial that passes through a given set of points (xi, yi).
Two commonly used methods for polynomial interpolation are Lagrange
Interpolation and Newton's Divided Difference Interpolation.
Methods Used For Polynomial Interpolation:
1. Lagrange Interpolation: It constructs a polynomial of degree n−1 given
nnn data points. The Lagrange polynomial for a set of points
(x0,y0),(x1,y1),…,(xn,yn) is defined as:
𝒏
𝑷(𝒙) = 𝐲𝐢 . 𝑳𝒊 (𝒙)
𝒊 𝟎
where the Lagrange basis polynomial Li(x) is:
𝑥-𝑥
𝐿 (𝑥) =
𝑥 -𝑥
,
Advantages:
Simple and easy to implement.
Disadvantages:
For large datasets, the calculation of Lagrange polynomials becomes
inefficient,
Modifying or adding a new data point requires recalculating the entire
polynomial.
2. Newton's Divided Difference Interpolation: Newton’s interpolation uses
divided differences to construct the polynomial. The interpolating polynomial in
Newton's form is:
𝑷(𝒙) = 𝒇[𝒙𝟎 ] + (𝒙 − 𝒙𝟎 )𝒇[𝒙𝟎 , 𝒙𝟏 ] + (𝒙 − 𝒙𝟎 )(𝒙 − 𝒙𝟏 )𝒇[𝒙𝟎 , 𝒙𝟏 , 𝒙𝟐 ]+. . . ..
where f [x0,x1,……,xn] are the divided differences, calculated as:
𝑓[𝑥 ] - 𝑓[𝑥 ]
𝑓[𝑥 , 𝑥 ] =
𝑥 -𝑥
Advantages:
Easy updating of the interpolation polynomial when new data points are
added,
The divided difference table can be computed incrementally.
Disadvantages:
The method is not as straightforward to understand and implement as
Lagrange interpolation.
ALGORITHM:
1. Define the Data Points: Choose the known data points (xi,yi).
2. Initialize Parameters: Define polynomial degree n = len(x) - 1.
3. Lagrange Interpolation: For each i, construct Lagrange basis polynomial
Li(x).
4. Newton’s Divided Difference Method: Compute divided differences
recursively. Construct Newton’s interpolation polynomial based on the
computed divided differences.
5. Plot the Solution: The interpolated polynomial and corresponding values at
desired points.
FLOWCHART:
START
INPUT DATA POINTS (x,y)
COMPUTE LAGRANGE
POLYNIMAL
COMPUTE NEWTON’S
DIVIDED DIFFERENCES
EVALUATE THE
POLYNOMIALS
END
CODE:
import numpy as np
import matplotlib.pyplot as plt
def lagrange_interpolation(x_vals, y_vals, x):
result = 0
for i in range(len(x_vals)):
term = y_vals[i]
for j in range(len(x_vals)):
if i != j:
term *= (x - x_vals[j]) / (x_vals[i] - x_vals[j])
result += term
return result
def newton_interpolation(x_vals, y_vals, x):
n = len(x_vals)
table = np.zeros((n, n))
table[:, 0] = y_vals
for j in range(1, n):
for i in range(n - j):
table[i][j] = (table[i+1][j-1] - table[i][j-1]) / (x_vals[i+j] - x_vals[i])
result = table[0, 0]
product_term = 1
for i in range(1, n):
product_term *= (x - x_vals[i-1])
result += product_term * table[0, i]
return result
x_vals, y_vals = [1, 3, 5], [2, 6, 10]
x_interp = 4
print(f"Lagrange at x = {x_interp}: {lagrange_interpolation(x_vals, y_vals,
x_interp)}")
print(f"Newton at x = {x_interp}: {newton_interpolation(x_vals, y_vals,
x_interp)}")
x_plot = np.linspace(min(x_vals), max(x_vals), 100)
y_lagrange = [lagrange_interpolation(x_vals, y_vals, x) for x in x_plot]
y_newton = [newton_interpolation(x_vals, y_vals, x) for x in x_plot]
plt.plot(x_vals, y_vals, 'ro', label='Data Points')
plt.plot(x_plot, y_lagrange, '--', label="Lagrange")
plt.plot(x_plot, y_newton, ':', label="Newton")
plt.legend(); plt.grid(True); plt.show()
OUTPUT:
