<< . .

. 60
( : 95)



. . >>

10.1 Approximation of Functions by Generalized Fourier Series 417

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

<< . .

. 60
( : 95)



. . >>