Coding in Python and please write in details.
Math 104A Homework #4 ∗ Instructor: Ruimeng Hu General Instructions: Please write your homework papers neatly. You need to turn in both full printouts of your codes (a pdf file) and the appropriate runs you made (a jupyter notebook), on Gauchospace. 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 function numpy.fft in python). 1. Let ck = N−1∑ j=0 fje −i2πkj/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. Let PN (x) be the trigonometric polynomial of lowest order that interpolates the periodic array fj at the equidistributed nodes xj = j(2π/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, 2π], 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. 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). ∗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 Prof. Hector D. Ceniceros. 1 3. Let fj = e sinxj , xj = j2π/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. 4. 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). 5. (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