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
