convergent 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

{{NumBlk|::| $\lim_{k \to \infty}( \mathbf T^k)_{ij} = 0,$ |{{EquationRef|1}}}}

for each i = 1, 2, ..., n and j = 1, 2, ..., n.{{harvtxt|Burden|Faires|1993|p=404}}{{harvtxt|Isaacson|Keller|1994|p=14}}{{harvtxt|Varga|1962|p=13}}

Example

Let

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

Computing successive powers of T, we obtain

: $\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}$

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

and, in general,

: $\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}$

Since

: $\lim_{k \to \infty} \left( \frac{1}{4} \right)^k = 0$

and

: $\lim_{k \to \infty} \frac{k}{2^{2k - 1}} = 0,$

T is a convergent matrix. Note that ρ(T) = {{math|{{sfrac|1|4}}}}, where ρ(T) represents the spectral radius of T, since {{math|{{sfrac|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:

$\lim_{k \to \infty} \| \mathbf T^k \| = 0,$ for some natural norm;
$\lim_{k \to \infty} \| \mathbf T^k \| = 0,$ for all natural norms;
$\rho( \mathbf T ) < 1$ ;
$\lim_{k \to \infty} \mathbf T^k \mathbf x = \mathbf 0,$ for every x.{{harvtxt|Burden|Faires|1993|p=404}}{{harvtxt|Isaacson|Keller|1994|pp=14,63}}{{harvtxt|Varga|1960|p=122}}{{harvtxt|Varga|1962|p=13}}

Iterative methods

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

{{NumBlk|::| $\mathbf{Ax} = \mathbf{b}$ |{{EquationRef|2}}}}

into an equivalent system of the form

{{NumBlk|::| $\mathbf{x} = \mathbf{Tx} + \mathbf{c}$ |{{EquationRef|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

{{NumBlk|::| $\mathbf{x}^{(k + 1)} = \mathbf{Tx}^{(k)} + \mathbf{c}$ |{{EquationRef|4}}}}

for each k ≥ 0.{{harvtxt|Burden|Faires|1993|p=406}}{{harvtxt|Varga|1962|p=61}} For any initial vector x⁽⁰⁾ ∈ $\mathbb{R}^n$ , the sequence $\lbrace \mathbf{x}^{ \left( k \right) } \rbrace _{k = 0}^{\infty}$ defined by ({{EquationNote|4}}), for each k ≥ 0 and c ≠ 0, converges to the unique solution of ({{EquationNote|3}}) if and only if ρ(T) < 1, that is, T is a convergent matrix.{{harvtxt|Burden|Faires|1993|p=412}}{{harvtxt|Isaacson|Keller|1994|pp=62–63}}

=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 ({{EquationNote|2}}) above, with A non-singular, the matrix A can be split, that is, written as a difference

{{NumBlk|::| $\mathbf{A} = \mathbf{B} - \mathbf{C}$ |{{EquationRef|5}}}}

so that ({{EquationNote|2}}) can be re-written as ({{EquationNote|4}}) above. The expression ({{EquationNote|5}}) is a regular splitting of A if and only if B⁻¹ ≥ 0 and C ≥ 0, that is, {{nowrap|B⁻¹}} and C have only nonnegative entries. If the splitting ({{EquationNote|5}}) is a regular splitting of the matrix A and A⁻¹ ≥ 0, then ρ(T) < 1 and T is a convergent matrix. Hence the method ({{EquationNote|4}}) converges.{{harvtxt|Varga|1960|pp=122–123}}{{harvtxt|Varga|1962|p=89}}

Semi-convergent matrix

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

{{NumBlk|::| $\lim_{k \to \infty} \mathbf T^k$ |{{EquationRef|6}}}}

exists.{{harvtxt|Meyer & Plemmons|1977|p=699}} If A is possibly singular but ({{EquationNote|2}}) is consistent, that is, b is in the range of A, then the sequence defined by ({{EquationNote|4}}) converges to a solution to ({{EquationNote|2}}) for every x⁽⁰⁾ ∈ $\mathbb{R}^n$ if and only if T is semi-convergent. In this case, the splitting ({{EquationNote|5}}) is called a semi-convergent splitting of A.{{harvtxt|Meyer & Plemmons|1977|p=700}}

Notes

References

{{citation | first1 = Richard L. | last1 = Burden | first2 = J. Douglas | last2 = Faires | year = 1993 | isbn = 0-534-93219-3 | title = Numerical Analysis | edition = 5th | publisher = Prindle, Weber and Schmidt | location = Boston | url-access = registration | url = https://archive.org/details/numericalanalysi00burd }}.
{{ citation | first1 = Eugene | last1 = Isaacson | first2 = Herbert Bishop | last2 = Keller| year = 1994 | isbn = 0-486-68029-0 | title = Analysis of Numerical Methods | publisher = Dover | location = New York }}.
{{ cite journal | title = Convergent Powers of a Matrix with Applications to Iterative Methods for Singular Linear Systems |date=Sep 1977 | author1 = Carl D. Meyer, Jr. | author2 = R. J. Plemmons | journal = SIAM Journal on Numerical Analysis | volume = 14 | issue = 4 | pages = 699–705 | doi=10.1137/0714047 | ref = {{harvid|Meyer & Plemmons|1977}} }}
{{ Cite book | first1 = Richard S. | last1 = Varga | chapter = Factorization and Normalized Iterative Methods | title = Boundary Problems in Differential Equations | editor1-last = Langer | editor1-first = Rudolph E. | publisher = University of Wisconsin Press | location = Madison | pages = 121–142 | year = 1960 | lccn = 60-60003 }}
{{ citation | first1 = Richard S. | last1 = Varga | title = Matrix Iterative Analysis | publisher = Prentice–Hall | location = New Jersey | year = 1962 | lccn = 62-21277 }}.

Category:Limits (mathematics)

Category:Matrices (mathematics)

Category:Numerical linear algebra

Category:Relaxation (iterative methods)