Description
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