數值線性代數中,矩陣分裂(matrix splitting)是一種將給定矩陣表為多個矩陣和或差的表示。很多迭代法(如解微分方程組的)都依賴於直接求解比三對角矩陣更一般的矩陣的方程,若將其分裂,通常可以更高效地求解。這項技術由Richard S. Varga(1960)發明。[1]
正則分裂[編輯]
解矩陣方程
| | (1) |
其中A是給定n階非奇異方陣,k是給定n元列向量。A可分裂為
| | (2) |
B、C都是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) |
其中D是A的主對角線元素構成的對角矩陣,U、L分別是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
|
- ^ Varga (1960)
- ^ Varga (1960, pp. 121–122)
- ^ Varga (1960, pp. 122–123)
- ^ Varga (1962, p. 89)
- ^ Burden & Faires (1993, p. 408)
- ^ Varga (1962, p. 88)
- ^ Burden & Faires (1993, p. 411)
- ^ Varga (1962, p. 88)
- ^ Burden & Faires (1993, p. 416)
- ^ Varga (1962, p. 88)
- ^ Burden & Faires (1993, p. 371)
參考文獻[編輯]
- Burden, Richard L.; Faires, J. Douglas, Numerical Analysis 5th, Boston: Prindle, Weber and Schmidt, 1993, ISBN 0-534-93219-3 .
- Varga, Richard S. Factorization and Normalized Iterative Methods. Langer, Rudolph E. (編). Boundary Problems in Differential Equations. Madison: University of Wisconsin Press. 1960: 121–142. LCCN 60-60003.
- Varga, Richard S., Matrix Iterative Analysis, New Jersey: Prentice-Hall, 1962, LCCN 62-21277 .