Convergent matrix

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

We call an n × n matrix T a convergent matrix if

 \lim_{k \to \infty}( \bold T^k)_{ij} = \bold 0, \quad (1)

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

Example[edit]

Let

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

Computing successive powers of T, we obtain

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

and, in general,

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

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[edit]

Let T be an n × n matrix. The following properties are equivalent to T being a convergent matrix:

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

Iterative methods[edit]

Main article: Iterative method

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

 \bold{Ax} = \bold{b} \quad (2)

into an equivalent system of the form

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

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

for each k ≥ 0.[8][9] For any initial vector x(0) \mathbb{R}^n , the sequence  \lbrace \bold{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[edit]

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

 \bold{A} = \bold{B} - \bold{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−10 and C0, i.e., 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[edit]

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

 \lim_{k \to \infty} \bold 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(0) \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]

See also[edit]

Notes[edit]

  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)

References[edit]

  • Isaacson, Eugene; Keller, Herbert Bishop (1994), Analysis of Numerical Methods, New York: Dover, ISBN 0-486-68029-0 .
  • 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 Check |lccn= value (help).