矩阵分裂

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

正则分裂
解矩阵方程

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

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

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

假设矩阵方程形式为

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

{{NumBlk|:| \mathbf B \mathbf x^{(m+1)} = \mathbf C \mathbf x^{(m)} + \mathbf k, \quad m = 0, 1, 2, \ldots , |}}

其中\mathbf x^{(0)}是任意向量。()可等价地改写为

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

若()表示A的正则分裂，则矩阵\mathbf D=\mathbf B^{-1}\mathbf C的元素非负。

可以证明，若\mathbf A^{-1}\ge \mathbf 0，则\rho (\mathbf D)，其中\rho (\mathbf D)表示D的谱半径，因此D是收敛矩阵。于是，迭代法()必然收敛。

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

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

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

雅可比法可表为

{{NumBlk|:| \mathbf x^{(m+1)} = \mathbf D^{-1}(\mathbf U + \mathbf L)\mathbf x^{(m)} + \mathbf D^{-1}\mathbf k. |}}

高斯-赛德尔迭代可表为
{{NumBlk|:| \mathbf x^{(m+1)} = (\mathbf D - \mathbf L)^{-1}\mathbf U \mathbf x^{(m)} + (\mathbf D - \mathbf L)^{-1}\mathbf k.

迭代法()应用于()，形式为
{{NumBlk|:| \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|}}

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

雅可比法
雅可比法()与上面演示的正则分裂()相同。

高斯-赛德尔法
由于()中矩阵A的对角项均非零，可以用分裂()表示A，其中

{{NumBlk|:|
\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}.
|}}

则有

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

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

将高斯-赛德尔法()应用于()有如下格式

{{NumBlk|:| \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|}}

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

逐次超松弛迭代法
置\omega=1.1。由分裂()，有

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

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

:\begin{align}
& \mathbf{\omega (D-\omega L)^{-1}k} = \frac{1}{12} \begin{pmatrix}
11 \\
-36.575 \\
25.6135
\end{pmatrix}.
\end{align}

将SOR法()应用于()，则有

{{NumBlk|:| \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|}}

以\mathbf x^{(0)}=(0.0,\ 0.0,\ 0.0)^T为初向量，列出()的前几次迭代。可见SOR法收敛到解()，比GS法略快。

另见
*矩阵分解
*
*

注释
参考文献

• .

*

• .