矩阵分裂

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

正则分裂

解矩阵方程

  1

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

  2

BC都是n阶方阵。对元素非负的任意n阶方阵M,可以记作 。若M元素均为正数,可以记作 。相似地,若 的元素非负,可以记作 

定义: 若 ,则 A的一个正则分裂regular splitting)。

假设矩阵方程形式为

  3

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

  4

其中 是任意向量。(4)可等价地改写为

  5

若(2)表示A的正则分裂,则矩阵 的元素非负。[2]

可以证明,若 ,则 ,其中 表示D谱半径,因此D收敛矩阵。于是,迭代法(5)必然收敛。[3][4]

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

矩阵迭代法

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

  6

其中DA的主对角线元素构成的对角矩阵,UL分别是n阶严格上、下三角矩阵,则有:

雅可比法可表为

 [5][6] 7

高斯-赛德尔迭代可表为

 [7][8] 8

逐次超松弛迭代法可表为

 [9][10] 9

例子

正则分裂

方程(1)中,令

  10

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

  11
 
 

由于 ,分裂(11)是正则分裂。由于 ,谱半径 D的近似特征值 )。因此D收敛,迭代法(5)对(10)收敛。注意A的对角元均大于零,非对角元均小于零,且A是强对角占优矩阵[11]

迭代法(5)应用于(10),形式为

  12

(12)的精确解为

  13

 为初向量,列出(12)的前几次迭代。可见此方法明显收敛到解(13),不过速度相当缓慢。

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

  14

则有

 
 

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

  15

 为初向量,列出(15)的前几次迭代。可见方法明显收敛到解(13),且比雅可比法快。

     
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

逐次超松弛迭代法

 。由分裂(14),有

 
 
 

将SOR法(9)应用于(10),则有

  16

 为初向量,列出(16)的前几次迭代。可见SOR法收敛到解(13),比GS法略快。

     
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

另见

注释

  1. ^ Varga (1960)
  2. ^ Varga (1960,第121–122頁)
  3. ^ Varga (1960,第122–123頁)
  4. ^ Varga (1962,第89頁)
  5. ^ Burden & Faires (1993,第408頁)
  6. ^ Varga (1962,第88頁)
  7. ^ Burden & Faires (1993,第411頁)
  8. ^ Varga (1962,第88頁)
  9. ^ Burden & Faires (1993,第416頁)
  10. ^ Varga (1962,第88頁)
  11. ^ Burden & Faires (1993,第371頁)

参考文献