行列分割

Representation of a matrix as a sum

数値線形代数という数学分野において、 行列分割とは、与えられた行列を行列の和または差として表す表現である。多くの反復法（例えば、 微分方程式系）は、三重対角行列よりも一般的な行列を含む行列方程式の直接解に依存している。これらの行列方程式は、行列分割として記述することで、多くの場合直接かつ効率的に解くことができる。この手法は1960年にリチャード・S・ヴァルガによって考案された。^[1]

定期的な分割

行列方程式を解こうとする

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

1

ここで、Aはn × nの 非特異行列、kはn成分の列ベクトルである。行列Aを以下のように 分割する。

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

2

ここで、 BとCはn × n行列です。任意のn × n行列Mに対して、Mが非負の要素を持つ場合、M ≥ 0と書きます。Mが正の要素のみを持つ場合、 M > 0と書きます。同様に、行列M ₁ − M _{2が非負の要素を持つ場合、} M ₁ ≥ M ₂と書きます。

定義: B ⁻¹ ≥ 0かつC ≥ 0の場合、A = B − CはA の正規分割です。

次のような行列方程式を仮定する。

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

3

ここでgは与えられた列ベクトルであり、ベクトルxについて直接解くことができる。( 2 )がAの正規分割を表す場合、反復法

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

4

ここでx ⁽⁰⁾は任意のベクトルである。同様に、( 4 )を次のように 書くこともできる。

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

5

行列D = B ⁻¹ Cは、（2 ）がAの正規分割を表す場合、非負の要素を持ちます。^[2]

A ⁻¹ > 0ならば< 1となることが示され、ここで はDのスペクトル半径を表し、したがってDは収束行列となる。結果として、反復法( 5 )は必然的に収束する。^{[3] [4]} ${\displaystyle \rho (\mathbf {D} )}$ ${\displaystyle \rho (\mathbf {D} )}$

さらに、分割（2）を選択して行列Bが対角行列（ Bは逆行列でなければならないため、対角要素がすべてゼロ以外）になるようにすると、Bは線形時間で逆行列を求めることができます（時間計算量を参照）。

行列反復法

多くの反復法は行列の分割として記述できる。行列Aの対角要素がすべて非ゼロで、行列Aを行列和として 表すと、

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

6

ここで、DはAの対角部分、UとLはそれぞれ厳密に上三角と下三角の n × n行列である場合、次のようになります。

ヤコビ法は、分割行列として表すことができる。

${\displaystyle \mathbf {x} ^{(m+1)}=\mathbf {D} ^{-1}(\mathbf {U} +\mathbf {L} )\mathbf {x} ^{(m)}+\mathbf {D} ^{-1}\mathbf {k} .}$[5] [6]

7

ガウス・ザイデル法は、分割行列として表すことができる。

${\displaystyle \mathbf {x} ^{(m+1)}=(\mathbf {D} -\mathbf {L} )^{-1}\mathbf {U} \mathbf {x} ^{(m)}+(\mathbf {D} -\mathbf {L} )^{-1}\mathbf {k} .}$[7] [8]

8

逐次過緩和法は、分割行列として表すことができる。

${\displaystyle \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

例

定期的な分割

式（１）において、

${\displaystyle \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の非対角要素すべてを反転したものから成るように分割します。（もちろん、これは行列を2つの行列に分割する唯一の有効な方法ではありません。）

${\displaystyle {\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

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

B ⁻¹ ≥ 0かつC ≥ 0なので、分割( 11 )^は正規分割である。A −1 > 0 なので、スペクトル半径< 1 である。（ Dの近似固有値は）したがって、行列Dは収束し、方法( 5 )は問題( 10 )に対して必然的に収束する。Aの対角要素はすべて0より大きく、 Aの非対角要素はすべて0より小さく、Aは厳密に対角優位であることに注意されたい。^[11] ${\displaystyle \rho (\mathbf {D} )}$ ${\displaystyle \lambda _{i}\approx -0.4599820,-0.3397859,0.7997679.}$

問題（10 ）に適用された方法（5 ）は、次の形をとる。

${\displaystyle \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

式（ １２）の正確な解は

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

13

式( 12 )の最初の数回の反復計算は、以下の表にx ⁽⁰⁾ = (0.0, 0.0, 0.0) ^{Tから始まる。表から、この方法は、ややゆっくりではあるが、明らかに解(} 13 )に収束していることがわかる。

${\displaystyle x_{1}^{(m)}}$	${\displaystyle x_{2}^{(m)}}$	${\displaystyle 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の対角成分はすべて非ゼロなので、行列Aを分割( 6 )として表すことができる。ここで

${\displaystyle \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

そして、

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

${\displaystyle {\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）に適用すると、次のようになる。

${\displaystyle \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

式( 15 )の最初の数回の反復計算は、 x ⁽⁰⁾ = (0.0, 0.0, 0.0) ^Tから始まり、以下の表に示されています。表から、この方法は明らかに解( 13 )に収束しており、上記のヤコビ法よりもいくらか速く収束していることがわかります。

${\displaystyle x_{1}^{(m)}}$	${\displaystyle x_{2}^{(m)}}$	${\displaystyle 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

逐次過緩和法

ω = 1.1とする。問題( 10 )の行列Aの分割( 14 )を逐次過緩和法に用いると、

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

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

問題（10 ）に適用された逐次過緩和法（9 ）は、次の形をとる。

${\displaystyle \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

式( 16 )の最初の数回の反復計算は、 x ⁽⁰⁾ = (0.0, 0.0, 0.0) ^Tから始まり、以下の表に示されています。表から、この方法は明らかに解( 13 )に収束しており、上記のガウス・ザイデル法よりもわずかに速いことがわかります。

${\displaystyle x_{1}^{(m)}}$	${\displaystyle x_{2}^{(m)}}$	${\displaystyle 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

参照

• 演算子分割トピックのリスト
• 行列分解
• M行列
• スティルチェス行列

注記

1. ヴァルガ（1960）
2. ヴァルガ（1960年、121～122ページ）
3. ヴァルガ（1960年、122～123ページ）
4. ヴァルガ（1962年、89ページ）
5. Burden & Faires (1993、p. 408)
6. ヴァルガ（1962年、88ページ）
7. Burden & Faires (1993、p. 411)
8. ヴァルガ（1962年、88ページ）
9. Burden & Faires (1993, p. 416)
10. ヴァルガ（1962年、88ページ）
11. Burden & Faires (1993、p. 371)

参考文献

• バーデン、リチャード・L.; フェアーズ、J.ダグラス (1993)、『数値解析』（第5版）、ボストン：プリンドル、ウェーバー、シュミット、ISBN 0-534-93219-3。
• Varga, Richard S. (1960). 「因数分解と正規化反復法」. Langer, Rudolph E. (編). 『微分方程式における境界問題』 . マディソン:ウィスコンシン大学出版局. pp.  121– 142. LCCN  60-60003.
• Varga, Richard S. (1962), Matrix Iterative Analysis , New Jersey: Prentice-Hall , Bibcode :1962mia..book.....V, LCCN  62-21277。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Matrix_splitting&oldid=1296012803"