Convergent matrix

Template:Short description 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{array}{cc}& 𝐓=\left(\begin{array}{cc}\frac{1}{4}& \frac{1}{2}\\ 0& \frac{1}{4}\end{array}\right).\end{array}$

Computing successive powers of T, we obtain

$\begin{array}{cc}& {𝐓}^2=\left(\begin{array}{cc}\frac{1}{16}& \frac{1}{4}\\ 0& \frac{1}{16}\end{array}\right),{𝐓}^3=\left(\begin{array}{cc}\frac{1}{64}& \frac{3}{32}\\ 0& \frac{1}{64}\end{array}\right),{𝐓}^4=\left(\begin{array}{cc}\frac{1}{256}& \frac{1}{32}\\ 0& \frac{1}{256}\end{array}\right),{𝐓}^5=\left(\begin{array}{cc}\frac{1}{1024}& \frac{5}{512}\\ 0& \frac{1}{1024}\end{array}\right),\end{array}$

$\begin{array}{c}{𝐓}^6=\left(\begin{array}{cc}\frac{1}{4096}& \frac{3}{1024}\\ 0& \frac{1}{4096}\end{array}\right),\end{array}$

and, in general,

$\begin{array}{c}{𝐓}^k=\left(\begin{array}{cc}(\frac{1}{4}{)}^k& \frac{k}{2^{2k-1}}\\ 0& (\frac{1}{4}{)}^k\end{array}\right).\end{array}$

Since

$\underset{k\to \mathrm{\infty }}{\lim }{\left(\frac{1}{4}\right)}^k=0$

and

$\underset{k\to \mathrm{\infty }}{\lim }\frac{k}{2^{2k-1}}=0,$

T is a convergent matrix. Note that ρ(T) = Template:Math, where ρ(T) represents the spectral radius of T, since Template:Math 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. $\underset{k\to \mathrm{\infty }}{\lim }\Vert {𝐓}^k\Vert =0,$ for some natural norm;
2. $\underset{k\to \mathrm{\infty }}{\lim }\Vert {𝐓}^k\Vert =0,$ for all natural norms;
3. $\rho (𝐓)<1$;
4. $\underset{k\to \mathrm{\infty }}{\lim }{𝐓}^k𝐱=\mathrm{𝟎},$ for every x.

Iterative methods

Template:Main 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⁽⁰⁾ ∈ ${ℝ}^n$, the sequence $\{{𝐱}^{\left(k\right)}{\}}_{k=0}^{\mathrm{\infty }}$ defined by (Template:EquationNote), for each k ≥ 0 and c ≠ 0, converges to the unique solution of (Template:EquationNote) if and only if ρ(T) < 1, that is, T is a convergent matrix.

Regular splitting

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

so that (Template:EquationNote) can be re-written as (Template:EquationNote) above. The expression (Template:EquationNote) is a regular splitting of A if and only if B⁻¹ ≥ 0 and C ≥ 0, that is, Template:Nowrap and C have only nonnegative entries. If the splitting (Template:EquationNote) is a regular splitting of the matrix A and A⁻¹ ≥ 0, then ρ(T) < 1 and T is a convergent matrix. Hence the method (Template:EquationNote) 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 (Template:EquationNote) is consistent, that is, b is in the range of A, then the sequence defined by (Template:EquationNote) converges to a solution to (Template:EquationNote) for every x⁽⁰⁾ ∈ ${ℝ}^n$ if and only if T is semi-convergent. In this case, the splitting (Template:EquationNote) is called a semi-convergent splitting of A.

See also

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

References

• Template:Citation.
• Template:Citation.
• Template:Cite journal
• Template:Cite book
• Template:Citation.