In themathematical discipline ofnumerical linear algebra, amatrix splitting is an expression which represents a givenmatrix as a sum or difference of matrices. Manyiterative methods (for example, for systems ofdifferential equations) depend upon the direct solution of matrix equations involving matrices more general thantridiagonal matrices. These matrix equations can often be solved directly and efficiently when written as a matrix splitting. The technique was devised byRichard S. Varga in 1960.^[1]

We seek to solve thematrix equation

${\displaystyle \mathbf{A}\mathbf{x}=\mathbf{k},}$

1

whereA is a givenn ×nnon-singular matrix, andk is a givencolumn vector withn components. We split the matrixA into

${\displaystyle \mathbf{A}=\mathbf{B}-\mathbf{C},}$

2

whereB andC aren ×n matrices. If, for an arbitraryn ×n matrixM,M has nonnegative entries, we writeM ≥0. IfM has only positive entries, we writeM >0. Similarly, if the matrixM₁ −M₂ has nonnegative entries, we writeM₁ ≥M₂.

Definition:A =B −C is aregular splitting of A ifB⁻¹ ≥0 andC ≥0.

We assume that matrix equations of the form

${\displaystyle \mathbf{B}\mathbf{x}=\mathbf{g},}$

3

whereg is a given column vector, can be solved directly for the vectorx. If (2) represents a regular splitting ofA, then the iterative method

${\displaystyle \mathbf{B}{\mathbf{x}}^{(m+1)}=\mathbf{C}{\mathbf{x}}^{(m)}+\mathbf{k},m=0,1,2,\dots ,}$

4

wherex⁽⁰⁾ is an arbitrary vector, can be carried out. Equivalently, we write (4) in the form

${\displaystyle {\mathbf{x}}^{(m+1)}={\mathbf{B}}^{-1}\mathbf{C}{\mathbf{x}}^{(m)}+{\mathbf{B}}^{-1}\mathbf{k},m=0,1,2,\dots }$

5

The matrixD =B⁻¹C has nonnegative entries if (2) represents a regular splitting ofA.^[2]

It can be shown that ifA⁻¹ >0, then${\displaystyle \rho (\mathbf{D})}$ < 1, where${\displaystyle \rho (\mathbf{D})}$ represents thespectral radius ofD, and thusD is aconvergent matrix. As a consequence, the iterative method (5) is necessarilyconvergent.^[3][4]

If, in addition, the splitting (2) is chosen so that the matrixB is adiagonal matrix (with the diagonal entries all non-zero, sinceB must beinvertible), thenB can be inverted in linear time (seeTime complexity).

Many iterative methods can be described as a matrix splitting. If the diagonal entries of the matrixA are all nonzero, and we express the matrixA as the matrix sum

${\displaystyle \mathbf{A}=\mathbf{D}-\mathbf{U}-\mathbf{L},}$

6

whereD is the diagonal part ofA, andU andL are respectively strictly upper and lowertriangularn ×n matrices, then we have the following.

TheJacobi method can be represented in matrix form as a splitting

${\displaystyle {\mathbf{x}}^{(m+1)}={\mathbf{D}}^{-1}(\mathbf{U}+\mathbf{L}){\mathbf{x}}^{(m)}+{\mathbf{D}}^{-1}\mathbf{k}.}$[5][6]

7

TheGauss–Seidel method can be represented in matrix form as a splitting

${\displaystyle {\mathbf{x}}^{(m+1)}=(\mathbf{D}-\mathbf{L}{)}^{-1}\mathbf{U}{\mathbf{x}}^{(m)}+(\mathbf{D}-\mathbf{L}{)}^{-1}\mathbf{k}.}$[7][8]

8

The method ofsuccessive over-relaxation can be represented in matrix form as a splitting

${\displaystyle {\mathbf{x}}^{(m+1)}=(\mathbf{D}-\omega \mathbf{L}{)}^{-1}[(1-\omega )\mathbf{D}+\omega \mathbf{U}]{\mathbf{x}}^{(m)}+\omega (\mathbf{D}-\omega \mathbf{L}{)}^{-1}\mathbf{k}.}$[9][10]

9

In equation (1), let

10

Let us apply the splitting (7) which is used in the Jacobi method: we splitA in such a way thatB consists ofall of the diagonal elements ofA, andC consists ofall of the off-diagonal elements ofA, negated. (Of course this is not the only useful way to split a matrix into two matrices.) We have

11

SinceB⁻¹ ≥0 andC ≥0, the splitting (11) is a regular splitting. SinceA⁻¹ >0, the spectral radius${\displaystyle \rho (\mathbf{D})}$ < 1. (The approximateeigenvalues ofD are${\displaystyle {\lambda }_i\approx -0.4599820,-0.3397859,\mathrm{0.7997679.}}$) Hence, the matrixD is convergent and the method (5) necessarily converges for the problem (10). Note that the diagonal elements ofA are all greater than zero, the off-diagonal elements ofA are all less than zero andA isstrictly diagonally dominant.^[11]

The method (5) applied to the problem (10) then takes the form

12

The exact solution to equation (12) is

${\displaystyle \mathbf{x}=\left(\begin{array}{c}2\\ -1\\ 3\end{array}\right).}$

13

The first few iterates for equation (12) are listed in the table below, beginning withx⁽⁰⁾ = (0.0, 0.0, 0.0)^T. From the table one can see that the method is evidently converging to the solution (13), albeit rather slowly.

${\displaystyle x_1^{(m)}}$	${\displaystyle x_2^{(m)}}$	${\displaystyle x_3^{(m)}}$
0.0	0.0	0.0
0.83333	-3.0000	2.0000
0.83333	-1.7917	1.9000
1.1861	-1.8417	2.1417
1.2903	-1.6326	2.3433
1.4608	-1.5058	2.4477
1.5553	-1.4110	2.5753
1.6507	-1.3235	2.6510
1.7177	-1.2618	2.7257
1.7756	-1.2077	2.7783
1.8199	-1.1670	2.8238

As stated above, the Jacobi method (7) is the same as the specific regular splitting (11) demonstrated above.

Since the diagonal entries of the matrixA in problem (10) are all nonzero, we can express the matrixA as the splitting (6), where

14

We then have

The Gauss–Seidel method (8) applied to the problem (10) takes the form

15

The first few iterates for equation (15) are listed in the table below, beginning withx⁽⁰⁾ = (0.0, 0.0, 0.0)^T. From the table one can see that the method is evidently converging to the solution (13), somewhat faster than the Jacobi method described above.

${\displaystyle x_1^{(m)}}$	${\displaystyle x_2^{(m)}}$	${\displaystyle x_3^{(m)}}$
0.0	0.0	0.0
0.8333	-2.7917	1.9417
0.8736	-1.8107	2.1620
1.3108	-1.5913	2.4682
1.5370	-1.3817	2.6459
1.6957	-1.2531	2.7668
1.7990	-1.1668	2.8461
1.8675	-1.1101	2.8985
1.9126	-1.0726	2.9330
1.9423	-1.0479	2.9558
1.9619	-1.0316	2.9708

Letω = 1.1. Using the splitting (14) of the matrixA in problem (10) for the successive over-relaxation method, we have

The successive over-relaxation method (9) applied to the problem (10) takes the form

16

The first few iterates for equation (16) are listed in the table below, beginning withx⁽⁰⁾ = (0.0, 0.0, 0.0)^T. From the table one can see that the method is evidently converging to the solution (13), slightly faster than the Gauss–Seidel method described above.

${\displaystyle x_1^{(m)}}$	${\displaystyle x_2^{(m)}}$	${\displaystyle x_3^{(m)}}$
0.0	0.0	0.0
0.9167	-3.0479	2.1345
0.8814	-1.5788	2.2209
1.4711	-1.5161	2.6153
1.6521	-1.2557	2.7526
1.8050	-1.1641	2.8599
1.8823	-1.0930	2.9158
1.9314	-1.0559	2.9508
1.9593	-1.0327	2.9709
1.9761	-1.0185	2.9829
1.9862	-1.0113	2.9901

• List of operator splitting topics
• Matrix decomposition
• M-matrix
• Stieltjes matrix

• Burden, Richard L.; Faires, J. Douglas (1993),Numerical Analysis (5th ed.), Boston:Prindle, Weber and Schmidt,ISBN 0-534-93219-3.
• 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,Bibcode:1962mia..book.....V,LCCN 62-21277.

• Matrices (mathematics)
• Numerical linear algebra
• Relaxation (iterative methods)

• Articles with short description
• Short description matches Wikidata