Project Three: Chebyshev Expansions

Numerical Analysis, Section 2
Project Three: Chebyshev Expansions

1. Project Description
In this project, you will write C functions to evaluate Chebyshev polynomials, to calculate the
Chebyshev coefficients of a function and to evaluate a function given its Chebyshev coefficients.
The first of these functions will be called “chebpolys,” and it will, given an integer N 0 and a
point x in the interval [−1, 1], return the values of
T0(x), T1(x), T2(x), . . . , TN (x),
where Tn(x) = cos(n arccos(x)) is the Chebyshev polynomial of degree n. You should compute the
Chebyshev polynomials using the formulas
T0(x) = 1, T1(x) = x, Tn+1(x) = 2xTn(x) − Tn−1(x).
The second function will be called “chebcoefs,” and it will, given the capability of evaluating a
function at any point on an interval [a, b] and an integer N 1, return approximations of the first
N + 1 Chebyshev coefficients of f. The Chebyshev expansion of f on [a, b] is
f(y) = X∞
n=0
0
anTn
ˆ
2
b − a
y −
b + a
b − a
˙
,
where the coefficients {an} are given by the formula
an =
2
π
Z 1
−1
f
ˆ
b − a
2
x +
b + a
2
˙
Tn(x) dx.
You will use the Chebyshev extrema quadrature rule to approximate the coefficients a0, a1, . . . , aN .
That is, if, for each j = 0, 1, . . . , N, we let
xj = cos ˜
j +
1
2
N + 1
π
¸
,
then you should use the quadrature formula
an ≈
2
N + 1
X
N
j=0
f
ˆ
b − a
2
xj +
b + a
2
˙
Tn pxj q.
to approximate the Chebyhev coefficients.
1
The third function will be called “chebeval,” and it will, given an integer N 1, a point y on
the interval [a, b] and the approximations of the coefficients a0, . . . , aN computed by “chebcoefs”,
compute the value of the expansion
X
N
n=0
0
anTn
ˆ
2
b − a
y −
b + a
b − a
˙
,
at the point y.
The file “chebexp.c” gives the calling syntax for the “chebcoefs”, “chebpolys” and “chebval” routines. Your task is to implement the functions as described there.
2. Testing and grading
A public test code is given in the file chebtest1.c. Another test code, called chebtest2.c, will be
used to test your function as well. Half of the project grade will come from the first test file, and
the second half will come from the second. The commands
gcc -o chebtest1 chebexp.c chebtest1.c -lm
./chebtest1
can be used to compiler and execute your program. The first command compiles your program and
creates an executable file named chebtest1. The -lm option tells the compiler to include the math
library which implements cosine, sine and other basic functions. The second command runs the
fourtest1 executable. There are five tests of your function in chebtest1, and the program will tell
your score out of 5. We will also test your code by compiling against chebtest2.c, which we will not
release until after the projects are due. You will get a 0 on your project if it does not compile and
run. Please start work on your project early and come see either myself or our TA, Karry Wong,
if you are having difficulties getting it to compile.
3. Submitting your project
You will submit your project using canvas. You should submit only your chebexp.c file. You must
submit your file by 11:59 PM on the due data. Late assignments will not be accepted.
2