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.
Please identify anyone, whether or not they are in the class, with whom you discussed your homework. This problem is worth 1 point, but on a multiplicative scale.
Make sure you have included your source-code and prepared your solution according to the most recent Piazza note on homework submissions.
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:
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.
Prove or disprove!
The eigenvalues of an real-valued matrix are always real.
The solution to is unique for any .
Every matrix can be written as the sum of two non-singular matrices.
An real-valued matrix has an orthogonal set of eigenvectors.
An matrix and its transpose have the same set of eigenvalues.
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.
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 ).
Show that if is an eigenvector of with eigenvalue , then is an eigenvector of . What is the eigenvalue?
Show that the Jacobi iteration will not converge for any choice of for the following system
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?