HW FOUR

1. 4.2

   (a) This matrix is not positive definite, see (b) below

   (b) Eigenvalues are $5$ and $-10$, so the matrix is not positive definite

   (c) Power method will converge to the dominant eigenvalue, which is $-10$.

   (d) Since dominant eigenvalue is $-10$, and we know that the other eigenvalue is such that $\vert\lambda_2\vert<10$, we can make a shift by $10$. Indeed, performing power iteration to the $A+10 I$ will converge to the nondominant eigenvalue.

2. 4.4

   (a) This matrix is not positive definite

   (b) Using Rayleigh quotient we find eigenvalues $-21$,$63$ and $63$.

   (c) Power method will converge to the dominant eigenvalue $63$ and the vector, which will be a linear combination of two different eigenvectors corresponding to the dominant eigenvalue.

   More precisely,

   $$y_0 = (1,1,1) = \alpha x_1 + \beta x_2 + \gamma x_3,$$
   where $x_1, x_2$ and $x_3$ are three different eigenvectors.

   Cross multiplying by corresponding eigenvectors, we obtain

   $$\alpha = \frac{y_0' \cdot x_1}{x_1'\cdot x_1}=\frac{3}{5},$$
   $$\beta= \frac{y_0' \cdot x_2}{x_2'\cdot x_2}=\frac{3}{35}\simeq 0.085714,$$
   $$\gamma \frac{y_0' \cdot x_3}{x_3'\cdot x_3}= -0.14286$$

   Performing power iteration on $y_0$ we will obtain the vector

   $$y = \alpha x_1 + \beta x_2 = \frac{1}{\sqrt{14}}(3,1,2)\simeq (0.80178, 0.26726, 0.53452).$$

3. 4.5

   (a) The power will fail since it will not be able to “decide” whether to converge to eigenvector corresponding to eigenvalue $2$ or $-2$. The resulting vector will therefore converge to the linear combination of the two eigenvectors corresponding to eigenvalue $2$ and $-2$, and will alternate its direction at each of the steps.

   (b) Consider the matrix $B = A+10 I$, and use power method and inverse power method to compute eigenvalues $2$ and $-2$.

   (c) Using $B=A+10^4 I$ will converge to the maximum positive eigenvalue of matrix $A$. The convergence will be very slow, the error will be multiplied by

   $$\left[(1+10^4)/(2+10^4)\right]^2.$$
   When you make a shift by $10$, the error will be multiplied by
   $$\left[(1+10)/(2+10)\right]^2,$$
   at each iteration.

4. (4.8)

   (a) Eigenvalues are $2$ and $-2$. Power method will presumptuously converge to linear combination of eigenvectors corresponding to these eigenvalues and will alternate its direction.

   (b) The equation (4.13) will reduce to

   $$v_k = \lambda_1 \frac{\alpha_1^2 - \alpha_2^2}{\alpha_1^2+\alpha_2^2} =\lambda_1 \frac{1-\alpha^2}{1+\alpha^2}.$$
   This formula does not have desired assymptotic behavior at $k\to\infty.$

   (c) When we choose $B = A - \mu I$, we are shifting eigenvalues from $-2$ and $2$ to $-2-\mu$ and $2-\mu$. The eigenvalues of $B$ will be different for nonzero $\mu$. Choose $\mu=2$ to find eigenvalue and corresponding eigenvector for the $-2$ eigenvalue of $A$. Choose $\mu = -2$ to find eigenvalue and corresponding eigenvector to $2$.

5. 4.12

   It is easier to work with $4\times 4$ or $6\times 6$ matrix first to gain intuition. For example, type in matlab

   In what follow, we assume that $n$ is even.

   To find eigenvalues, write $det(A - \lambda I) =0.$. To calculate this determinant, expand it in the first raw. The second $(n-1)\times(n-1)$ determinant should be expanded in the last raw. The result is

   $$(\lambda-a)^n - (\lambda-a)^{n-2}=0.$$
   The roots of this are $\lambda=a$, and $\lambda=a\pm 1$.

   To calculate eigenvectors, write $A x = \lambda x$ in components.

   The eigenvectors corresponding to $\lambda=a$ are

   $$\begin{bmatrix}0 \\ 1 \\ \\ dots \\ 0 \\ 0\\ 0 \end{bmatrix},$$
   $$\begin{bmatrix}0 \\ \\ 0 \\ 1 \\ \\ dots \\ 0 \\ 0\\ 0 \end{bmatrix},$$
   $$\dots$$
   $$\begin{bmatrix}0 \\ \\ 0 \\ \\ dots \\ 0 \\ 1\\ 0 \end{bmatrix}.$$

   The eigenvector corresponding to $\lambda = a+1$ is

   $$\begin{bmatrix}1 \\ 0 \\ 0 \\ \dots 1 \end{bmatrix}.$$

   Similarly, the eigenvector corresponding to $\lambda = a-1$ is

   $$\begin{bmatrix}1 \\ 0 \\ 0 \\ \dots \\ 0\\ -1 \end{bmatrix}.$$

6. 4.15

   (a)

   $$\pm 10 \sqrt{10405.0} \simeq \pm 1020.049018429996823846313$$
   $$510+100\sqrt{26.0}\simeq 1019.9019513592784830028224,$$
   $$1020=1020.$$
   So there are four eigenvalues close by absolute value to $1020$.

   (b) Power method will fail since four eigenvalues are very close to each other, and $(1020/ 1020.05)^2 \simeq 0.999902$, which is very close to 1

   (c) If you do a shift, and $\omega=-1$, then the dominant eigenvalue is

   $$10 \sqrt{10405.0} +1 \simeq \pm 1021.05.$$

   (d) The next biggest eigenvalue in the shifted matrix will be $1021$, so the error will be reduced each time by

   $$(1021/1021.05)^2 \simeq 0.999902.$$

   Now solve

   $$0.999902^n = \frac{1}{10},$$
   which gives $n=23494$.

   (e) To converge to $10 \sqrt{10405.0}$ one can choose $\omega=-1$. Then the eigenvalue $10 \sqrt{10405.0}+1$ will be the dominant one, so power method will converge to it.