Convergent matrix

In the mathematical discipline of numerical linear algebra, 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 is called a convergent 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

$\lim _{k\to \infty }({\mathbf {T}}^{k})_{ij}={\mathbf {0}},\quad (1)$

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

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

${\mathbf {x}}^{(k+1)}={\mathbf {Tx}}^{(k)}+{\mathbf {c}}\quad (4)$

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

Regular splitting

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 (2) above, with A non-singular, the matrix A can be split, i.e., written as a difference

${\mathbf {A}}={\mathbf {B}}-{\mathbf {C}}\quad (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, i.e., 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

$\lim _{k\to \infty }{\mathbf {T}}^{k}\quad (6)$

exists. If A is possibly singular but (2) is consistent, i.e., b is in the range of A, then the sequence defined by (4) converges to a solution to (2) for every x⁽⁰⁾ ∈ $\mathbb {R} ^{n}$ 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
• 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.

• 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.

• Varga, Richard S. (1960). "Factorization and Normalized Iterative Methods". In Langer, Rudolph E. (ed.). Boundary Problems in Differential Equations. Madison: University of Wisconsin Press. pp. 121–142. LCCN 60-60003.

• Varga, Richard S. (1962), Matrix Iterative Analysis, New Jersey: Prentice–Hall, LCCN 62-21277.