• Images
• Videos
• Documents
• Books
• Articles

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

lim k → ∞ ( T k ) i j = 0 , {\displaystyle \lim _{k\to \infty }(\mathbf {T} ^{k})_{ij}=0,}

1

for each i = 1, 2, ..., n and j = 1, 2, ..., n.¹²³

Example

Let

T = ( 1 4 1 2 0 1 4 ) . {\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

T 2 = ( 1 16 1 4 0 1 16 ) , T 3 = ( 1 64 3 32 0 1 64 ) , T 4 = ( 1 256 1 32 0 1 256 ) , T 5 = ( 1 1024 5 512 0 1 1024 ) , {\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}}} T 6 = ( 1 4096 3 1024 0 1 4096 ) , {\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,

T k = ( ( 1 4 ) k k 2 2 k − 1 0 ( 1 4 ) k ) . {\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

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

and

lim k → ∞ k 2 2 k − 1 = 0 , {\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. lim k → ∞ ‖ T k ‖ = 0 , {\displaystyle \lim _{k\to \infty }\|\mathbf {T} ^{k}\|=0,} for some natural norm;
2. lim k → ∞ ‖ T k ‖ = 0 , {\displaystyle \lim _{k\to \infty }\|\mathbf {T} ^{k}\|=0,} for all natural norms;
3. ρ ( T ) < 1 {\displaystyle \rho (\mathbf {T} )<1} ;
4. lim k → ∞ T k x = 0 , {\displaystyle \lim _{k\to \infty }\mathbf {T} ^{k}\mathbf {x} =\mathbf {0} ,} for every x.⁴⁵⁶⁷

Iterative methods

Main article: Iterative method

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

A x = b {\displaystyle \mathbf {Ax} =\mathbf {b} }

2

into an equivalent system of the form

x = T x + c {\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

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

4

for each k ≥ 0.⁸⁹ For any initial vector x(0) ∈ R n {\displaystyle \mathbb {R} ^{n}} , the sequence { x ( k ) } k = 0 ∞ {\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.¹⁰¹¹

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

A = B − C {\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−1 ≥ 0 and C ≥ 0, that is, B−1 and C have only nonnegative entries. If the splitting (5) is a regular splitting of the matrix A and A−1 ≥ 0, then ρ(T) < 1 and T is a convergent matrix. Hence the method (4) converges.¹²¹³

Semi-convergent matrix

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

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

6

exists.¹⁴ 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) ∈ R n {\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.¹⁵

See also

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

Notes

• 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. doi:10.1137/0714047.
• Varga, Richard S. (1960). "Factorization and Normalized Iterative Methods". In Langer, Rudolph E. (ed.). 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.

References

1. Burden & Faires (1993, p. 404) - Burden, Richard L.; Faires, J. Douglas (1993), Numerical Analysis (5th ed.), Boston: Prindle, Weber and Schmidt, ISBN 0-534-93219-3 https://archive.org/details/numericalanalysi00burd ↩

2. Isaacson & Keller (1994, p. 14) - Isaacson, Eugene; Keller, Herbert Bishop (1994), Analysis of Numerical Methods, New York: Dover, ISBN 0-486-68029-0 ↩

3. Varga (1962, p. 13) - Varga, Richard S. (1962), Matrix Iterative Analysis, New Jersey: Prentice–Hall, LCCN 62-21277 https://lccn.loc.gov/62-21277 ↩

4. Burden & Faires (1993, p. 404) - Burden, Richard L.; Faires, J. Douglas (1993), Numerical Analysis (5th ed.), Boston: Prindle, Weber and Schmidt, ISBN 0-534-93219-3 https://archive.org/details/numericalanalysi00burd ↩

5. Isaacson & Keller (1994, pp. 14, 63) - Isaacson, Eugene; Keller, Herbert Bishop (1994), Analysis of Numerical Methods, New York: Dover, ISBN 0-486-68029-0 ↩

6. Varga (1960, p. 122) - Varga, Richard S. (1960). "Factorization and Normalized Iterative Methods". In Langer, Rudolph E. (ed.). Boundary Problems in Differential Equations. Madison: University of Wisconsin Press. pp. 121–142. LCCN 60-60003. https://lccn.loc.gov/60-60003 ↩

7. Varga (1962, p. 13) - Varga, Richard S. (1962), Matrix Iterative Analysis, New Jersey: Prentice–Hall, LCCN 62-21277 https://lccn.loc.gov/62-21277 ↩

8. Burden & Faires (1993, p. 406) - Burden, Richard L.; Faires, J. Douglas (1993), Numerical Analysis (5th ed.), Boston: Prindle, Weber and Schmidt, ISBN 0-534-93219-3 https://archive.org/details/numericalanalysi00burd ↩

9. Varga (1962, p. 61) - Varga, Richard S. (1962), Matrix Iterative Analysis, New Jersey: Prentice–Hall, LCCN 62-21277 https://lccn.loc.gov/62-21277 ↩

10. Burden & Faires (1993, p. 412) - Burden, Richard L.; Faires, J. Douglas (1993), Numerical Analysis (5th ed.), Boston: Prindle, Weber and Schmidt, ISBN 0-534-93219-3 https://archive.org/details/numericalanalysi00burd ↩

11. Isaacson & Keller (1994, pp. 62–63) - Isaacson, Eugene; Keller, Herbert Bishop (1994), Analysis of Numerical Methods, New York: Dover, ISBN 0-486-68029-0 ↩

12. Varga (1960, pp. 122–123) - Varga, Richard S. (1960). "Factorization and Normalized Iterative Methods". In Langer, Rudolph E. (ed.). Boundary Problems in Differential Equations. Madison: University of Wisconsin Press. pp. 121–142. LCCN 60-60003. https://lccn.loc.gov/60-60003 ↩

13. Varga (1962, p. 89) - Varga, Richard S. (1962), Matrix Iterative Analysis, New Jersey: Prentice–Hall, LCCN 62-21277 https://lccn.loc.gov/62-21277 ↩

14. Meyer & Plemmons (1977, p. 699) - 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. doi:10.1137/0714047. https://doi.org/10.1137%2F0714047 ↩

15. Meyer & Plemmons (1977, p. 700) - 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. doi:10.1137/0714047. https://doi.org/10.1137%2F0714047 ↩