# Matrix splitting

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Matrix_splitting
> Markdown URL: https://mediated.wiki/source/Matrix_splitting.md
> Source: https://en.wikipedia.org/wiki/Matrix_splitting
> Source revision: 1296012803
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Representation of a matrix as a sum}}
In the [mathematical](/source/mathematics) discipline of [numerical linear algebra](/source/numerical_linear_algebra), a  '''matrix splitting''' is an expression which represents a given [matrix](/source/matrix_(mathematics)) as a sum or difference of matrices.  Many [iterative method](/source/iterative_method)s (for example, for systems of  [differential equation](/source/differential_equation)s) depend upon the direct solution of matrix equations involving matrices more general than [tridiagonal matrices](/source/tridiagonal_matrix).  These matrix equations can often be solved directly and efficiently when written as a matrix splitting.  The technique was devised by [Richard S. Varga](/source/Richard_S._Varga) in 1960.<ref>{{harvtxt|Varga|1960}}</ref>

==Regular splittings==
We seek to solve the [matrix equation](/source/Matrix_(mathematics))

{{NumBlk|:|<math> \mathbf A \mathbf x = \mathbf k,  </math>|{{EquationRef|1}}}}

where '''A''' is a given ''n'' × ''n'' [non-singular](/source/invertible_matrix) matrix, and '''k''' is a given [column vector](/source/column_vector) with ''n'' components.  We split the matrix '''A''' into

{{NumBlk|:|<math> \mathbf A = \mathbf B - \mathbf C, </math>|{{EquationRef|2}}}}

where '''B''' and '''C''' are ''n'' × ''n'' matrices.  If, for an arbitrary ''n'' × ''n'' matrix '''M''', '''M''' has nonnegative entries, we write '''M''' &ge; '''0'''.  If '''M''' has only positive entries, we write '''M''' &gt; '''0'''.  Similarly, if the matrix '''M'''<sub>1</sub> &minus; '''M'''<sub>2</sub> has nonnegative entries, we write '''M'''<sub>1</sub> &ge; '''M'''<sub>2</sub>.

Definition:  '''A''' = '''B''' &minus; '''C''' is a '''regular splitting of A''' if '''B'''<sup>&minus;1</sup> &ge; '''0''' and '''C''' &ge; '''0'''.

We assume that matrix equations of the form

{{NumBlk|:|<math> \mathbf B \mathbf x = \mathbf g,  </math>|{{EquationRef|3}}}}

where '''g''' is a given column vector, can be solved directly for the vector '''x'''.  If ({{EquationNote|2}}) represents a regular splitting of '''A''', then the iterative method

{{NumBlk|:|<math> \mathbf B \mathbf x^{(m+1)} = \mathbf C \mathbf x^{(m)} + \mathbf k, \quad m = 0, 1, 2, \ldots ,  </math>|{{EquationRef|4}}}}

where '''x'''<sup>(0)</sup> is an arbitrary vector, can be carried out.  Equivalently, we write ({{EquationNote|4}}) in the form

{{NumBlk|:|<math> \mathbf x^{(m+1)} = \mathbf B^{-1} \mathbf C \mathbf x^{(m)} + \mathbf B^{-1} \mathbf k, \quad m = 0, 1, 2, \ldots  </math>|{{EquationRef|5}}}}

The matrix '''D''' = '''B'''<sup>&minus;1</sup>'''C''' has nonnegative entries if ({{EquationNote|2}}) represents a regular splitting of '''A'''.<ref>{{harvtxt|Varga|1960|pp=121–122}}</ref>

It can be shown that if '''A'''<sup>&minus;1</sup> &gt; '''0''', then <math>\rho (\mathbf D)</math> < 1, where <math>\rho (\mathbf D)</math> represents the [spectral radius](/source/spectral_radius) of '''D''', and thus '''D''' is a [convergent matrix](/source/convergent_matrix).  As a consequence, the iterative method ({{EquationNote|5}}) is necessarily [convergent](/source/Jacobi_method).<ref>{{harvtxt|Varga|1960|pp=122–123}}</ref><ref>{{harvtxt|Varga|1962|p=89}}</ref>

If, in addition, the splitting ({{EquationNote|2}}) is chosen so that the matrix '''B''' is a [diagonal matrix](/source/diagonal_matrix) (with the diagonal entries all non-zero, since '''B''' must be [invertible](/source/Invertible_matrix)), then '''B''' can be inverted in linear time (see [Time complexity](/source/Time_complexity)).

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

{{NumBlk|:|<math> \mathbf A = \mathbf D - \mathbf U - \mathbf L, </math>|{{EquationRef|6}}}}

where '''D''' is the diagonal part of '''A''', and '''U''' and '''L''' are respectively strictly upper and lower [triangular](/source/triangular_matrix) ''n'' × ''n'' matrices, then we have the following.

The [Jacobi method](/source/Jacobi_method) can be represented in matrix form as a splitting

{{NumBlk|:|<math> \mathbf x^{(m+1)} = \mathbf D^{-1}(\mathbf U + \mathbf L)\mathbf x^{(m)} + \mathbf D^{-1}\mathbf k. </math><ref>{{harvtxt|Burden|Faires|1993|p=408}}</ref><ref>{{harvtxt|Varga|1962|p=88}}</ref>|{{EquationRef|7}}}}

The [Gauss–Seidel method](/source/Gauss%E2%80%93Seidel_method) can be represented in matrix form as a splitting
{{NumBlk|:|<math> \mathbf x^{(m+1)} = (\mathbf D - \mathbf L)^{-1}\mathbf U \mathbf x^{(m)} + (\mathbf D - \mathbf L)^{-1}\mathbf k. </math><ref>{{harvtxt|Burden|Faires|1993|p=411}}</ref><ref>{{harvtxt|Varga|1962|p=88}}</ref>|{{EquationRef|8}}}}

The method of [successive over-relaxation](/source/successive_over-relaxation) can be represented in matrix form as a splitting
{{NumBlk|:|<math> \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. </math><ref>{{harvtxt|Burden|Faires|1993|p=416}}</ref><ref>{{harvtxt|Varga|1962|p=88}}</ref>|{{EquationRef|9}}}}

==Example==

===Regular splitting===
In equation ({{EquationNote|1}}), let
{{NumBlk|:|<math>
\mathbf{A} = \begin{pmatrix}
6 & -2 & -3 \\
-1 & 4 & -2 \\
-3 & -1 & 5
\end{pmatrix}, \quad 
\mathbf{k} = \begin{pmatrix}
5 \\
-12 \\
10
\end{pmatrix}.
</math>|{{EquationRef|10}}}}
Let us apply the splitting ({{EquationNote|7}}) which is used in the Jacobi method: we split '''A''' in such a way that '''B''' consists of ''all'' of the diagonal elements of '''A''', and '''C''' consists of ''all'' of the off-diagonal elements of '''A''', negated.  (Of course this is not the only useful way to split a matrix into two matrices.)  We have
{{NumBlk|:|<math>\begin{align}
& \mathbf{B} = \begin{pmatrix}
6 & 0 & 0 \\
0 & 4 & 0 \\
0 & 0 & 5
\end{pmatrix}, \quad \mathbf{C} = \begin{pmatrix}
0 & 2 & 3 \\
1 & 0 & 2 \\
3 & 1 & 0
\end{pmatrix},
\end{align}</math>|{{EquationRef|11}}}}
:<math>\begin{align}
& \mathbf{A^{-1}} = \frac{1}{47} \begin{pmatrix}
18 & 13 & 16 \\
11 & 21 & 15 \\
13 & 12 & 22
\end{pmatrix}, \quad \mathbf{B^{-1}} = \begin{pmatrix}
\frac{1}{6} & 0 & 0 \\[4pt]
0 & \frac{1}{4} & 0 \\[4pt]
0 & 0 & \frac{1}{5}
\end{pmatrix},
\end{align}</math>
:<math>\begin{align}
\mathbf{D} = \mathbf{B^{-1}C} = \begin{pmatrix}
0 & \frac{1}{3} & \frac{1}{2} \\[4pt]
\frac{1}{4} & 0 & \frac{1}{2} \\[4pt]
\frac{3}{5} & \frac{1}{5} & 0
\end{pmatrix}, \quad \mathbf{B^{-1}k} = \begin{pmatrix}
\frac{5}{6} \\[4pt]
-3 \\[4pt]
2
\end{pmatrix}.
\end{align}</math>
Since '''B'''<sup>&minus;1</sup> &ge; '''0''' and '''C''' &ge; '''0''', the splitting ({{EquationNote|11}}) is a regular splitting.  Since '''A'''<sup>&minus;1</sup> &gt; '''0''', the spectral radius  <math>\rho (\mathbf D)</math> < 1.  (The approximate [eigenvalues](/source/eigenvalues) of '''D''' are <math>\lambda_i \approx -0.4599820, -0.3397859, 0.7997679.</math>)   Hence, the matrix '''D''' is convergent and the method ({{EquationNote|5}}) necessarily converges for the problem ({{EquationNote|10}}).  Note that the diagonal elements of '''A''' are all greater than zero, the off-diagonal elements of '''A''' are all less than zero and '''A''' is [strictly diagonally dominant](/source/strictly_diagonally_dominant).<ref>{{harvtxt|Burden|Faires|1993|p=371}}</ref>

The method ({{EquationNote|5}}) applied to the problem ({{EquationNote|10}}) then takes the form
{{NumBlk|:|<math> \mathbf x^{(m+1)} =
\begin{pmatrix}
0 & \frac{1}{3} & \frac{1}{2} \\[4pt]
\frac{1}{4} & 0 & \frac{1}{2} \\[4pt]
\frac{3}{5} & \frac{1}{5} & 0
\end{pmatrix}
\mathbf x^{(m)} +
\begin{pmatrix}
\frac{5}{6} \\[4pt]
-3 \\[4pt]
2
\end{pmatrix},
\quad m = 0, 1, 2, \ldots</math>|{{EquationRef|12}}}}

The exact solution to equation ({{EquationNote|12}}) is
{{NumBlk|:|<math>
\mathbf{x} = \begin{pmatrix}
2 \\
-1 \\
3
\end{pmatrix}.
</math>|{{EquationRef|13}}}}
The first few iterates for equation ({{EquationNote|12}}) are listed in the table below, beginning with {{math|1='''x'''<sup>(0)</sup> = (0.0, 0.0, 0.0)<sup>T</sup>}}.  From the table one can see that the method is evidently converging to the solution ({{EquationNote|13}}), albeit rather slowly.

{| class="wikitable" border="1"
|-
! <math>x^{(m)}_1</math>
! <math>x^{(m)}_2</math>
! <math>x^{(m)}_3</math>
|-
| 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
|}

===Jacobi method===
As stated above, the Jacobi method ({{EquationNote|7}}) is the same as the specific regular splitting ({{EquationNote|11}}) demonstrated above.

===Gauss–Seidel method===
Since the diagonal entries of the matrix '''A''' in problem ({{EquationNote|10}}) are all nonzero, we can express the matrix '''A''' as the splitting ({{EquationNote|6}}), where

{{NumBlk|:|<math>
\mathbf{D} = \begin{pmatrix}
6 & 0 & 0 \\
0 & 4 & 0 \\
0 & 0 & 5
\end{pmatrix}, \quad \mathbf{U} = \begin{pmatrix}
0 & 2 & 3 \\
0 & 0 & 2 \\
0 & 0 & 0
\end{pmatrix}, \quad \mathbf{L} = \begin{pmatrix}
0 & 0 & 0 \\
1 & 0 & 0 \\
3 & 1 & 0
\end{pmatrix}.
</math>|{{EquationRef|14}}}}

We then have

:<math>\begin{align}
& \mathbf{(D-L)^{-1}} = \frac{1}{120} \begin{pmatrix}
20 & 0 & 0 \\
5 & 30 & 0 \\
13 & 6 & 24
\end{pmatrix},
\end{align}</math>

:<math>\begin{align}
& \mathbf{(D-L)^{-1}U} = \frac{1}{120} \begin{pmatrix}
0 & 40 & 60 \\
0 & 10 & 75 \\
0 & 26 & 51
\end{pmatrix}, \quad \mathbf{(D-L)^{-1}k} = \frac{1}{120} \begin{pmatrix}
100 \\
-335 \\
233
\end{pmatrix}.
\end{align}</math>

The Gauss–Seidel method ({{EquationNote|8}}) applied to the problem ({{EquationNote|10}}) takes the form

{{NumBlk|:|<math> \mathbf x^{(m+1)} =
\frac{1}{120} \begin{pmatrix}
0 & 40 & 60 \\
0 & 10 & 75 \\
0 & 26 & 51
\end{pmatrix}
\mathbf x^{(m)} +
\frac{1}{120} \begin{pmatrix}
100 \\
-335 \\
233
\end{pmatrix},
\quad m = 0, 1, 2, \ldots</math>|{{EquationRef|15}}}}

The first few iterates for equation ({{EquationNote|15}}) are listed in the table below, beginning with {{math|1='''x'''<sup>(0)</sup> = (0.0, 0.0, 0.0)<sup>T</sup>}}.  From the table one can see that the method is evidently converging to the solution ({{EquationNote|13}}), somewhat faster than the Jacobi method described above.

{| class="wikitable" border="1"
|-
! <math>x^{(m)}_1</math>
! <math>x^{(m)}_2</math>
! <math>x^{(m)}_3</math>
|-
| 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
|}

===Successive over-relaxation method===
Let ''ω'' = 1.1.  Using the splitting ({{EquationNote|14}}) of the matrix '''A''' in problem ({{EquationNote|10}}) for the successive over-relaxation method, we have

<!-- (D – wL)–1 -->
:<math>\begin{align}
& \mathbf{(D-\omega L)^{-1}} = \frac{1}{12} \begin{pmatrix}
2 & 0 & 0 \\
0.55 & 3 & 0 \\
1.441 & 0.66 & 2.4
\end{pmatrix},
\end{align}</math>

<!-- (D – wL)–1[(1 – w)D + wU] -->
:<math>\begin{align}
& \mathbf{(D-\omega L)^{-1}[(1-\omega )D+\omega U]} = \frac{1}{12} \begin{pmatrix}
-1.2 & 4.4 & 6.6 \\
-0.33 & 0.01 & 8.415 \\
-0.8646 & 2.9062 & 5.0073
\end{pmatrix},
\end{align}</math>

<!-- w(D – wL)–1k -->
:<math>\begin{align}
& \mathbf{\omega (D-\omega L)^{-1}k} = \frac{1}{12} \begin{pmatrix}
11 \\
-36.575 \\
25.6135
\end{pmatrix}.
\end{align}</math>

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

{{NumBlk|:|<math> \mathbf x^{(m+1)} =
\frac{1}{12} \begin{pmatrix}
-1.2 & 4.4 & 6.6 \\
-0.33 & 0.01 & 8.415 \\
-0.8646 & 2.9062 & 5.0073
\end{pmatrix}
\mathbf x^{(m)} +
\frac{1}{12} \begin{pmatrix}
11 \\
-36.575 \\
25.6135
\end{pmatrix},
\quad m = 0, 1, 2, \ldots</math>|{{EquationRef|16}}}}

The first few iterates for equation ({{EquationNote|16}}) are listed in the table below, beginning with {{math|1='''x'''<sup>(0)</sup> = (0.0, 0.0, 0.0)<sup>T</sup>}}.  From the table one can see that the method is evidently converging to the solution ({{EquationNote|13}}), slightly faster than the Gauss–Seidel method described above.

{| class="wikitable" border="1"
|-
! <math>x^{(m)}_1</math>
! <math>x^{(m)}_2</math>
! <math>x^{(m)}_3</math>
|-
| 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
|}

==See also==
*[List of operator splitting topics](/source/List_of_operator_splitting_topics)
*[Matrix decomposition](/source/Matrix_decomposition)
*[M-matrix](/source/M-matrix)
*[Stieltjes matrix](/source/Stieltjes_matrix)

==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](/source/Prindle%2C_Weber_and_Schmidt) | location = Boston | url-access = registration | url = https://archive.org/details/numericalanalysi00burd }}.
* {{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](/source/University_of_Wisconsin_Press) | location = Madison | pages = 121&ndash;142 | year = 1960 | lccn = 60-60003 }}
* {{citation | first1 = Richard S. | last1 = Varga | title = Matrix Iterative Analysis | publisher = [Prentice-Hall](/source/Prentice-Hall) | location = New Jersey | year = 1962 | bibcode = 1962mia..book.....V | lccn = 62-21277}}.

{{Numerical linear algebra}}
{{Authority control}}

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

---
Adapted from the Wikipedia article [Matrix splitting](https://en.wikipedia.org/wiki/Matrix_splitting) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Matrix_splitting?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.