スポンサーリンク

二変数または多変数の漸化式は,特性多項式で解ける

数学の解説コラムの目次へ


一変数の漸化式,たとえば 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) の値を使う。 このような漸化式による再帰法を二重再帰という(アルゴリズムの話)

数学の解説コラムの目次へ