矩陣分裂

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