Convergent matrix

Jump to: navigation, search

In numerical 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

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

(1)

for each i = 1, 2, ..., n and j = 1, 2, ..., n.[1][2][3]

Example

Let

{\displaystyle {\begin{aligned}&\mathbf {T} ={\begin{pmatrix}{\frac {1}{4}}&{\frac {1}{2}}\\[4pt]0&{\frac {1}{4}}\end{pmatrix}}.\end{aligned}}}

Computing successive powers of T, we obtain

{\displaystyle {\begin{aligned}&\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{aligned}}}
{\displaystyle {\begin{aligned}\mathbf {T} ^{6}={\begin{pmatrix}{\frac {1}{4096}}&{\frac {3}{1024}}\\[4pt]0&{\frac {1}{4096}}\end{pmatrix}},\end{aligned}}}

and, in general,

{\displaystyle {\begin{aligned}\mathbf {T} ^{k}={\begin{pmatrix}({\frac {1}{4}})^{k}&{\frac {k}{2^{2k-1}}}\\[4pt]0&({\frac {1}{4}})^{k}\end{pmatrix}}.\end{aligned}}}

Since

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

and

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

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

1. ${\displaystyle \lim _{k\to \infty }\|{\mathbf {T}}^{k}\|=0,}$ for some natural norm;
2. ${\displaystyle \lim _{k\to \infty }\|{\mathbf {T}}^{k}\|=0,}$ for all natural norms;
3. ${\displaystyle \rho ({\mathbf {T}})<1}$;
4. ${\displaystyle \lim _{k\to \infty }{\mathbf {T}}^{k}{\mathbf {x}}={\mathbf {0}},}$ for every x.[4][5][6][7]

Iterative methods

Main article: Iterative method

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

${\displaystyle {\mathbf {Ax}}={\mathbf {b}}}$

(2)

into an equivalent system of the form

${\displaystyle {\mathbf {x}}={\mathbf {Tx}}+{\mathbf {c}}}$

(3)

for some matrix T and vector c. After the initial vector x(0) is selected, the sequence of approximate solution vectors is generated by computing

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

(4)

for each k ≥ 0.[8][9] For any initial vector x(0)${\displaystyle \mathbb {R} ^{n}}$, the sequence ${\displaystyle \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, that is, T is a convergent matrix.[10][11]

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, that is, written as a difference

${\displaystyle {\mathbf {A}}={\mathbf {B}}-{\mathbf {C}}}$

(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−10 and C0, that is, B−1 and C have only nonnegative entries. If the splitting (5) is a regular splitting of the matrix A and A−10, then ρ(T) < 1 and T is a convergent matrix. Hence the method (4) converges.[12][13]

Semi-convergent matrix

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

${\displaystyle \lim _{k\to \infty }{\mathbf {T}}^{k}}$

(6)

exists.[14] If A is possibly singular but (2) is consistent, that is, b is in the range of A, then the sequence defined by (4) converges to a solution to (2) for every x(0)${\displaystyle \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.[15]

Notes

1. ^ Burden & Faires (1993, p. 404)
2. ^ Isaacson & Keller (1994, p. 14)
3. ^ Varga (1962, p. 13)
4. ^ Burden & Faires (1993, p. 404)
5. ^ Isaacson & Keller (1994, pp. 14,63)
6. ^ Varga (1960, p. 122)
7. ^ Varga (1962, p. 13)
8. ^ Burden & Faires (1993, p. 406)
9. ^ Varga (1962, p. 61)
10. ^ Burden & Faires (1993, p. 412)
11. ^ Isaacson & Keller (1994, pp. 62–63)
12. ^ Varga (1960, pp. 122–123)
13. ^ Varga (1962, p. 89)
14. ^ Meyer & Plemmons (1977, p. 699)
15. ^ Meyer & Plemmons (1977, p. 700)