数值线性代数 中，矩阵分裂 （matrix splitting ）是一种将给定矩阵 表为多个矩阵和或差的表示。很多迭代法 （如解微分方程组 的）都依赖于直接求解比三对角矩阵 更一般的矩阵的方程，若将其分裂，通常可以更高效地求解。这项技术由Richard S. Varga（1960）发明。[1]
解矩阵方程
A
x
=
k
,
{\displaystyle \mathbf {A} \mathbf {x} =\mathbf {k} ,}
1
其中A 是给定n 阶非奇异方阵 ，k 是给定n 元列向量 。A 可分裂为
A
=
B
−
C
,
{\displaystyle \mathbf {A} =\mathbf {B} -\mathbf {C} ,}
2
B 、C 都是n 阶方阵。对元素非负的任意n 阶方阵M ，可以记作
M
≥
0
{\displaystyle \mathbf {M} \geq \mathbf {0} }
M 元素均为正数，可以记作
M
>
0
{\displaystyle \mathbf {M} >\mathbf {0} }
M
1
−
M
2
{\displaystyle \mathbf {M} _{1}-\mathbf {M} _{2}}
M
1
≥
M
2
{\displaystyle \mathbf {M} _{1}\geq \mathbf {M} _{2}}
定义： 若
B
−
1
≥
0
,
C
≥
0
{\displaystyle \mathbf {B} ^{-1}\geq 0,\ \mathbf {C} \geq \mathbf {0} }
A
=
B
−
C
{\displaystyle \mathbf {A} =\mathbf {B} -\mathbf {C} }
A的一个正则分裂 （regular splitting ）。
假设矩阵方程形式为
B
x
=
g
,
{\displaystyle \mathbf {B} \mathbf {x} =\mathbf {g} ,}
3
其中g 是给定列向量，可直接求解x 。若(2 A 的正则分裂，则迭代法
B
x
(
m
+
1
)
=
C
x
(
m
)
+
k
,
m
=
0
,
1
,
2
,
…
,
{\displaystyle \mathbf {B} \mathbf {x} ^{(m+1)}=\mathbf {C} \mathbf {x} ^{(m)}+\mathbf {k} ,\quad m=0,1,2,\ldots ,}
4
其中
x
(
0
)
{\displaystyle \mathbf {x} ^{(0)}}
4
x
(
m
+
1
)
=
B
−
1
C
x
(
m
)
+
B
−
1
k
,
m
=
0
,
1
,
2
,
…
{\displaystyle \mathbf {x} ^{(m+1)}=\mathbf {B} ^{-1}\mathbf {C} \mathbf {x} ^{(m)}+\mathbf {B} ^{-1}\mathbf {k} ,\quad m=0,1,2,\ldots }
5
若(2 A 的正则分裂，则矩阵
D
=
B
−
1
C
{\displaystyle \mathbf {D} =\mathbf {B} ^{-1}\mathbf {C} }
[2]
可以证明，若
A
−
1
≥
0
{\displaystyle \mathbf {A} ^{-1}\geq \mathbf {0} }
ρ
(
D
)
<
1
{\displaystyle \rho (\mathbf {D} )<1}
ρ
(
D
)
{\displaystyle \rho (\mathbf {D} )}
D 的谱半径 ，因此D 是收敛矩阵 。于是，迭代法(5 [3] [4]
此外，若选择分裂(2 B 是对角矩阵 （由于B 可逆，所以对角项全部不为零），则B 可在线性时间内求得逆（见时间复杂度 ）。
很多迭代法都可描述为矩阵分裂。若A 的对角项都是非零的，且A 表为矩阵和
A
=
D
−
U
−
L
,
{\displaystyle \mathbf {A} =\mathbf {D} -\mathbf {U} -\mathbf {L} ,}
6
其中D 是A 的主对角线元素构成的对角矩阵，U 、L 分别是n 阶严格上、下三角矩阵 ，则有：
雅可比法 可表为
x
(
m
+
1
)
=
D
−
1
(
U
+
L
)
x
(
m
)
+
D
−
1
k
.
{\displaystyle \mathbf {x} ^{(m+1)}=\mathbf {D} ^{-1}(\mathbf {U} +\mathbf {L} )\mathbf {x} ^{(m)}+\mathbf {D} ^{-1}\mathbf {k} .}
[5] [6] 7
高斯-赛德尔迭代 可表为
x
(
m
+
1
)
=
(
D
−
L
)
−
1
U
x
(
m
)
+
(
D
−
L
)
−
1
k
.
{\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
逐次超松弛迭代法 可表为
x
(
m
+
1
)
=
(
D
−
ω
L
)
−
1
[
(
1
−
ω
)
D
+
ω
U
]
x
(
m
)
+
ω
(
D
−
ω
L
)
−
1
k
.
{\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
方程(1
A
=
(
6
−
2
−
3
−
1
4
−
2
−
3
−
1
5
)
,
k
=
(
5
−
12
10
)
.
{\displaystyle \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}}.}
10
应用雅可比中的分裂(7 A 分裂，使B 包含A 的所有对角元素，C 包含A 的所有对角线外元素并取负（当然这不是将矩阵分裂为两矩阵的唯一有效方法），则有
B
=
(
6
0
0
0
4
0
0
0
5
)
,
C
=
(
0
2
3
1
0
2
3
1
0
)
,
{\displaystyle {\begin{aligned}&\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{aligned}}}
11
A
−
1
=
1
47
(
18
13
16
11
21
15
13
12
22
)
,
B
−
1
=
(
1
6
0
0
0
1
4
0
0
0
1
5
)
,
{\displaystyle {\begin{aligned}&\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{aligned}}}
D
=
B
−
1
C
=
(
0
1
3
1
2
1
4
0
1
2
3
5
1
5
0
)
,
B
−
1
k
=
(
5
6
−
3
2
)
.
{\displaystyle {\begin{aligned}\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{aligned}}}
由于
B
−
1
≥
0
,
C
≥
0
{\displaystyle \mathbf {B} ^{-1}\geq \mathbf {0} ,\ \mathbf {C} \geq \mathbf {0} }
11
A
−
1
>
0
{\displaystyle \mathbf {A} ^{-1}>\mathbf {0} }
ρ
(
D
)
<
1
{\displaystyle \rho (\mathbf {D} )<1}
D 的近似特征值 是
λ
i
≈
−
0.4599820
,
−
0.3397859
,
0.7997679
{\displaystyle \lambda _{i}\approx -0.4599820,-0.3397859,0.7997679}
D 收敛，迭代法(5 10 A 的对角元均大于零，非对角元均小于零，且A 是强对角占优矩阵 。[11]
迭代法(5 10
x
(
m
+
1
)
=
(
0
1
3
1
2
1
4
0
1
2
3
5
1
5
0
)
x
(
m
)
+
(
5
6
−
3
2
)
,
m
=
0
,
1
,
2
,
…
{\displaystyle \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 }
12
(12
x
=
(
2
−
1
3
)
.
{\displaystyle \mathbf {x} ={\begin{pmatrix}2\\-1\\3\end{pmatrix}}.}
13
以
x
(
0
)
=
(
0.0
,
0.0
,
0.0
)
T
{\displaystyle \mathbf {x} ^{(0)}=(0.0,\ 0.0,\ 0.0)^{T}}
12 13
x
1
(
m
)
{\displaystyle x_{1}^{(m)}}
x
2
(
m
)
{\displaystyle x_{2}^{(m)}}
x
3
(
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
雅可比法(7 11
由于(10 A 的对角项均非零，可以用分裂(6 A ，其中
D
=
(
6
0
0
0
4
0
0
0
5
)
,
U
=
(
0
2
3
0
0
2
0
0
0
)
,
L
=
(
0
0
0
1
0
0
3
1
0
)
.
{\displaystyle \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}}.}
14
则有
(
D
−
L
)
−
1
=
1
120
(
20
0
0
5
30
0
13
6
24
)
,
{\displaystyle {\begin{aligned}&\mathbf {(D-L)^{-1}} ={\frac {1}{120}}{\begin{pmatrix}20&0&0\\5&30&0\\13&6&24\end{pmatrix}},\end{aligned}}}
(
D
−
L
)
−
1
U
=
1
120
(
0
40
60
0
10
75
0
26
51
)
,
(
D
−
L
)
−
1
k
=
1
120
(
100
−
335
233
)
.
{\displaystyle {\begin{aligned}&\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{aligned}}}
将高斯-赛德尔法(8 10
x
(
m
+
1
)
=
1
120
(
0
40
60
0
10
75
0
26
51
)
x
(
m
)
+
1
120
(
100
−
335
233
)
,
m
=
0
,
1
,
2
,
…
{\displaystyle \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 }
15
以
x
(
0
)
=
(
0.0
,
0.0
,
0.0
)
T
{\displaystyle \mathbf {x} ^{(0)}=(0.0,\ 0.0,\ 0.0)^{T}}
15 13
x
1
(
m
)
{\displaystyle x_{1}^{(m)}}
x
2
(
m
)
{\displaystyle x_{2}^{(m)}}
x
3
(
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
置
ω
=
1.1
{\displaystyle \omega =1.1}
14
(
D
−
ω
L
)
−
1
=
1
12
(
2
0
0
0.55
3
0
1.441
0.66
2.4
)
,
{\displaystyle {\begin{aligned}&\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{aligned}}}
(
D
−
ω
L
)
−
1
[
(
1
−
ω
)
D
+
ω
U
]
=
1
12
(
−
1.2
4.4
6.6
−
0.33
0.01
8.415
−
0.8646
2.9062
5.0073
)
,
{\displaystyle {\begin{aligned}&\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{aligned}}}
ω
(
D
−
ω
L
)
−
1
k
=
1
12
(
11
−
36.575
25.6135
)
.
{\displaystyle {\begin{aligned}&\mathbf {\omega (D-\omega L)^{-1}k} ={\frac {1}{12}}{\begin{pmatrix}11\\-36.575\\25.6135\end{pmatrix}}.\end{aligned}}}
将SOR法(9 10
x
(
m
+
1
)
=
1
12
(
−
1.2
4.4
6.6
−
0.33
0.01
8.415
−
0.8646
2.9062
5.0073
)
x
(
m
)
+
1
12
(
11
−
36.575
25.6135
)
,
m
=
0
,
1
,
2
,
…
{\displaystyle \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 }
16
以
x
(
0
)
=
(
0.0
,
0.0
,
0.0
)
T
{\displaystyle \mathbf {x} ^{(0)}=(0.0,\ 0.0,\ 0.0)^{T}}
16 13
x
1
(
m
)
{\displaystyle x_{1}^{(m)}}
x
2
(
m
)
{\displaystyle x_{2}^{(m)}}
x
3
(
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
^ Varga (1960 )^ Varga (1960 , pp. 121–122)^ Varga (1960 , pp. 122–123)^ Varga (1962 , p. 89)^ Burden & Faires (1993 , p. 408)^ Varga (1962 , p. 88)^ Burden & Faires (1993 , p. 411)^ Varga (1962 , p. 88)^ Burden & Faires (1993 , p. 416)^ Varga (1962 , p. 88)^ Burden & Faires (1993 , p. 371)
Burden, Richard L.; Faires, J. Douglas, Numerical Analysis Prindle, Weber and Schmidt , 1993, ISBN 0-534-93219-3 Varga, Richard S. Factorization and Normalized Iterative Methods. Langer, Rudolph E. (编). Boundary Problems in Differential Equations. Madison: University of Wisconsin Press . 1960: 121–142. LCCN 60-60003 Varga, Richard S., Matrix Iterative Analysis, New Jersey: Prentice-Hall , 1962, LCCN 62-21277 
![{\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} .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/60cb521721c2a11d3610e135810d8f37ba75f641)
![{\displaystyle {\begin{aligned}&\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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/706adc9af9b6df209d29700f145a2fe77b29716d)
![{\displaystyle {\begin{aligned}\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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72868cf21551d227e6c81aec2e3e9a2aa388a6b7)
![{\displaystyle \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 }](https://wikimedia.org/api/rest_v1/media/math/render/svg/da7f8e892f3b13ec8b8d7540716706a6814f05e1)
![{\displaystyle {\begin{aligned}&\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{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b70f8eeeae3c92eb5c04cee5525998cf469db09f)
5th, Boston: Prindle, Weber and Schmidt, 1993, ISBN 0-534-93219-3.