Chebyshev approximation

In the previous post I mentioned that Remez algorithm computes the best polynomial approximation to a given function f as measured by the maximum norm. That is, for a given n, it finds the polynomial p of order n that minimizes the absolute error

|| f - p ||_a.

The Mathematica function MiniMaxApproximation minimizes the relative error by minimizing

|| (f - p) / f ||_a.

As was pointed out in the comments to the previous post, Chebyshev approximation produces a nearly optimal approximation, coming close to minimizing the absolute error. The Chebyshev approximation can be computed more easily and the results are easier to understand.

To form a Chebyshev approximation, we expand a function in a series of Chebyshev polynomials, analogous to expanding a function in a Fourier series, and keep the first few terms. Like sines and cosines, Chebyshev polynomials are orthogonal functions, and so Chebyshev series are analogous to Fourier series. (If you find it puzzling to hear of functions being orthogonal to each other, see this post.)

Here is Mathematica code to find and plot the Chebyshev approximation to e^x over [-1, 1]. First, here are the coefficients.

 weight[x_] := 2/(Pi Sqrt[1 - x^2]) c = Table[ Integrate[ Exp[x] ChebyshevT[n, x] weight[x], {x, -1, 1}], {n, 0, 5}]

The coefficients turn out to be exactly expressible in terms of Bessel functions, but typically you'd need to do a numerical integration with NIntegrate.

Now we use the Chebyshev coefficients to evaluate the Chebyshev approximation.

 p[x_] := Evaluate[c . Table[ChebyshevT[n - 1, x], {n, Length[c]}]] - First[c]/2

You could see the approximating polynomial with

 Simplify[N[p[x]]]

which displays

 1.00004 + 1.00002 x + 0.499197 x^2 + 0.166489 x^3 + 0.0437939 x^4 + 0.00868682 x^5

The code

 Plot[Exp[x] - p[x], {x, -1, 1}]

shows the error in approximating the exponential function with the polynomial above.

Note that the plot has nearly equal ripples; the optimal approximation would have exactly equal ripples. The Chebyshev approximation is not optimal, but it is close. The absolute error is smaller than that of MiniMaxApproximation by a factor of about e.

There are bounds on how different the error can be between the best polynomial approximation and the Chebyshev series approximation. For polynomials of degree n, the Chebyshev error is never more than

4 + 4 log(n + 1)/I

times the Chebyshev series approximation error. See Theorem 16.1 in Approximation Theory and Approximation Practice by Lloyd N. Trefethen.

More Chebyshev posts

• Chebyshev interpolation
• Notes on Chebyshev polynomials
• Improving on Chebyshev's inequality