Convergent matrix

From Wikipedia, the free encyclopedia

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.^[1]^[2]^[3]

Example

Let

${\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

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

${\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,

${\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

$\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) = $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:

$\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.^[4]^[5]^[6]^[7]

Iterative methods

Main article: Iterative method

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

${\mathbf {Ax}}={\mathbf {b}}\quad (2)$

into an equivalent system of the form

${\mathbf {x}}={\mathbf {Tx}}+{\mathbf {c}}\quad (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

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

for each k ≥ 0.^[8]^[9] 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.^[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, 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.^[12]^[13]

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.^[14] 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.^[15]

Notes

↑ Burden & Faires (1993, p. 404)
↑ Isaacson & Keller (1994, p. 14)
↑ Varga (1962, p. 13)
↑ Burden & Faires (1993, p. 404)
↑ Isaacson & Keller (1994, pp. 14,63)
↑ Varga (1960, p. 122)
↑ Varga (1962, p. 13)
↑ Burden & Faires (1993, p. 406)
↑ Varga (1962, p. 61)
↑ Burden & Faires (1993, p. 412)
↑ Isaacson & Keller (1994, pp. 62–63)
↑ Varga (1960, pp. 122–123)
↑ Varga (1962, p. 89)
↑ Meyer & Plemmons (1977, p. 699)
↑ Meyer & Plemmons (1977, p. 700)

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

v t e Numerical linear algebra

Key concepts	Floating point Numerical stability BLAS

Problems	Matrix multiplication Matrix decompositions Linear equations Sparse problems

Hardware	CPU cache TLB Cache-oblivious algorithm SIMD Multiprocessing

Software	Specialized libraries General purpose software

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.