二変数または多変数の漸化式は,特性多項式で解ける
一変数の漸化式,たとえば a_n についての漸化式は,簡単に解ける。
特性多項式をたてればよい。
では一変数ではなく二次元だと,漸化式の解法はどうなるか?
隣接した多項の1変数漸化式ではない。 a_n と b_n のように二変数ということ。
多変数であっても,特性多項式で解ける
変数の数が複数であっても,
機械的に漸化式の一般項を求めるための計算法が存在する。
それが,特性多項式を用いる方法。
一般項に「べき乗」を仮定してみるとうまくいく
概略を述べると,
一番簡単な形の漸化式 a_n = r a_{n-1} の解は,r の「べき乗」で与えられる。
だから,もっと複雑な形の漸化式であっても,何かの「べき乗」を組み合わせた形で表せる,
そうに違いない・・・。
と仮定した場合に出現するのが,漸化式の特性方程式(固有方程式)だ。
「特性多項式」をもっと詳しく
特性多項式についての詳しい情報。
二次元のtとnに関する漸化式 P(t,n)=P(t-1,n-1)/2 + P(t,n+1)/2 + a * (1/2)^(N-n...
http://detail.chiebukuro.yahoo.co.jp/...
- まず解の形として,べき乗を含む関数を仮定している
漸化式 - Wikipedia
http://ja.wikipedia.org/wiki/%E6%BC%B...
- 格子点と多重数列:一変数(一元)漸化式は(一次元整格子点 (grid) の上で定義される函数としての)数列について記述するものである。
- 多変数(n-元)漸化式は同様に n-次元整格子点 (n-grid) 上で定まる概念であると理解することができる。n-次元整格子点上で定義される函数(n-重数列)についても偏差分方程式 (partial difference equations) を考えることができる。
- そして特性多項式の話。
数列 - Wikipedia
http://ja.wikipedia.org/wiki/%E6%95%B...
- 二つの異なる数列が存在して,それらが連立線型漸化式を成立させる時,行列を使って計算できる
Comp Prog DosC Note 381
http://chausson.eng.kagawa-u.ac.jp/Co...
- 2変数のそれぞれが関わるような漸化式を二重漸化式という
Comp Prog DosC Note 476
http://chausson.eng.kagawa-u.ac.jp/Co...
- 多変数の漸化式と多重再帰。二変数の漸化式では、F(n,m) の定義に、F(n-1, m), F(n, m-1), F(n-1, m-1) の値を使う。 このような漸化式による再帰法を二重再帰という(アルゴリズムの話)