Stationary Iterative Methods

Let λ₁, λ₂, … , &lambda_n be the eigenvalues of square matrix H. Every square matrix H may be transformed to a blockwise diagonal matrix S^-1H S (the Jordan canonical form of H), each of whose diagonal blocks has the form \[ {\bf J}_i = \begin{bmatrix} \lambda_i & 1 & 0 & \cdots & 0 \\ 0&\lambda_i & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots & \lambda_i\end{bmatrix} . \] Note that the same eigenvalue may appear in several blocks. In other words, in a certain oblique column coordinate system (the columns of S) matrix H takes the relatively simple form of a direct sum of transformations J_i. We can decompose an arbitrary vector v in the same coordinate system writing v = v₁ + v₂ + ⋯ + v_m, where the term v_i of the sum corresponds to the Jordan block J_i. We may assume that v_i ≠ 0.

Then we have only to prove the theorem for an arbitrary block of the form above.

Every Jordan block can be decomposed into a sum of the diagonal matrix λ_iI and the nilpotent matrix C: \[ {\bf J}_i = \lambda_i {\bf I} + {\bf C} \in \mathbb{R}^{m \times m} , \] where m = m_{i depends on index i, which we drop for simplicity. Matrix C is independent of th eigenvalue and depends only on the dimension of eigenspace; it consists of one on the superdiagonal and zeroes elsewhere: \[ {\bf C}_i = \begin{bmatrix} 0& 1 & 0 & \cdots & 0 \\ 0&0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0&0&0& \cdots & 0 \end{bmatrix} \in \mathbb{R}^{m \times m} . \] It can be shown that power matrices C^k (k = 1, 2, …) vanish when power k exceeds the dimension of the Jordan block. You can verify with Mathematica that every time you multiply by C, superdiagonal of ones is shifted up.}

Hence, \begin{align*} {\bf J}_i^k &= \left( \lambda_i {\bf I} + {\bf C} \right)^k = \lambda_i^k {\bf I} + \binom{k}{1} \lambda_i^{k-1} {\bf C} + \binom{k}{2} \lambda_i^{k-2} {\bf C}^2 \\ & \quad + \cdots + \binom{k}{m-1} \lambda_i^{k-m+1} {\bf C}^{m-1} , \tag{E2.1} \end{align*} where \[ \binom{k}{n} = \frac{k^{\underline{n}}}{n!}, \qquad k^{\underline{n}} = k \left( k-1 \right) \left( k-2 \right) \cdots \left( k-n+1 \right) , \] is the binomial coefficient. Here are some values of binomial coefficients: \begin{align*} \binom{k}{1} &= = k , \\ \binom{k}{2} &= = \frac{k(k-1)}{2} = \frac{1}{2} \left( k^2 - k \right) , \\ \binom{k}{3} &= = \frac{k(k-1)(k-2)}{3!} = \frac{1}{6} \left( k^3 - 3k^2 + 2k \right) , \\ \binom{k}{4} &= = \frac{k(k-1)(k-2)(k-3)}{4!} = \frac{1}{24} \left( k^4 - 6k^3 + 11k^2 - 6k \right) . \end{align*} So the binomial coefficient \( \quad \binom{k}{n} \quad \) is a polynomial in k, the upper index, of degree n, the lower index. From Eq.(E2.1), it follows that \begin{align*} {\bf J}_i^k {\bf v} &= \lambda_i^k {\bf v} + \binom{k}{1} \lambda_i^{k-1} {\bf C} {\bf v} + \binom{k}{2} \lambda_i^{k-2} {\bf C}^2 {\bf v} \\ & \quad + \cdots + \binom{k}{m-1} \lambda_i^{k-m+1} {\bf C}^{m-1} {\bf v} . \tag{E2.2} \end{align*} Any eigenvector u_i of the block J_i must satisfy the equation J_iu_i = λ_iu_i, so C_iu_i = 0.

The power of nilpotent matrix Cⁿ is a matrix whose only nonzero elements are "1" in the upper superdiagonal in the upper right corner. Moreover, the power matrix C^m-1 (last term in Eq.(E2.2)) has a single nonzero entry of "1" in the upper right corner.

If |λ_i| < 1, then every term \( \displaystyle \quad \binom{k}{n} \lambda^{k-n}_i {\bf C}^n {\bf v} \quad \) in Eq.(E2.2) turns to zero as k → ∞ because exponential functions decreases faster than any polynomial.

If |λ_i| > 1, then every term in Eq.(E2.2) blows up for any vector v.

If |λ_i| = 1 and λ_i ≠ 1, then every term in Eq.(E2.2) oscillates, so the Jordan block J_iv diverges for any v. If u is an eigenvector corresponding to λ_i with |λ_i| = 1, then J_iu = λ_iv, so C_iu = 0. Expanding arbitrary vector v over eigenvectors (including generalized eigenvectors), we see that at least one part of it containing u oscillates. Therefore, the corresponding Jordan block does not converge.

If λ_i = 1 and m = 1, then the Jordan block becomes one-dimensional and it consists of one diagonal entry of 1. Then if v is an eigenvector corresponding to λ_i = 1, then J_iv = v.