From the free course CS323: Numerical Analysis and Computing on Lykke

Polynomial Interpolation and Approximation

Key concepts: Lagrange Interpolation · Newton Basis and Divided Differences · Chebyshev Points · Piecewise Polynomials (Splines) · Horner's Method

Constructing functions that pass through a specific set of data points.

Polynomial Interpolation and Approximation

Overview

Interpolation allows us to represent discrete data as continuous functions. This is vital for computer graphics, data fitting, and numerical integration.

Key Concepts

  • Bases for Interpolation:
    • Monomial: Simple but numerically unstable for high degrees.
    • Lagrange: Elegant theoretical form but expensive to update.
    • Newton: Uses Divided Differences; efficient to compute and easy to add new points.
  • Chebyshev Nodes: Specifically chosen points that minimize the "Runge Phenomenon" (oscillations at the edges of the interval).
  • Piecewise Interpolation: Using low-degree polynomials (like cubics) over small sub-intervals to ensure smoothness and stability.
  • Horner's Method: An efficient algorithm for evaluating polynomials that minimizes the number of multiplications.

Practical Application

Homework #5 focuses on implementing divided differences and comparing the stability of different polynomial bases.

Source Materials

Study CS323: Numerical Analysis and Computing on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of CS323: Numerical Analysis and Computing · Browse more course pages

Polynomial Interpolation and Approximation — CS323: Numerical Analysis and Computing | Lykke