Summary

Summary#

This chapter introduces the theory and practice of polynomial interpolation, a foundational tool in scientific computing with applications in approximation, numerical integration, and differential equations. The goal is to approximate a function \(f(x)\) using a polynomial that passes through a given set of data points \((x_i, y_i)\). The chapter progresses from basic definitions to error analysis and optimal node selection.

🔹 Section 2.1 – Introduction and Applications

  • Motivation: estimating unknown values from discrete data (e.g., historical CO₂ levels).

  • Interpolation problem: find a polynomial \(p(x) \in \mathbb{P}_n\) such that \(p(x_i) = y_i\).

🔹 Section 2.2 – Preliminaries

  • Definitions: polynomial degree, zero/root, polynomial spaces \(\mathbb{P}_n\), and their properties.

  • Review of the algebraic structure of polynomials.

🔹 Section 2.3 – Direct Approach: Vandermonde System

  • Constructing the interpolation polynomial by solving a linear system with a Vandermonde matrix.

  • Uniqueness and solvability when nodes \(x_i\) are distinct.

🔹 Section 2.4 – Lagrange Interpolation

  • Definition and construction of Lagrange basis polynomials \(\ell_i(x)\).

  • Expression of \(p(x) = \sum y_i \ell_i(x)\).

  • Advantages: no need to solve a system, polynomials are explicit.

🔹 Section 2.5 – Implementation

  • Python code for computing cardinal functions and interpolation polynomials.

  • Visualization of Lagrange basis and interpolated curves.

🔹 Section 2.6 – Existence and Uniqueness

  • The interpolation polynomial exists and is unique for n+1 distinct nodes.

  • Proof via contradiction using the root structure of polynomials.

🔹 Section 2.7 – Error Theory

  • Defines error \(e(x) = f(x) - p_n(x)\).

  • Derivation of the interpolation error formula using the Newton form and Rolle’s Theorem.

  • Error depends on smoothness of \(f\), number of nodes, and distribution of nodes

  • Uniformly spaced nodes can lead to large interpolation errors near the boundaries (Runge’s phenomenon).

  • Optimal distribution of nodes minimizes the maximum of \(|\omega(x)| = \prod(x - x_i)\).

  • Chebyshev nodes reduce error and avoid Runge’s phenomenon.

  • Derivation of error bound for interpolation with Chebyshev nodes.

🎯 Learning Outcomes for Chapter 2

By the end of this chapter, students will be able to:

📘 Theory and Definitions

  • Define the interpolation problem and identify when a unique solution exists.

  • Explain the role of the interpolation polynomial and nodes.

  • Distinguish between different polynomial bases (monomial, Lagrange).

✍️ Construction Methods

  • Construct interpolation polynomials using:

    • Direct method via Vandermonde matrices

    • Lagrange interpolation using cardinal functions

  • Implement polynomial interpolation numerically and visualize results.

📏 Error Analysis

  • Derive and interpret the interpolation error formula.

  • Analyze how the error depends on:

    • The degree of the interpolating polynomial

    • The function’s smoothness

    • The distribution of interpolation nodes

🧪 Experiments and Applications

  • Perform numerical experiments interpolating function with different node distributions.

  • Demonstrate how Runge’s phenomenon arises from equidistant nodes.

  • Estimate the maximum interpolation error for various choices of \(n\) and node distributions.

🔍 Chebyshev Interpolation

  • Compute and use Chebyshev nodes to reduce interpolation error.

  • Compare error behavior of equidistributed and Chebyshev node interpolation.

  • Derive and apply error bounds for Chebyshev interpolation.