Skip to content
All work
  • NTNU
  • TMA4215 Numerical Mathematics
  • Individual

Function Approximation: Interpolation, RBFs and Optimised Nodes

Often you only know a function at a handful of points, but need its value everywhere in between. Getting this right is at the heart of simulations and data analysis. I compared several classic ways of filling in the gaps, found out where each one breaks down, and used optimisation to choose better points.

Team
Individual project.
Period
Sep 2026
Status
Completed
Tools
Python · NumPy · autograd · matplotlib · Interpolation · Optimisation

Problem

Given a function's values at n+1n+1 points, how do you best approximate it everywhere else? The obvious answer, fitting one polynomial through equally spaced points, can fail badly: for Runge's function f(x)=1/(1+x2)f(x) = 1/(1+x^2) the error grows near the ends as you add more points.

The project compared global polynomial interpolation, piecewise interpolation and radial basis functions (RBFs). It asked for predictions before experiments, and explanations whenever theory and numerics disagreed.

Technical skills

  • Polynomial interpolation (Lagrange) with equidistant and Chebyshev nodes
  • Error analysis: interpolation error bounds, max-norm and 2-norm estimates, convergence rates
  • Piecewise polynomial interpolation and run-time measurements
  • Radial basis function interpolation and condition numbers of linear systems
  • Gradient descent with backtracking line search
  • Automatic differentiation with autograd
  • Scientific Python: NumPy, matplotlib and Jupyter

Approach

  1. Lagrange interpolation

    Equidistant vs Chebyshev nodes, with error measured in the max-norm and 2-norm and compared with theoretical error bounds.

  2. Piecewise interpolation

    Low-degree polynomials on many subintervals; convergence rates and measured run times compared with global interpolation.

  3. Radial basis functions

    Gaussian RBF interpolation, and how the shape parameter ε\varepsilon trades accuracy against the conditioning of the linear system.

  4. Optimising the nodes

    Gradient descent with backtracking, using automatic differentiation (autograd) to optimise node positions and ε\varepsilon together.

Results

Evenly spaced points
Interpolants with equidistant nodes oscillating wildly near x = ±5 as n grows.
Chebyshev points
Interpolants with Chebyshev nodes approaching Runge's function as n grows.
The classic warning example (Runge's function). With evenly spaced points (left), adding more points makes the approximation worse near the edges. With points packed closer to the edges, so-called Chebyshev nodes (right), it gets better. Legend: Runge-funksjonen = Runge's function.[Notebook figure]
Log-scale 2-norm error against n for optimised, equidistant and Chebyshev RBF nodes; optimised nodes give the lowest error.
Letting an optimisation algorithm choose where to place the points (black) gave a smaller error than both fixed layouts.[Notebook figure]

The full notebook with code, plots and discussion is on GitHub.

See the notebook on GitHub (opens in new tab)

Links