數值線性代數 中，矩陣分裂 （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
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.