查看“︁矩阵分裂”︁的源代码

[[数值线性代数]]中，'''矩阵分裂'''（'''matrix splitting'''）是一种将给定[[矩阵]]表为多个矩阵和或差的表示。很多[[迭代法]]（如解[[微分方程]]组的）都依赖于直接求解比[[三对角矩阵]]更一般的矩阵的方程，若将其分裂，通常可以更高效地求解。这项技术由Richard S. Varga（1960）发明。<ref>{{harvtxt|Varga|1960}}</ref>

==正则分裂==
解矩阵方程
{{NumBlk|:|<math> \mathbf A \mathbf x = \mathbf k,  </math>|{{EquationRef|1}}}}

其中'''A'''是给定''n''阶[[非奇异方阵]]，'''k'''是给定''n''元[[列向量]]。'''A'''可分裂为

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

'''B'''、'''C'''都是''n''阶方阵。对元素非负的任意''n''阶方阵'''M'''，可以记作<math>\mathbf{M}\ge \mathbf{0}</math>。若'''M'''元素均为正数，可以记作<math>\mathbf{M}>\mathbf{0}</math>。相似地，若<math>\mathbf{M}_1-\mathbf{M}_2</math>的元素非负，可以记作<math>\mathbf{M}_1\ge \mathbf{M}_2</math>。

定义： 若<math>\mathbf{B}^{-1}\ge 0,\ \mathbf{C}\ge \mathbf{0}</math>，则<math>\mathbf{A}=\mathbf{B}-\mathbf{C}</math>是'''A的一个正则分裂'''（'''regular splitting'''）。

假设矩阵方程形式为

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

其中'''g'''是给定列向量，可直接求解'''x'''。若({{EquationNote|2}})表示'''A'''的正则分裂，则迭代法

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

其中<math>\mathbf x^{(0)}</math>是任意向量。({{EquationNote|4}})可等价地改写为

{{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}}}}

若({{EquationNote|2}})表示'''A'''的正则分裂，则矩阵<math>\mathbf D=\mathbf B^{-1}\mathbf  C</math>的元素非负。<ref>{{harvtxt|Varga|1960|pp=121–122}}</ref>

可以证明，若<math>\mathbf A^{-1}\ge \mathbf 0</math>，则<math>\rho (\mathbf D)<1</math>，其中<math>\rho (\mathbf D)</math>表示'''D'''的[[谱半径]]，因此'''D'''是[[收敛矩阵]]。于是，迭代法({{EquationNote|5}})必然收敛。<ref>{{harvtxt|Varga|1960|pp=122–123}}</ref><ref>{{harvtxt|Varga|1962|p=89}}</ref>

此外，若选择分裂({{EquationNote|2}})，使'''B'''是[[对角矩阵]]（由于'''B'''可逆，所以对角项全部不为零），则'''B'''可在线性时间内求得逆（见[[时间复杂度]]）。

==矩阵迭代法==
很多迭代法都可描述为矩阵分裂。若'''A'''的对角项都是非零的，且'''A'''表为矩阵和

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

其中'''D'''是'''A'''的主对角线元素构成的对角矩阵，'''U'''、'''L'''分别是''n''阶严格上、下[[三角矩阵]]，则有：

[[雅可比法]]可表为

{{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 name="未命名-20250106100607">{{harvtxt|Varga|1962|p=88}}</ref>|{{EquationRef|7}}}}

[[高斯-赛德尔迭代]]可表为
{{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 name="未命名-20250106100607"/>|{{EquationRef|8}}}}

[[逐次超松弛迭代法]]可表为
{{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 name="未命名-20250106100607"/>|{{EquationRef|9}}}}

==例子==
===正则分裂===
方程({{EquationNote|1}})中，令
{{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}}}}
应用雅可比中的分裂({{EquationNote|7}})：将'''A'''分裂，使'''B'''包含'''A'''的所有对角元素，'''C'''包含'''A'''的所有对角线外元素并取负（当然这不是将矩阵分裂为两矩阵的唯一有效方法），则有
{{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>
由于<math>\mathbf B^{-1}\ge \mathbf 0,\ \mathbf C\ge \mathbf 0</math>，分裂({{EquationNote|11}})是正则分裂。由于<math>\mathbf A^{-1}> \mathbf 0</math>，谱半径<math>\rho (\mathbf D)<1</math>（'''D'''的近似[[特征值]]是<math>\lambda_i \approx -0.4599820, -0.3397859, 0.7997679</math>）。因此'''D'''收敛，迭代法({{EquationNote|5}})对({{EquationNote|10}})收敛。注意'''A'''的对角元均大于零，非对角元均小于零，且'''A'''是强[[对角占优矩阵]]。<ref>{{harvtxt|Burden|Faires|1993|p=371}}</ref>

迭代法({{EquationNote|5}})应用于({{EquationNote|10}})，形式为
{{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}}}}

({{EquationNote|12}})的精确解为
{{NumBlk|:|<math>
\mathbf{x} = \begin{pmatrix}
2 \\
-1 \\
3
\end{pmatrix}.
</math>|{{EquationRef|13}}}}
以<math>\mathbf x^{(0)}=(0.0,\ 0.0,\ 0.0)^T</math>为初向量，列出({{EquationNote|12}})的前几次迭代。可见此方法明显收敛到解({{EquationNote|13}})，不过速度相当缓慢。

{| 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
|}

===雅可比法===
雅可比法({{EquationNote|7}})与上面演示的正则分裂({{EquationNote|11}})相同。

===高斯-赛德尔法===
由于({{EquationNote|10}})中矩阵'''A'''的对角项均非零，可以用分裂({{EquationNote|6}})表示'''A'''，其中

{{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}}}}

则有

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

将高斯-赛德尔法({{EquationNote|8}})应用于({{EquationNote|10}})有如下格式

{{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}}}}

以<math>\mathbf x^{(0)}=(0.0,\ 0.0,\ 0.0)^T</math>为初向量，列出({{EquationNote|15}})的前几次迭代。可见方法明显收敛到解({{EquationNote|13}})，且比雅可比法快。

{| 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
|}

===逐次超松弛迭代法===
置<math>\omega=1.1</math>。由分裂({{EquationNote|14}})，有

<!-- (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>

将SOR法({{EquationNote|9}})应用于({{EquationNote|10}})，则有

{{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}}}}

以<math>\mathbf x^{(0)}=(0.0,\ 0.0,\ 0.0)^T</math>为初向量，列出({{EquationNote|16}})的前几次迭代。可见SOR法收敛到解({{EquationNote|13}})，比GS法略快。
{| 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
|}

==另见==
*[[矩阵分解]]
*{{le|M-矩阵|M-matrix}}
*{{le|斯蒂尔杰斯矩阵|Stieltjes matrix}}

==注释==
{{reflist}}

==参考文献==
* {{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]] | 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 | url = https://archive.org/details/boundaryproblems0000lang | editor1-last = Langer | editor1-first = Rudolph E. | publisher = [[University of Wisconsin Press]] | location = Madison | pages = [https://archive.org/details/boundaryproblems0000lang/page/n134 121]&ndash;142 | year = 1960 | lccn = 60-60003 }}
* {{citation | first1 = Richard S. | last1 = Varga | title = Matrix Iterative Analysis | publisher = [[Prentice-Hall]] | location = New Jersey | year = 1962 | lccn = 62-21277}}.
{{Authority control}}

[[Category:矩阵]]
[[Category:数值线性代数]]