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.