[course:Part IB Numerical Analysis, Cambridge, Michaelmas Term]

Exact solutions to mathematical problems — inverting matrices, evaluating [integrals](/page/Integral), solving differential equations — are rarely available in practice. When the matrix is $10{,}000 \times 10{,}000$, the integral has no closed form, or the ODE is nonlinear, the only option is to compute an *approximate* answer and control the error. [Numerical analysis](/page/Numerical%20Analysis) is the systematic study of such approximations: how to construct them, how accurate they are, when they converge, and when they fail.

The course divides into three parts. Chapters 1–3 address **approximation theory**: how to represent complicated [functions](/page/Function) by polynomials (interpolation, least-squares fitting), how to approximate integrals using finitely many function evaluations (quadrature), and how to bound the resulting errors (the Peano kernel theorem). Chapters 4–6 treat the **numerical solution of ordinary differential equations**: one-step methods (Euler, $\theta$-methods), multi-step methods (Adams, BDF), Runge-Kutta methods, and the interplay between accuracy and stability. Chapters 7–8 cover **numerical linear algebra**: LU and Cholesky factorizations for solving linear systems, and QR factorization for the least-squares problem.

A recurring theme is the tension between *accuracy* (how well does the approximation match the exact answer?) and *efficiency* (how much computational work is required?). The best numerical methods resolve this tension by exploiting mathematical structure — orthogonality, symmetry, sparsity — to achieve high accuracy at low cost.

# Polynomial Interpolation

Polynomials are the simplest class of functions that can be evaluated, differentiated, and integrated exactly using finitely many arithmetic operations. Writing down a polynomial of degree $n$ requires only $n + 1$ numbers (its coefficients), and evaluating it at a point costs $O(n)$ operations via Horner's scheme. The goal of this chapter is to approximate a complicated function $f$ by a polynomial that agrees with $f$ at prescribed points, and to understand the error of this approximation.

**Notation.** We write $P_n[x]$ for the real vector space of polynomials of degree $\le n$. Note $\dim P_n[x] = n + 1$.

## The Interpolation Problem and the Lagrange Formula

Given $n + 1$ distinct points $x_0, \dots, x_n \in \mathbb{R}$ and values $f_0, \dots, f_n \in \mathbb{R}$, the **interpolation problem** asks for a polynomial $p \in P_n[x]$ satisfying $p(x_i) = f_i$ for $i = 0, \dots, n$. Writing $p(x) = a_n x^n + \cdots + a_0$ and imposing the $n + 1$ conditions gives a system of $n + 1$ equations in $n + 1$ unknowns. From linear algebra, such a system need not have a solution in general — but the special structure of polynomial evaluation (the Vandermonde structure) guarantees both existence and uniqueness.

The construction uses the **Lagrange cardinal polynomials** $\ell_k(x) := \prod_{i \ne k} \frac{x - x_i}{x_k - x_i}$, which satisfy $\ell_k(x_j) = \delta_{jk}$. Each $\ell_k$ has degree exactly $n$, equals $1$ at $x_k$, and vanishes at every other interpolation point.

[quotetheorem:473]

The existence proof is immediate: $p(x) = \sum_{k=0}^n f_k \ell_k(x) \in P_n[x]$ satisfies $p(x_j) = \sum_k f_k \delta_{jk} = f_j$. For uniqueness: if $p, q \in P_n[x]$ both interpolate, then $r = p - q \in P_n[x]$ has $n + 1$ zeros $x_0, \dots, x_n$, but a nonzero polynomial of degree $\le n$ has at most $n$ zeros. So $r = 0$.

The Lagrange formula is elegant but impractical: adding a new interpolation point $x_{n+1}$ requires recomputing every cardinal polynomial from scratch. Newton's formula solves this by building the interpolant incrementally.

## Newton's Formula and Divided Differences

The idea is to write the interpolant as a telescoping sum. For $k = 0, \dots, n$, let $p_k \in P_k[x]$ be the unique polynomial interpolating the first $k + 1$ points. Then $p_n(x) = p_0(x) + \sum_{k=1}^n (p_k(x) - p_{k-1}(x))$. Since $p_k$ and $p_{k-1}$ agree at $x_0, \dots, x_{k-1}$, the difference $p_k - p_{k-1}$ vanishes at these points, so $p_k(x) - p_{k-1}(x) = A_k \prod_{i=0}^{k-1}(x - x_i)$ for some coefficient $A_k$.

[definition:Divided Difference] The **divided difference** $f[x_j, \dots, x_k]$ is the leading coefficient of the unique polynomial in $P_{k-j}[x]$ that interpolates $f$ at $x_j, \dots, x_k$. In particular, $f[x_i] = f(x_i)$. [/definition]

[quotetheorem:474]

The coefficients $A_k = f[x_0, \dots, x_k]$ appear along the top diagonal of the **divided difference table**, which is built column by column using the recurrence relation.

[quotetheorem:907]

The proof constructs the interpolant at $\{x_j, \dots, x_k\}$ as a convex combination of interpolants at $\{x_j, \dots, x_{k-1}\}$ and $\{x_{j+1}, \dots, x_k\}$: $q_2(x) = \frac{x - x_j}{x_k - x_j} q_1(x) + \frac{x_k - x}{x_k - x_j} q_0(x)$. This correctly interpolates all the data (check directly at $x_j$, $x_k$, and the interior points), so by uniqueness it equals $q_2$. Comparing leading coefficients gives the recurrence.