a logo for the course

Matrix Computations

David Gleich

Purdue University

Fall 2017

Course number CS-51500

Tuesday and Thursday, 10:30-11:45am

Location Forney B124


Homework 9

Homework 9

Please answer the following questions in complete sentences in a typed, clearly prepared manuscript and submit the solution by the due date on Blackboard (Monday, November 13th, 2017, around 4-5 am)

Problem 0: Homework checklist

Problem 1: Compare CG as described in class to the standard CG iteration

  1. Implement a CG method based on the Lanczos method. That is, implement the Lanczos method to compute the matrix and . Then solve and compute . (All this notation is taken from the CG handout from class, here https://www.cs.purdue.edu/homes/dgleich/cs515-2017/notes/conjugate-gradient.pdf). Show the code for your implementation. At each step, you should compute the normalized residuals.

  2. Compare the first 25 residuals from your Lanczos-based CG code with the a standard implementation of CG from: http://www.cs.purdue.edu/homes/dgleich/cs515-2017/julia/cg.jl for the linear system

      n = 100
      on = ones(Int64,n)    
      A = spdiagm((-2*on[1:end-1],4*on,-2*on[1:end-1]),(-1,0,1))
      b = ones(n)
    
  3. Using the cg.jl function, look at how many iterations are required for CG to converge to a tolerance of for the matrix in the last part. Determine how this scales with .

Problem 2: Orthogonality of Lanczos

Let and , , .
Consider the -by- matrix with diagonal elements
(This is called the Strako\v{s} matrix.)

  1. Implement the Lanczos method starting from a a random vector and the vector and then plot the quantity for to . Describe what you SHOULD find and what you actually find. Do your results depend on the starting vector?

  2. Plot for the to . Also plot for to .

  3. What is What should it be?

  4. Plot for to .