線形連立方程式の正規化解法とマルコフ連鎖への応用
日本大学 篠原 正明 情報システム研究所 篠原 健
１．はじめに
遷移確率行列Pを持つマルコフ連鎖の定常 状態確率ベクトルxは、線形連立方程式系 を解くことにより求ま る。これを解く方法として、私個人的に多用 している正規化法を説明(提案)し、さらに一 般の連立方程式へ拡張する。最後に、一般化 正規化条件 が付加されたマルコフ連 鎖の意味付けについて考察する。
∑
== , 1}
{x PTx xi
=1 x aT
２．マルコフ連鎖の正規化解法
マ ル コ フ 連 鎖 の 正 規 化 解 法 と は 、 において、仮に と置き、
の適当なn-1本の線形連立方程式を 何らかの方法で解き、その解を、
とした時に、(1)式により正規化することによ り、解を求める方法である。
∑
== , 1}
{x PTx xi x1 =1
x P x= T
xn
x x2, 3,L,
∑
=← x x (i 1, ,n) (1)
xi i j L
この方法の利点は、n変数方程式が( −1)変 数方程式の求解に帰着される点である。n=3、
=4 程度のマルコフ連鎖の定常状態確率ベ クトルの手計算求解では非常に有効である。
n n
例１
遷移確率行列Pが(2)式で与えられると、平衡 方程式は(3)−(5)式である。
) 2 ( 1
. 0 0 9 . 0
3 . 0 2 . 0 5 . 0
0 4 . 0 6 . 0
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
= P
) 5 ( 1
. 0 3 . 0
) 4 ( 2
. 0 4 . 0
) 3 ( 9
. 0 5 . 0 6 . 0
3 2
3
2 1
2
3 2
1 1
x
x x
x x
x
x x
x x
+ +
=
+
=
+ +
=
疎な(4)式と(5)式において、x1=1を代入する と簡単に、
6 / 1 , 5 .
0 3
2 = x =
x を得る。
3 2 1,x ,x
x を総和して１になるように正規化 すると、x1 =0.6,x2 =0.3,x3 =0.1を得る。
すなわち、(3)-(5)式において、密結合な変数 を選んで１とでも置き、疎な2本の方程式に 代入して、それを残った変数で解けばよい。
経験上、手計算では大幅に手間が減少する。
2 章の正規化法がどこまで一般化・拡張でき るかを次章で試みる。まず正当性は問わない で、形式的にアルゴリズムを拡張してみよう。
3．一般の連立方程式への拡張の可能性検討 n変数連立方程式系（線形に限定されない）
において、少なくとも１方程式において以下 の非同次線形方程式の存在を仮定しよう。
) 6 ( )
0
2 (
2 1
1x +a x + +a x =b b≠
a L n n
すると、拡張正規化法の手続きは以下の通り である。
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
A Normalization Method to Solve a Set of Linear Equations and its Application to Markov Chain
Masaaki SHINOHARA and Ken SHINOHARA
ステップ１：例えば、x1 =1と仮に置く。
ステップ２： を除いた（n-1）方程式 系を何らかの方法で解き、その 解を とする。
=1 x aT
xn
x x2, 3,L,
ステップ３：
∑
=←bx a x (i 1, ,n) (7)
xi i j j L
２章と同様に、ｎ変数方程式の求解が（n-1）
変数方程式の求解に帰着されるわけだが、こ の拡張正規化法の正当性は？
残念ながら、この拡張正規化法は必ずしも 正解を与えないことは、簡単な次の例２より 判明する。
例２
(8)-(10)式の線形連立方程式を考える。
) 10 ( 2
) 9 ( 16
4 3 2
) 8 ( 10
3 2
3 2 1
3 2 1
3 2 1
= +
−
= + +
= + +
x x x
x x x
x x x
1 =1
x とおいて、（９）と（１０）をとくと
7 , 17 7 10
3
2 = x =
x となるが、（８）式で正規化 しても、正解を得られない。
この正解を得られな理由は、残った（n-１）
次方程式系（９）、（10）が非同次であるから であり、それらが同次形ならば、拡張正規化 法が正常動作することを次の例３より確認す る。
例３
(11)-(13)式の線形連立方程式を考える。
) 13 ( 0
2
) 12 ( 0
) 11 ( 10
3 2
3 2 1
3 2 1
3 2 1
= +
−
=
−
−
= + +
x x x
x x x
x x x
1 =1
x とおいて、(12)、(13)を解くと
3 , 1 3 2
3
2 = x =
x を得る。(11)式にもとづき正 規化すると、
) 14 ( 3
3 3 3 1 4
1 10
1 = +
+
← × x
) 15 ( 2
3 3 3 1 4
3 10 2
2 = +
+
×
← x
) 16 ( 1
3 3 3 1 4
3 10 1
3 = +
+
×
← x
以上に示すように正解を得る。
4. マルコフ連鎖における一般化正規化条件 線 形 連立方 程 式 系
（ を仮定）で定義されるマルコフ連鎖 を考える。
∑
== , 1}
{x PTx aixi
>0 ai
数値計算的には、Ax=bと変形することに より、求解できるが、マルコフ連鎖としての 意味を考察する。
) 17 (
i i
i a x
y =
(17)式の変数変換を行うと、次の線形連立方 程式を得る。
) 18 ( y
Q y= T
∑
yi =1 (19)但し、
i j ij ij
ij a
p a q q
Q={ }, =
ここで、Ｑは一般には確率行列の条件を満 たさないが、 はどのような振舞をする かを次の例４で観察する。
Qk
lim
例４
(2)式のＰを持つマルコフ連鎖に
1 3
2 2 3
1 + x + x =
x の正規化条件を付加する。
線 形 連 立 方 程 式 と し て の 解 は
) 2 . 0 , 4 . 0 , 4 . 0 (
066667 .
0 , 2 . 0 , 4 . 0
3 2
1
3 2
1
=
=
=
=
=
=
y y
y
x x
x
Ｑは(20)式で与えられる。
) 20 ( 1
. 0 0 3 . 0
45 . 0 2 . 0 25 . 0
0 8 . 0 6 . 0
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
= Q
ＰもＱも４乗程度で以下の値に収束する。
) 21 ( 1
. 0 3 . 0 6 . 0
1 . 0 3 . 0 6 . 0
1 . 0 3 . 0 6 . 0
4
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
= P
) 22 ( 1
. 0 2 . 0 2 . 0
15 . 0 3 . 0 3 . 0
3 . 0 6 . 0 6 . 0
4
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛
= Q
Ｑは行一様ではないが収束し、対角要素は
0.6、0.3、0.1であり、Pkの収束値と一致す
る。
5．線形連立方程式に対する正規化法による 再帰解法
ｎ 変 数 非 同 次 線 形 連 立 方 程 式 において、右辺定数 ベクトルｂは、適当な等価変形を行えば、
と変形できる。そうすれば、
と仮に置いた残りの（n-1）変数の非同 次線形連立方程式
) 0 ( ( )
) ( ) ( )
(n xn =bn bn ≠ A
) 0 , , 0 , 0 , 1
) (
(Tn = L
b
1 =1 x
) 0
)(
1 ( ) 1 ( ) 1
(n− xn− =bn− ≠ A
の求解に帰着できる。同様にこれも適当な代
入操作により、 と変形で
き、 と仮に置いた(n-2)変数の非同次線 形 連 立 方 程 式 の 求 解に帰着できる。すなわち正規化法による再 帰解法が可能となる。このアルゴリズムを例 2の線形連立方程式(8)-(10)に適用し、以下に 手続きを説明する。
) 0 , , 0 , 0 , 1
) (
1
(Tn− = L
b
2 =1 x
) 0
)(
2 ( ) 2 ( ) 2
(n− xn− =bn− ≠ A
例５
以下に例2の方程式を再載する。
) 25 ( 2
) 24 ( 16
4 3 2
) 23 ( 10
3 2
3 2 1
3 2 1
3 2 1
= +
−
= + +
= + +
x x x
x x x
x x x
右辺定数ベクトルを に変形す るため、以下の線形変換を行う。
) 0 , 0 , 1
=( bT
(23)はそのまま→(26)
−5×(23)+3×(24)+(25)→(26) (23)−(24)+3×(25)→(27)
) 28 ( 0
2
) 27 ( 0
) 26 ( 10
3 2
3 2 1
3 2 1
3 2 1
= +
−
=
−
−
= + +
x x x
x x x
x x x
ここで、(26)式の右辺定数が１でなく10で あるが、本質的でない。又、例３に一致させ るための変換を行ったが、これも本質的でな く の形式なら階数を保持する範 囲で任意である。
) 0 , 0 , 1
=( bT
1 =1
x と仮に置いて(27)、(28)を解くと、次の ２元連立方程式を得る。
) 29 (
3 1
2 +x = x
) 30 ( 1
2x2 −x3 =
右辺定数ベクトルを に変形するた め、以下の線形変換を行う。
) 0 , 1
=( bT
(29)はそのまま→(31) (29)−(30)→(32)
) 30 (
3 1
2 +x = x
) 31 ( 0
2 3
2 + =
−x x
2 =1
x と仮に置いて、(31)を解くと、(31)は 次の一元（連立）方程式となる。
) 32 ( 0
2
1+ 3 =
− x
) 33 2 (
1
3 =
∴x
(30)で正規化すると、途中解 (34)、 (35) を得る。
x2 x3
) 34 ( 2
1 1 1 3 2
2 +
=
= x
) 35 ( 2
1 1 2 1 3 1
3 +
=
= x
次に、途中解
3 , 1 3 2
3
2 = x =
x を(26)で正規化 すると、最終解 (37)、 (38)、 (39)を得 る。
x1 x2 x3
) 37 ( 3
3 3 3 1 4
1 10
1 = +
+
← × x
) 38 ( 2
3 3 3 1 4
3 10 2
2 = +
+
×
← x
) 39 ( 1
3 3 3 1 4
3 10 1
3 = +
+
×
← x
これらは、線形連立方程式(23)-(25)の正解で ある。
6. 解法アルゴリズムの分類
線形連立方程式あるいは連立一次方程式の 求解アルゴリズムの分類法は、立場により若 干の差異は存在するものの、以下がその代表 例と思われる。
・①直接法と反復法〔１〕
・②有理解法と反復解法〔２〕
・③消去法と反復法と共役勾配法〔３〕
提案した新解法アルゴリズムは、①と②の分
類に従えば、それぞれ、①では直接法、②で は有理解法に属すると言える。③の分類法で は、どこにも属さない。
7. 解法アルゴリズムの手間評価
直接法あるいは有理解法の代表的な既存解 法として、Gauss-Jordanの掃き出し法をとり あげ、新解法アルゴリズムと比較して、ｎ変 数の線形連立方程式を解く際の足算、引算、
掛算、割算の演算回数をおおまかに評価する と以下の結果を得る。
掃 き 出 し 法 ： 引 算 n(n-1)(n+1)/3、 掛 算 n(n-1)(n+1)/3、割算n(n+1)/2
新解法アルゴリズム：足算 n(n-1)/2、引算 n(n-1)(n+1)/3、掛算n(n-1)(n+1)/3＋n(n+1)/2、
割算n(n+1)
た だ し 、 ＝ n(n-1)(n+1)/3 、
＝n(n+1)/2である。
k k
n
k
∑
−=1 2
∑
= nk
k
1
これより、掃き出し法と比較すると、新解法 アルゴリズムの方が、わずかに、正規化作業 の分だけ多いことがわかる。正規化作業以外 の手間は、同じである。
8. おわりに
提案した正規化法による再帰解法の既存手 法との比較、 の形式をとる 線形系の双対性の考察、などは今後の課題で ある。提案した正規化法による線形連立方程 式の再帰解法が新解法アルゴリズムであるこ とが判明すれば、特定応用分野、非線形系、
他の双演算系、など関連分野への波及効果が 期待できる。
) 0 , , 0 , 0 , 1
( L
= bT
又、マルコフ連鎖における一般化正規化条 件の意味付けについては、その理論基盤の解 明と共に今後の課題である。
参考文献
〔１〕 大野豊、磯田和夫：数値計算ハンドブ ック、オーム社（1990）
〔２〕 伊 理 正 夫 ： 線 形 代 数 Ⅱ 、 岩 波 書 店
（1997）
〔３〕 森 正 武 、 他 ： 線 形 計 算 、 岩 波 書 店
（1997）
