Key Approximation Algorithms

Why This Matters

Approximation algorithms form the computational backbone of numerical analysis—they're how we turn intractable mathematical problems into solvable ones. You're being tested not just on what each algorithm does, but on when and why you'd choose one method over another. The core tension in approximation theory is always the same: accuracy vs. computational cost, and understanding how different algorithms navigate this tradeoff is what separates surface-level memorization from genuine mastery.

These algorithms demonstrate fundamental principles like convergence behavior, error distribution, stability, and the bias-variance tradeoff. When you encounter an FRQ asking you to approximate a function, you need to immediately recognize whether you're dealing with smoothness constraints, periodicity, singularities, or noisy data—because each scenario points to a different optimal approach. Don't just memorize the formulas; know what problem each algorithm was designed to solve and where it breaks down.

---

Local Expansion Methods

These algorithms build approximations by expanding around a single point, using local information (function values and derivatives) to construct global estimates. The key insight is that smooth functions behave predictably near any given point—but this local knowledge may not extend well across the entire domain.

Taylor Series Approximation

• Expands a function as an infinite polynomial sum—terms are computed from successive derivatives evaluated at a single expansion point $a$
• Convergence radius determines where the approximation is valid; outside this radius, the series may diverge or converge slowly
• Best for analytic functions near the expansion point, but accuracy degrades rapidly as you move away from $a$

Padé Approximation

• Rational function form $\frac{P_m(x)}{Q_n(x)}$—uses a ratio of polynomials rather than a single polynomial, capturing behavior Taylor series cannot
• Handles poles and singularities effectively, making it superior for functions with asymptotic or divergent behavior
• Widely applied in control theory and signal processing where transfer functions naturally take rational form

Hermite Interpolation

• Matches both function values and derivatives at specified nodes—provides smoothness guarantees that standard interpolation lacks
• Higher-order contact at each point means fewer nodes needed for comparable accuracy
• Ideal when derivative data is available or when smooth transitions between segments are critical

---

Minimax and Optimal Approximation

These methods focus on minimizing the worst-case error across an entire interval, rather than optimizing at a single point. The minimax criterion ensures no part of the domain is poorly approximated—critical when uniform accuracy matters.

Chebyshev Approximation

• Minimizes maximum error (the $L^\infty$ norm) over a specified interval $[a, b]$, achieving the best uniform approximation
• Chebyshev polynomials $T_n(x) = \cos(n \arccos(x))$ serve as the basis, with roots clustered near interval endpoints to reduce oscillation
• Equioscillation property—the optimal approximation error alternates in sign at exactly $n+2$ points

Remez Algorithm

• Iterative exchange method for computing minimax polynomial approximations—the standard numerical approach to Chebyshev approximation
• Guarantees equioscillation at convergence, identifying the points where maximum error occurs
• Computationally intensive but produces provably optimal results for continuous functions on closed intervals

---

Interpolation-Based Methods

Interpolation methods construct approximations that pass exactly through specified data points. The tradeoff: exactness at nodes comes at the cost of potential instability between them, especially with high-degree polynomials.

Lagrange Interpolation

• Constructs the unique polynomial of degree at most $n$ passing through $n+1$ points using basis polynomials $L_i(x) = \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}$
• Runge's phenomenon causes severe oscillation near interval endpoints when using equally-spaced nodes with high-degree polynomials
• Conceptually simple but numerically unstable for large $n$; better implementations exist (Newton form, barycentric)

Spline Interpolation

• Piecewise polynomial construction—typically cubic polynomials joined with continuous first and second derivatives at knots
• Avoids Runge's phenomenon by keeping polynomial degree low while increasing the number of pieces
• Dominant method in practice for computer graphics, CAD, and data fitting due to local control and guaranteed smoothness

---

Least Squares and Statistical Methods

When data contains noise or when exact interpolation isn't desired, these methods find the best fit in a statistical sense. The key principle: minimizing squared errors gives mathematically tractable solutions with desirable statistical properties.

Least Squares Approximation

• Minimizes $\sum (y_i - f(x_i))^2$—the sum of squared residuals between observed data and the approximating function
• Normal equations $A^T A \mathbf{c} = A^T \mathbf{b}$ yield the optimal coefficients for linear models; nonlinear versions require iterative methods
• Statistically optimal under Gaussian noise assumptions; ubiquitous in regression, signal processing, and machine learning

---

Iterative and Root-Finding Methods

These algorithms use successive refinement to converge toward a solution, with each iteration improving the approximation. Convergence rate and stability conditions are the critical properties to understand.

Newton's Method

• Quadratic convergence near simple roots—error roughly squares each iteration, giving rapid convergence when close to the solution
• Update formula $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ uses tangent line approximation to predict root location
• Failure modes include zero derivatives, poor initial guesses, and cycling—always verify convergence conditions before applying

---

Periodic and Frequency-Domain Methods

For functions with repeating patterns, decomposition into frequency components provides natural and powerful approximations. Periodic structure means global information can be captured efficiently with trigonometric bases.

Fourier Series Approximation

• Decomposes periodic functions into sums of sines and cosines: $f(x) \approx \frac{a_0}{2} + \sum_{n=1}^{N} (a_n \cos(nx) + b_n \sin(nx))$
• Gibbs phenomenon causes ~9% overshoot near discontinuities that persists regardless of how many terms are included
• Optimal for smooth periodic functions in the $L^2$ sense; foundational for signal processing and spectral methods

---

Quick Reference Table

---

Self-Check Questions

1. You need to approximate $f(x) = \frac{1}{1+x^2}$ on $[-5, 5]$ with uniform accuracy. Which two methods would you consider, and why might polynomial interpolation with equally-spaced nodes fail?

2. Compare Taylor series and Padé approximation for $\tan(x)$ near $x = 0$. Which converges in a larger region, and what property of $\tan(x)$ explains the difference?

3. A dataset of 50 noisy measurements needs to be fit with a smooth curve. Explain why spline interpolation would be inappropriate and what method you should use instead.

4. Both Chebyshev approximation and Fourier series provide "optimal" approximations. In what sense is each optimal, and for what class of functions is each best suited?

5. An FRQ asks you to find the root of $f(x) = e^x - 3x$ to high precision. Describe how Newton's method would proceed, identify what could cause it to fail, and explain why this is an approximation algorithm even though it finds an exact root.