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

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

Example

Let
:\begin
& \mathbf = \begin
\frac & \frac \\ pt0 & \frac
\end.
\end
Computing successive powers of T, we obtain
:\begin
& \mathbf^2 = \begin
\frac & \frac \\ pt0 & \frac
\end, \quad \mathbf^3 = \begin
\frac & \frac \\ pt0 & \frac
\end, \quad \mathbf^4 = \begin
\frac & \frac \\ pt0 & \frac
\end, \quad \mathbf^5 = \begin
\frac & \frac \\ pt0 & \frac
\end,
\end
:\begin
\mathbf^6 = \begin
\frac & \frac \\ pt0 & \frac
\end,
\end
and, in general,
:\begin
\mathbf^k = \begin
(\frac)^k & \frac \\ pt0 & (\frac)^k
\end.
\end
Since
:$\lim_ \left( \frac \right)^k = 0$
and
:$\lim_ \frac = 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_ \, \mathbf T^k \, = 0,$ for some natural norm;
#$\lim_ \, \mathbf T^k \, = 0,$ for all natural norms;
#$\rho( \mathbf T ) < 1$;
#$\lim_ \mathbf T^k \mathbf x = \mathbf 0,$ for every x.

Iterative methods

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⁽⁰⁾ ∈ $\mathbb^n$, the sequence $\lbrace \mathbf^ \rbrace _^$ 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

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⁻¹ ≥ 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⁻¹ ≥ 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⁽⁰⁾ ∈ $\mathbb^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

Notes

References

* .
* .
*
*
* .

{{Authority control

Limits (mathematics)
Matrices (mathematics)
Numerical linear algebra
Relaxation (iterative methods)