%% Computer Assignment 8 (project)
%
% Due Thursday, Dec 1 at 11:59pm
%
% This final computer assignment should be completed ON YOUR OWN.  You may
% discuss the problems with your classmates but the final version must be
% your own work.  We will not hesitate to give zero points for an assignment if it is
% not your own work.
%
% The assignment MUST be published as ONE .pdf file.  The m-files you use
% should be put in a .zip archive.  Your final submission should then
% consist of one .pdf file and one .zip file.  This is worth 50% of your
% lab grade.  Even if you use the m-files that are provided as solutions in
% the class, they should be turned in.  You must also describe where you
% got the code you use.  Stock MATLAB(R) implementations of the main
% algorithms in the course can ONLY be used to check your results.

%% Problem 1: The inverse power method
%
% Assume the eigenvalues of an $n \times n$ matrix $A$ satisfy
%
% $$|\lambda_1| \geq |\lambda_2| \geq \cdots \geq |\lambda_{n-1}| >
% |\lambda_n| > 0.$$
%
% The inverse power method is used to compute $\lambda_n$, the smallest
% eigenvalue of $A$.
%
% Write a function
%
%  InvPower(A,Nmax,TOL)
%
% that performs the following:
%
% 1. Compute a $PA=LU$ factorization of $A$ using partial pivoting.
%
% 2. Let $x^{(0)}$ be a randomly generated unit vector.
%
% 3. For $k = 1,2,\ldots,Nmax$ do 4-6
%
% 4. Define $x^{(k)}$ by $A y^{(k)} = x^{(k-1)}$.  Solve for $y^{(k)}$ using the $PA=LU$ factorization in the following way:
%
% Set $y_1 = P^T x^{(k-1)}$.
%
% Solve $L y_2 = y_1$ with forward substitution.
%
% Solve $U y^{(k)} = y_2$ with backward substitution.
%
% 5. Set $\lambda^{(k)} = [y^{(k)})^Tx^{(k-1)}]^{-1}$.
%
% 6. Set $x^{(k)} = y^{(k)}/\|y\|_2$.
%
% 6. If $|\lambda^{(k)} - \lambda^{(k-1)}| < TOL$ then return
% $\lambda^{(k)}$.
%
% 7. If $k = Nmax$ return an appropriate error message.
%
% Apply this method to the matrix
%
%  A = [-2 1 0 0 0; 1 -2 1 0 0; 0 1 -2 1 0; 0 0 1 -2 1; 0 0 0 1 -2];
%
% How many iterations do you need when $TOL = 10e-10$?

%% Problem 2: Relaxation for fixed-point iteration
%
% Consider finding the fixed-point of the function
%
% $$g(x) = \cos^2(x).$$
%
% Consider using the relaxation iteration
%
% $$g_w(x) = wg(x) + (1-w)x.$$
%
% If $p$ is the fixed
% point, we'd like to choose $\omega$ so that $g'_w(p) = 0$ so that we get
% quadratic convergence, but of course, $p$ is not known.  The relaxation parameter $w$ does not need to be
% the same at each iteration.  At each iteration, to compute $x_n$, find $w$ by setting
% $g_w'(x_{n-1}) = 0$.  
%
% Implement this method to compute the fixed point of $g(x)$.  Show either numerically or analytically that this
% method converges quadratically.
%
%

%% Problem 3:  The modified Gram-Schmidt process
%
% Implement the modified Gram-Schmidt process to compute a QR factorization
% of an invertible $n \times n$ matrix $A$.   Call your function
%
%  QR(A)
%
% Demonstrate clearly that your method works on the matrix 
%
%  A = [-2 1 0 0 0; 1 -2 1 0 0; 0 1 -2 1 0; 0 0 1 -2 1; 0 0 0 1 -2];

