9.3 Legendre and Chebyshev polynomials

For finite intervals, Legendre and Chebyshev polynomials are the ones most typically used. In the Chebyshev case, the polynomials themselves, their roots and quadrature points in general can be computed in closed form. They also satisfy a minmax property and lend themselves to using a fast Fourier transform (FFT).

9.3.1 Legendre

Legendre polynomials correspond to the trivial weight function ω ≡ 1 and the choice α = β = 0 in Eqs. (9.28View Equation, 9.29View Equation, 9.30View Equation). The eigenvalues are

λ = j(j + 1), (9.42 ) j
and the first two polynomials
P0 (x) = 1, P1 (x) = x. (9.43 )
A variation (in that it leads to non-monic polynomials) of the three term recurrence formula (9.40View Equation) is
( ) ( ) 2j + 1 j Pj+1(x) = N--+-1- xPj (x) − j +-1 Pj−1(x), j = 1,2,3,..., (9.44 )
leading to the normalization
∫1 ⟨Pi,Pj ⟩ω = Pi(x )Pj (x)dx = ---2---δij. (9.45 ) 2j + 1 − 1

9.3.2 Chebyshev

Chebyshev polynomials correspond to the choice 2 −1∕2 ω (x) = (1 − x ), x ∈ (− 1,1) and α = β = − 1∕2 in Eqs. (9.28View Equation, 9.29View Equation, 9.30View Equation). In particular, the eigenvalues are

2 λj = j . (9.46 )
A closed-form expression for Chebyshev polynomials (which lends itself to the use of FFT) is
( − 1 ) Tj (x ) = cos j cos (x ) , j = 0,1,2,.... (9.47 )
At first sight it might appear confusing that, given the above definition through trigonometric functions, T (x ) j are actually polynomials in x (of degree j, in fact). To get an idea of why this is so, we can compute the first few:
T0 (x ) = cos(0 ) = 1, − 1 T1 (x ) = cos(cos (x )) = x, −1 2 −1 T2 (x ) = cos(2 cos (x)) = − 1 + 2cos (cos (x)) = − 1 + 2x2.
Notice from the above expressions that T2(x) = 2xT1 (x) − T0. In fact, a slight variation of the three-term recurrence formula (9.40View Equation) for Chebyshev polynomials becomes
T0 (x) = 1, (9.48 ) T1 (x) = x, (9.49 ) Tj+1 (x) = 2xTj(x) − Tj−1, j = 1,2,3,.... (9.50 )
As in the Legendre case, this is a variation of Eqs. (9.38View Equation, 9.39View Equation, 9.40View Equation) in that the resulting polynomials are not monic: the leading coefficient is given by
Tj (x) = 2j−1xj + ..., (9.51 )
That is, the polynomial 1−j 2 Tj(x) is monic.

Both Eq. (9.47View Equation) and Eq. (9.50View Equation) lead to the normalization

( ∫1 |{ π for i = 0 ⟨T,T ⟩ = T (x)T (x )(1 − x2)−1∕2dx = δ . (9.52 ) i j ω i j ij|( π- − 1 2 for i > 0

From the explicit expression (9.47View Equation), it can be noticed that the roots {xj} of Tk are

( ) xj = − cos 2j +-1π , j = 0,1,2,...,k − 1. (9.53 ) 2k
These points play an important role below in Gauss quadratures and collocation methods (Section 9.4).

9.3.3 The minmax property of Chebyshev points

Chebyshev polynomials satisfy a rather remarkable property in the context of interpolation. In Section 8.1 we pointed out that the error in polynomial interpolation of a function f at (N + 1) nodal points xj satisfies [cf. Eq. (8.5View Equation)]

---1-----|| (N+1 ) || EN (x ) = (N + 1)! f (ξx)ωN+1 (x ) , (9.54 )
where ∏N ωN+1 (x) := j=0(x − xj).

When doing global interpolation, that is, keeping the endpoints {x0, xN} fixed and increasing N, it is not true that the error converges to zero even if the function is C ∞. For example, for each N, (N+1 ) f (x ) could remain bounded as a function of x,

|f(N+1)(x)| ≤ CN for all x ∈ [x0, xN], (9.55 )
but CN could grow with N. A classical example of non-convergence of polynomial interpolation on uniform grids is the following:

Example 53. Runge phenomenon (see, for instance, [154]).
Consider the function

f (x ) = --1---, x ∈ [− 5,5] (9.56 ) 1 + x2
and its interpolating polynomial ℐ [f](x) N [cf. Eq. (8.1View Equation)] at equally-spaced points
-i- xi = − 5 + N 10, i = 0,...,N . (9.57 )
Then
|f(x) − ℐN[f](x)| → ∞ as N → ∞ for all x satisfying xc < |x| < 5, (9.58 )
where xc ≈ 3.63.

The error (8.5View Equation) can be decomposed into two terms, one related to the behavior of the derivatives of f, f (N+1 )(ξx)∕(N + 1)!, and another related to the distribution of the nodal points, ωN+1 (x ). We assume in what follows that x ∈ [x0,xN ] and that [x0,xN ] = [− 1,1]. The analogue results for an arbitrary interval can easily be obtained by a shifting and rescaling of coordinates. It can then be shown that, for all choices of nodal points,

max |ωN+1 (x )| ≥ 2− N. (9.59 ) x∈[−1,1]
Furthermore, the nodes, which minimize this maximum (thus the minmax term), are the roots of the Chebyshev polynomial of order (n + 1 ), for which the equality is achieved:
−N xm∈a[−x1,1]|ωN+1 (x)| = 2 (9.60 )
when {x0,x1, ...,xN} are given by Eq. (9.53View Equation); see, for example, [138], for the proof.

In other words, using Chebyshev points, that is, the roots of the Chebyshev polynomials, as interpolating nodes, minimizes the maximum error associated with the nodal polynomial term. Notice that, in this case, the nodal polynomial is given by TN+1 (x)∕2N.


  Go to previous page Go up Go to next page