Convergent matrix explained

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

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

Example

Let

\begin{align} & T = \begin{pmatrix} (1)/(4) & (1)/(2) \\[ 4 pt] 0 & (1)/(4) \end{pmatrix}. \end{align} Computing successive powers of T, we obtain\begin{align} & T ^{2} = \begin{pmatrix} (1)/(16) & (1)/(4) \\[ 4 pt] 0 & (1)/(16) \end{pmatrix}, T ^{3} = \begin{pmatrix} (1)/(64) & (3)/(32) \\[ 4 pt] 0 & (1)/(64) \end{pmatrix}, T ^{4} = \begin{pmatrix} (1)/(256) & (1)/(32) \\[ 4 pt] 0 & (1)/(256) \end{pmatrix}, T ^{5} = \begin{pmatrix} (1)/(1024) & (5)/(512) \\[ 4 pt] 0 & (1)/(1024) \end{pmatrix}, \end{align} \begin{align} T ^{6} = \begin{pmatrix} (1)/(4096) & (3)/(1024) \\[ 4 pt] 0 & (1)/(4096) \end{pmatrix}, \end{align} and, in general,\begin{align} T ^{k} = \begin{pmatrix} ( (1)/(4) ) ^{k} & (k)/(2 ^{2k}) \\[ 4 pt] 0 & ( (1)/(4) ) ^{k \end{pmatrix}. \end{align}} Since\lim _{k} \left( (1)/(4) \right) ^{k} = 0 and\lim _{k} (k)/(2 ^{2k}) = 0 , T is a convergent matrix. Note that ρ(T) =, where ρ(T) represents the spectral radius of T, since 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:

\lim _{k} \| T ^{k} \| = 0 , for some natural norm;\lim _{k} \| T ^{k} \| = 0 , for all natural norms;\rho( T ) < 1 \lim _{k} T ^{k} x = 0, for every x.

Iterative methods

See main article: Iterative method. A general iterative method involves a process that converts the system of linear equations

into an equivalent system of the form

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

for each k ≥ 0. For any initial vector x⁽⁰⁾ ∈

R ^{n} , the sequence \lbrace x \rbrace ^{inf ty} ^{k =0} defined by, for each k ≥ 0 and c ≠ 0, converges to the unique solution of if and only if ρ(T) < 1, that is, T is a convergent matrix.

Regular splitting

See main article: Matrix 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 above, with A non-singular, the matrix A can be split, that is, written as a difference

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

Semi-convergent matrix

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

exists. If A is possibly singular but is consistent, that is, b is in the range of A, then the sequence defined by converges to a solution to for every x⁽⁰⁾ ∈

R ^{n} if and only if T is semi-convergent. In this case, the splitting is called a semi-convergent splitting of A.

See also

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

References

• .
• .
• Convergent Powers of a Matrix with Applications to Iterative Methods for Singular Linear Systems . Sep 1977 . Carl D. Meyer, Jr. . R. J. Plemmons . . 14 . 4 . 699–705 . 10.1137/0714047 . .
• Book: Richard S. . Varga . Factorization and Normalized Iterative Methods . Boundary Problems in Differential Equations . Langer . Rudolph E. . . Madison . 121 - 142 . 1960 . 60-60003 .
• .