Note Of Newton Polynomial

Last Updated on 2024-08-26 by Clay

Newton’s interpolation is a polynomial interpolation method that constructs a set of polynomial functions using multiple data points. A major advantage is that with the addition of new data, Newton’s interpolation method does not require recalculations from scratch but can instead expand on the existing function.

---

Calculation Method

1. Divided Difference Calculation

For a set of input data and their corresponding values , the first order divided difference is defined as:

Higher order divided differences are computed recursively:

2. Constructing the Interpolation Polynomial

Using the computed divided differences, we can construct the polynomial :

3. Calculating New Interpolated Values

Using this polynomial , we can compute interpolated values for any , even if was not part of the original dataset. Naturally, the more data points we have, the smaller the interpolation error will be.

This interpolation method allows for the addition of new data points into the polynomial without needing to recalculate previous coefficients. However, when dealing with a large amount of data, the computational and storage demands for the divided difference table can increase significantly.

A notable case is the Runge’s phenomenon, a prominent issue in polynomial interpolation, especially when selecting equidistant data points for high-degree polynomial interpolations. Even if the function itself is very smooth, the polynomial can exhibit significant approximation errors near the edges of the interval, resulting in severe oscillations at the endpoints.

---

Program Implementation

Below is an implementation in Python.

from typing import List def divided_diff(x: List[float], y: List[float]) -> List[float]: """Calculate the divided difference table""" n = len(y) coef = y[:] for j in range(1, n): for i in range(n-1, j-1, -1): coef[i] = (coef[i] - coef[i-1]) / (x[i] - x[i-j]) return coef def newton_interpolate(x: List[float], y: List[float], x_value: float) -> float: """Calculate the interpolation at x_value""" coef = divided_diff(x, y) n = len(x) - 1 p = coef[n] for k in range(1, n+1): p = coef[n-k] + (x_value - x[n-k]) * p return p # Given points x = [-1, 1, 2, 4] y = [-2, 6, 7, 93] # Calculate the interpolation at x=3 x_value = 3 interpolated_value = newton_interpolate(x, y, x_value) print(f"The interpolation result at x={x_value} is: {interpolated_value}")

Output:

The interpolation result at x=3 is: 30.0

---

References

• Wikipedia – Newton Polynomial
• Newton’s Interpolating Polynomials: What Would Lagrange Say?

---

Read More

Note Of Singular Value Decomposition (SVD)

What Is Probability Density Function (PDF)?