3Approximation of linear functionals

IB Numerical Analysis

3.2 Gaussian quadrature

The objective of Gaussian quadrature is to approximate integrals of the form

L(f) =

Z

b

a

w(x)f(x) dx,

where w(x) is a weight function that determines a scalar product.

Traditionally, we have a different set of notations used for Gaussian quadra-

ture. So just in this section, we will use some funny notation that is inconsistent

with the rest of the course.

We let

hf, gi =

Z

b

a

w(x)f(x)g(x) dx

be a scalar product for

P

ν

[

x

]. We will show that we can find weights, written

{b

n

}

ν

k=1

, and nodes, written {c

k

}

ν

k=1

⊆ [a, b], such that the approximation

Z

b

a

w(x)f(x) dx ≈

ν

X

k=1

b

k

f(c

k

)

is exact for

f ∈ P

2ν−1

[

x

]. The nodes

{c

k

}

ν

k=1

will turn out to be the zeros of

the orthogonal polynomial

p

ν

with respect to the scalar product. The aim of

this section is to work this thing out.

We start by showing that this is the best we can achieve.

Proposition.

There is no choice of

ν

weights and nodes such that the approxi-

mation of

R

b

a

w(x)f(x) dx is exact for all f ∈ P

2ν

[x].

Proof. Define

q(x) =

ν

Y

k=1

(x − c

k

) ∈ P

ν

[x].

Then we know

Z

b

a

w(x)q

2

(x) dx > 0,

since q

2

is always non-negative and has finitely many zeros. However,

ν

X

k=1

b

k

q

2

(c

n

) = 0.

So this cannot be exact for q

2

.

Recall that we initially had the idea of doing the approximation by interpo-

lating f at some arbitrary points in [a, b]. We call this ordinary quadrature.

Theorem

(Ordinary quadrature)

.

For any distinct

{c

k

}

ν

k=1

⊆

[

a, b

], let

{`

k

}

ν

k=1

be the Lagrange cardinal polynomials with respect to

{c

k

}

ν

k=1

. Then by choosing

b

k

=

Z

b

a

w(x)`

k

(x) dx,

the approximation

L(f) =

Z

b

a

w(x)f(x) dx ≈

ν

X

k=1

b

k

f(c

k

)

is exact for f ∈ P

ν−1

[x].

We call this method ordinary quadrature.

This simple idea is how we generate many classical numerical integration

techniques, such as the trapezoidal rule. But those are quite inaccurate. It turns

out a clever choice of

{c

k

}

does much better — take them to be the zeros of

the orthogonal polynomials. However, to do this, we must make sure the roots

indeed lie in [

a, b

]. This is what we will prove now — given any inner product,

the roots of the orthogonal polynomials must lie in [a, b].

Theorem.

For

ν ≥

1, the zeros of the orthogonal polynomial

p

ν

are real, distinct

and lie in (a, b).

We have in fact proved this for a particular case in IB Methods, and the

same argument applies.

Proof.

First we show there is at least one root. Notice that

p

0

= 1. Thus for

ν ≥ 1, by orthogonality, we know

Z

b

a

w(x)p

ν

(x)p

1

(x) dx =

Z

b

a

w(x)p

ν

(x) dx = 0.

So there is at least one sign change in (

a, b

). We have already got the result we

need for ν = 1, since we only need one zero in (a, b).

Now for

ν >

1, suppose

{ξ

j

}

m

j=1

are the places where the sign of

p

ν

changes

in (a, b) (which is a subset of the roots of p

ν

). We define

q(x) =

m

Y

j=1

(x − ξ

j

) ∈ P

m

[x].

Since this changes sign at the same place as

p

ν

, we know

qp

ν

maintains the same

sign in (a, b). Now if we had m < ν, then orthogonality gives

hq, p

ν

i =

Z

b

a

w(x)q(x)p

ν

(x) dx = 0,

which is impossible, since

qp

ν

does not change sign. Hence we must have

m = ν.

Theorem.

In the ordinary quadrature, if we pick

{c

k

}

ν

k=1

to be the roots of

p

ν

(

x

), then get we exactness for

f ∈ P

2ν−1

[

x

]. In addition,

{b

n

}

ν

k=1

are all

positive.

Proof. Let f ∈ P

2ν−1

[x]. Then by polynomial division, we get

f = qp

ν

+ r,

where

q, r

are polynomials of degree at most

ν −

1. We apply orthogonality to

get

Z

b

a

w(x)f(x) dx =

Z

b

a

w(x)(q(x)p

ν

(x) + r(x)) dx =

Z

b

a

w(x)r(x) dx.

Also, since each c

k

is a root of p

ν

, we get

ν

X

k=1

b

k

f(c

k

) =

ν

X

k=1

b

k

(q(c

k

)p

ν

(c

k

) + r(c

k

)) =

ν

X

k=1

b

k

r(c

k

).

But

r

has degree at most

ν −

1, and this formula is exact for polynomials in

P

ν−1

[x]. Hence we know

Z

b

a

w(x)f(x) dx =

Z

b

a

w(x)r(x) dx =

ν

X

k=1

b

k

r(c

k

) =

ν

X

k=1

b

k

f(c

k

).

To show the weights are positive, we simply pick as special

f

. Consider

f ∈

{`

2

k

}

ν

k=1

⊆ P

2ν−2

[

x

], for

`

k

the Lagrange cardinal polynomials for

{c

k

}

ν

k=1

. Since

the quadrature is exact for these, we get

0 <

Z

b

a

w(x)`

2

k

(x) dx =

ν

X

j=1

b

j

`

2

k

(c

j

) =

ν

X

j=1

b

j

δ

jk

= b

k

.

Since this is true for all k = 1, ··· , ν, we get the desired result.