(a) Implement both algorithms. In each iteration compute the solution ..\"E'j [computed as if this would be the last iteration) and store the residual of = \"A * my b\". (b) Use the following three test matrices with both algorithms and plot the norm of the residual over the iteration number in a plot with a logarithmic y-axis. In Matlab such plots can be generated by the function semilogy. 2 H1 1 2 1 i. tridiagonal matrix: A = of size IUUEIDU, with a ran- -1 2 1 1 2 dom right hand side and with b = ain(2*pi*tranapose (1 :n)! (n+1)) + sin(5*pi*transpose(1:n)f(n+1} ) + sin(19*pi*tranapose(1:n};'(n+1)); ii. random matrix: a = randn(1,100); a = a + transpose(it)1 witharandom right hand side, iii. very ill-conditioned matrix from Per Christian Hansen's Regularization Tools1 [A,h,x,t] = heart. (500) provides the system matrix A, the right hand side a the exact solution I. and a vector t specifying the discretization points (not of interest here). The function heart is available on moodle. (c) Submit your code. (d) Experiment with your code and describe your observations. (e) Try to explain your observations. 1. [hand in] (10 points) (a) (2 points) Show that the inverse of an upper triangular matrix is upper triangular. (b) (3 points) Choose five different invertible upper Hessenberg matrices. Compute the inverse of these upper Hessenberg matrices H e Cox numerically. Compute the rank of H kin.1:k_1 for some ke {2, ..., n}. Submit your code with all testmatrices. (Hint: Matlab's built-in function hess (.) uses Householder reflections to find a sim- ilarity transform reducing an arbitrary matrix to upper Hessenberg form. Alternatively, the result of triu(., -1), which sets the entries in the lower triangular part of the matrix to zero, is also an upper Hessenberg matrix.) (c) (2 points) Repeat the experiment with two tridiagonal matrices. What do you observe? Submit this code as well. (d) (3 points) Prove that for an upper Hessenberg matrix H E Coxn the rank of H-kin, 1:k-1 is less or equal than 1. (Hint: There are many ways to show this, for instance using Cramer's rule. I personally, however, prefer using a QR decomposition of H with Givens rotations in factored form. ) 2. [hand in] (10 points) We want to compare the convergence behavior of the Lanczos algorithm and the CG method for solving a linear system