矩陣分裂

數值線性代數中，矩陣分裂（matrix splitting）是一種將給定矩陣表為多個矩陣和或差的表示。很多迭代法（如解微分方程組的）都依賴於直接求解比三對角矩陣更一般的矩陣的方程，若將其分裂，通常可以更高效地求解。這項技術由Richard S. Varga（1960）發明。^[1]

正則分裂[編輯]

解矩陣方程

\mathbf {A} \mathbf {x} =\mathbf {k} ,

(1)

其中A是給定n階非奇異方陣，k是給定n元列向量。A可分裂為

\mathbf {A} =\mathbf {B} -\mathbf {C} ,

(2)

B、C都是n階方陣。對元素非負的任意n階方陣M，可以記作 $\mathbf {M} \geq \mathbf {0}$ 。若M元素均為正數，可以記作 $\mathbf {M} >\mathbf {0}$ 。相似地，若 $\mathbf {M} _{1}-\mathbf {M} _{2}$ 的元素非負，可以記作 $\mathbf {M} _{1}\geq \mathbf {M} _{2}$ 。

定義：若 $\mathbf {B} ^{-1}\geq 0,\ \mathbf {C} \geq \mathbf {0}$ ，則 $\mathbf {A} =\mathbf {B} -\mathbf {C}$ 是A的一個正則分裂（regular splitting）。

假設矩陣方程形式為

\mathbf {B} \mathbf {x} =\mathbf {g} ,

(3)

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

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

(4)

其中 $\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

(5)

若(2)表示A的正則分裂，則矩陣 $\mathbf {D} =\mathbf {B} ^{-1}\mathbf {C}$ 的元素非負。^[2]

可以證明，若 $\mathbf {A} ^{-1}\geq \mathbf {0}$ ，則 $\rho (\mathbf {D} )<1$ ，其中 $\rho (\mathbf {D} )$ 表示D的譜半徑，因此D是收斂矩陣。於是，迭代法(5)必然收斂。^[3]^[4]

此外，若選擇分裂(2)，使B是對角矩陣（由於B可逆，所以對角項全部不為零），則B可在線性時間內求得逆（見時間複雜度）。

矩陣迭代法[編輯]

很多迭代法都可描述為矩陣分裂。若A的對角項都是非零的，且A表為矩陣和

\mathbf {A} =\mathbf {D} -\mathbf {U} -\mathbf {L} ,

(6)

其中D是A的主對角線元素構成的對角矩陣，U、L分別是n階嚴格上、下三角矩陣，則有：

雅可比法可表為

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

^[5]^[6]

(7)

高斯-賽德爾迭代可表為

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

^[7]^[8]

(8)

逐次超鬆弛迭代法可表為

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

^[9]^[10]

(9)

例子[編輯]

正則分裂[編輯]

方程(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}}.

(10)

應用雅可比中的分裂(7)：將A分裂，使B包含A的所有對角元素，C包含A的所有對角線外元素並取負（當然這不是將矩陣分裂為兩矩陣的唯一有效方法），則有

{\begin{aligned}&\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{aligned}}

(11)

{\begin{aligned}&\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{aligned}}

{\begin{aligned}\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{aligned}}

由於 $\mathbf {B} ^{-1}\geq \mathbf {0} ,\ \mathbf {C} \geq \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是強對角占優矩陣。^[11]

迭代法(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)

(12)的精確解為

\mathbf {x} ={\begin{pmatrix}2\\-1\\3\end{pmatrix}}.

(13)

以 $\mathbf {x} ^{(0)}=(0.0,\ 0.0,\ 0.0)^{T}$ 為初向量，列出(12)的前幾次迭代。可見此方法明顯收斂到解(13)，不過速度相當緩慢。

$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

雅可比法[編輯]

雅可比法(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}}.

(14)

則有

{\begin{aligned}&\mathbf {(D-L)^{-1}} ={\frac {1}{120}}{\begin{pmatrix}20&0&0\\5&30&0\\13&6&24\end{pmatrix}},\end{aligned}}

{\begin{aligned}&\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{aligned}}

將高斯-賽德爾法(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

(15)

以 $\mathbf {x} ^{(0)}=(0.0,\ 0.0,\ 0.0)^{T}$ 為初向量，列出(15)的前幾次迭代。可見方法明顯收斂到解(13)，且比雅可比法快。

$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$ 。由分裂(14)，有

{\begin{aligned}&\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{aligned}}

{\begin{aligned}&\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{aligned}}

{\begin{aligned}&\mathbf {\omega (D-\omega L)^{-1}k} ={\frac {1}{12}}{\begin{pmatrix}11\\-36.575\\25.6135\end{pmatrix}}.\end{aligned}}

將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

(16)

以 $\mathbf {x} ^{(0)}=(0.0,\ 0.0,\ 0.0)^{T}$ 為初向量，列出(16)的前幾次迭代。可見SOR法收斂到解(13)，比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

另見[編輯]

注釋[編輯]

^ 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 .

[1] Varga (1960)

[2] Varga (1960, pp. 121–122)

[3] Varga (1960, pp. 122–123)

[4] Varga (1962, p. 89)

[5] Burden & Faires (1993, p. 408)

[6] Varga (1962, p. 88)

[7] Burden & Faires (1993, p. 411)

[8] Varga (1962, p. 88)

[9] Burden & Faires (1993, p. 416)

[10] Varga (1962, p. 88)

[11] Burden & Faires (1993, p. 371)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]