Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Convergent matrix
open-in-new
<h2 id="background">Background</h2> <p>When successive powers of a <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a> 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 <a href="/facts/Matrix_splitting/lSExxJBj">regular splitting</a> of a <a href="/facts/Invertible_matrix/fPqXk3V8">non-singular</a> 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 <a href="/facts/Iterative_method/uKMAJhEh">iterative method</a> converges for every initial vector if T is convergent, and under certain conditions if T is semi-convergent. </p> <h2 id="definition">Definition</h2> <p>We call an <i>n</i> × <i>n</i> matrix T a convergent matrix if </p> <table><tbody><tr><td> lim k → ∞ ( T k ) i j = 0 , {\displaystyle \lim _{k\to \infty }(\mathbf {T} ^{k})_{ij}=0,} </td> <td></td> <td>1</td></tr></tbody></table> <p>for each <i>i</i> = 1, 2, ..., <i>n</i> and <i>j</i> = 1, 2, ..., <i>n</i>.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a><a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p> <h2 id="example">Example</h2> <p>Let </p> 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}}} <p>Computing successive powers of T, we obtain </p> 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}}} <p>and, in general, </p> 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}}} <p>Since </p> lim k → ∞ ( 1 4 ) k = 0 {\displaystyle \lim _{k\to \infty }\left({\frac {1}{4}}\right)^{k}=0} <p>and </p> lim k → ∞ k 2 2 k − 1 = 0 , {\displaystyle \lim _{k\to \infty }{\frac {k}{2^{2k-1}}}=0,} <p>T is a convergent matrix. Note that <i>ρ</i>(T) = 1/4, where <i>ρ</i>(T) represents the <a href="/facts/Spectral_radius/j8T2xrLu">spectral radius</a> of T, since 1/4 is the only <a href="/facts/Eigenvalue/8TjEoT8u">eigenvalue</a> of T. </p> <h2 id="characterizations">Characterizations</h2> <p>Let T be an <i>n</i> × <i>n</i> matrix. The following properties are equivalent to T being a convergent matrix: </p> <ol><li> lim k → ∞ ‖ T k ‖ = 0 , {\displaystyle \lim _{k\to \infty }\|\mathbf {T} ^{k}\|=0,} for some natural norm;</li> <li> lim k → ∞ ‖ T k ‖ = 0 , {\displaystyle \lim _{k\to \infty }\|\mathbf {T} ^{k}\|=0,} for all natural norms;</li> <li> ρ ( T ) < 1 {\displaystyle \rho (\mathbf {T} )<1} ;</li> <li> lim k → ∞ T k x = 0 , {\displaystyle \lim _{k\to \infty }\mathbf {T} ^{k}\mathbf {x} =\mathbf {0} ,} for every x.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a><a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a><a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a></li></ol> <h2 id="iterative-methods">Iterative methods</h2> <p class="note">Main article: <a href="/facts/Iterative_method/uKMAJhEh">Iterative method</a></p> <p>A general iterative method involves a process that converts the <a href="/facts/System_of_linear_equations/fk9CFdgp">system of linear equations</a> </p> <table><tbody><tr><td> A x = b {\displaystyle \mathbf {Ax} =\mathbf {b} } </td> <td></td> <td>2</td></tr></tbody></table> <p>into an equivalent system of the form </p> <table><tbody><tr><td> x = T x + c {\displaystyle \mathbf {x} =\mathbf {Tx} +\mathbf {c} } </td> <td></td> <td>3</td></tr></tbody></table> <p>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 </p> <table><tbody><tr><td> x ( k + 1 ) = T x ( k ) + c {\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {Tx} ^{(k)}+\mathbf {c} } </td> <td></td> <td>4</td></tr></tbody></table> <p>for each <i>k</i> ≥ 0.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a><a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> 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 <i>k</i> ≥ 0 and c ≠ 0, converges to the unique solution of (3) if and only if <i>ρ</i>(T) < 1, that is, T is a convergent matrix.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a><a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a> </p> <h3>Regular splitting</h3> <p class="note">Main article: <a href="/facts/Matrix_splitting/lSExxJBj">Matrix splitting</a></p> <p>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 </p> <table><tbody><tr><td> A = B − C {\displaystyle \mathbf {A} =\mathbf {B} -\mathbf {C} } </td> <td></td> <td>5</td></tr></tbody></table> <p>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 <i>ρ</i>(T) < 1 and T is a convergent matrix. Hence the method (4) converges.<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a><a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a> </p> <h2 id="semi-convergent-matrix">Semi-convergent matrix</h2> <p>We call an <i>n</i> × <i>n</i> matrix T a semi-convergent matrix if the limit </p> <table><tbody><tr><td> lim k → ∞ T k {\displaystyle \lim _{k\to \infty }\mathbf {T} ^{k}} </td> <td></td> <td>6</td></tr></tbody></table> <p>exists.<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> 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.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Gauss%E2%80%93Seidel_method/eK94QeFt">Gauss–Seidel method</a></li> <li><a href="/facts/Jacobi_method/aNf3WE63">Jacobi method</a></li> <li><a href="/facts/List_of_matrices/op20J9jC">List of matrices</a></li> <li><a href="/facts/Nilpotent_matrix/qIns3FJJ">Nilpotent matrix</a></li> <li><a href="/facts/Successive_over-relaxation/rCUV11er">Successive over-relaxation</a></li></ul> <h2 id="notes">Notes</h2> <ul><li>Burden, Richard L.; Faires, J. Douglas (1993), <a href="https://archive.org/details/numericalanalysi00burd"><i>Numerical Analysis</i></a> (5th ed.), Boston: Prindle, Weber and Schmidt, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-534-93219-3.</li> <li>Isaacson, Eugene; Keller, Herbert Bishop (1994), <i>Analysis of Numerical Methods</i>, New York: <a href="/facts/Dover_Publications/RwjvlSFv">Dover</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-486-68029-0.</li> <li>Carl D. Meyer, Jr.; R. J. Plemmons (Sep 1977). "Convergent Powers of a Matrix with Applications to Iterative Methods for Singular Linear Systems". <i><a href="/facts/SIAM_Journal_on_Numerical_Analysis/uUEWPahC">SIAM Journal on Numerical Analysis</a></i>. 14 (4): 699–705. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1137%2F0714047">10.1137/0714047</a>.</li> <li>Varga, Richard S. (1960). "Factorization and Normalized Iterative Methods". In Langer, Rudolph E. (ed.). <i>Boundary Problems in Differential Equations</i>. Madison: <a href="/facts/University_of_Wisconsin_Press/Mq2AawzW">University of Wisconsin Press</a>. pp. 121–142. <a href="/facts/LCCN_(identifier)/5hb5Cw2V">LCCN</a> <a href="https://lccn.loc.gov/60-60003">60-60003</a>.</li> <li>Varga, Richard S. (1962), <i>Matrix Iterative Analysis</i>, New Jersey: <a href="/facts/Prentice%E2%80%93Hall/bynWAuat">Prentice–Hall</a>, <a href="/facts/LCCN_(identifier)/5hb5Cw2V">LCCN</a> <a href="https://lccn.loc.gov/62-21277">62-21277</a>.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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 <a href="https://archive.org/details/numericalanalysi00burd" target="_blank">https://archive.org/details/numericalanalysi00burd</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Isaacson & Keller (1994, p. 14) - Isaacson, Eugene; Keller, Herbert Bishop (1994), Analysis of Numerical Methods, New York: Dover, ISBN 0-486-68029-0 <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Varga (1962, p. 13) - Varga, Richard S. (1962), Matrix Iterative Analysis, New Jersey: Prentice–Hall, LCCN 62-21277 <a href="https://lccn.loc.gov/62-21277" target="_blank">https://lccn.loc.gov/62-21277</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>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 <a href="https://archive.org/details/numericalanalysi00burd" target="_blank">https://archive.org/details/numericalanalysi00burd</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Isaacson & Keller (1994, pp. 14, 63) - Isaacson, Eugene; Keller, Herbert Bishop (1994), Analysis of Numerical Methods, New York: Dover, ISBN 0-486-68029-0 <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>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. <a href="https://lccn.loc.gov/60-60003" target="_blank">https://lccn.loc.gov/60-60003</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Varga (1962, p. 13) - Varga, Richard S. (1962), Matrix Iterative Analysis, New Jersey: Prentice–Hall, LCCN 62-21277 <a href="https://lccn.loc.gov/62-21277" target="_blank">https://lccn.loc.gov/62-21277</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>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 <a href="https://archive.org/details/numericalanalysi00burd" target="_blank">https://archive.org/details/numericalanalysi00burd</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>Varga (1962, p. 61) - Varga, Richard S. (1962), Matrix Iterative Analysis, New Jersey: Prentice–Hall, LCCN 62-21277 <a href="https://lccn.loc.gov/62-21277" target="_blank">https://lccn.loc.gov/62-21277</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>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 <a href="https://archive.org/details/numericalanalysi00burd" target="_blank">https://archive.org/details/numericalanalysi00burd</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>Isaacson & Keller (1994, pp. 62–63) - Isaacson, Eugene; Keller, Herbert Bishop (1994), Analysis of Numerical Methods, New York: Dover, ISBN 0-486-68029-0 <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>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. <a href="https://lccn.loc.gov/60-60003" target="_blank">https://lccn.loc.gov/60-60003</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>Varga (1962, p. 89) - Varga, Richard S. (1962), Matrix Iterative Analysis, New Jersey: Prentice–Hall, LCCN 62-21277 <a href="https://lccn.loc.gov/62-21277" target="_blank">https://lccn.loc.gov/62-21277</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>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. <a href="https://doi.org/10.1137%2F0714047" target="_blank">https://doi.org/10.1137%2F0714047</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>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. <a href="https://doi.org/10.1137%2F0714047" target="_blank">https://doi.org/10.1137%2F0714047</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> </ol>