2015年4月5日日曜日

n項間線形漸化式を持った数列の一般項

体K上の数列{x_i}がp=0,1,2,...に対して
の関係を満たすとき、線形回帰数列と言います。例えば加算個の状態を持ったマルコフモデルとかでの定常分布でこういう式が出てきて一般項を求めたい、もしくは三重対角行列の行列式を求めるときにこういう感じの漸化式が出てくると思いますが、今回はそれを解決したいと思います。
なお、本記事は
斎藤正彦著『線形代数入門』『線形代数演習』(東京大学出版会)
を参考にさせて頂いております。ちなみにこの本はとても良い本です。

出来るだけ事前知識を必要としないように書くつもりですが、やはり線形代数の基礎的な知識(次元基底の定義とか)は必要だと思います。

目標

さて、まずは「体K上の数列の集合」を考えます。(大体KはRもしくはCです)
この集合の部分集合として上の漸化式を満たすものの全体をVとします。今回はこの空間Vが実は線形空間でしかもその次元がnであることを示した後、n個の基底の構成方法を述べることによってVの任意の元すなわち上の漸化式を満たす数列がこれらの基底の線形結合で表せる、ということを述べます。

まず、二つの数列{a_i},{b_i}に対して加法とスカラー乗法を定義しますがこれは簡単で
{a_i}+{b_i} = {a_i+b_i}
k*{a_i} = {k*a_i}
と定義します(普通のやつです)

Vが線形空間かどうか

そして数列{x_i},{y_i}∈Vの時、{x_i}+{y_i}及びk*{x_i}は明らかにVの要素になっている(実際に計算すれば確かめられます)ので、Vはこれらの演算で閉じていて、Vの零元を{0,0,...}と定義すれば確かに零元になっていて結合則とかもろもろは体K上の数列であることから実際に計算してみれば明らかですので、Vは線形空間となっています。

Vの次元は?

VからK^nへの写像Tを「数列の最初のn項を取り出す写像」つまり
と定義します。これはT(ax+by)=aT(x)+bT(y)より明らかに線形写像で、任意のK^nの要素に対してそのn個の数を最初のn項にした数列がV内に存在するため全射で、違う数列は違う値に移されるため、全単射である。従って同型写像である。
同型写像が存在する時、どちらの空間も次元が等しいため、
dimV = dim(K^n) = n
です。これはV内のn個の線形独立な数列を見つけたらVの任意の要素がこれらの線形結合で表されることに他なりません。

1.特性多項式

ここが一番大事なところです。そのためにまずVからVへ移す写像DとIを考えます。
Iは恒等写像で、Dはずらし変換、即ち
と定義します。DがVからVへ移すことはDによって数列のn項間の関係が変化しないことから明らかです。また、写像f,gの加法と乗法及びスカラー乗法を
(f+g)(x) = f(x)+g(x)
(fg)(x) = f(g(x))
(k*f)(x) = k*f(x)
と定義すると、Iは当然ながらDも
D(ax+by) = aD(x)+bD(y)
となります。そしてDの冪乗D^nもDをn回合成した写像として定義することが出来ます。
この定義に基づくとこの画像で確かめている通り

(aD+bI)と(cD+dI)は交換可能(AB=BA)であることが分かります。
最初の漸化式の左辺をpに関する一般項とする数列{0_p}は、恒等的に0、即ち零元だから
0_p = (D^n(x))_p + (a_1*D^(n-1)(x))_p + ... + (a_{n-1}*D(x))_p + (a_n*I(x))p = 0
写像の和算の定義より右辺は

となり、これがどのpに対しても0だから

となります。この()内のDをスカラーuに変えて多項式にしたものを特性多項式と呼びます。これをΦ(u)で表すことにします。すると上の式はΦ(D)x=0と表記できます。注意してほしいのはこれの左辺は数列を表すものであって、スカラーではないということです。

2.特性多項式の根から解を生成する

代数学の基本定理より、特性多項式の根はn個あります。これらのn個の根をそれぞれb1,b2,...,bnとします。
この時、Φ(u)=(u-b1)(u-b2)...(u-bn)
と表され、先ほど確かめた通り、交換可能な者同士の積ならばDとIに関しても展開した結果が普通の展開と結果が同じになるので、Φ(D)=(D-b1I)(D-b2I)...(D-bnI)となります。

ここで、各(D-biI)と(D-bjI)は交換可能だから、あるkに対してxが(D-bkI)x=0となっている時、かけ算の順序で(D-bkI)を最後に持ってきて
Φ(D) = (D-b1I)...(D-bnI)(D-bkI)x = 0
は明らか。

従って、(D-biI)^mi x=0 (miは解biの重複度)
の解を全てのbiに対してmi個ずつ見つけ、これらが線形独立であることを証明すれば、n個の基底が見つかったことになる。

mi=1のとき
(D-bi)x=0よりDx=bi*x
Dxは一項ずらすものなので、これは明らかに公比がbiの等比数列である。つまり例えば
x_k = (bi)^{k}
が解である。

mi>1のとき
(D-bi)^m (x)=0
天下り的だが
x_k = k^j *(bi)^{k-1} (j=0,1,...,mi-1)
を考えると確かにこれらは(D-bi)^mi(x) = 0のmi個の解になっている。

以上より、m1+m2+... = n個の解が構成出来た。
また、これらの解が線形独立であることは実際にこれらの数列の線形結合が0に等しいならば自明な線形関係が成り立つ(係数が全て0である)ことによって示すことが出来る。

最後らへんは結構投げやりだが、これによって線形回帰数列を求めることが出来た。




0 件のコメント:

コメントを投稿

Håstadのスイッチング補題

回路計算量の理論における重要な結果の一つである Håstadのスイッチング補題 を紹介します. 簡潔にいうとこの補題は, 99%の変数をランダムに固定することによってDNFの決定木が小さくなることを主張する結果です. 応用としてparity関数に対する$\mathrm{AC}^0...