差分方程式（漸化式）

　そこらじゅうに現れる漸化式を Maxima で，まとめてみよう。まずは数列で出現。
Maxima でいうと，関数の再帰的定義が使える。

その１　具体例は，なんといってもリュカ（フランスの数学者）のハノイの塔でしょう。
パズル雑誌に付録としてついていたハノイの塔が，漸化式の授業ではいい教材だ。１００円ショップにもある。
どころか，入試問題にもそのまま出たことがある。



Maxima でこれをやろうとすると，方法はいくつか考えられる。
@BASIC 的にやったもの。
A配列を使った数列に一番近いと思われるもの。
B最後のものが，関数の再帰的定義。
@Aは数列の帰納的（inductive）定義つまり漸化式，小さい方から大きい方へ決めていくもの。
Bは漸化式を再帰的（reflexive）に定義した，大きい方から小さい方へ調べていくもの。

(%i1) a:1$for i:1 thru 10 do
(print(a),a:2*a+1);
Result

(%i3) array(a,10)$a[1]:1$for i:1 thru 9 do a[i+1]:2*a[i]+1$

(%i6) for i:1 thru 10 do print(a[i]);
Result

(%i7) f1(x):=block(if(x=1)then return(1),return(2*f1(x-1)+1))$

(%i8) for i:1 thru 10 do print(f1(i));
Result

(%i9) kill(a);

漸化式を解くのは「数B」で説明済み。

(%i10) load(solve_rec)$

(%i11) solve_rec(a[n+1]=2*a[n]+1,a[n],a[1]=1);

Result

(%i12) load(dynamics)$

(%i13) staircase(2*x+1,2,5,[gnuplot_preamble, "set zeroaxis"]);


これ以上の解説は「フラクタルとカオス」参照。

その２　それから，百花繚乱，フィボナッチの数列。前が隣接２項間漸化式，これが隣接３項間漸化式。
ここらへんになると，再帰的定義を使うと実は時間がかかりだす。一つの項で戻って戻ってとどんどん繰り返すので時間がかかるのだ。
（Maxima には fib(i) で i 番目のフィボナッチ数をかえす関数がある。）

(%i1) a:1$b:1$print(a)$print(b)$for i:1 thru 10 do
(c:a+b,a:b,b:c,print(c));
Result

(%i6) array(a,12)$a[1]:1$a[2]:1$for i:1 thru 10 do a[i+2]:a[i+1]+a[i]$

(%i10) for i:1 thru 12 do print(a[i]);
Result

(%i11) f2(x):=block(if(x=1)then return(1),if(x=2)then return(1),return(f2(x-1)+f2(x-2)))$

(%i12) for i:1 thru 12 do print(f2(i));
Result

(%i13) kill(a);

解くのも同上だが，隣接３項間漸化式の階段図は私の作。
詳しくは「Maxima で隣接３項間漸化式を目で見る」参照

(%i14) load(solve_rec)$

(%i15) solve_rec(a[n+2]=a[n+1]+a[n],a[n],a[1]=1,a[2]=1);

Result

(%i16) load(draw)$load(descriptive)$

(%i18) staircase2(p,q,s,t,m):=block(
a[1]:s,a[2]:t,
for i:1 thru m do
    a[i+2]:p*a[i+1]+q*a[i],
    l1:makelist(a[k],k,1,m-1),
    l2:makelist(a[k],k,2,m),
    m1:max(maxi(l1),maxi(l2)),
    m2:min(mini(l1),mini(l2)),
        draw2d(
        points_joined=true,
        point_type = 6,
        point_size = 1,
        color=blue,
        points(l1,l2),
        color=green,
        points([m2,m1],[m2,m1]),
        points([m2,m1],[0,0]),
        points([0,0],[m2,m1])
        )
)$

(%i19) staircase2(1,1,1,1,12)$


これ以上の解説は「フラクタルとカオス」参照。

その３　入試問題に欠かせないのは，確率の漸化式でしょう。
これがまた面白いことがあるんだ。「世界を変えた手紙」という本，
原題「THE UNFINISHED GAME Pascal,Fermat,and the Seventeenth-Century Letter that Made the World Modern」
確率計算の歴史をまとめてある本なのだが，ゲームを途中でやめた（UNFINISHED GAME）ときの賞金の分け方についてかわしたパスカルとフェルマーの手紙が中心。
フェルマーはすべての場合を調べつくす方法，パスカルは漸化式という方法でこれを解いたとある。
これなんか実に，再帰的定義にあっていると思われる。

パスカルは例の三角形でも有名だが（これも漸化式で表現される），もともと確率と漸化式はその理論の初めから密接なのだった。
例えば，

(%i1) e(a,b):=block(if(a=b) then return(1/2),
if(a=0)then return(1),
if(b=0)then return (0),
return((e(a-1,b)+e(a,b-1))/2))$

(%i2) e(1,2);

Result

(%i3) e(2,3);

Result

パスカルがフェルマーに手紙で質問したのはこの３人バージョン。２人勝つという状態がありうるので,何回戦やるか決めないと確率が変わる。

(%i4) e2(a,b,c):=block(if(a=b and a=c) then return(1/3),
if(a=0)then return(1),
if(b*c=0)then return(0),
return((e2(a-1,b,c)+e2(a,b-1,c)+e2(a,b,c-1))/3))$

(%i5) e2(1,2,2);

Result

(%i6) e2(2,3,3);

Result

(%i7) e3(a,b,c,n):=block(
    if(a=b and a=c) then return(1/3),
    if(a=0)then return(1),
    if(b*c=0)then return(0),
    if(n=0 and min(a,b,c)=a and(a=b or a=c))then return(1/2),
    if(n=0 and min(a,b,c)=a)then return(1),
    if(n=0 and min(a,b,c)# a) then return(0),
    return((e3(a-1,b,c,n-1)+e3(a,b-1,c,n-1)+e3(a,b,c-1,n-1))/3)
)$

(%i8) for i:0 thru 6 do print(e3(2,3,3,i));

Result

上の本は 16/27 の答えが間違っているように書いてあるし，漸化式の方法（パスカル）よりすべての場合を数え上げる方法（フェルマー）のほうが優れているとあったので（訳者は否定していたが）どうも納得がいかなかったが，ここまでやってやっと納得した。 inserted by FC2 system