矩阵分裂

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

正则分裂

解矩阵方程 Template:NumBlk

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

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

定义： 若${𝐁}^{-1}\ge 0,𝐂\ge \mathrm{𝟎}$，则$𝐀=𝐁-𝐂$是A的一个正则分裂（regular splitting）。

假设矩阵方程形式为

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

其中${𝐱}^{(0)}$是任意向量。(Template:EquationNote)可等价地改写为

若(Template:EquationNote)表示A的正则分裂，则矩阵$𝐃={𝐁}^{-1}𝐂$的元素非负。

可以证明，若${𝐀}^{-1}\ge \mathrm{𝟎}$，则$\rho (𝐃)<1$，其中$\rho (𝐃)$表示D的谱半径，因此D是收敛矩阵。于是，迭代法(Template:EquationNote)必然收敛。

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

矩阵迭代法

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

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

雅可比法可表为

高斯-赛德尔迭代可表为 Template:NumBlk

逐次超松弛迭代法可表为 Template:NumBlk

例子

正则分裂

方程(Template:EquationNote)中，令 Template:NumBlk 应用雅可比中的分裂(Template:EquationNote)：将A分裂，使B包含A的所有对角元素，C包含A的所有对角线外元素并取负（当然这不是将矩阵分裂为两矩阵的唯一有效方法），则有 Template:NumBlk

$\begin{array}{cc}& {𝐀}^{\mathbf{-}\mathrm{𝟏}}=\frac{1}{47}\left(\begin{array}{ccc}18& 13& 16\\ 11& 21& 15\\ 13& 12& 22\end{array}\right),{𝐁}^{\mathbf{-}\mathrm{𝟏}}=\left(\begin{array}{ccc}\frac{1}{6}& 0& 0\\ 0& \frac{1}{4}& 0\\ 0& 0& \frac{1}{5}\end{array}\right),\end{array}$

$\begin{array}{c}𝐃={𝐁}^{\mathbf{-}\mathrm{𝟏}}𝐂=\left(\begin{array}{ccc}0& \frac{1}{3}& \frac{1}{2}\\ \frac{1}{4}& 0& \frac{1}{2}\\ \frac{3}{5}& \frac{1}{5}& 0\end{array}\right),{𝐁}^{\mathbf{-}\mathrm{𝟏}}𝐤=\left(\begin{array}{c}\frac{5}{6}\\ -3\\ 2\end{array}\right).\end{array}$

由于${𝐁}^{-1}\ge \mathrm{𝟎},𝐂\ge \mathrm{𝟎}$，分裂(Template:EquationNote)是正则分裂。由于${𝐀}^{-1}>\mathrm{𝟎}$，谱半径$\rho (𝐃)<1$（D的近似特征值是${\lambda }_i\approx -0.4599820,-0.3397859,0.7997679$）。因此D收敛，迭代法(Template:EquationNote)对(Template:EquationNote)收敛。注意A的对角元均大于零，非对角元均小于零，且A是强对角占优矩阵。

迭代法(Template:EquationNote)应用于(Template:EquationNote)，形式为 Template:NumBlk

(Template:EquationNote)的精确解为 Template:NumBlk 以${𝐱}^{(0)}=(0.0,0.0,0.0{)}^T$为初向量，列出(Template:EquationNote)的前几次迭代。可见此方法明显收敛到解(Template:EquationNote)，不过速度相当缓慢。

$x_1^{(m)}$	$x_2^{(m)}$	$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

雅可比法

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

高斯-赛德尔法

由于(Template:EquationNote)中矩阵A的对角项均非零，可以用分裂(Template:EquationNote)表示A，其中

则有

$\begin{array}{cc}& \mathbf{(}𝐃\mathbf{-}𝐋{\mathbf{)}}^{\mathbf{-}\mathrm{𝟏}}=\frac{1}{120}\left(\begin{array}{ccc}20& 0& 0\\ 5& 30& 0\\ 13& 6& 24\end{array}\right),\end{array}$

$\begin{array}{cc}& \mathbf{(}𝐃\mathbf{-}𝐋{\mathbf{)}}^{\mathbf{-}\mathrm{𝟏}}𝐔=\frac{1}{120}\left(\begin{array}{ccc}0& 40& 60\\ 0& 10& 75\\ 0& 26& 51\end{array}\right),\mathbf{(}𝐃\mathbf{-}𝐋{\mathbf{)}}^{\mathbf{-}\mathrm{𝟏}}𝐤=\frac{1}{120}\left(\begin{array}{c}100\\ -335\\ 233\end{array}\right).\end{array}$

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

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

$x_1^{(m)}$	$x_2^{(m)}$	$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

逐次超松弛迭代法

置$\omega =1.1$。由分裂(Template:EquationNote)，有

$\begin{array}{cc}& \mathbf{(}𝐃\mathbf{-}\mathit{\omega }𝐋{\mathbf{)}}^{\mathbf{-}\mathrm{𝟏}}=\frac{1}{12}\left(\begin{array}{ccc}2& 0& 0\\ 0.55& 3& 0\\ 1.441& 0.66& 2.4\end{array}\right),\end{array}$

$\begin{array}{cc}& \mathbf{(}𝐃\mathbf{-}\mathit{\omega }𝐋{\mathbf{)}}^{\mathbf{-}\mathrm{𝟏}}\mathbf{[}\mathbf{(}\mathrm{𝟏}\mathbf{-}\mathit{\omega }\mathbf{)}𝐃\mathbf{+}\mathit{\omega }𝐔\mathbf{]}=\frac{1}{12}\left(\begin{array}{ccc}-1.2& 4.4& 6.6\\ -0.33& 0.01& 8.415\\ -0.8646& 2.9062& 5.0073\end{array}\right),\end{array}$

$\begin{array}{cc}& \mathit{\omega }\mathbf{(}𝐃\mathbf{-}\mathit{\omega }𝐋{\mathbf{)}}^{\mathbf{-}\mathrm{𝟏}}𝐤=\frac{1}{12}\left(\begin{array}{c}11\\ -36.575\\ 25.6135\end{array}\right).\end{array}$

将SOR法(Template:EquationNote)应用于(Template:EquationNote)，则有

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

$x_1^{(m)}$	$x_2^{(m)}$	$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

另见

• 矩阵分解
• Template:Le
• Template:Le

参考文献

• Template:Citation.
• Template:Cite book
• Template:Citation.