Let $f(x)$ be continuous on a closed interval $[a,b]$. Then there exists a unique $n$th degree polynomial $p_n(x)$, called the minimax (or best uniform) polynomial approximation to $f(x)$ on $[a,b]$, that minimizes ${\max }_{a\le x\le b}\left|{ϵ}_n(x)\right|$, where ${ϵ}_n(x)=f(x)-p_n(x)$.

A sufficient condition for $p_n(x)$ to be the minimax polynomial is that $\left|{ϵ}_n(x)\right|$ attains its maximum at $n+2$ distinct points in $[a,b]$ and ${ϵ}_n(x)$ changes sign at these consecutive maxima.

If we have a sufficiently close approximation

to $f(x)$, then the coefficients $a_k$ can be computed iteratively. Assume that $f^{\prime }(x)$ is continuous on $[a,b]$ and let $x_0=a$, $x_{n+1}=b$, and $x_1,x_2,\mathrm{\dots },x_n$ be the zeros of ${ϵ}_n^{\prime }(x)$ in $(a,b)$ arranged so that

Also, let

(Thus the $m_j$ are approximations to $m$, where $\pm m$ is the maximum value of $\left|{ϵ}_n(x)\right|$ on $[a,b]$.)

Then (in general) a better approximation to $p_n(x)$ is given by

where

This is a set of $n+2$ equations for the $n+2$ unknowns $𝛿a_0,𝛿a_1,\mathrm{\dots },𝛿a_n$ and $m$.

The iterative process converges locally and quadratically (§3.8(i)).

A method for obtaining a sufficiently accurate first approximation is described in the next subsection.

For the theory of minimax approximations see Meinardus (1967). For examples of minimax polynomial approximations to elementary and special functions see Hart et al. (1968). See also Cody (1970) and Ralston (1965).

The Chebyshev polynomials $T_n$ are given by

They satisfy the recurrence relation

with initial values $T_0\left(x\right)=1$, $T_1\left(x\right)=x$. They enjoy an orthogonal property with respect to integrals:

as well as an orthogonal property with respect to sums, as follows. When $n>0$ and $0\le j\le n$, $0\le k\le n$,

where $x_{\mathrm{\ell }}=\cos \left(\pi \mathrm{\ell }/n\right)$ and the double prime means that the first and last terms are to be halved.

For these and further properties of Chebyshev polynomials, see Chapter 18, Gil et al. (2007a, Chapter 3), and Mason and Handscomb (2003).

Let $f$ be continuous on a closed interval $[a,b]$ and $w$ be a continuous nonvanishing function on $[a,b]$: $w$ is called a weight function. Then the minimax (or best uniform) rational approximation

of type $[k,\mathrm{\ell }]$ to $f$ on $[a,b]$ minimizes the maximum value of $\left|{ϵ}_{k,\mathrm{\ell }}(x)\right|$ on $[a,b]$, where

The theory of polynomial minimax approximation given in §3.11(i) can be extended to the case when $p_n(x)$ is replaced by a rational function $R_{k,\mathrm{\ell }}(x)$. There exists a unique solution of this minimax problem and there are at least $k+\mathrm{\ell }+2$ values $x_j$, , such that $m_j=m$, where

and $\pm m$ is the maximum of $\left|{ϵ}_{k,\mathrm{\ell }}(x)\right|$ on $[a,b]$.

A collection of minimax rational approximations to elementary and special functions can be found in Hart et al. (1968).

A widely implemented and used algorithm for calculating the coefficients $p_j$ and $q_j$ in (3.11.16) is Remez’s second algorithm. See Remez (1957), Werner et al. (1967), and Johnson and Blair (1973).

Let

be a formal power series. The rational function

is called a Padé approximant at zero of $f$ if

It is denoted by ${[p/q]}_f\left(z\right)$. Thus if $b_0\ne 0$, then the Maclaurin expansion of (3.11.21) agrees with (3.11.20) up to, and including, the term in $z^{p+q}$.

The requirement (3.11.22) implies

where $c_j=0$ if . With $b_0=1$, the last $q$ equations give $b_1,\mathrm{\dots },b_q$ as the solution of a system of linear equations. The first $p+1$ equations then yield $a_0,\mathrm{\dots },a_p$.

The array of Padé approximants

is called a Padé table. Approximants with the same denominator degree are located in the same column of the table.

For convergence results for Padé approximants, and the connection with continued fractions and Gaussian quadrature, see Baker and Graves-Morris (1996, §4.7).

The Padé approximants can be computed by Wynn’s cross rule. Any five approximants arranged in the Padé table as

satisfy

Starting with the first column ${[n/0]}_f$, $n=0,1,2,\mathrm{\dots }$, and initializing the preceding column by ${[n/-1]}_f=\mathrm{\infty }$, $n=1,2,\mathrm{\dots }$, we can compute the lower triangular part of the table via (3.11.25). Similarly, the upper triangular part follows from the first row ${[0/n]}_f$, $n=0,1,2,\mathrm{\dots }$, by initializing ${[-1/n]}_f=0$, $n=1,2,\mathrm{\dots }$.

For the recursive computation of ${[n+k/k]}_f$ by Wynn’s epsilon algorithm, see (3.9.11) and the subsequent text.

Suppose a function $f(x)$ is approximated by the polynomial

that minimizes

Here $x_j$, $j=1,2,\mathrm{\dots },J$, is a given set of distinct real points and $J\ge n+1$. From the equations $\partial S/\partial a_k=0$, $k=0,1,\mathrm{\dots },n$, we derive the normal equations

where

(3.11.29) is a system of $n+1$ linear equations for the coefficients $a_0,a_1,\mathrm{\dots },a_n$. The matrix is symmetric and positive definite, but the system is ill-conditioned when $n$ is large because the lower rows of the matrix are approximately proportional to one another. If $J=n+1$, then $p_n(x)$ is the Lagrange interpolation polynomial for the set $x_1,x_2,\mathrm{\dots },x_J$ (§3.3(i)).

More generally, let $f(x)$ be approximated by a linear combination

of given functions ${\varphi }_k(x)$, $k=0,1,\mathrm{\dots },n$, that minimizes

$w(x)$ being a given positive weight function, and again $J\ge n+1$. Then (3.11.29) is replaced by

with

and

Since $X_{k\mathrm{\ell }}=X_{\mathrm{\ell }k}$, the matrix is again symmetric.

If the functions ${\varphi }_k(x)$ are linearly independent on the set $x_1,x_2,\mathrm{\dots },x_J$, that is, the only solution of the system of equations

is $c_0=c_1=\mathrm{\cdots }=c_n=0$, then the approximation ${\mathrm{\Phi }}_n(x)$ is determined uniquely.

Now suppose that $X_{k\mathrm{\ell }}=0$ when $k\ne \mathrm{\ell }$, that is, the functions ${\varphi }_k(x)$ are orthogonal with respect to weighted summation on the discrete set $x_1,x_2,\mathrm{\dots },x_J$. Then the system (3.11.33) is diagonal and hence well-conditioned.

A set of functions ${\varphi }_0(x),{\varphi }_1(x),\mathrm{\dots },{\varphi }_n(x)$ that is linearly independent on the set $x_1,x_2,\mathrm{\dots },x_J$ (compare (3.11.36)) can always be orthogonalized in the sense given in the preceding paragraph by the Gram–Schmidt procedure; see Gautschi (1997a).

Splines are defined piecewise and usually by low-degree polynomials. Given $n+1$ distinct points $x_k$ in the real interval $[a,b]$, with ($a=$)($=b$), on each subinterval $[x_k,x_{k+1}]$, $k=0,1,\mathrm{\dots },n-1$, a low-degree polynomial is defined with coefficients determined by, for example, values $f_k$ and $f_k^{\prime }$ of a function $f$ and its derivative at the nodes $x_k$ and $x_{k+1}$. The set of all the polynomials defines a function, the spline, on $[a,b]$. By taking more derivatives into account, the smoothness of the spline will increase.

For splines based on Bernoulli and Euler polynomials, see §24.17(ii).

For many applications a spline function is a more adaptable approximating tool than the Lagrange interpolation polynomial involving a comparable number of parameters; see §3.3(i), where a single polynomial is used for interpolating $f(x)$ on the complete interval $[a,b]$. Multivariate functions can also be approximated in terms of multivariate polynomial splines. See de Boor (2001), Chui (1988), and Schumaker (1981) for further information.

In computer graphics a special type of spline is used which produces a Bézier curve. A cubic Bézier curve is defined by four points. Two are endpoints: $(x_0,y_0)$ and $(x_3,y_3)$; the other points $(x_1,y_1)$ and $(x_2,y_2)$ are control points. The slope of the curve at $(x_0,y_0)$ is tangent to the line between $(x_0,y_0)$ and $(x_1,y_1)$; similarly the slope at $(x_3,y_3)$ is tangent to the line between $x_2,y_2$ and $x_3,y_3$. The curve is described by $x(t)$ and $y(t)$, which are cubic polynomials with $t\in [0,1]$. A complete spline results by composing several Bézier curves. A special applications area of Bézier curves is mathematical typography and the design of type fonts. See Knuth (1986, pp. 116-136).