MAT128A: Numerical Analysis, Section 2

1. Suppose that f is a polynomial of degree N, and that

f(x) = X

N

n=0

anTn(x). (1)

The Chebyshev polynomials satisfy the recurrence relation

Tn+1(x) = 2xTn(x) − Tn−1(x).

Suppose that we define a finite sequence of polynomials {b0(x), b1(x), . . . , bN (x), bN+1(x), bN+2(x)}

via the formulas

bN+1 = bN+2 = 0

and

bn(x) = an + 2xbn+1(x) − bn+2(x).

Show that

f(x) = b0(x).

Hint: first show that if qN−1 is defined by

qN−1(y) =

N

X−1

n=0

2bn+1(x)Tn(y),

then

(y − x)qN−1(y) + b0(x) = f(y) (2)

and then let y = x in (2).

2. The last problem suggests a method for computing the sum (1). How many arithmetic operations

does it take to compute f(x) = b0(x) using this method?

Suppose that instead we sum (1) in the most direct way. That is, we first use the recurrence

relations

Tn+1(x) = 2xTn(x) − Tn−1(x)

to compute the values of T0(x), T1(x), . . . , Tn(x). We then form the values

a0T0(x), a1T1(x), . . . , anTn(x), (3)

and sum them to obtain the value of f(x). How many arithmetic operations does this more direct

procedure take?

3. Find the coefficients {an} in the Chebyshev expansion

f(x) = X

N

n=0

0

anTn(x)

1

of the function f(x) = ?

1 − x

2. Recall that the coefficients are defined via the formula

an =

2

π

Z 1

−1

f(x)Tn(x)

dx

?

1 − x

2

,

so computing an is equvalent to determing the value of the quantity

an =

2

π

Z 1

−1

Tn(x) dx.

4. Find the coefficients {an} in the Chebyshev expansion

f(x) = X

N

n=0

0

anTn(x)

of the function

f(x) = sign pxq =

(

1 x 0

−1 x ≤ 0.

Recall that the coefficients are defined via the formula

an =

2

π

Z π

0

f(x)Tn(x)

dx

?

1 − x

2

.

2