Unit II: Polynomial Interpolation
Polynomial Interpolation
Polynomial interpolation is the process of finding a polynomial of degree n that passes through a given set of data points. It is a fundamental tool in numerical analysis used to estimate unknown function values between known data points.
Key Concepts and Definitions
Definition: Let (x0, y0), (x1, y1), ..., (xn, yn) be a set of n + 1 distinct data points. A polynomial interpolation constructs a function Pn(x) of degree at most n such that Pn(xi) = yi for each i = 0, 1, ..., n.
The core assumption is that the underlying phenomenon can be reasonably approximated by a smooth polynomial curve over a local interval.
Real-World Applications
- Computer graphics and curve fitting for smooth path generation.
- Resampling digital images and audio signals.
- Estimating values in meteorological tables, scientific measurements, and financial modeling where only discrete data points are recorded.
Exam-Oriented Notes
Always verify that the given data points have equally spaced intervals before applying standard forward or backward difference operators, unless using Lagrange's method which does not require equal spacing.
Newton's Forward Interpolation Formula
Newton's forward interpolation formula is best suited for interpolating values near the beginning of a set of tabulated data points where the independent variable x values are equally spaced.
Step-by-Step Explanation
- Construct a forward difference table using the given values of x and y.
- Calculate the step size h = x1 - x0.
- Compute the scaling parameter u using the formula:
u = (x - x0) / h
- Apply the Newton's forward interpolation polynomial formula.
Formula
y(x) = y0 + uΔy0 + [u(u - 1) / 2!]Δ2y0 + [u(u - 1)(u - 2) / 3!]Δ3y0 + ... + [u(u - 1)...(u - n + 1) / n!]Δny0
Where Δ represents the forward difference operator.
Practical Example
Given data points: x = 0, 1, 2, 3 and y = 1, 3, 9, 27. To find y at x = 0.5, we first verify equal spacing h = 1, compute u = (0.5 - 0)/1 = 0.5, generate the difference table, and substitute into the forward formula.
Common Mistakes
- Using the forward formula for data points located near the end of the table, which leads to poor convergence and larger rounding errors.
- Incorrectly calculating the parameter u by mixing up x and x0.
Newton's Backward Interpolation Formula
Newton's backward interpolation formula is utilized when the value of the function is required near the end of the table of values with equal spacing.
Step-by-Step Explanation
- Construct a backward difference table using the given data.
- Identify the last data point (xn, yn).
- Compute the scaling parameter v using the formula:
v = (x - xn) / h
- Apply the backward interpolation polynomial formula.
Formula
y(x) = yn + v∇yn + [v(v + 1) / 2!]∇2yn + [v(v + 1)(v + 2) / 3!]∇3yn + ... + [v(v + 1)...(v + n - 1) / n!]∇nyn
Where ∇ represents the backward difference operator.
Important Observations
While forward interpolation moves downward diagonally from the top entry, backward interpolation moves upward diagonally from the bottom-most entry of the difference table.
Lagrange's Interpolation Formula
Lagrange's interpolation formula can be used whether the values of the independent variable x are equally spaced or unequally spaced. It expresses the interpolating polynomial as a linear combination of Lagrange basis polynomials.
Formula
Pn(x) = ∑ Li(x)yi
Where the basis polynomial Li(x) is defined as:
Li(x) = ∏j ≠ i [(x - xj) / (xi - xj)]
Expanded for three points (x0, y0), (x1, y1), (x2, y2):
P2(x) = [(x - x1)(x - x2) / (x0 - x1)(x0 - x2)]y0 + [(x - x0)(x - x2) / (x1 - x0)(x1 - x2)]y1 + [(x - x0)(x - x1) / (x2 - x0)(x2 - x1)]y2
Advantages and Disadvantages
| Features | Newton's Interpolation | Lagrange's Interpolation |
|---|---|---|
| Spacing Requirement | Requires equally spaced intervals | Works for both equal and unequal intervals |
| Adding Data Points | Easy to incorporate new data points by adding terms to the difference table | Must recalculate all basis polynomials from scratch if a data point is added |
| Complexity | Compact table-driven calculation | Requires evaluating product terms for every point |
Errors in Interpolation Formulae
When a function is replaced by an interpolating polynomial, an error is inevitably introduced because the polynomial only matches the function at specific nodes and deviates elsewhere.
Error Formula
E(x) = f(x) - Pn(x) = [(x - x0)(x - x1)...(x - xn) / (n + 1)!] f(n+1)(ξ)
Where ξ is an unknown value lying within the smallest interval containing all xi and x.
Key Definitions
- Truncation Error: The error caused by cutting off the interpolation polynomial series at a finite degree n.
- Round-off Error: The error resulting from computer arithmetic limitations and floating-point representations during manual or computational table construction.
Exam-Oriented Notes
To bound the error, find the maximum possible absolute value of the (n + 1)-th derivative of the function f(x) over the given domain, and maximize the product term ∏(x - xi).