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, November 11th, 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 cases for updating solutions of that we did not discuss in class is what happens when the linear system grows. Suppose we add a row and column to the system of linear equations in such a way that the system stays non-singular. Formally, we have: In this case, however, we have already computed a factorization to solve systems with the matrix . Show how to use this to solve for the new, enlarged systems.
In class, we showed how to solve when given a fast factorization method to solve . In this problem, we will address the question of how to update the factorization itself. Suppose that we are given a Cholesky factorization of as we saw in class. Show how to update this factorization to produce . Your algorithm should do no more than work.
In class, we showed that the Krylov subspace: arises when solving via the simple Neumann series method. Here, we note that it also arises in the power-method to identify the largest eigenvalue of a matrix. Note that the simple monomial basis for the Krylov subspace is: In this case, the power-method uses the vector as the estimate of the largest eigenvalue.
State an algorithm to search the Krylov subspace for the largest eigenvalue of a symmetric matrix using the fact that the largest eigenvalue solves the problem: (Note, that you are welcome to use ideas that we discuss in subsequent lectures, but you don't have to. Everything can be done with the material presented through lecture 21.) Note that you may use any routine you want on a -by- matrix.
Implement your algorithm and compare the eigenvalue estimates for a few small matrices. (Hint, a good idea here would be to show convergence plots for the error in the largest eigenvalue compared with iterations -- usually on a log-y-scale.)
Comment on any issues that arise in your implementation.
We aren't doing this problem because I got the homework out late. Work out an analytical formula for the largest entry of where is a -by- tridiagonal matrix of with entries of 1. For instance: