en>BG19bot: WP:CHECKWIKI error fix for #84. Empty section. Do general fixes if a problem exists. -, added orphan tag using AWB (9421)

2013-08-19T07:43:55Z

WP:CHECKWIKI error fix for #84. Empty section. Do general fixes if a problem exists. -, added orphan tag using AWB (9421)

New page

In the [[mathematics|mathematical]] discipline of [[numerical linear algebra]], when successive powers of a [[matrix (mathematics)|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 [[matrix splitting|regular splitting]] of a [[invertible matrix|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

:<math> \lim_{k \to \infty}( \bold T^k)_{ij} = \bold 0, \quad (1) </math>

for each ''i'' = 1, 2, ..., ''n'' and ''j'' = 1, 2, ..., ''n''.<ref>{{harvtxt|Burden|Faires|1993|p=404}}</ref><ref>{{harvtxt|Isaacson|Keller|1994|p=14}}</ref><ref>{{harvtxt|Varga|1962|p=13}}</ref>

==Example==
Let
:<math>\begin{align}
& \mathbf{T} = \begin{pmatrix}
\frac{1}{4} & \frac{1}{2} \\[4pt]
0 & \frac{1}{4}
\end{pmatrix}.
\end{align}</math>
Computing successive powers of '''T''', we obtain
:<math>\begin{align}
& \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{align}</math>
:<math>\begin{align}
\mathbf{T}^6 = \begin{pmatrix}
\frac{1}{4096} & \frac{3}{1024} \\[4pt]
0 & \frac{1}{4096}
\end{pmatrix},
\end{align}</math>
and, in general,
:<math>\begin{align}
\mathbf{T}^k = \begin{pmatrix}
(\frac{1}{4})^k & \frac{k}{2^{2k - 1}} \\[4pt]
0 & (\frac{1}{4})^k
\end{pmatrix}.
\end{align}</math>
Since
:<math> \lim_{k \to \infty} \left( \frac{1}{4} \right)^k = 0 </math>
and
:<math> \lim_{k \to \infty} \frac{k}{2^{2k - 1}} = 0, </math>
'''T''' is a convergent matrix. Note that ''ρ''('''T''') = {{math|{{sfrac|1|4}}}}, where ''ρ''('''T''') represents the [[spectral radius]] of '''T''', since {{math|{{sfrac|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:
#<math> \lim_{k \to \infty} \| \bold T^k \| = 0, </math> for some natural norm;
#<math> \lim_{k \to \infty} \| \bold T^k \| = 0, </math> for all natural norms;
#<math> \rho( \bold T ) < 1 </math>;
#<math> \lim_{k \to \infty} \bold T^k \bold x = \bold 0, </math> for every '''x'''.<ref>{{harvtxt|Burden|Faires|1993|p=404}}</ref><ref>{{harvtxt|Isaacson|Keller|1994|pp=14,63}}</ref><ref>{{harvtxt|Varga|1960|p=122}}</ref><ref>{{harvtxt|Varga|1962|p=13}}</ref>

==Iterative methods==
{{main|Iterative method}}
A general '''iterative method''' involves a process that converts the [[system of linear equations]]

:<math> \bold{Ax} = \bold{b} \quad (2) </math>

into an equivalent system of the form

:<math> \bold{x} = \bold{Tx} + \bold{c} \quad (3) </math>

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

:<math> \bold{x}^{(k + 1)} = \bold{Tx}^{(k)} + \bold{c} \quad (4) </math>

for each ''k'' ≥ 0.<ref>{{harvtxt|Burden|Faires|1993|p=406}}</ref><ref>{{harvtxt|Varga|1962|p=61}}</ref> For any initial vector '''x'''(0) ∈ <math> \mathbb{R}^n </math>, the sequence <math> \lbrace \bold{x}^{ \left( k \right) } \rbrace _{k = 0}^{\infty} </math> 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.<ref>{{harvtxt|Burden|Faires|1993|p=412}}</ref><ref>{{harvtxt|Isaacson|Keller|1994|pp=62–63}}</ref>

==Regular splitting==
{{main|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

:<math> \bold{A} = \bold{B} - \bold{C} \quad (5) </math>

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''', i.e., '''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.<ref>{{harvtxt|Varga|1960|pp=122–123}}</ref><ref>{{harvtxt|Varga|1962|p=89}}</ref>

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

:<math> \lim_{k \to \infty} \bold T^k \quad (6) </math>

exists.<ref>{{harvtxt|Meyer|Plemmons|1977|p=699}}</ref> 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'''(0) ∈ <math> \mathbb{R}^n </math> if and only if '''T''' is semi-convergent. In this case, the splitting (5) is called a '''semi-convergent splitting''' of '''A'''.<ref>{{harvtxt|Meyer|Plemmons|1977|p=700}}</ref>

==See also==
*[[Gauss–Seidel method]]
*[[Jacobi method]]
*[[List of matrices]]
*[[Successive over-relaxation]]

==Notes==
{{reflist}}

==References==
* {{ citation | first1 = Richard L. | last1 = Burden | first2 = J. Douglas | last2 = Faires | year = 1993 | isbn = 0-534-93219-3 | title = Numerical Analysis | edition = 5th | publisher = [[Prindle, Weber and Schmidt]] | location = Boston }}.

* {{ citation | first1 = Eugene | last1 = Isaacson | first2 = Herbert Bishop | last2 = Keller| year = 1994 | isbn = 0-486-68029-0 | title = Analysis of Numerical Methods | publisher = [[Dover]] | location = New York }}.

* {{ cite journal | title = Convergent Powers of a Matrix with Applications to Iterative Methods for Singular Linear Systems |date=Sep 1977 | author1 = Carl D. Meyer, Jr. | author2 = R. J. Plemmons | journal = [[SIAM Journal on Numerical Analysis]] | volume = 14 | issue = 4 | pages = 699–705 }}

* {{ Cite book | first1 = Richard S. | last1 = Varga | chapter = Factorization and Normalized Iterative Methods | title = Boundary Problems in Differential Equations | editor1-last = Langer | editor1-first = Rudolph E. | publisher = [[University of Wisconsin Press]] | location = Madison | pages = 121–142 | year = 1960 | lccn = 60-60003 }}

* {{ citation | first1 = Richard S. | last1 = Varga | title = Matrix Iterative Analysis | publisher = [[Prentice–Hall]] | location = New Jersey | year = 1962 | lccn = 62-21277 }}.

{{Numerical linear algebra}}

[[Category:Limits (mathematics)]]
[[Category:Matrices]]
[[Category:Numerical linear algebra]]
[[Category:Relaxation (iterative methods)]]

Neutral Density - Revision history

en>BG19bot: WP:CHECKWIKI error fix for #84. Empty section. Do general fixes if a problem exists. -, added orphan tag using AWB (9421)