Numerical Analysis, Section 2

Project Four: Piecewise Chebyshev Expansions

1. Project Description

In this project, you will write C functions to construct and evaluate piecewise Chebyshev expansions. Recall that the Nth order Chebyshev expansion of the function f on the interval [a, b] is the

polynomial

p(x) = X

N

n=0

0

anTn

ˆ

2

b − a

x −

b + a

b − a

˙

,

where the coefficients {an} are defined via the formula

an =

2

N + 1

X

N

j=0

f

ˆ

b − a

2

xj +

b + a

2

˙

Tn pxj q

with x0, x1, . . . , xN given by

xj = cos ˜

j +

1

2

N + 1

π

¸

.

The Nth order piecewise Chebyshev expansion of the function f : [a, b] → R

n given on the partition

a = a0 < a1 < a2 < . . . < am = b (1)

consists of m polynomials of degree N

p0, p1, . . . , pm−1.

The i

th polynomial pi

is the Nth order Chebyshev expansion of f on the interval [ai

, ai+1]. It is

defined by the formula

pi(x) = X

N

n=0

c

i

n Tn

ˆ

2

ai+1 − ai

x −

ai+1 + ai

ai+1 − ai

˙

,

where the coefficients ?

c

i

n

are

c

i

n =

2

N + 1

X

N

j=0

f

ˆ

ai+1 − ai

2

xj +

ai+1 + ai

2

˙

Tn pxj q.

I have provided you with a function called “chebadap” which, given a user-specified function f :

[a, b] → R and an integer N, attempts to determine a partition of [a, b] of the form (1) such that

for each i = 0, 1, . . . , m − 1, pi approximates f on the interval [ai

, ai+1] to specified precision.

1

Your task is to implement two functions, “chebadap coefs” and “chebadap eval”. The first of these

computes the coefficients ?

c

i

n

in a piecewise Chebyshev expansion of a user-specified function f.

The second uses the coefficients in the piecewise Chebyshev expansion of f to approximate f at

a specified point. More explicitly, it finds the interval rai

, ai+1q containing the point x and then

evaluates pi(x) in order to approximate f(x).

The file “chebdap.c” contains the “chebadap” routine and gives the calling syntax for the “chebadap coefs”,

“chebadap eval” . Your task is to implement the functions as described there. Your code should

rely on the “chebexp.c” code you wrote for Project 3 (or, if you wish, you can use the version of

“chebexp.c” which I wrote and posted to the course website).

2. Testing and grading

A public test code is given in the file adaptest1.c. Another test code, called adaptest2.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 adaptest1 chebexp.c chebadap.c adaptest1.c -lm

./adaptest1

can be used to compiler and execute your program. There are five tests of your function in

“adaptest1.c”, and the program will tell your score out of 5. We will also test your code by

compiling against adaptest2.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 chebadap.c file. You must

submit your file by 11:59 PM on the due data. Late assignments will not be accepted.

2