# 辅导案例-104A

Math 104A Final Projects∗
Instructor: Xu Yang
General Instructions: Please follow TA’s instructions (on Gauchoapace) to turn it in. Write
your own code individually. Do not copy codes!
The Discrete Fourier Transform (DFT) of a periodic array fj , for j = 0, 1, ..., N−1 (correspond-
ing to data at equally spaced points, starting at the left end point of the interval of periodicity) is
evaluated via the Fast Fourier Transform (FFT) algorithm (N power of 2). Use an FFT package,
i.e. an already coded FFT (the functions fft and ifft in Matlab or numpy.fft in python).
1. Let
ck =
N−1∑
j=0
fje
−i2pikj/N .
Prove that if the fj , for j = 0, 1, ..., N − 1 are real numbers then c0 is real and cN−k = c¯k,
where the bar denotes complex conjugate.
2. Which fft package are you using? Read the manual of your fft package, and write down the
formula it’s using to return the coefficients. (Note: different packages may use different
definitions of the DFT, so it is very important to figure out what your package is calculating
before using it.)
3. Let PN (x) be the trigonometric polynomial of lowest order that interpolates the periodic
array fj at the equidistributed nodes xj = j(2pi/N), for j = 0, 1, ..., N − 1, i.e.
PN (x) =
1
2
a0 +
N/2−1∑
k=1
(ak cos kx+ bk sin kx) +
1
2
aN/2 cos
(
N
2
x
)
,
for x ∈ [0, 2pi], where
ak =
2
N
N−1∑
j=1
fj cos kxj , for k = 0, 1, ..., N/2,
bk =
2
N
N−1∑
j=1
fj sin kxj , for k = 0, 1, ..., N/2− 1.
∗All course materials (class lectures and discussions, handouts, homework assignments, examinations, web ma-
terials) and the intellectual content of the course itself are protected by United States Federal Copyright Law, the
California Civil Code. The UC Policy 102.23 expressly prohibits students (and all other persons) from recording
lectures or discussions and from distributing or selling lectures notes and all other course materials without the prior
written permission of class instructors.
1
Write a formula that relates the complex Fourier coefficients computed by your fft package
to the real Fourier coefficients, ak and bk, that define PN (x).
4. Let fj = e
sinxj , xj = j2pi/N for j = 0, 1, ..., N−1. Take N = 8. Using your fft package obtain
P8(x) and find a spectral approximation of the derivative of e
sinx at xj for j = 0, 1, ..., N − 1
by computing P ′8(xj). Compute the actual error in the approximation.
5. The solution Pn(x) to the Least Squares Approximation problem of f by a polynomial of
degree at most n is given explicitly in terms of orthogonal polynomials ψ0(x), ψ1(x), ...,
ψn(x), where ψj is a polynomial of degree j, by
Pn(x) =
n∑
j=0
ajψj(x), aj =
〈f, ψj〉
〈ψj , ψj〉 .
(a) Let Pn be the space of polynomials of degree at most n. Prove that the error f − Pn is
orthogonal to this space, i.e. 〈f − Pn, q〉 = 0 for any q ∈ Pn.
(b) Using the analogy of vectors interpret this result geometrically (recall the concept of
orthogonal projection).
6. (a) Obtain the first 4 Legendre polynomials in [−1, 1].
(b) Find the least squares polynomial approximations of degrees 1, 2, and 3 for the function
f(x) = ex on [−1, 1].
(c) What is the polynomial least squares approximation of degree 4 for f(x) = x3 on [−1, 1]?
Explain.
2  Email:51zuoyejun

@gmail.com