Convergent matrix

From formulasearchengine
Jump to navigation Jump to 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

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

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

Example

Let

Computing successive powers of T, we obtain

and, in general,

Since

and

T is a convergent matrix. Note that ρ(T) = {{ safesubst:#invoke:Unsubst||$B=1/4}}, where ρ(T) represents the spectral radius of T, since {{ safesubst:#invoke:Unsubst||$B=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. for some natural norm;
  2. for all natural norms;
  3. ;
  4. for every x.[4][5][6][7]

Iterative methods

{{#invoke:main|main}} A general iterative method involves a process that converts the system of linear equations

into an equivalent system of the form

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

for each k ≥ 0.[8][9] For any initial vector x(0), the sequence 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

{{#invoke:main|main}} 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

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

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

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

Notes

References

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

  • {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

  • {{#invoke:citation/CS1|citation

|CitationClass=book }}

  • {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

Template:Numerical linear algebra