漸化式の計算法
1
特性方程式による解法
まず次のような例題を考える：
いまここに産まれたての一つがいのウサギがいる。この一つがいが成長して二年
後からは毎年一つがいずつ産んでいくものとする。生まれたばかりの一つがいも，
同様に二年後からは毎年一つがいずつ産んでいくものとする。そうすると n 年後
には合計何つがいになっているだろうか。
最初の年 (0 年とする) にいた一つがいは，次の年 (1 年とする) にはまだ子供を産めないので，
次年の年末にはまだ一つがいである。この一つがいは翌々年 (2 年) には新たに一つがいを産むの
で，2 年末には合計二つがいになる。 3 年末には，この二つがいのうち初めからいた方がまた一
つがい産むので，合計三つがいになる。このように数えていくと下の表のようになる。
ウサギのつがい数
年
つがい
0
1
2
3
4
5
···
···
1
1
2
3
5
8
···
···
ここで，n 年末と n+1 年末のつがい数をそれぞれ fn と fn+1 とする。そうすると n+2 年には，
n 年末にいた fn つがいがそれぞれ一つがい産むので，年末は fn つがい増えて，fn+2 = fn+1 +fn
つがいとなる。したがって fn の値は，差分方程式 (漸化式) (difference equation)
fn+2 = fn+1 + fn ,
f0 = f1 = 1
(1)
を計算していけば順次求まることになる。上式で表される数列 {fk } は フィボナッチ数列 (Fibonacci
sequence) と呼ばれでいる。
下に fn を計算する C によるプログラムを示す。
1: #include <stdio.h>
2: main()
3: {
4:
int n,f[11];
5:
f[0]=1; f[1]=1;
6:
printf("
n
f_n \n");
7:
8:
for (n=0; n<=8; n++)
9:
f[n+2]=f[n+1]+f[n];
10:
1
11:
for (n=0; n<=10; n++)
12:
printf(" %2d %3d \n",n,f[n]);
13: }
実行結果
n
f_n
0
1
1
1
2
2
3
3
4
5
5
8
6 13
7 21
8 34
9 55
10 89
これを配列を用いないで書くとつぎのようなプログラムになる。
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
#include <stdio.h>
main()
{
int n,f0=1,f1=1,f2;
printf("
n
f_n \n");
n=0;
printf("
n=1;
printf("
%2d %3d \n",n,f0);
%2d %3d \n",n,f1);
for (n=2; n<=10; n++) {
f2=f1+f0;
printf(" %2d %3d \n",n,f2);
f0=f1; f1=f2;
}
}
ここで数値計算によらず，解析的な手法によって式 (1) の解を求めることを考える。まず fn
を
fn = λn ,
λ = 0
(2)
と置いてみる。これを式 (1) に代入して両辺を λn で割ると
λ2 − λ − 1 = 0
(3)
となる。この方程式は差分方程式 (1) の 特性方程式 (characteristic equation) と呼ばれている。
特性方程式 (3) の解は
√
√
1+ 5
1− 5
,
λ2 =
λ1 =
2
2
となるので，n にも λ にも依らない定数 c1 , c2 を用いて
fn = c1 λn1 + c2 λn2
2
(4)
と表したのが差分方程式 (1) の 一般解 (general solution) になる。ここで，任意定数 c1 , c2 を初
期条件
f0 = f1 = 1
にあわせて決めると
√
√
1+ 5
−1 + 5
√
c1 = √ ,
c2 =
2 5
2 5
を得る。これを式 (4) に代入すると，解は
⎧
⎫
√ n+1 √ n+1 ⎬
⎨
1+ 5
1
1− 5
fn = √
−
,
⎭
2
2
5⎩
(5)
n = 0, 1, . . .
(6)
となる。
一般の差分方程式
fn+2 = a fn+1 + b fn ,
f0 = α, f1 = β
(7)
に対しては，同様に特性方程式
λ2 − a λ − b = 0
(8)
を求め，その解 λ1 , λ2 から一般解
fn = c1 λn1 + c2 λn2
を求め，それに含まれる任意定数 c1 , c2 を初期条件にあわせて決める。ここで特性方程式 (8) が
重解 λ を持つ場合は
fn = (c1 + c2 n) λn
(9)
が一般解になる (演習問題４参照)。
演習問題
1. 式 (4) で与えられる解 (一般解) が方程式
fn+2 = fn+1 + fn
を満たすことを示せ。
2. 定数 c1 , c2 が式 (5) で与えられることを示せ。
3. 式 (4) で与えられる fn は
lim
n→∞
fn+1
= λ1
fn
を満たすことを示せ。
4. 特性方程式 (8) において，a2 + 4 b = 0 が成り立っているとき，この方程式は重解 λ = a/2
を持つ。このとき，漸化式 (7) の一般解は (9) になることを示せ。
5. 次の漸化式を初期条件のもとに解け。
(a) fn = 2 fn−1 + 1, f0 = 1
(b) fn = 2 fn−1 ,
3
2
f0 = 1
fn+1 − 12 fn ,
(c) fn = 5 fn−1 − 6 fn−2 ,
f0 = 1, f1 = 0 (d) fn+2 =
(e) fn = 6 fn−1 − 9 fn−2 ,
f0 = 1, f1 = 6 (f) fn+2 = 4 fn+1 − 4fn ,
3
f0 = 0, f1 = 1
f0 = 0, f1 = 1
6. 長さ n (n ≥ 2) のビット列で 0 が 2 つ連続して続かないものの数を fn で表す。
(a) f2 , f3 を求めよ。
(b) fn が満たす漸化式を求めよ。
(c) f5 を求めよ。
7. 長さ 1 秒の符号 A と長さ 2 秒の符号 B を用いて，AABABA· · · , BABAA· · · のような
メッセージを送りたい。 n (n ≥ 2) 秒で送れるメッセージの総数を fn で表す。
(a) f1 , f2 を求めよ。
(b) fn の満たす漸化式を求めよ。
(c) fn を n の関数で表せ。
8. 次の漸化式の解を求めよ。
fn = 6 fn−1 − 11 fn−2 + 6 fn−3 ,
f0 = 2, f1 = 5, f2 = 15
9. 漸化式 Ln+1 = Ln + Ln−1 , L0 = 1, L1 = 3 で与えられる数列 Ln は
Ln = fn+1 + fn−1
を満たすことを数学的帰納法を用いて示せ。ここで fn はフィボナッチ数である。
2
行列による解法
こんどは次の問題を考える：
現在 A 市の人口は 10,000 人で，隣の B 村の人口はたった 1,000 人である。に
もかかわらず，B 村では人口の 6 割もが毎年 A 市に流れ，逆に A 市から B 村
へ移動するのは，毎年 A 市の人口の 1 割に過ぎない。このままでは B 村は 10
年後には消滅しているのだろうか。
n 年における A 市と B 村の人口をそれぞれ an , bn とする。この二市町村以外からの流出流
入はなく，また出生死亡による変化もないとすると，翌年の人口 an+1 , bn+1 は
an+1 = 0.9 an + 0.6 bn ,
a0 = 10000
bn+1 = 0.1 an + 0.4 bn ,
b0 = 1000
(10)
で表される。この式を計算機で計算してみると， 10 年後には B 村は消滅するどころか， 50%も
増えているという意外な結果が得られた。
1: #include <stdio.h>
2: int main ()
3: {
4:
double a[11],b[11];
5:
int n;
6:
a[0]=10000;
4
7:
8:
9:
10:
11:
12:
13:
14:
15:
16: }
b[0]=1000;
for (n=0; n<10; n++) {
a[n+1]=0.9*a[n]+0.6*b[n];
b[n+1]=0.1*a[n]+0.4*b[n];
}
printf(" 年 A 市 B 村 \n");
for (n=0; n<=20; n++)
printf(" %2d %9.0f
%9.0f \n",n,a[n],b[n]);
年 A 市 B 村
0
10000
1000
1
9600
1400
2
9480
1520
3
9444
1556
4
9433
1567
5
9430
1570
6
9429
1571
7
9429
1571
8
9429
1571
9
9429
1571
10
9429
1571
式 (10) を行列とベクトルを用いて表すと
an+1
0.9 0.6
an
=
bn+1
bn
0.1 0.4
となる。この行列を A で表すと an , bn は
an
a0
= An
bn
b0
(11)
(12)
と表される。
ここで A のベキ An の計算法を考える。まず，行列 A の固有値は
λ1 = 1,
λ2 = 0.3
となる。一方これらの固有値に対応する固有ベクトルを p1 , p2 とすると
1
1
p1 = 1 ,
p2 =
−1
6
となる。したがって，行列 A は T = (p1 , p2 ) という行列によって
1 0
A=T
T −1
0 0.3
のように 対角化 (diagonalize) できる。これより
n
1
0
1
0
An = T
T −1 = T
T −1
0 0.3
0 0.3n
5
(13)
を得る。T −1 は
T −1
6
=
7
となる。以上より An を計算すると
6
A =
7
n
となり
an
bn
6
=
7
1
1
6
0.3n
6
1−0.3n
6
1+
1
−1
1 − 0.3n
1
n
6 + 0.3
n
(1 + 0.36 ) a0 + (1 − 0.3n ) b0
n
(1 − 0.36 ) a0 + ( 16 + 0.3n ) b0
(14)
(15)
を得る。n = 20 のとき 0.3n = 5.90 × 10−6 なので，これを 0 で置き換えると
a10 =
6
(a + b0 ) = 9429,
7 0
b10 =
1
(a + b0 ) = 1571
7 0
となり，数値計算結果と同じ結果が得られる。
別解
仮定より A 市と B 村の人口の和は一定だから an + bn = 11000 である。これを式 (10) の最
初の式に代入すると
an+1 = 0.9 an + 0.6 (11000 − an )
= 0.3 an + 0.6 × 11000
(16)
を得る。これを解いて
an = α + 0.3n (a0 − α)
(17)
となる。ここで α は
α = 0.3 α + 0.6 × 11000
の解である。式 (17) より limn→∞ an = α となる。α = 67 × 11000 ≈ 9429 なので，n = 10 のと
き 0.310 = 5.9 × 10−6 となり，an ≈ α = 9429 となり，前と同じ結果が得られる。
6
© Copyright 2024 ExpyDoc
