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.