スポンサードリンク

こんにちは、ももやまです。
今回は差分方程式(漸化式)を行列の n 乗を使って解くテクニックを紹介します!

 

 

前回の記事(行列の n 乗の求め方)はこちらから↓

www.momoyama-usagi.com

 

普通に差分方程式(漸化式)を解く方法はこちら!

www.momoyama-usagi.com

 

 

★注意★

この記事では、初項を a1 ではなく a0 としてるので気をつけてください。初項が a1 だと特殊解は an1 のような形で出ますが、a0 の場合は an の形で出てきます。

また、人によっては an という形ではなく、f(n) を使って表す人もいるので気をつけてください。

例:an=2an1+1f(n)=2f(n1)+1 と同じ

スポンサードリンク

1.行列を用いた連立漸化式

まずは、2次連立漸化式を行列で解く流れを誘導付きの例題で見ていきましょう。

例題1

初項 a0=7, b0=4 で表される漸化式、

 {an=2an1+  bn1bn=2an1+3bn1

an, bn を求めたい。つぎの問いに答えなさい。

(1) xn=(anbn)とおく。このとき、xn=Axn1を満たす行列 A を求めなさい。

(2) x0, x1 の値を求めなさい。

(3) 行列 A の固有値 t1, t2 とそれぞれの固有値に属する固有ベクトル p1, p2 を求めなさい。

(4) x0 を固有ベクトル p1p2 の1次結合で表しなさい。

(5) xn を求めることで、an, bn の特殊解を求めなさい。

 

解説1

(1)

与えられた漸化式(差分方程式)を行列で表すだけ。(anbn)=(2123)(an1bn1)と表せるので、A=(2123)となる。

 

(2) x0=(a0b0)=(74)x1=(2123)(74)=(102)

 

(3)

固有値を t とすると、固有方程式は、|AtE|=|2t123t|=(t3)(t2)2=t25t+4=(t1)(t4)=0より固有値は1, 4となる。

よって、t1=1, t2=4 となる。

[検算ポイント:固有値の和は対角成分の和になっていることを確認(5になればOK)]

 

(i) 固有値が1のときの固有ベクトル p1(AE)=(1122) (1100)となる。x+y=0を解くと、任意定数 k を用いて(xy)=k(11)と表せるので、固有ベクトル p1 は、p1=(11)となる。

 

(ii) 固有値が4のときの固有ベクトル p1(A4E)=(2121) (2100)となる。2xy=0を解くと、任意定数 k を用いて(xy)=k(12)と表せるので、固有ベクトル p2 は、p2=(12)となる。

 

(4)x0=c1p1+c2p2(74)=c1(11)+c2(12)(1112)(c1c2)=(74)となるような c1, c2 の値をもとめればよい。

求め方は2パターン

[パターン1:行基本変形で求める] C= (117124) (117033) (117011) (106011)\]となるので、c1=6, c2=1 となる。よって、x0=6p1+p2となる。

 

[パターン2:逆行列を用いる] (1112)1=13(2111)となるので、(c1c2)=(1112)1(74)=13(2111)(74)=13(183)=(61)

より、x0=6p1+p2となる。

※1次結合は2次の場合は逆行列(パターン2)を、3次以上の場合は行基本変形で求めること(パターン1)をおすすめします。

 

(5)

行列のべき乗 An を使って求めてもよいのですが、せっかく x0p1, p2 で表したので利用してしまいましょう。

 

固有値 tt に属する固有ベクトル p には、Ap=tpの関係がありますね。(忘れていたら早急に復習しましょう。)

 

ここで、Anp=An1(Ap)=An1(tp)=tAn1p=tAn2(Ap)=tAn2(tp)=t2An2==tnpとなるので、Anp=tnpの関係も成立しますよね。

 

ここで、(anbn)xn=Anx0=An(6p1+p2)=6Anp1+Anp2=61p1+4np2=6(11)+4n(12)=(4n+624n6)と求められますね。

よって、一般項はan=4n+6bn=4n6と求められます。

 

ポイントは、Anp=tnpを使うことです。

 

行列を用いて漸化式を解くコツ

固有値 t と固有値に属する固有ベクトル p にはAnp=tnpが成立する。

ここで、固有値と固有ベクトル (t1,p1)(t2,p2), …, (tk,pk) に対し、初項 x0x0=c1p1+c2p2++ckpkと固有ベクトルの1次結合で表されるとき、一般項 xn は、xn=Anx0==An(c1p1+c2p2++ckpk)=c1Anp1+c2Anp2++ckAnpk=c1t1np1+c2t2np2++cktknpkと変形でき、行列 An を求めることなく一般項を算出できる。

今回は xan, bn の2次でしたが、an, bn, cn と3次(もしくは4次以上)になった場合でも同じ方法で求めることができます。

 

一般項を求めるまでの流れは、

  1. 漸化式を行列やベクトルを用いて表す
  2. 行列の固有値、(固有値に属する)固有ベクトルを求める
  3. 初項ベクトルを2で求めた固有ベクトルの1次結合で求める
  4. xn=Anx0 を用いて一般項を求める

となります。

 

スポンサードリンク

2.隣接3項間漸化式(差分方程式)

行列の置き方を工夫することで、隣接3項間漸化式を解くこともできます。an=pan1+qan2で表される漸化式を、{an=pan1+qan2an1=1an1と式を2つおくことにより、(anan1)=(pq10)(an1an2)とおくことができます。

 

隣接3項間差分方程式(漸化式)の解き方初項 a0, a1 で表される隣接3項間漸化式an=pan1+qan2xn=(anan1)   A=(pq10)xn=Axn1と変形することにより、xn=Anx0=(a1a0)となり、 An を用いることで an の一般項を出すことができる。

 

例題2

a0=2, a1=7, an3an1+2an2=0

の初期値による特殊解を求めたい。

(1) (anan1)=(abcd)(an1an2)   を満たすような a, b, c, d を求めなさい。

以降、A=(abcd)とする。

(2) 行列 A の固有値 t1, t2 とそれぞれの固有値に属する固有ベクトル p1, p2 を求めなさい。

(3) 初項を表すベクトル x0 を、(a1a0)=(72)とする。x0p1, p2 の1次結合で表しなさい。

(4) xn=(an+1an)とし、an の特殊解を求めなさい。

解説2

(1)

差分方程式の形を変え、{an=3an12an2an1=1an1とします。すると、行列 A は、(3210)となります。よって、a=3,  b=2,  c=1,  d=0となる。

 

(2)

固有値を t とすると、固有方程式は、|AtE|=|3t21t|=t(t3)+2=t23t+2=(t1)(t2)=0より固有値は1, 2となる。

よって、t1=1, t2=2 となる。

[検算ポイント:固有値の和は対角成分の和になっていることを確認(3になればOK)]

 

(3)

固有値を t とすると、固有方程式は、|AtE|=|3t21t|=t(t3)+2=t23t+2=(t1)(t2)=0より固有値は1, 2となる。

よって、t1=1, t2=2 となる。

[検算ポイント:固有値の和は対角成分の和になっていることを確認(3になればOK)]

 

固有値が1のときの固有ベクトル p1 (A1E)=(2211) (1100)となる。x+y=0を解くと、任意定数 k を用いて(xy)=k(11)と表せるので、固有ベクトル p1 は、p1=(11)となる。

 

 固有値が2のときの固有ベクトル p2(A3E)=(1212) (1200)となる。x2y=0を解くと、任意定数 k を用いて(xy)=k(21)と表せるので、固有ベクトル p2 は、p2=(21)となる。

 

(4)

x0=c1p1+c2p2(72)=c1(11)+c2(21)(1211)(c1c2)=(72)となるような c1, c2 の値をもとめればよい。

求め方は2パターン

[パターン1:行基本変形で求める] C= (127112) (127015) (103015)\]となるので、c1=3, c2=5 となる。よって、x0=3p1+5p2となる。

 

[パターン2:逆行列を用いる] (1211)1=(1211)となるので、(c1c2)=(1211)1(72)=(1211)(72)=13(35)

となり、x0=3p1+5p2と表せる。

 

(5)

ここで、(an+1an)=xn=Anx0=An(3p1+5p2)=3Anp1+5Anp2=31p1+52np2=3(11)+52n(21)=(3+102n3+52n)と求められますね。

よって、一般項はan=52n3と求められます。

 

an+1=52n+13=102n3 とすることで検算することができますね。)

 

参考までに隣接4項間の差分方程式を行列に変換する方法も下に記しておきます。

 

隣接4項間差分方程式(漸化式)の解き方初項 a0, a1, a2 で表される隣接3項間漸化式an=pan1+qan2+ran3xn=(anan1an2)   A=(pqr100010)xn=Axn1と変形することにより、xn=Anx0=(a2a1a0)となり、 An を用いることで an の一般項を出すことができる。

 隣接4項間漸化式は練習問題のほうに1問用意したのでチャレンジしたい方はぜひチャレンジしてみてください!

 

スポンサードリンク

3.練習問題

では、3問ほど練習してみましょう。

練習1

とある大学の休憩コーナー(通称:LA)では、毎日12時になるとご飯を食べるための座席(陣地)を占領するために大量の人が訪れる。

しかし、LAの陣地はあまり広くないため、陣地を占領するためのナワバリバトルが生徒組と教授組の間で毎日繰り広げられ戦争となる。

ナワバリバトルの結果は不思議なことにつぎのような一定確率で決まる。

当日の争いで生徒組が勝った場合、翌日の争いで勝つ確率は 6/7、負ける確率は 1/7 となる。

当日の争いで生徒組が負けた場合、翌日の争いで勝つ確率は 3/7、負ける確率は 4/7 となる。

n 日目(ただし n は0以上の整数)のナワバリバトルで生徒組が勝利する確率を an、教授組が敗北する確率を bn とする。

戦争開始日を0日目とし、0日目の争いでは生徒組が勝利したとき、つまり a0=1, b0=0 のとき、つぎの問いに答えなさい。

(1) xn=(anbn)としたとき、xn=Axn1を満たすような行列 A を求めなさい。

(2) x0, x1 を求めなさい。
(ヒント an+bn=1 は必ず成立する)

(3) 行列 A の固有値 t1, t2 およびそれぞれの固有値に対応する固有ベクトル p1, p2 を求めなさい。

(4) ベクトル x0p1, p2 の1次結合で表しなさい。

(5) xn を求めなさい。

(6) 十分長い間ナワバリバトルが行われたときの生徒お組の勝利確率をlimxxnを求めて答えなさい。

練習2 [名古屋大学(理系)前期日程 問題3]

大学入試の問題を行列を使って解いてみましょう!
もとの問題はこちらから!

はじめにAくんが赤玉を1個、Bくんが白玉を1個、Cくんが青玉を1個もっている。表裏の出る確率がそれぞれ1/2の硬貨を投げ、表が出ればAとBの玉を交換し、裏が出ればBとCを玉が交換する。という操作を考える。この操作を n 回繰り返したあとにAくん、Bくん、Cくんが赤玉を持っている確率を an, bn, cn とおく。

このとき、 
{an+1=12an+12bnbn+1=12an+12cncn+1=12bn+12cnの差分方程式(漸化式)が成り立つ。

このとき、つぎの問いに答えなさい。

(1) xn=(anbncn)とおく。このとき、xn+1=Axnを満たす行列 A を求めなさい。

(2) x1, x2 の値を答えなさい。

(3) 行列 A の固有値 t1, t2, t3 と固有値に対応する固有ベクトル p1, p2, p3 を求めなさい。

(4) x0p1, p2, p3 の1次結合で表しなさい。

(5) xn を求め、an, bn, cn の一般項を求めなさい。

(6) limxxnを求め、十分な回数硬貨を投げたとき(n が大きくなったとき)、an, bn, cn にはどのような関係が生まれるかを答えなさい。

 

練習3

差分方程式an+3=10an+231an+1+30ana0=1, a1=2,a2=5

の初期値による特殊解を求めたい。差分方程式を変形し、{an=3an12an2an1=1an1an2=1an2としてみることにより、xn=(an+2bn+1cn)   A=(103130100010)xn=Axn1と表すことができる。

(1) x0, x1 の値を求めなさい。

(2) 行列 A の固有値、固有ベクトルを求めなさい

(3) 行列 A の固有値 t1, t2, t3 と固有値に対応する固有ベクトル p1, p2, p3 を求めなさい。

(4) x0p1, p2, p3 の1次結合で表しなさい。

(5) xn を求め、an の一般項を求めなさい。

 

解答1

(1) 

n 日目のナワバリバトルの勝利確率 an, bn は前日の勝利確率 an1、敗北確率 bn1 を用いて
{an=67an1+37bn1bn=17an1+47bn1となる。これを行列を用いて表すと、(anbn)=(67371747)(an1bn1)とかけるため、行列 A は、A=(67371747)=17(6314)となる。

 

(2) x0=(a0b0)=(10)x1=Ax0=17(6314)(10)=17(61)

 

(3)

固有値を t とすると、固有方程式は、|AtE|=|67t371747t|=17|67t3147t|=(7t6)(7t4)3=49t270t+21=(7t3)(7t7)=0より固有値は 3/7,1 となる。

 

(i) 固有値が1のときの固有ベクトル p117(A7E)=17(1313) (1300)となる。x3y=0を解くと、任意定数 k を用いて(xy)=k(31)と表せるので、固有ベクトル p1 は、p1=(31)となる。

 

(ii) 固有値が3/7のときの固有ベクトル p117(A3E)=17(3311) (1100)となる。x+y=0を解くと、任意定数 k を用いて(xy)=k(11)と表せるので、固有ベクトル p2 は、p2=(11)となる。

 

(4)x0=c1p1+c2p2(10)=c1(31)+c2(11)(3111)(c1c2)=(10)となるような c1, c2 の値をもとめればよい。

求め方は2パターン

[パターン1:行基本変形で求める] (311110) (401440) (400041) (10140114)\]となるので、c1=1/4, c2=1/4 となる。よって、x0=14p1+14p2となる。

 

[パターン2:逆行列を用いる] (3111)1=14(1113)となるので、(c1c2)=(3111)1(10)=14(1113)(10)=14(11)

となる。よって、x0=14p1+14p2が求められる。

 

(5)

ここで、(anbn)=xn=Anx0=An(14p1+14p2)=14Anp1+14Anp2=141p1+14(37)np2=14(31)+14(37)n(11)=14(3+(37)n1(37)n)と求められますね。

よって、一般項はan=14{3+(37)n}bn=14{1(37)n}と求められます。

 

(6)

((5)の計算よりもこちらのほうが簡単かも)

xn=14(31)+14(37)n(11)n を十分大きくすると、limxxn=14(31)となる*1

よって、十分な回数硬貨を投げるとan=34   bn=14に収束する。

 

解答2

(1) 

与えられた漸化式(差分方程式)を行列で表すだけ。(an+1bn+1cn+1)=(121201201201212)(anbncn)と表せるので、A=12(121201201201212)=12(110101011)となる。

 

(2)

行列の積を計算するだけ。

x1=Ax012(110101011)(100)=12(110)x2=A2x0=Ax1=14(110101011)(110)=14(211)ちなみに名古屋大の入試でも a1, b1, c1, a2, b2, c2 の値を答えさせる問題は出題されている。

 

(3)

ここからがオリジナル問題。

固有値を t とすると、固有方程式は、|AtE|=|12t12012t1201212t|=12|12t1012t10112t|=12|22t22t22t12t10112t|=(1t)|11112t10112t|=(1t)|11102t100112t|=(1t)|2t10112t|となる。

となる。

ここで、|2t10112t|=(12t)(1+2t)となるので、|AtE|=(1t)(12t)(1+2t)を満たす t が固有値となり、固有値は1, 1/2, -1/2となる。

 

(i) 固有値が1のときの固有ベクトル p1 12(A2E)=12(110121011) (110011011) (110011000)となる。{xy=0yz=0を解くと、任意定数 k を用いて(xyz)=k(111)と表せるので、固有ベクトル p1 は、p1=(111)となる。

 

(ii) 固有値が1/2のときの固有ベクトル p2 12(A1E)=12(010111010) (101010000)となる。{x+z=0y=0を解くと、任意定数 k を用いて(xyz)=k(101)と表せるので、固有ベクトル p2 は、p2=(101)となる。

 

(iii) 固有値が-1/2のときの固有ベクトル p3 12(A+1E)=12(210111012) (012111012) (101012000)となる。{x+z=0y=0を解くと、任意定数 k を用いて(xyz)=k(121)と表せるので、固有ベクトル p3 は、p3=(121)となる。

 

(4)

x0=c1p1+c2p2+c3p3(100)=c1(111)+c2(101)+c3(121)(111102111)(c1c2c3)=(100)となるような c1, c2, c3 の値をもとめればよい。

 

3次正方行列の逆行列はあまりおすすめしないので素直に行基本変形で求める。

[パターン1:行基本変形で求める] (111110201110) (111101310201) (666602620201) (606300610201) (600200610201) (100130101200116)\]となるので、c1=1/3, c2=1/2, c3=1/6 となる。よって、x0=13p1+12p2+16p3となる。

 

(5)

ここで、(anbncn)=xn=Anx0=An(13p1+12p2+16p3)=13Anp1+An12p2+An16p3=131p1+12(12)np2+16(12)np3=13(111)+(12)n+1(101)+16(12)n(121)=(13+(12)n+1+16(12)n+11313(12)n+113(12)n+1+16(12)n+1)と求められますね。

よって、一般項はan=13+(12)n+1+16(12)n+1bn=1313(12)n+1cn=16(12)n+1と求められます。

 

(6)

((5)の計算よりもこちらのほうが簡単かも)

xn=13(111)+(12)n+1(101)+16(12)n(121)n を十分大きくすると、limxxn=13(111)となる*2

よって、十分な回数硬貨を投げるとan=bn=cnとなるので、Aくん、Bくん、Cくんがそれぞれ均等な確率で赤玉をもつ。

 

解答3

(1) 

x0=(a2a1a0)=(521)x1=Ax0=(103130100010)(521)=(1852)

 

(2) 

実はこの固有値問題は行基本変形で簡単な形にするのが難しい、行列の0の成分が2つあることなどからサラスの公式でゴリ押しで求めたほうが早く固有値を出せる。

固有値を t とすると、固有方程式は、|AtE|=|10t31301t001t|=t2(10t)+3031t=t3+10t231t+30=(t310t2+31t30)=2(t2)(t28t+15)=2(t2)(t3)(t5)より固有値は 2,3,5 となる。

 

(i) 固有値が2のときの固有ベクトル p1 (A2E)=(83130120012) (01530120012) (120012012)となる。{x2y=0y2z=0を解くと、任意定数 k を用いて(xyz)=k(421)と表せるので、固有ベクトル p1 は、p1=(421)となる。

 

(ii) 固有値が3のときの固有ベクトル p2 (A2E)=(73130130013) (01030130013) (130013000)となる。{x3y=0y3z=0を解くと、任意定数 k を用いて(xyz)=k(941)と表せるので、固有ベクトル p2 は、p2=(941)となる。

 

(iii) 固有値が5のときの固有ベクトル p3 (A5E)=(53130150015) (0630150015) (150015000)となる。{x5y=0y5z=0を解くと、任意定数 k を用いて(xyz)=k(2551)と表せるので、固有ベクトル p3 は、p3=(2551)となる。

 

(4) x0=c1p1+c2p2+c3p3(521)=c1(421)+c2(941)+c3(2551)(4925245111)(c1c2c3)=(521)となるような c1, c2, c3 の値をもとめればよい。

 

3次正方行列の逆行列はあまりおすすめしないので素直に行基本変形で求める。

 (4925523521111) (0521101301111) (006102606666) (006102016605) (006102016008) (600802010061) (100430101200116)\]となるので、c1=4/3, c2=1/2, c3=1/6 となる。よって、x0=43p112p2+16p3となる。

 

(5)

ここで、(an+2an+1an)=xn=Anx0=An(43p112p2+16p3)=43Anp1An12p2+An16p3=432np1123n(12)np2+165np3=432n(421)123n(931)+165n(2551)=(432n+2123n+2+165n+2432n+1123n+1+165n+1432n123n+165n)と求められますね。

よって、一般項はan=2n123n+165nと求められます。

 

4.さいごに

今回は差分方程式(漸化式)を行列を用いて解く流れを例題などで説明しました。

 

実際に差分方程式を解く際にはおそらく行列を使わないこちらの解き方のほうがかなり早く出せるので、線形代数の練習をしたいときや問題文で指示されたとき以外は行列で解かないほうがいいかもしれません。

 

また、万が一漸化式を直した行列 A が対角化できない場合は、ジョルダン標準形を求めたり、Anp=tnp が使えなくなるので計算過程がさらに複雑になります。

 

 

 

*1:limx(37)n=0より

*2:limx(12)n=0   limx(12)n=0より

関連広告・スポンサードリンク

おすすめの記事