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 3

Homework 3

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 16th, 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: Getting Poisson's equations to converge with Richardson

In class we showed that the Richardson method for will converge for any positive semi definite matrix as long as . We have not yet determined ways of computing , however.

In the previous homework (HW2), you found that setting did not result in a method that converged for Poisson's equation with .

  1. Experimentally or theoretically, find a value of such that using the Richardson method will converge for Poisson's equation (as used in HW2) with .

  2. What happens when you try , does the same value of work? If not, find a new one that does.

  3. Experimentally, find a value of that takes the fewest iterations to produce a solution with relative residual for both and .

  4. Prove that using will result in a method that converges.

Problem 2: Norms

Let be any vector norm. This means that must be a vector norm for . Show that if , then for some value of .

Problem 3

Consider the following function:

  1. Show that is a matrix norm. (Very easy!)

  2. Show that does not satisfy the sub-multiplicative property.

  3. Show that there exists such that: is a sub-multiplicative matrix-norm.

  4. Extra tough problem for the adventurous! Not graded. This problem has a relatively easy proof related to something we saw in class. But making it fully formal requires a few technicalities that are easy to get tripped up on. Now let be an arbitrary matrix norm. Show that there exists such that is a sub-multiplicative matrix-norm.

Problem 4: Solving the PageRank linear system of equations via Richardson.

We will derive the following at some point in the class, but you have everything you need to solve this right now. Let be a matrix that is entry-wise non-negative () and also has columns that sum to ().

Informally, the matrix describes the probability of moving around a graph, just like the matrix described the probability of moving around the game of Candyland. The interpretation of is the probability of moving from node to node .

The PageRank linear system is: where and . The solution can be interpreted as the asymptotic fraction of time a random walk spends at a node of a graph when, at each step, it moves in the graph (according to ) with probability and it jumps according to with probability .

Show that we can solve the PageRank linear system using the Richardson method.