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,

    $\displaystyle 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

    $\displaystyle \alpha = \frac{y_0' \cdot x_1}{x_1'\cdot x_1}=\frac{3}{5},$

    $\displaystyle \beta= \frac{y_0' \cdot x_2}{x_2'\cdot x_2}=\frac{3}{35}\simeq 0.085714,$

    $\displaystyle \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

    $\displaystyle 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

    $\displaystyle \left[(1+10^4)/(2+10^4)\right]^2.$

    When you make a shift by $ 10$, the error will be multiplied by

    $\displaystyle \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

    $\displaystyle 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

    $\displaystyle (\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

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

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

    $\displaystyle \dots $

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

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

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

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

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

  6. 4.15

    (a)

    $\displaystyle \pm 10 \sqrt{10405.0} \simeq \pm 1020.049018429996823846313$

    $\displaystyle 510+100\sqrt{26.0}\simeq 1019.9019513592784830028224,$

    $\displaystyle 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

    $\displaystyle 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

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

    Now solve

    $\displaystyle 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.