Topic 1: Matrix functions with Chebyshev polynomials Let A BV*N be a symmetric matrix. In the homework we have explained how to form polyno- mials of matrices p(A). More general functions f(A) of matrices can be constructed as limits of polynomials. By approximating general functions f with Chebyshev polynomials, one can derive efficient algorithms for performing matvecs by f(A) using only matvecs by A as the main ingredient. In this project, we will explore how this can be accomplished. 1. By the spectral theorem, A can be factorized as A = UAU " where U is orthogonal and A is diagonal. In terms of U and A, deduce the diagonalization of p(A) for a given polynomial p. 2. Suppose that the eigenvalues of A are contained within the interval [a,b]. Suppose moreover that f is a real-valued function whose domain contains [a,b] and that p,, k= 0,1,2,..., define a sequence of polynomials that converge pointwise to f on [a, b]. Define f(A) = lim pi(A). In terms of U and A, deduce the diagonalization of f(A). Explain why the definition of f(A) does not depend on the specific choice of sequence {p; } but only on the limiting function f. 3. Explain why if [a, b] does not contain (), then by taking the function f(x) = %, f(A) coincides with A=, Moreover, for flx) = Z aplx c)k k=0 that is given hy a convergent Taylor series expansion (such as, for example, f(x) = \"), explain why flA) = Z ap(A eIk, k=0 4. Show that given a,b I such that [a,b] contains the eigenvalues of A and a function f whose domain contains [a, b, we can find scalars o, R such that the eigenvalues of A := ad + 31 are contained within [1, 1] and a modified function f whose domain contains [1, 1] such that f(A) = f(A). 5. After constructing such f: [1,1] R, recall how to approximate T fla) = Z erTp(x) (%) k=0 as a linear combination of Chebyshev polynomials. If you have determined the coefficients , then given a vector v R, explain how you can use the three-term recurrence to perform the matvec L flAw = f(Aw approximately without ever forming the matrix f(A4). Your algorithm should rely on matvecs by A, together with operations that are guaranteed scale linearly in N. (This means for example that if A is sparse, then you can exploit fast matvecs by A.) Hint: Following (*), it will suffice to form the sequence of matvecs Ty(A)v, ..., T, (A)w. Try to figure out how to form these by plugging the matrix A in for x in the three-term recurrence, then right-multiplying the recurrence equations by the vector v. 6. Practice applying this pipeline to form the matrix-vector product f(A)v efficiently for f(x) = % and f(x) = * on test matrices A