2Orthogonal polynomials
IB Numerical Analysis
2.3 Three-term recurrence relation
Recall that for the Chebyshev polynomials, we obtained a three-term recurrence
relation for them using special properties of the cosine. It turns out these
recurrence relations exist in general for orthogonal polynomials.
We start by picking
q
n+1
=
xp
n
in the previous proof. We now use the fact
that
hxf, gi = hf, xgi.
This is not necessarily true for arbitrary inner products, but for most sensible
inner products we will meet in this course, this is true. In particular, it is clearly
true for inner products of the form
hf, gi =
Z
w(x)f(x)g(x) dx.
Assuming this, we obtain the following theorem.
Theorem. Monic orthogonal polynomials are generated by
p
k+1
(x) = (x − α
k
)p
k
(x) − β
k
p
k−1
(x)
with initial conditions
p
0
= 1, p
1
(x) = (x − α
0
)p
0
,
where
α
k
=
hxp
k
, p
k
i
hp
k
, p
k
i
, β
k
=
hp
k
, p
k
i
hp
k−1
, p
k−1
i
.
Proof. By inspection, the p
1
given is monic and satisfies
hp
1
, p
0
i = 0.
Using q
n+1
= xp
n
in the Gram-Schmidt process gives
p
n+1
= xp
n
−
n
X
k=0
hxp
n
, p
k
i
hp
k
, p
k
i
p
k
p
n+1
= xp
n
−
n
X
k=0
hp
n
, xp
k
i
hp
k
, p
k
i
p
k
We notice that
hp
n
, xp
k
i
and vanishes whenever
xp
k
has degree less than
n
. So
we are left with
= xp
n
−
hxp
n
, p
n
i
hp
n
, p
n
i
p
n
−
hp
n
, xp
n−1
i
hp
n−1
, p
n−1
i
p
n−1
= (x − α
n
)p
n
−
hp
n
, xp
n−1
i
hp
n−1
, p
n−1
i
p
n−1
.
Now we notice that
xp
n−1
is a monic polynomial of degree
n
so we can write
this as xp
n−1
= p
n
+ q. Thus
hp
n
, xp
n−1
i = hp
n
, p
n
+ qi = hp
n
, p
n
i.
Hence the coefficient of p
n−1
is indeed the β we defined.