Convergent matrix

Short description: Matrix that converges to zero matrix

In linear algebra, a convergent matrix is a matrix that converges to the zero matrix under matrix exponentiation.

Background

When successive powers of a matrix T become small (that is, when all of the entries of T approach zero, upon raising T to successive powers), the matrix T converges to the zero matrix. A regular splitting of a non-singular matrix A results in a convergent matrix T. A semi-convergent splitting of a matrix A results in a semi-convergent matrix T. A general iterative method converges for every initial vector if T is convergent, and under certain conditions if T is semi-convergent.

Definition

We call an n × n matrix T a convergent matrix if

[math]\displaystyle{ \lim_{k \to \infty}( \mathbf T^k)_{ij} = 0, }[/math]

(1)

for each i = 1, 2, ..., n and j = 1, 2, ..., n.

Example

Let

[math]\displaystyle{ \begin{align} & \mathbf{T} = \begin{pmatrix} \frac{1}{4} & \frac{1}{2} \\[4pt] 0 & \frac{1}{4} \end{pmatrix}. \end{align} }[/math]

Computing successive powers of T, we obtain

[math]\displaystyle{ \begin{align} & \mathbf{T}^2 = \begin{pmatrix} \frac{1}{16} & \frac{1}{4} \\[4pt] 0 & \frac{1}{16} \end{pmatrix}, \quad \mathbf{T}^3 = \begin{pmatrix} \frac{1}{64} & \frac{3}{32} \\[4pt] 0 & \frac{1}{64} \end{pmatrix}, \quad \mathbf{T}^4 = \begin{pmatrix} \frac{1}{256} & \frac{1}{32} \\[4pt] 0 & \frac{1}{256} \end{pmatrix}, \quad \mathbf{T}^5 = \begin{pmatrix} \frac{1}{1024} & \frac{5}{512} \\[4pt] 0 & \frac{1}{1024} \end{pmatrix}, \end{align} }[/math]

[math]\displaystyle{ \begin{align} \mathbf{T}^6 = \begin{pmatrix} \frac{1}{4096} & \frac{3}{1024} \\[4pt] 0 & \frac{1}{4096} \end{pmatrix}, \end{align} }[/math]

and, in general,

[math]\displaystyle{ \begin{align} \mathbf{T}^k = \begin{pmatrix} (\frac{1}{4})^k & \frac{k}{2^{2k - 1}} \\[4pt] 0 & (\frac{1}{4})^k \end{pmatrix}. \end{align} }[/math]

Since

[math]\displaystyle{ \lim_{k \to \infty} \left( \frac{1}{4} \right)^k = 0 }[/math]

and

[math]\displaystyle{ \lim_{k \to \infty} \frac{k}{2^{2k - 1}} = 0, }[/math]

T is a convergent matrix. Note that ρ(T) = 1/4, where ρ(T) represents the spectral radius of T, since 1/4 is the only eigenvalue of T.

Characterizations

Let T be an n × n matrix. The following properties are equivalent to T being a convergent matrix:

1. [math]\displaystyle{ \lim_{k \to \infty} \| \mathbf T^k \| = 0, }[/math] for some natural norm;
2. [math]\displaystyle{ \lim_{k \to \infty} \| \mathbf T^k \| = 0, }[/math] for all natural norms;
3. [math]\displaystyle{ \rho( \mathbf T ) \lt 1 }[/math];
4. [math]\displaystyle{ \lim_{k \to \infty} \mathbf T^k \mathbf x = \mathbf 0, }[/math] for every x.

Iterative methods

A general iterative method involves a process that converts the system of linear equations

[math]\displaystyle{ \mathbf{Ax} = \mathbf{b} }[/math]

(2)

into an equivalent system of the form

[math]\displaystyle{ \mathbf{x} = \mathbf{Tx} + \mathbf{c} }[/math]

(3)

for some matrix T and vector c. After the initial vector x⁽⁰⁾ is selected, the sequence of approximate solution vectors is generated by computing

[math]\displaystyle{ \mathbf{x}^{(k + 1)} = \mathbf{Tx}^{(k)} + \mathbf{c} }[/math]

(4)

for each k ≥ 0. For any initial vector x⁽⁰⁾ ∈ [math]\displaystyle{ \mathbb{R}^n }[/math], the sequence [math]\displaystyle{ \lbrace \mathbf{x}^{ \left( k \right) } \rbrace _{k = 0}^{\infty} }[/math] defined by (4), for each k ≥ 0 and c ≠ 0, converges to the unique solution of (3) if and only if ρ(T) < 1, that is, T is a convergent matrix.

Regular splitting

A matrix splitting is an expression which represents a given matrix as a sum or difference of matrices. In the system of linear equations (2) above, with A non-singular, the matrix A can be split, that is, written as a difference

[math]\displaystyle{ \mathbf{A} = \mathbf{B} - \mathbf{C} }[/math]

(5)

so that (2) can be re-written as (4) above. The expression (5) is a regular splitting of A if and only if B⁻¹ ≥ 0 and C ≥ 0, that is, B⁻¹ and C have only nonnegative entries. If the splitting (5) is a regular splitting of the matrix A and A⁻¹ ≥ 0, then ρ(T) < 1 and T is a convergent matrix. Hence the method (4) converges.

Semi-convergent matrix

We call an n × n matrix T a semi-convergent matrix if the limit

[math]\displaystyle{ \lim_{k \to \infty} \mathbf T^k }[/math]

(6)

exists. If A is possibly singular but (2) is consistent, that is, b is in the range of A, then the sequence defined by (4) converges to a solution to (2) for every x⁽⁰⁾ ∈ [math]\displaystyle{ \mathbb{R}^n }[/math] if and only if T is semi-convergent. In this case, the splitting (5) is called a semi-convergent splitting of A.

See also

• Gauss–Seidel method
• Jacobi method
• List of matrices
• Nilpotent matrix
• Successive over-relaxation

References

• Burden, Richard L.; Faires, J. Douglas (1993), Numerical Analysis (5th ed.), Boston: Prindle, Weber and Schmidt, ISBN 0-534-93219-3, https://archive.org/details/numericalanalysi00burd .
• Isaacson, Eugene; Keller, Herbert Bishop (1994), Analysis of Numerical Methods, New York: Dover, ISBN 0-486-68029-0 .
• Carl D. Meyer, Jr.; R. J. Plemmons (Sep 1977). "Convergent Powers of a Matrix with Applications to Iterative Methods for Singular Linear Systems". SIAM Journal on Numerical Analysis 14 (4): 699–705. doi:10.1137/0714047. 
• Varga, Richard S. (1960). "Factorization and Normalized Iterative Methods". in Langer, Rudolph E.. Boundary Problems in Differential Equations. Madison: University of Wisconsin Press. pp. 121–142. 
• Varga, Richard S. (1962), Matrix Iterative Analysis, New Jersey: Prentice–Hall .