Interpolation and Extrapolation Lab

Interpolation and Extrapolation Lab#

Investigating Runge’s Phenomenon#

Polynomial interpolation is a widely used technique to approximate functions by constructing a polynomial that passes through a given set of data points. While this approach is popular, it has limitations, particularly when using high-degree polynomials over evenly spaced points.

One of the most famous examples of this limitation is Runge’s Phenomenon, first observed by Carl Runge. It demonstrates that using evenly spaced interpolation points for high-degree polynomials can lead to large oscillations, particularly near the edges of the interpolation interval. These oscillations become more pronounced as the number of interpolation points increases, making the polynomial approximation unreliable.

A key way to mitigate this issue is to use Chebyshev nodes instead of evenly spaced nodes. Chebyshev nodes are distributed in such a way that they reduce the maximum error of polynomial interpolation, leading to a more stable and accurate approximation.

Goals of this Lab#

  1. Understand and visualize Runge’s Phenomenon by using polynomial interpolation on equidistant nodes.

  2. Compare the performance of equidistant nodes with Chebyshev nodes to see how they mitigate oscillations.

  3. Explore how increasing the number of interpolation points affects the approximation.

Step 1: Define Runge’s Function#

Runge’s function is defined as:

(125)#\[\begin{align} f(x) = \frac{1}{1 + 25x^2} \end{align}\]

This function is well-behaved within \([-1,1]\), yet when interpolated using high-degree polynomials, it exhibits large oscillations at the edges.

import numpy as np
import matplotlib.pyplot as plt

# Define Runge's function
def Runge(x):
    # HANDSON: implement Runge's function here

# Define dense x values for plotting
X = np.linspace(-1, 1, 1001)
Y = Runge(X)

  Cell In[1], line 9
    X = np.linspace(-1, 1, 1001)
    ^
IndentationError: expected an indented block after function definition on line 5

Step 2: Generate Interpolation Nodes#

We will generate two sets of interpolation nodes:

  1. Equidistant nodes: Evenly spaced across the interval \([-1,1]\).

  2. Chebyshev nodes: Specially chosen to reduce oscillatory behavior.

# Number of interpolation points
N = 11

# Equidistant nodes
Xeq = np.linspace(-1, 1, N)
Yeq = Runge(Xeq)

# Chebyshev nodes
Xch = np.cos((2 * np.arange(N) + 1) / (2 * N) * np.pi)
Ych = Runge(Xch)

Step 3: Perform Polynomial Interpolation#

Using Neville’s algorithm we developed in notes.ipynb, construct polynomials based on the two sets of nodes.

# HANDSON: copy and paste PolynomialInterpolator from the notes

Runge_eq = PolynomialInterpolator(Xeq, Yeq)
Runge_ch = PolynomialInterpolator(Xch, Ych)

Step 4: Visualize the Results#

Now, we plot the original function along with the interpolated curves.

plt.plot(X, Y, 'k-', label="True Function")
plt.plot(X, [Runge_eq(x) for x in X], 'r--', label="Equidistant Interpolation")
plt.plot(X, [Runge_ch(x) for x in X], 'b-.', label="Chebyshev Interpolation")
plt.scatter(Xeq, Yeq, c='r', label="Equidistant Nodes")
plt.scatter(Xch, Ych, c='b', label="Chebyshev Nodes")
plt.legend()

Exploration Questions#

  1. How does the interpolated curve behave near the edges when using equidistant points?

  2. Why do Chebyshev nodes reduce oscillations compared to equidistant nodes?

  3. Try increasing n_points to 15 or 20. What happens, and why?

  4. What real-world scenarios might suffer from Runge’s phenomenon? How could we mitigate it?

Extrapolation is Difficult#

Interpolation works well within a known data range, but extrapolation—predicting values beyond that range—can lead to large errors. This lab explores the limitations of extrapolation using polynomials.

# Define a function with known behavior outside the range

def f(x):
    # HANDSON: define, e.g., sin(2 pi x), exp(-x^2/2)

# Sample points in the limited domain used in the previous example

Y   = f(X)
Yeq = f(Xeq)
Ych = f(Xch)

# Use the PolynomialInterpolator class to create interpolator

f_eq = ...
f_ch = ...

# Extrapolation range

Xex = np.linspace(-1.5, 1.5, 1001)
Yex = f(Xex)
Yex_eq = [f_eq(x) for x in Xex]
Yex_ch = [f_ch(x) for x in Xex]

# Plot results

plt.plot(Xex, Yex,    'k-',  label="True Function")
plt.plot(Xex, Yex_eq, 'r--', label="Equidistant Interpolation")
plt.plot(Xex, Yex_ch, 'b-.', label="Chebyshev Interpolation")
plt.scatter(Xeq, Yeq, c='r', label="Equidistant Nodes")
plt.scatter(Xch, Ych, c='b', label="Chebyshev Nodes")
plt.ylim(-5,5)
plt.legend()

Exploration Questions#

  1. How well does the extrapolated spline match the true function outside the sampled range?

  2. Try increasing the number of sample points. Does it improve extrapolation?

  3. What real-world problems could arise due to poor extrapolation behavior?

Contents