The Central Idea

Let \(f(x)\) be a target function and let \(p(x)\) be a simpler approximation.

The approximation error is

\[ \boxed{e(x)=f(x)-p(x)}. \]

Function approximation asks:

Interpolation and Approximation Are Different

Interpolation requires

\[ p(x_i)=f(x_i) \]

at selected nodes.

General approximation instead seeks

\[ p(x)\approx f(x) \]

over a region, according to a chosen criterion.

Why Approximate a Function?

A simpler approximation can make later numerical work easier.

Choosing an Approximation Space

We first choose a family of functions.

For example, we might approximate \(f\) by a polynomial of degree at most \(n\):

\[ p_n(x)=a_0+a_1x+\cdots+a_nx^n. \]

More generally, choose basis functions

\[ \phi_0(x),\phi_1(x),\ldots,\phi_n(x) \]

and write

\[ \boxed{p_n(x)=\sum_{k=0}^{n}a_k\phi_k(x)}. \]

Approximation Depends on the Error Measure

There is no single universal definition of the best approximation.

One method may minimize average squared error, while another may minimize the largest error anywhere on the interval.

The chosen norm determines what best means.

The Maximum Norm

On an interval \([a,b]\), the maximum or uniform norm is

\[ \boxed{\|f\|_\infty=\max_{a\le x\le b}|f(x)|}. \]

The corresponding approximation error is

\[ \boxed{\|f-p\|_\infty=\max_{a\le x\le b}|f(x)-p(x)|}. \]

The \(L^2\) Norm

A continuous least-squares error can be measured by

\[ \boxed{\|f-p\|_2=\left(\int_a^b|f(x)-p(x)|^2\,dx\right)^{1/2}}. \]

Minimizing this norm emphasizes overall squared error rather than the single worst point.

Weighted Norms

Some regions of an interval may matter more than others.

Introduce a nonnegative weight \(w(x)\):

\[ \boxed{\|f-p\|_{2,w}=\left(\int_a^b w(x)|f(x)-p(x)|^2\,dx\right)^{1/2}}. \]

The weight changes which parts of the domain receive greater emphasis.

Discrete Least Squares

Suppose data values are known at sample points:

\[ (x_1,y_1),\ldots,(x_m,y_m). \]

We choose coefficients to minimize

\[ \boxed{\sum_{i=1}^{m}\left(y_i-p(x_i)\right)^2}. \]

This is the standard discrete least-squares objective.

Linear Least-Squares Approximation

Suppose

\[ p(x)=a+bx. \]

For data \((x_i,y_i)\), minimize

\[ S(a,b)=\sum_{i=1}^{m}\left(y_i-a-bx_i\right)^2. \]

The Normal Equations

Setting the derivatives of \(S\) with respect to \(a\) and \(b\) equal to zero gives

\[ \boxed{ \begin{aligned} ma+b\sum x_i&=\sum y_i,\\ a\sum x_i+b\sum x_i^2&=\sum x_i y_i. \end{aligned}} \]

Matrix Form of Least Squares

With design matrix \(A\), coefficient vector \(\mathbf{c}\), and data vector \(\mathbf{y}\), the model is

\[ A\mathbf{c}\approx\mathbf{y}. \]

Least squares minimizes

\[ \|A\mathbf{c}-\mathbf{y}\|_2. \]

The formal normal equations are

\[ \boxed{A^TA\mathbf{c}=A^T\mathbf{y}}. \]

Why Numerical Linear Algebra Matters Here

Least-squares approximation is a linear algebra problem in the unknown coefficients.

QR factorization or the singular value decomposition is often preferable to forming \(A^TA\) explicitly because

\[ \kappa_2(A^TA)=\kappa_2(A)^2. \]

Thus the previous lesson feeds directly into approximation theory.

Continuous Least Squares

Instead of discrete sample points, suppose we want to approximate a function throughout \([a,b]\).

Choose \(p\) to minimize

\[ \boxed{\int_a^b\left(f(x)-p(x)\right)^2\,dx}. \]

Inner Products

Define

\[ \boxed{\langle f,g\rangle=\int_a^b f(x)g(x)\,dx}. \]

Then

\[ \|f\|_2^2=\langle f,f\rangle. \]

Continuous least squares can therefore be viewed geometrically in a function space.

Orthogonality of Functions

Functions \(f\) and \(g\) are orthogonal when

\[ \boxed{\langle f,g\rangle=0}. \]

This generalizes the perpendicular-vector idea from linear algebra.

Orthogonal Projection

Let the approximation space be spanned by \(\phi_0,\phi_1,\ldots,\phi_n\).

The best least-squares approximation \(p\) satisfies

\[ \boxed{\langle f-p,\phi_k\rangle=0} \]

for every basis function \(\phi_k\).

The error is orthogonal to the approximation space.

Orthogonal Bases Simplify Coefficients

If

\[ \langle \phi_i,\phi_j\rangle=0\qquad(i\ne j), \]

then the coefficients decouple:

\[ \boxed{a_k=\frac{\langle f,\phi_k\rangle}{\langle \phi_k,\phi_k\rangle}}. \]

Orthonormal Bases

If the basis also satisfies \(\|\phi_k\|_2=1\), then

\[ \boxed{a_k=\langle f,\phi_k\rangle}. \]

The coefficient is simply the projection of \(f\) onto the basis direction.

Legendre Polynomials

On \([-1,1]\), the Legendre polynomials form an important orthogonal family.

\[ P_0(x)=1, \] \[ P_1(x)=x, \] \[ P_2(x)=\frac12(3x^2-1). \]

They satisfy orthogonality relations under the ordinary weight \(w(x)=1\).

Chebyshev Polynomials

The Chebyshev polynomials of the first kind are defined by

\[ \boxed{T_n(x)=\cos(n\arccos x)},\qquad -1\le x\le1. \]

The first few are

\[ T_0(x)=1,\qquad T_1(x)=x,\qquad T_2(x)=2x^2-1. \]

Chebyshev Recurrence

\[ \boxed{T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)}. \]

Recurrence relations support efficient evaluation without expanding large powers of \(x\).

Why Chebyshev Polynomials Are Numerically Important

Mapping an Interval to \([-1,1]\)

Map \(x\in[a,b]\) to

\[ \boxed{t=\frac{2x-(a+b)}{b-a}}. \]

Approximation can then be carried out in the standardized coordinate \(t\).

Taylor Approximation

Taylor polynomials provide a local approximation around a point \(a\):

\[ \boxed{T_n(x)=\sum_{k=0}^{n}\frac{f^{(k)}(a)}{k!}(x-a)^k}. \]

Taylor approximation is built from derivative matching rather than global error minimization.

Example: Taylor Approximation of \(e^x\)

Around \(a=0\),

\[ e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots. \]

A quadratic approximation is

\[ \boxed{p_2(x)=1+x+\frac{x^2}{2}}. \]

Local and Global Approximation

Taylor polynomials are typically strongest near their expansion point.

Least-squares or minimax approximations are designed to distribute error across an entire interval.

Thus the word best depends on where and how accuracy is required.

Minimax Approximation

A minimax approximation minimizes the maximum error:

\[ \boxed{\min_{p\in\mathcal{P}_n}\|f-p\|_\infty}. \]

It seeks the degree-\(n\) polynomial whose worst-case error on the interval is as small as possible.

Uniform Approximation

Minimax approximation is also called uniform approximation because it controls the maximum deviation across the whole interval.

This is useful when no point in the interval may exceed a prescribed error.

Equioscillation

A hallmark of best polynomial minimax approximation is an alternating pattern in the error.

The optimal error reaches equal magnitude with alternating signs at several points across the interval.

This is the basis of the equioscillation principle.

Rational Approximation

Instead of a polynomial, approximate \(f\) by a rational function

\[ \boxed{r(x)=\frac{p_m(x)}{q_n(x)}}. \]

Rational functions can represent poles, steep transitions, and certain global behaviors more efficiently than polynomials.

Padé Approximation

A Padé approximant chooses

\[ r(x)=\frac{p_m(x)}{q_n(x)} \]

so that its Taylor expansion agrees with the target function through as many terms as possible.

Example: A Simple Rational Approximation

Near \(x=0\),

\[ \boxed{e^x\approx\frac{1+x/2}{1-x/2}}. \]

Expanding the rational expression gives

\[ 1+x+\frac{x^2}{2}+\cdots, \]

matching the first terms of the exponential series.

Approximation by Trigonometric Functions

Periodic functions are often better approximated with trigonometric bases:

\[ \boxed{p_n(x)=a_0+\sum_{k=1}^{n}\left(a_k\cos kx+b_k\sin kx\right)}. \]

This leads naturally to Fourier approximation.

Approximation and Compression

A function or data set may contain thousands of sampled values.

If a small number of coefficients captures most of the important behavior, the approximation acts as a compressed representation.

Truncating a Basis Expansion

Suppose

\[ f(x)=\sum_{k=0}^{\infty}a_k\phi_k(x). \]

A finite approximation retains only the first \(n+1\) terms:

\[ \boxed{p_n(x)=\sum_{k=0}^{n}a_k\phi_k(x)}. \]

The omitted tail becomes the approximation error.

Coefficient Decay

When basis coefficients decrease rapidly in magnitude, a low-order approximation may capture the function effectively.

Slow coefficient decay signals that more terms may be needed.

Smoothness and Approximation Quality

Smooth functions are generally easier to approximate efficiently with global polynomial or spectral methods.

Discontinuities, corners, singularities, or sharp boundary layers can slow convergence and create oscillation.

Piecewise Approximation

Instead of using one global approximant on \([a,b]\), divide the interval into subintervals and approximate locally.

Adaptive Approximation

An adaptive method allocates more computational effort where the function is hard to approximate and less where it is smooth.

Absolute Approximation Error

\[ \boxed{|f(x)-p(x)|}. \]

This is often the most direct local error measure.

Relative Approximation Error

When \(f(x)\neq0\), define

\[ \boxed{\frac{|f(x)-p(x)|}{|f(x)|}}. \]

Relative error is especially useful when the magnitude of \(f\) varies widely across the interval.

Relative Error Near Zeros

If \(f(x)\approx0\), relative error can become very large even when the absolute error is small.

Near zeros, absolute and relative criteria should be interpreted together.

Approximation Error and Numerical Error

  1. approximation error: the difference between \(f\) and the ideal chosen approximant;
  2. numerical error: the additional error introduced while computing coefficients or evaluating the approximant.

A theoretically excellent approximation can still be implemented poorly.

Stable Evaluation Matters

Horner's Method

A polynomial

\[ p(x)=a_0+a_1x+\cdots+a_nx^n \]

can be rewritten as

\[ \boxed{p(x)=a_0+x\left(a_1+x\left(a_2+\cdots+x(a_{n-1}+xa_n)\right)\right)}. \]

Approximation in Several Variables

The same ideas extend to

\[ f(x_1,\ldots,x_d). \]

Approximation spaces may contain multivariable polynomials, tensor-product bases, radial functions, or other structured families.

The Curse of Dimensionality

If each variable uses \(m\) grid values in \(d\) dimensions, a full tensor grid contains

\[ \boxed{m^d} \]

points.

This exponential growth is one form of the curse of dimensionality.

Low-Dimensional Structure

Model Reduction

Function approximation can replace an expensive simulation with a cheaper surrogate.

Approximation and Differentiation

Once

\[ f(x)\approx p(x), \]

one may approximate derivatives by

\[ f'(x)\approx p'(x). \]

Differentiation can amplify approximation and rounding error. The next lesson develops this issue directly.

Approximation and Integration

If

\[ f(x)\approx p(x), \]

then

\[ \int_a^b f(x)\,dx\approx\int_a^b p(x)\,dx. \]

Many numerical integration formulas can be understood as integrating an interpolating or approximating function.

Choosing the Approximation Family

A Reliable Approximation Workflow

  1. Identify the domain and purpose of the approximation.
  2. Choose an error norm tied to the application.
  3. Select a suitable approximation family.
  4. Scale the domain when helpful.
  5. Compute coefficients using a numerically stable method.
  6. Evaluate the approximant using a stable representation.
  7. Estimate absolute, relative, or normwise error.
  8. Increase degree or refine locally only when the error requires it.
  9. Check for overfitting, oscillation, and sensitivity.

A Reliable Least-Squares Workflow

  1. Choose basis functions.
  2. Form the design matrix.
  3. Scale columns if needed.
  4. Use QR or SVD when numerical conditioning matters.
  5. Compute the residual.
  6. Inspect whether higher-order terms materially reduce error.
  7. Validate on independent data when the approximation is predictive.

A Reliable Orthogonal-Expansion Workflow

  1. Map the domain to the basis interval if necessary.
  2. Select an orthogonal basis appropriate to the weight and domain.
  3. Compute projection coefficients.
  4. Inspect coefficient decay.
  5. Truncate when the remaining terms are below the required error scale.
  6. Evaluate using a stable recurrence.

Common Error: Assuming Interpolation Is Always Best

Interpolation exactly reproduces supplied data.

If the data contain noise, this may reproduce noise rather than the underlying signal.

Least-squares or smoothing methods may be more appropriate.

Common Error: Choosing Degree Only by Data Count

A large number of data points does not imply that a high-degree polynomial is desirable.

Approximation degree should be guided by accuracy, smoothness, conditioning, and stability.

Common Error: Ignoring the Error Norm

A least-squares approximation and a minimax approximation solve different optimization problems.

Neither is universally superior. Choose the norm that reflects the actual performance requirement.

Common Error: Using Monomials at High Degree Without Scaling

Powers \(1,x,x^2,\ldots,x^n\) can vary dramatically in magnitude on poorly scaled intervals.

Orthogonal bases and interval scaling can produce better numerical behavior.

Common Error: Forming Normal Equations Automatically

Least-squares normal equations square the \(2\)-norm condition number:

\[ \kappa_2(A^TA)=\kappa_2(A)^2. \]

QR or SVD can be more stable.

Common Error: Assuming More Terms Always Improve the Computation

Additional basis terms reduce approximation error only until numerical error, noise, or ill-conditioning begins to dominate.

A larger model can be worse than a smaller well-conditioned one.

Common Error: Ignoring Relative Error Near Zero

Relative error becomes unstable as the target approaches zero.

Use combined absolute and relative criteria when the function crosses or approaches zero.

Common Error: Treating Extrapolation as Approximation on the Same Terms

An approximation validated on \([a,b]\) may behave poorly outside that interval.

Extrapolation requires separate analysis because the error can grow quickly.

Example: Least-Squares Constant Approximation

Approximate \(f(x)=x\) on \([0,1]\) by a constant \(c\).

Minimize

\[ \int_0^1(x-c)^2\,dx. \]

Differentiate with respect to \(c\):

\[ -2\int_0^1(x-c)\,dx=0. \]

Thus

\[ \int_0^1x\,dx=c\int_0^1 1\,dx, \]

so

\[ \boxed{c=\frac12}. \]

Example: Projection onto \(\{1,x\}\)

To approximate \(f\) by \(p(x)=a+bx\) in the least-squares sense, require

\[ \langle f-p,1\rangle=0 \]

and

\[ \langle f-p,x\rangle=0. \]

These orthogonality equations determine \(a\) and \(b\).

Example: Chebyshev Evaluation

Since \(T_2(x)=2x^2-1\), at \(x=\frac12\),

\[ T_2\left(\frac12\right)=2\left(\frac14\right)-1=-\frac12. \]

Therefore,

\[ \boxed{T_2\left(\frac12\right)=-\frac12}. \]

Example: Maximum Error

Suppose on \([0,1]\),

\[ |f(x)-p(x)|\le0.003 \]

for every \(x\). Then

\[ \boxed{\|f-p\|_\infty\le0.003}. \]

Practice 1: Approximation Error

If \(f(x)=e^x\) and \(p(x)=1+x\), write the error function \(e(x)\).

Practice 2: Maximum Norm

What does \(\|f-p\|_\infty\) measure?

Practice 3: Least-Squares Objective

For data \((x_i,y_i)\), write the discrete least-squares objective for a model \(p(x)\).

Practice 4: Orthogonality Condition

In continuous least squares, what condition does the error satisfy relative to every basis function in the approximation space?

Practice 5: Chebyshev Recurrence

Complete:

\[ T_{n+1}(x)=\ ? \]

Practice 6: Taylor Approximation

Write the quadratic Taylor approximation of \(e^x\) about \(x=0\).

Practice 7: Minimax Meaning

What quantity does a minimax polynomial minimize?

Practice 8: Rational Approximation

Write the general form of a rational approximant with numerator degree \(m\) and denominator degree \(n\).

Practice 9: Scaling an Interval

Map \(x\in[a,b]\) to \(t\in[-1,1]\).

Practice 10: Method Selection

Which approximation family is especially natural for:

  1. a smooth periodic function;
  2. a function with pole-like behavior;
  3. noisy sampled data?

Practice Answers

Practice 1

\[ \boxed{e(x)=e^x-(1+x)}. \]

Practice 2

It measures the largest absolute approximation error on the interval:

\[ \boxed{\|f-p\|_\infty=\max |f(x)-p(x)|}. \]

Practice 3

\[ \boxed{\sum_i\left(y_i-p(x_i)\right)^2}. \]

Practice 4

\[ \boxed{\langle f-p,\phi_k\rangle=0}. \]

Practice 5

\[ \boxed{T_{n+1}(x)=2xT_n(x)-T_{n-1}(x)}. \]

Practice 6

\[ \boxed{1+x+\frac{x^2}{2}}. \]

Practice 7

It minimizes the worst-case or maximum error:

\[ \boxed{\|f-p\|_\infty}. \]

Practice 8

\[ \boxed{r(x)=\frac{p_m(x)}{q_n(x)}}. \]

Practice 9

\[ \boxed{t=\frac{2x-(a+b)}{b-a}}. \]

Practice 10

  1. smooth periodic function: trigonometric or Fourier approximation;
  2. pole-like behavior: rational approximation;
  3. noisy sampled data: least-squares approximation.

What to Remember

Function approximation replaces a complicated target \(f\) with a simpler function \(p\):

\[ \boxed{f(x)\approx p(x)}. \]

Where We Go Next

Once a function has been represented approximately, nearby values or approximating polynomials can be used to estimate derivatives. Differentiation is numerically delicate because it tends to amplify noise and rounding error.

The next lesson, Numerical Differentiation, develops finite differences, forward, backward, and central formulas, truncation error, Richardson extrapolation, step-size selection, and the balance between approximation error and floating-point error.