Chebyshev Polynomials

Three equivalent definitions

Chebyshev polynomials of the first kind are defined in three different ways, all giving the same family:

(1) Trigonometric. On [−1, 1], substitute x = cos θ for θ ∈ [0, π]:

T_n(x) = T_n(cos θ) = cos(n θ)

This is the cleanest definition. The cosine on the right is a polynomial in cos θ (by the multiple-angle formula), so T_n(x) is a polynomial in x. For example T_2(x) = cos(2θ) = 2cos²θ − 1 = 2x² − 1.

(2) Recurrence. Starting from T_0(x) = 1, T_1(x) = x, all higher polynomials follow from:

T_{n+1}(x) = 2 x T_n(x) − T_{n−1}(x)

This is the recurrence used in code; it's numerically stable on [−1, 1] and runs in O(n) time.

(3) As a solution. T_n(x) satisfies the second-order ODE:

(1 − x²) y'' − x y' + n² y = 0

This places Chebyshev polynomials inside the larger family of classical orthogonal polynomials, with weight w(x) = 1/√(1 − x²).

The first six Chebyshev polynomials

n	T_n(x)	From identity cos(nθ)
0	1	cos(0) = 1
1	x	cos(θ) = x
2	2x² − 1	cos(2θ) = 2cos²θ − 1
3	4x³ − 3x	cos(3θ) = 4cos³θ − 3cosθ
4	8x⁴ − 8x² + 1	cos(4θ) = 8cos⁴θ − 8cos²θ + 1
5	16x⁵ − 20x³ + 5x	cos(5θ)
6	32x⁶ − 48x⁴ + 18x² − 1	cos(6θ)

Notice each leading coefficient doubles: 1, 1, 2, 4, 8, 16, 32. In general the leading coefficient of T_n for n ≥ 1 is 2^(n−1).

Equioscillation — the signature property

On [−1, 1], T_n(x) sweeps between +1 and −1 exactly n + 1 times, with extrema at the so-called Chebyshev extrema:

x_k = cos(k π / n),  k = 0, 1, ..., n
T_n(x_k) = cos(k π) = (−1)^k

So the values alternate: +1, −1, +1, −1, …, (−1)ⁿ. This is the equioscillation property — equal amplitude, alternating sign, n + 1 extrema, error envelope swings ±max with n + 2 extrema in the minimax problem. It is the defining geometric feature of Chebyshev polynomials and the reason they solve the minimax problem.

Chebyshev's equioscillation theorem. Among all continuous functions p with deg p ≤ n, the best uniform approximation to f on [a, b] is characterized by the property that the error e(x) = f(x) − p(x) equioscillates — attains its maximum absolute value with alternating signs at least n + 2 times. T_n itself is the best uniform approximation to the zero function with leading coefficient pinned at 2^(n−1): the error equioscillates by construction.

The minimax property in detail

Among all monic polynomials p(x) = xⁿ + lower-order terms, the one that minimises max_{x ∈ [−1, 1]} |p(x)| is the scaled Chebyshev polynomial:

p*(x) = 2^{1−n} T_n(x),    with max |p*(x)| = 2^{1−n}

Any other monic degree-n polynomial has max-norm strictly greater than 2^{1−n} on [−1, 1]. For comparison, the monic polynomial xⁿ itself has max-norm 1, much worse than 2^{1−n} for large n. Picking different leading-coefficient targets just rescales.

This is the deep reason Chebyshev nodes are the right grid for polynomial interpolation: the error of polynomial interpolation at n nodes x_0, …, x_{n−1} is proportional to ∏(x − x_k), and the product polynomial achieves its minimum max-norm — and hence smallest worst-case interpolation error — when the x_k are Chebyshev nodes.

Defeating the Runge phenomenon

If you sample f(x) = 1/(1 + 25x²) at n + 1 equally spaced points on [−1, 1] and fit a degree-n interpolating polynomial, the result has wild oscillations near x = ±1 that get worse as n grows. Even though the underlying function is smooth, the error blows up:

n = 4:  max error ≈ 0.4
n = 10: max error ≈ 1.9
n = 20: max error ≈ 60 (grows without bound)

This is the Runge phenomenon, discovered by Carl Runge in 1901. It is caused by sampling too coarsely near the endpoints. Switch to Chebyshev nodes:

x_k = cos((2k − 1) π / (2n)),  k = 1, 2, ..., n

and the interpolation error decreases monotonically with n for the same Runge function:

n = 4:  max error ≈ 0.4
n = 10: max error ≈ 0.10
n = 20: max error ≈ 0.018 (decreasing nicely)

The Chebyshev nodes are denser near ±1 (precisely where equally spaced nodes are scarce), undoing the asymmetry that creates the Runge oscillation.

Orthogonality

With weight w(x) = 1/√(1 − x²), Chebyshev polynomials are orthogonal on [−1, 1]:

∫_{−1}^{1} T_m(x) T_n(x) / √(1 − x²) dx = 0  (m ≠ n)
                                          = π   (m = n = 0)
                                          = π/2 (m = n ≥ 1)

Substituting x = cos θ turns this into ∫₀^π cos(mθ) cos(nθ) dθ — just the orthogonality of cosines, dressed up. Any function f on [−1, 1] can be expanded as a Chebyshev series:

f(x) = (c_0 / 2) + ∑_{n=1}^∞ c_n T_n(x)
c_n = (2/π) ∫_{−1}^{1} f(x) T_n(x) / √(1 − x²) dx

For smooth functions, the coefficients c_n decay exponentially in n — much faster than the algebraic decay of Fourier coefficients of non-periodic functions. Truncating the Chebyshev series at degree N gives a near-minimax polynomial approximation, only slightly worse than the true minimax polynomial.

JavaScript — Chebyshev polynomials and interpolation

// Evaluate T_n(x) via recurrence
function chebyshev(n, x) {
  if (n === 0) return 1;
  if (n === 1) return x;
  let Tprev = 1, Tcurr = x;
  for (let k = 2; k <= n; k++) {
    const Tnext = 2 * x * Tcurr - Tprev;
    Tprev = Tcurr;
    Tcurr = Tnext;
  }
  return Tcurr;
}

// Chebyshev nodes on [-1, 1]
function chebyshevNodes(n) {
  const nodes = [];
  for (let k = 1; k <= n; k++) {
    nodes.push(Math.cos((2 * k - 1) * Math.PI / (2 * n)));
  }
  return nodes;
}

// Chebyshev interpolation of a function f on [-1, 1]
function chebyshevInterp(f, x, n) {
  const nodes = chebyshevNodes(n);
  // barycentric form with Chebyshev weights w_k = (-1)^k sin((2k+1)pi/2n)
  let num = 0, den = 0;
  for (let k = 0; k < n; k++) {
    if (x === nodes[k]) return f(nodes[k]);
    const wk = (k % 2 === 0 ? 1 : -1) * Math.sin((2*k + 1) * Math.PI / (2*n));
    const t = wk / (x - nodes[k]);
    num += t * f(nodes[k]);
    den += t;
  }
  return num / den;
}

// Demonstrate against Runge's function 1/(1+25 x²)
const runge = x => 1 / (1 + 25 * x * x);
console.log(chebyshevInterp(runge, 0.95, 20).toFixed(4));  // very close to true
console.log(runge(0.95).toFixed(4));

Chebyshev vs other approximation bases

	Taylor	Chebyshev	Minimax (Remez)
Optimises	Error at expansion point	Near-uniform error on [−1, 1]	Uniform error (theoretical optimum)
Error structure	Tiny at center, large at edges	Roughly uniform with mild edge variation	Perfectly equioscillating
Coefficient computation	Derivatives at one point	Cosine integrals (or DCT)	Remez iteration (numerical)
Convergence rate (smooth f)	Geometric near center	Geometric, uniform on [−1, 1]	Geometric, optimal constant
Practical use	Theory, local approximations	libm-style table-free function evaluation	Hand-tuned math library polynomials
Cost	Cheap	O(n log n) via DCT	Expensive offline computation

In practice, math libraries use minimax (Remez) polynomials for production code but the polynomials themselves look nearly identical to truncated Chebyshev series — within a few percent in the coefficients. The Chebyshev expansion is the natural starting point for Remez iteration.

Chebyshev filters in DSP

Analog and digital filter design uses the equiripple property of Chebyshev polynomials to maximise rolloff steepness for a given passband distortion:

• Chebyshev Type I. Equiripple in passband, monotone in stopband. The magnitude squared is 1/(1 + ε² T_n²(ω/ω_p)) — ripples follow T_n.
• Chebyshev Type II. Monotone passband, equiripple stopband. Same idea, swapped role.
• Elliptic (Cauer) filters. Equiripple in both — uses Jacobi elliptic functions, an extension of the Chebyshev idea.

For the same filter order, a Chebyshev Type I filter has a steeper transition band than a Butterworth (which is monotone everywhere) at the cost of some passband ripple. Both Chebyshev variants beat Butterworth in transition-band steepness; only the elliptic filter is steeper still, at the cost of ripple in both bands.

Where Chebyshev polynomials show up

• Math libraries (libm, glibc, Intel MKL). Sin, cos, exp, log are evaluated using minimax polynomials derived from Chebyshev expansions. Argument reduction first, then a degree-5 to degree-15 polynomial.
• Spectral methods for PDEs. Chebyshev collocation and Chebyshev–Galerkin methods solve PDEs on bounded intervals with exponential convergence for smooth solutions. ChebFun is a MATLAB library entirely built around this idea.
• Filter design. Chebyshev type I/II analog and digital filters; equiripple FIR filter design (Parks–McClellan algorithm produces equiripple FIR filters).
• Solving polynomials. Companion matrix of a Chebyshev polynomial expansion has good conditioning, used by MATLAB's roots and similar tools to find polynomial roots.
• Surveying and least-squares. Chebyshev's name attaches to many discrete-optimization "minimax fitting" methods.
• Quantum mechanics — Chebyshev propagation. Time evolution operator e^{−i H t/ℏ} expanded in Chebyshev polynomials of the Hamiltonian — converges spectrally fast.

Common mistakes

• Confusing T_n with U_n. Chebyshev polynomials of the second kind U_n(cos θ) = sin((n + 1)θ)/sin θ are a different family with weight √(1 − x²). U_n appears as the derivative of T_{n+1} divided by (n + 1) and in inversion problems, but T_n is the workhorse for minimax approximation.
• Using equally spaced nodes for high-degree interpolation. The Runge phenomenon makes equally spaced interpolation useless beyond degree ~10 for non-periodic functions. Switch to Chebyshev nodes.
• Ignoring the weight in orthogonality. Chebyshev orthogonality is under ∫·dx/√(1 − x²), not plain Lebesgue. Coefficient formulas must include the weight.
• Evaluating T_n via the explicit polynomial form for large n. Coefficients alternate sign and grow as 2^n. The recurrence T_{n+1} = 2x T_n − T_{n−1} is dramatically more stable.
• Thinking Chebyshev is the minimax polynomial. T_n itself is the minimax-norm monic polynomial of degree n. For best approximation of a given function f, the minimax polynomial is found by Remez — typically very close to the truncated Chebyshev expansion but not identical.
• Stretching beyond [−1, 1]. The minimax property is for [−1, 1]. To approximate on [a, b], linearly remap x ↦ (2x − a − b)/(b − a) and use Chebyshev there.