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® implementations of the main algorithms in the course can ONLY be used to check your results.

Contents

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];


Published with MATLAB® R2015a