CG -- Eigenvalues (Eigenvectors) and convergency

Apply a matrix to Eigenvectors <=> Apply an eigenvalue to this vector

Iterative methods often depend on applying matrix $B$ to a vector over and over again.

When $B$ is repeatedly applied to an eigenvector $v$, one of two things can happen.

• If $|\lambda <1|$, then $B^{i}v={\lambda }^{i}v$ will vanish as $i$ approaches infinity (Figure 9).
• If $|\lambda |>1$, then $B^{i}v$ will grow to infinity (Figure 10).

-cite from An Introduction to the Conjugate Gradient Method Without the Agonizing Pain

Any vector can be written as the sum of eigenvectors if matrix $B$ is symmetric

If $B$ is symmetric (and often if it is not), then there exists a set of $n$ linearly independenteigenvectors of $B$ denoted $v_1,v_2,....,v_n$.

Thus, one can examine the effect of $B$ on each eigenvector separately.

Example: Jacobi iterations

The matrix $A$ is split into two parts:

• $D$, whose diagonal elements are identical to those of $A$, and whose off-diagonal elements are zero;
• $E$ , whose whose diagonal elements are zero, and whose off-diagonal elements are identical to those of $A$. ž
  That is$$A=D+E$$

Suppose we start with some arbitrary vector $x\mathrm{\_}(0)$. For each iteration, we apply $B$ to this vector, then add $z$ to the result.

Spectral radius of a matrix $\rho$

$\rho (B)=max|{\lambda }_i|$, ${\lambda }_i$ is an eigenvalue of $B$

Thus, if $\rho (B)\text{<}1$, then the error term $e\mathrm{\_}(i)$ will converge to zero as $i$ approaches infinity. Hence, we have a ==guarantee of convergency ==regardless of the initial vector $x\mathrm{\_}(0)$ .