矩阵分裂

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

## 正则分裂

解矩阵方程$$\mathbf A \mathbf x = \mathbf k,$$

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

$$\mathbf A = \mathbf B - \mathbf C,$$

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）。

假设矩阵方程形式为

$$\mathbf B \mathbf x = \mathbf g,$$

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

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

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

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

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

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

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

## 矩阵迭代法

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

$$\mathbf A = \mathbf D - \mathbf U - \mathbf L,$$

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

雅可比法可表为

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

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

逐次超松弛迭代法可表为$\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.$

## 例子

### 正则分裂

方程(1)中，令$$\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}.$$ 应用雅可比中的分裂(7)：将A分裂，使B包含A的所有对角元素，C包含A的所有对角线外元素并取负（当然这不是将矩阵分裂为两矩阵的唯一有效方法），则有$$\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}$$

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

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

由于$\mathbf B^{-1}\ge \mathbf 0,\ \mathbf C\ge \mathbf 0$，分裂(11)是正则分裂。由于$\mathbf A^{-1}> \mathbf 0$，谱半径$\rho (\mathbf D)<1$（D的近似特征值是$\lambda_i \approx -0.4599820, -0.3397859, 0.7997679$）。因此D收敛，迭代法(5)对(10)收敛。注意A的对角元均大于零，非对角元均小于零，且A是强对角占优矩阵。

迭代法(5)应用于(10)，形式为$$\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)的精确解为$$\mathbf{x} = \begin{pmatrix} 2 \\ -1 \\ 3 \end{pmatrix}.$$ 以$\mathbf x^{(0)}=(0.0,\ 0.0,\ 0.0)^T$为初向量，列出(12)的前几次迭代。可见此方法明显收敛到解(13)，不过速度相当缓慢。

$x^{(m)}_1$｜$x^{(m)}_2$｜$x^{(m)}_3$

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，其中

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

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

$$\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$为初向量，列出(15)的前几次迭代。可见方法明显收敛到解(13)，且比雅可比法快。

$x^{(m)}_1$｜$x^{(m)}_2$｜$x^{(m)}_3$

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

### 逐次超松弛迭代法

置$\omega=1.1$。由分裂(14)，有

$$\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法(9)应用于(10)，则有

$$\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$为初向量，列出(16)的前几次迭代。可见SOR法收敛到解(13)，比GS法略快。

$x^{(m)}_1$｜$x^{(m)}_2$｜$x^{(m)}_3$

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