a logo for the course

Matrix Computations

David Gleich

Purdue University

Fall 2018

Course number CS-51500

Tuesday and Thursday, 3:00-4:15pm

Location Forney G124


Homework 5

Homework 5

Please answer the following questions in complete sentences in a clearly prepared manuscript and submit the solution by the due date on Blackboard (around Sunday, September 30th, 2018.)

Remember that this is a graduate class. There may be elements of the problem statements that require you to fill in appropriate assumptions. You are also responsible for determining what evidence to include. An answer alone is rarely sufficient, but neither is an overly verbose description required. Use your judgement to focus your discussion on the most interesting pieces. The answer to "should I include 'something' in my solution?" will almost always be: Yes, if you think it helps support your answer.

Problem 0: Homework checklist

Problem 1: Show that the Jacobi method converges on a diagonally dominant system.

One of the common classes of matrices are called diagonally dominant. They have, or can be permuted to have, entries on on the diagonal such that: Suppose that is a diagonally dominant system. Show that the Jacobi iteration will converge to the solution when, for at least one row , we have:

Problem 2: Implement Gauss-Seidel and Jacobi for a sparse system of equations

For each iteration through all rows, you must use work proportional to the number of non-zeros in the matrix. Stop your iteration when the relative residual drops below .

Show how many iterations the methods take on the Candyland linear system of equations.

Problem 3: Eigenvalue Review

Prove or disprove!

  1. The eigenvalues of an real-valued matrix are always real.

  2. The solution to is unique for any .

  3. Every matrix can be written as the sum of two non-singular matrices.

  4. An real-valued matrix has an orthogonal set of eigenvectors.

  5. An matrix and its transpose have the same set of eigenvalues.

Problem 4: The power method, and beyond!

We'll show that the humble power-method is really rather more interesting than we saw in class! It's a flexible starting point that serves as the basis for almost all of the eigenvalue algorithms.

  1. Consider the power method as a Julia code:

     maxit = 1000
     lam = 0
     for i=1:maxit
         x = A*x
         x = x./norm(x)
         lam = x'*A*x
     end
    

    Let be the value of x at the start of the th instance of this loop. And let be the value of lam at the start of the th iteration. Suppose that and are the true eigenvector, eigenvalue pair that we are converging too. If , show that: is (where the constant may depend on the matrix ).

  2. Show that if is an eigenvector of with eigenvalue , then is an eigenvector of . What is the eigenvalue?

Problem 5: A matrix where Jacobi will not converge.

Show that the Jacobi iteration will not converge for any choice of for the following system

Problem 6: Find and read a proof.

Find and read two different proofs that Gauss-Seidel will converge for any symmetric positive definite system . Give the references. List any steps that were unclear. Which proof do you prefer and why?