sections, this is usually done by suitably approximating the integrals that

appear in the de¬nition of fk . By doing so, one gets the so-called discrete

˜

coe¬cients fk of f , and, as a consequence, the new polynomial

n

— ˜

fn (x) = fk pk (x) (10.4)

k=0

which is called the discrete truncation of order n of the Fourier series of f .

Typically,

(f, pk )n

˜

fk = , (10.5)

pk 2 n

where, for any pair of continuous functions f and g, (f, g)n is the approxi-

mation of the scalar product (f, g)w and g n = (g, g)n is the seminorm

associated with (·, ·)w . In a manner analogous to what was done for fn , it

can be checked that

—

f ’ fn = min f ’ q (10.6)

n n

q∈Pn

—

and we say that fn is the approximation to f in Pn in the least-squares

sense (the reason for using this name will be made clear later on).

We conclude this section by recalling that, for any family of monic orthog-

onal polynomials {pk }, the following recursive three-term formula holds (for

the proof, see for instance [Gau96])

pk+1 (x) = (x ’ ±k )pk (x) ’ βk pk’1 (x) k ≥ 0,

(10.7)

p’1 (x) = 0, p0 (x) = 1,

where

(xpk , pk )w (pk+1 , pk+1 )w

k ≥ 0.

±k = , βk+1 = , (10.8)

(pk , pk )w (pk , pk )w

Since p’1 = 0, the coe¬cient β0 is arbitrary and is chosen according to

the particular family of orthogonal polynomials at hand. The recursive

three-term relation is generally quite stable and can thus be conveniently

employed in the numerical computation of orthogonal polynomials, as will

be seen in Section 10.6.

In the forthcoming sections we introduce two relevant families of orthogonal

polynomials.

10.1.1 The Chebyshev Polynomials

Consider the Chebyshev weight function w(x) = (1’x2 )’1/2 on the interval

(’1, 1), and, according to (10.1), introduce the space of square-integrable

418 10. Orthogonal Polynomials in Approximation Theory

functions with respect to the weight w

1

f 2 (x)(1 ’ x2 )’1/2 dx < ∞ .

f : (’1, 1) ’ R :

L2 (’1, 1) =

w

’1

A scalar product and a norm for this space are de¬ned as

1

f (x)g(x)(1 ’ x2 )’1/2 dx,

(f, g)w =

’1

± 1/2 (10.9)

1

f 2 (x)(1 ’ x2 )’1/2 dx

f = .

w

’1

The Chebyshev polynomials are de¬ned as follows

Tk (x) = cos kθ, θ = arccos x, k = 0, 1, 2, . . . (10.10)

They can be recursively generated by the following formula (a consequence

of (10.7), see [DR75], pp. 25-26)

±

Tk+1 (x) = 2xTk (x) ’ Tk’1 (x) k = 1, 2, . . .

(10.11)

T0 (x) = 1, T1 (x) = x.

In particular, for any k ≥ 0, we notice that Tk ∈ Pk , i.e., Tk (x) is an alge-

braic polynomial of degree k with respect to x. Using well-known trigono-

metric relations, we have

c0 = π if n = 0,

(Tk , Tn )w = 0 if k = n, (Tn , Tn )w =

cn = π/2 if n = 0,

which expresses the orthogonality of the Chebyshev polynomials with re-

spect to the scalar product (·, ·)w . Therefore, the Chebyshev series of a

function f ∈ L2 takes the form

w

1

∞

1

f (x)Tk (x)(1 ’ x2 )’1/2 dx.

Cf = fk Tk , with fk =

ck

k=0 ’1

Notice that Tn = 1 for every n and the following minimax property

∞

holds

¤ min p

21’n Tn ∞,

∞ 1

p∈Pn

n

where P1 = {p(x) = k=0 ak xk , an = 1} denotes the subset of polynomials

n

of degree n with leading coe¬cient equal to 1.

10.2 Gaussian Integration and Interpolation 419

10.1.2 The Legendre Polynomials

The Legendre polynomials are orthogonal polynomials over the interval

(’1, 1) with respect to the weight function w(x) = 1. For these polynomials,

L2 is the usual L2 (’1, 1) space introduced in (8.25), while (·, ·)w and · w

w

coincide with the scalar product and norm in L2 (’1, 1), respectively given

by

« 1

2

1 1

= f 2 (x) dx .

(f, g) = f (x)g(x) dx, f L2 (’1,1)

’1 ’1

The Legendre polynomials are de¬ned as

[k/2]

2k ’ 2l

1 k

(’1)l xk’2l

Lk (x) = k k = 0, 1, . . . (10.12)

l k

2

l=0

where [k/2] is the integer part of k/2, or, recursively, through the three-

term relation

±

2k + 1 k

L

k+1 (x) = xLk (x) ’ Lk’1 (x) k = 1, 2 . . .

k+1 k+1

L0 (x) = 1, L1 (x) = x.

For every k = 0, 1 . . . , Lk ∈ Pk and (Lk , Lm ) = δkm (k + 1/2)’1 for k, m =

0, 1, 2, . . . . For any function f ∈ L2 (’1, 1), its Legendre series takes the

following form

1

∞ ’1

1

Lf = fk Lk , with fk = k+ f (x)Lk (x)dx.

2

k=0 ’1

Remark 10.1 (The Jacobi polynomials) The polynomials previously

±β

introduced belong to the wider family of Jacobi polynomials {Jk , k =

0, . . . , n}, that are orthogonal with respect to the weight w(x) = (1 ’

x)± (1 + x)β , for ±, β > ’1. Indeed, setting ± = β = 0 we recover the

Legendre polynomials, while choosing ± = β = ’1/2 gives the Chebyshev

polynomials.

10.2 Gaussian Integration and Interpolation

Orthogonal polynomials play a crucial role in devising quadrature formulae

with maximal degrees of exactness. Let x0 , . . . , xn be n + 1 given distinct

points in the interval [’1, 1]. For the approximation of the weighted integral

420 10. Orthogonal Polynomials in Approximation Theory

1

Iw (f ) = ’1 f (x)w(x)dx, being f ∈ C 0 ([’1, 1]), we consider quadrature

rules of the type

n

In,w (f ) = ±i f (xi ) (10.13)

i=0

where ±i are coe¬cients to be suitably determined. Obviously, both nodes

and weights depend on n, however this dependence will be understood.

Denoting by

En,w (f ) = Iw (f ) ’ In,w (f )

the error between the exact integral and its approximation (10.13), if

En,w (p) = 0 for any p ∈ Pr (for a suitable r ≥ 0) we shall say that for-

mula (10.13) has degree of exactness r with respect to the weight w. This

de¬nition generalizes the one given for ordinary integration with weight

w = 1.

Clearly, we can get a degree of exactness equal to (at least) n taking

1

In,w (f ) = Πn f (x)w(x)dx

’1

where Πn f ∈ Pn is the Lagrange interpolating polynomial of the function

f at the nodes {xi , i = 0, . . . , n}, given by (8.4). Therefore, (10.13) has

degree of exactness at least equal to n taking

1

±i = li (x)w(x)dx, i = 0, . . . , n, (10.14)

’1

where li ∈ Pn is the i-th characteristic Lagrange polynomial such that

li (xj ) = δij , for i, j = 0, . . . , n.

The question that arises is whether suitable choices of the nodes exist

such that the degree of exactness is greater than n, say, equal to r = n + m

for some m > 0. The answer to this question is furnished by the following

theorem, due to Jacobi [Jac26].

Theorem 10.1 For a given m > 0, the quadrature formula (10.13) has

degree of exactness n + m i¬ it is of interpolatory type and the nodal poly-

nomial ωn+1 (8.6) associated with the nodes {xi } is such that

1

∀p ∈ Pm’1 .

ωn+1 (x)p(x)w(x)dx = 0, (10.15)

’1

Proof. Let us prove that these conditions are su¬cient. If f ∈ Pn+m then

there exist a quotient πm’1 ∈ Pm’1 and a remainder qn ∈ Pn , such that f =

10.2 Gaussian Integration and Interpolation 421

ωn+1 πm’1 + qn . Since the degree of exactness of an interpolatory formula with

n + 1 nodes is equal to n (at least), we get

1 1 1

n

f (x)w(x)dx ’

±i qn (xi ) = qn (x)w(x)dx = ωn+1 (x)πm’1 (x)w(x)dx.

i=0 ’1 ’1 ’1

As a consequence of (10.15), the last integral is null, thus

1 n n

f (x)w(x)dx = ±i qn (xi ) = ±i f (xi ).

i=0 i=0

’1

Since f is arbitrary, we conclude that En,w (f ) = 0 for any f ∈ Pn+m . Proving

3

that the conditions are also necessary is an exercise left to the reader.

Corollary 10.1 The maximum degree of exactness of the quadrature for-

mula (10.13) is 2n + 1.

Proof. If this would not be true, one could take m ≥ n + 2 in the previous

theorem. This, in turn, would allow us to choose p = ωn+1 in (10.15) and come

3

to the conclusion that ωn+1 is identically zero, which is absurd.

Setting m = n + 1 (the maximum admissible value), from (10.15) we get

that the nodal polynomial ωn+1 satis¬es the relation

1

∀p ∈ Pn .

ωn+1 (x)p(x)w(x)dx = 0,

’1

Since ωn+1 is a polynomial of degree n + 1 orthogonal to all the polyno-

mials of lower degree, we conclude that ωn+1 is the only monic polynomial

multiple of pn+1 (recall that {pk } is the system of orthogonal polynomials

introduced in Section 10.1). In particular, its roots {xj } coincide with those

of pn+1 , that is

pn+1 (xj ) = 0, j = 0, . . . , n. (10.16)

The abscissae {xj } are the Gauss nodes associated with the weight func-

tion w(x). We can thus conclude that the quadrature formula (10.13) with

coe¬cients and nodes given by (10.14) and (10.16), respectively, has degree

of exactness 2n + 1, the maximum value that can be achieved using inter-

polatory quadrature formulae with n + 1 nodes, and is called the Gauss

quadrature formula.

Its weights are all positive and the nodes are internal to the interval

(’1, 1) (see, for instance, [CHQZ88], p. 56). However, it is often useful to

also include the end points of the interval among the quadrature nodes. By

422 10. Orthogonal Polynomials in Approximation Theory

doing so, the Gauss formula with the highest degree of exactness is the one

that employs as nodes the n + 1 roots of the polynomial

ω n+1 (x) = pn+1 (x) + apn (x) + bpn’1 (x), (10.17)

where the constants a and b are selected in such a way that ω n+1 (’1) =

ω n+1 (1) = 0.

Denoting these roots by x0 = ’1, x1 , . . . , xn = 1, the coe¬cients {±i , i =

0, . . . , n} can then be obtained from the usual formulae (10.14), that is

1

±i = li (x)w(x)dx, i = 0, . . . , n,

’1

where li ∈ Pn is the i-th characteristic Lagrange polynomial such that

li (xj ) = δij , for i, j = 0, . . . , n. The quadrature formula

n

GL

In,w (f ) = ±i f (xi ) (10.18)

i=0

is called the Gauss-Lobatto formula with n + 1 nodes, and has degree of

exactness 2n ’ 1. Indeed, for any f ∈ P2n’1 , there exist a polynomial

πn’2 ∈ Pn’2 and a remainder qn ∈ Pn such that f = ω n+1 πn’2 + qn .

The quadrature formula (10.18) has degree of exactness at least equal to

n (being interpolatory with n + 1 distinct nodes), thus we get

1 1 1

n

f (x)w(x)dx ’

±j qn (xj ) = qn (x)w(x)dx = ω n+1 (x)πn’2 (x)w(x)dx.

j=0 ’1 ’1 ’1

From (10.17) we conclude that ωn+1 is orthogonal to all the polynomials

¯

of degree ¤ n ’ 2, so that the last integral is null. Moreover, since f (xj ) =

qn (xj ) for j = 0, . . . , n, we conclude that

1 n

∀f ∈ P2n’1 .

f (x)w(x)dx = ±i f (xi ),

i=0

’1

Denoting by ΠGL f the polynomial of degree n that interpolates f at the

n,w

nodes {xj , j = 0, . . . , n}, we get

n

ΠGL f (x) = f (xi )li (x) (10.19)

n,w

i=0

1

GL

ΠGL f (x)w(x)dx.

and thus In,w (f ) = ’1 n,w

10.2 Gaussian Integration and Interpolation 423

Remark 10.2 In the special case where the Gauss-Lobatto quadrature is

considered with respect to the Jacobi weight w(x) = (1 ’ x)± (1 ’ x)β ,

with ±, β > ’1, the internal nodes x1 , . . . , xn’1 can be identi¬ed as the

(±,β)

roots of the polynomial (Jn ) , that is, the extremants of the n-th Jacobi

(±,β)

polynomial Jn (see [CHQZ88], pp. 57-58).

The following convergence result holds for Gaussian integration (see [Atk89],

Chapter 5)

1 n

f (x)w(x)dx ’ ∀f ∈ C 0 ([’1, 1]).

lim ±j f (xj ) = 0,

n’+∞

j=0

’1

A similar result also holds for Gauss-Lobatto integration. If the integrand

function is not only continuous, but also di¬erentiable up to the order

p ≥ 1, we shall see that Gaussian integration converges with an order of

in¬nitesimal with respect to 1/n that is larger when p is greater. In the

forthcoming sections, the previous results will be speci¬ed in the cases of

the Chebyshev and Legendre polynomials.

Remark 10.3 (Integration over an arbitrary interval) A quadrature

formula with nodes ξj and coe¬cients βj , j = 0, . . . , n over the interval

[’1, 1] can be mapped on any interval [a, b]. Indeed, let • : [’1, 1] ’ [a, b]

be the a¬ne map x = •(ξ) = a+b ξ + b’a . Then

2 2

b 1

a+b

(f —¦ •)(ξ)dξ.

f (x)dx =

2

’1

a

Therefore, we can employ on the interval [a, b] the quadrature formula with

nodes xj = •(ξj ) and weights ±j = a+b βj . Notice that this formula main-

2

tains on the interval [a, b] the same degree of exactness of the generating

formula over [’1, 1]. Indeed, assuming that

1 n

p(ξ)dξ = p(ξj )βj

j=0

’1

for any polynomial p of degree r over [’1, 1] (for a suitable integer r), for

any polynomial q of the same degree on [a, b] we get

1 b

n n

a+b a+b

(q —¦ •)(ξj )βj = (q —¦ •)(ξ)dξ =

q(xj )±j = q(x)dx,

2 j=0 2

j=0 ’1 a