Module 3: Approximation of Functions (Weeks 5-6)
Topic 5: Interpolation
1. Polynomial Interpolation
a. Lagrange Form
Definition: The Lagrange interpolation polynomial is a method to find a unique
polynomial of degree ≤ n that passes through n+1 given data points (x₀,y₀), (x₁,y₁), ...,
(xₙ,yₙ) where all xᵢ are distinct.
Formula: The Lagrange polynomial is given by:
P(x) = Σᵢ yᵢ · Lᵢ(x)
where Lᵢ(x) are the Lagrange basis polynomials:
Lᵢ(x) = Πⱼ≠ᵢ (x - xⱼ) / (xᵢ - xⱼ)
Advantages:
• Straightforward to understand
• Easy to implement
• Explicit formula
Disadvantages:
• Computationally expensive for large n
• Adding a new data point requires recomputing the entire polynomial
• Numerically unstable for large n
b. Newton Form
Definition: The Newton interpolation polynomial is an alternative form of polynomial
interpolation that uses divided differences and is more efficient when adding new data
points.
Formula: The Newton polynomial is given by:
P(x) = f[x₀] + f[x₀,x₁](x-x₀) + f[x₀,x₁,x₂](x-x₀)(x-x₁) + ... + f[x₀,x₁,...,xₙ]Πᵢ(x-xᵢ)
where f[x₀,x₁,...,xₖ] are divided differences.
f[xᵢ] = yᵢ
f[xᵢ,xⱼ] = (f[xⱼ] - f[xᵢ]) / (xⱼ - xᵢ)
f[xᵢ,xⱼ,xₖ] = (f[xⱼ,xₖ] - f[xᵢ,xⱼ]) / (xₖ - xᵢ)
Example: For points (1,2), (2,3), (4,1):
f[x₀] = 2
f[x₁] = 3
f[x₂] = 1
f[x₀,x₁] = (3-2)/(2-1) = 1
f[x₁,x₂] = (1-3)/(4-2) = -1
f[x₀,x₁,x₂] = (-1-1)/(4-1) = -2/3
P(x) = 2 + 1(x-1) - 2/3(x-1)(x-2)
Advantages:
• More efficient when adding new data points
• Better numerical stability
• Can be computed using a simple algorithm
Disadvantages:
• Less intuitive than Lagrange form
• Still suffers from Runge's phenomenon for high degrees
c. Runge's Phenomenon
Definition: Runge's phenomenon is the oscillation problem that occurs when using
high-degree polynomial interpolation with equally spaced points.
Example: Consider interpolating the function f(x) = 1/(1+25x²) on [-1,1] using equally
spaced points. As the degree increases, the interpolation polynomial oscillates wildly
near the endpoints.
Explanation:
• High-degree polynomials tend to oscillate
• Equally spaced points are not optimal for interpolation
• The error term in polynomial interpolation grows with the (n+1)th derivative of the
function
Mitigation:
• Use Chebyshev nodes instead of equally spaced points
• Use piecewise interpolation (splines)
• Limit the degree of the polynomial
2. Piecewise Interpolation
a. Introduction to Splines
Definition: A spline is a piecewise polynomial function that is smooth (has continuous
derivatives) at the points where the polynomial pieces connect (knots).
Motivation:
• Avoids Runge's phenomenon
• Provides better approximation with lower-degree polynomials
• More stable numerically
Types of Splines:
• Linear splines (degree 1)
• Quadratic splines (degree 2)
• Cubic splines (degree 3)
• Higher-degree splines
b. Cubic Splines
Definition: A cubic spline is a piecewise cubic polynomial that has continuous first and
second derivatives at the interior knots.
Formulation: Given points (x₀,y₀), (x₁,y₁), ..., (xₙ,yₙ), we want to find cubic polynomials
Sᵢ(x) for each interval [xᵢ, xᵢ₊₁]:
text
Sᵢ(x) = aᵢ + bᵢ(x-xᵢ) + cᵢ(x-xᵢ)² + dᵢ(x-xᵢ)³
Conditions:
1. Interpolation: Sᵢ(xᵢ) = yᵢ and Sᵢ(xᵢ₊₁) = yᵢ₊₁ for all i
2. Continuity: Sᵢ(xᵢ₊₁) = Sᵢ₊₁(xᵢ₊₁) for all i
3. First derivative continuity: Sᵢ'(xᵢ₊₁) = Sᵢ₊₁'(xᵢ₊₁) for all i
4. Second derivative continuity: Sᵢ''(xᵢ₊₁) = Sᵢ₊₁''(xᵢ₊₁) for all i
Boundary Conditions:
• Natural spline: S₀''(x₀) = Sₙ₋₁''(xₙ) = 0
• Clamped spline: S₀'(x₀) and Sₙ₋₁'(xₙ) are specified
• Not-a-knot: S₀'''(x₁) = S₁'''(x₁) and Sₙ₋₂'''(xₙ₋₁) = Sₙ₋₁'''(xₙ₋₁)
Solution Method:
1. Express the second derivatives at the knots as unknowns
2. Set up a tridiagonal system of equations
3. Solve for the second derivatives
4. Compute the coefficients aᵢ, bᵢ, cᵢ, dᵢ
Advantages:
• Avoids Runge's phenomenon
• Provides smooth interpolation
• Computationally efficient (tridiagonal system)
• Good approximation properties
Topic 6: Curve Fitting and Least Squares Approximation
1. Linear and Polynomial Regression
a. Linear Regression
Definition: Linear regression is a method to model the relationship between a
dependent variable y and one or more independent variables x by fitting a linear
equation to the observed data.
Simple Linear Regression (one independent variable):
text
y = β₀ + β₁x + ε
where β₀ is the intercept, β₁ is the slope, and ε is the error term.
Multiple Linear Regression (multiple independent variables):
text
y = β₀ + β₁x₁ + β₂x₂ + ... + βₚxₚ + ε
Solution Method: The coefficients are estimated by minimizing the sum of squared
residuals:
text
min Σᵢ (yᵢ - (β₀ + β₁xᵢ))²
b. Polynomial Regression
Definition: Polynomial regression is a form of regression analysis where the relationship
between the independent variable x and the dependent variable y is modeled as an nth-
degree polynomial.
Formulation:
text
y = β₀ + β₁x + β₂x² + ... + βₙxⁿ + ε
Solution Method: The coefficients are estimated by minimizing the sum of squared
residuals:
text
min Σᵢ (yᵢ - (β₀ + β₁xᵢ + β₂xᵢ² + ... + βₙxᵢⁿ))²
Note: Polynomial regression can be viewed as a special case of multiple linear
regression where the independent variables are powers of x.
2. The Method of Least Squares
a. Introduction
Definition: The method of least squares is a standard approach to approximate the
solution of overdetermined systems by minimizing the sum of the squares of the
residuals made in the results of every single equation.
Motivation:
• Often, we have more data points than unknown parameters
• The data may contain noise or measurement errors
• We want the "best" fit in some sense
General Formulation: Given data points (x₁,y₁), (x₂,y₂), ..., (xₘ,yₘ) and a model function
f(x,β) with parameters β = (β₀, β₁, ..., βₙ), we want to find β that minimizes:
text
S(β) = Σᵢ (yᵢ - f(xᵢ,β))²
b. Solution
Normal Equations: For a linear model f(x,β) = β₀φ₀(x) + β₁φ₁(x) + ... + βₙφₙ(x), the normal
equations are:
text
AᵀAβ = Aᵀy
where A is the design matrix with elements Aᵢⱼ = φⱼ(xᵢ) and y is the vector of observed
values.
Matrix Formulation:
text
min ||Aβ - y||²
The solution is:
text
β = (AᵀA)⁻¹Aᵀy
provided AᵀA is invertible.
Example: For linear regression y = β₀ + β₁x:
text
A = [[1, x₁],
[1, x₂],
...
[1, xₘ]]
y = [y₁, y₂, ..., yₘ]ᵀ
β = (AᵀA)⁻¹Aᵀy
c. Applications
Data Fitting:
• Fitting experimental data to theoretical models
• Trend analysis
• Forecasting
Model Selection:
• Choosing the appropriate degree of polynomial
• Balancing goodness of fit with model complexity
• Avoiding overfitting
Goodness of Fit Measures:
• R-squared (coefficient of determination)
• Adjusted R-squared
• Root Mean Square Error (RMSE)
• Akaike Information Criterion (AIC)
• Bayesian Information Criterion (BIC)
Nonlinear Least Squares: For nonlinear models, iterative methods like Gauss-Newton
or Levenberg-Marquardt are used to minimize the sum of squared residuals.