6 - Math 104B, Winter 20161 Due on Thursday, February 25th, 2016 Instructor: Carlos J. Garc Cervera a 1. Consider the tridiagonal matrix A = (ai,j )1i,jn given by 1 h2 |i j| = 1 2 i=j ai,j = h2 0 Otherwise (1) obtained when the following ODE, u (x) = f (x), x [0, 1] u(0) = u(1) = 0, (2) is discretized using second order centered dierences: ui+1 2ui + ui1 = f (xi ) i = 1, 2, . . . , n, h2 (3) where h = 1/(n + 1). (a) For each k = 1, 2, . . . , n, show that the vector u(k) given by (k) ui = sin ki n+1 , i = 1, 2, . . . , n (4) is an eigenvector of the matrix A, and determine the corresponding eigenvalue k . (b) Set up the Jacobi iteration for system (3), and show that the vectors (4) are also eigenvectors of the Jacobi iteration matrix, TJ . (c) Determine the spectral radius of TJ , (TJ ). (d) The Jacobi iteration can be written as x(k+1 = TJ x(k + c (5) 1 All course materials (class lectures and discussions, handouts, homework assignments, examinations, web materials, etc) and the intellectual content of the course itself are protected by United States Federal Copyright Law, and 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 lecture notes and all other course materials without the prior written permission of the instructor. 1 2 From the previous steps, we know that TJ is symmetric and diagonalizable. Use this fact to show that if x is the (unique) xed point of (5), then x(k x 2 (TJ )k x(0 x 2 (6) (e) Use formula (6) and the spectral radius obtained earlier to estimate the number of iterations necessary for the error to be less than a given as a function of the number of grid points used, n. You should end up with a formula of the form Iter = O(n ) for some . (f) Fix = 103 . Consider the vector u such that i n+1 ui = sin (7) and construct the right hand side f = Au. Solve the system of equations Ax = f (8) using Jacobi's method. Use the values n = 10, 20, 40, 80, 160, 320. Do a log-log plot of the number of Jacobi iterations necessary for the error to satisfy x(k u 2 u . (9) How does the computed number of iterations compare with the theoretical one obtained earlier? (g) Repeat the previous part with Gauss-Seidel's method. How much faster is it