漸化式 漸化式の概要

ウィキペディア

漸化式

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/23 14:42 UTC 版)

ある種の漸化式はしばしば差分方程式 (difference equation) と呼ばれる。また、「差分方程式」という言葉を単に「漸化式」と同義なものとして扱うことも多い。

漸化式の例として、ロジスティック写像

${\displaystyle x_{n+1}=rx_{n}(1-x_{n})}$

が挙げられる。このような単純な形の漸化式が、しばしば非常に複雑な（カオス的な）挙動を示すことがあり、このような現象についての研究は非線型解析学などと呼ばれる分野を形成している。

漸化式を解くとは、 添字 n に関する非再帰的な函数として、一般項を表す閉じた形（英語版）の式を得ることをいう。

簡単な例

フィボナッチ数列は線型漸化式

${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$

に初期値、${\displaystyle F_{0}:=0,\ F_{1}:=1}$を与えて得られる。

この漸化式は、陽に書けば ${\displaystyle F_{2}=F_{1}+F_{0},\ F_{3}=F_{2}+F_{1},\ F_{4}=F_{3}+F_{2},\dots }$ といった無限個の式と同じである。

こうして得られるフィボナッチ数列のはじめのほうを書けば

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

となる。後述するような方法で漸化式を解けば、特性多項式（固有多項式） t² - t - 1 の二つの根を用いた閉じた式（英語版）が得られる。フィボナッチ数列の母関数は

${\displaystyle {\frac {t}{1-t-t^{2}}}}$

という有理式である。

構造

定数係数斉次線型漸化式

定数係数の d-階斉次線型漸化式は、一般に

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d}}$

の形に表される式で、d 個の係数 c_i はすべての i について定数となるものである。

一般にd-階斉次線型漸化式の解は、異なる公比をもつ d-個の幾何数列の和として表される。例外は、それらの幾何数列の公比を与える方程式の根が重根を持つ場合である^[1]。このように幾何数列の和として書かれた式をビネーの公式 (Binet's formula) という^[2]（ただし「ビネーの公式」という名称は、フィボナッチ数列の一般項を二つの冪数列の和として表す式の意味で用いられることのほうが多い）。

もう少し詳しく言えば、この線型漸化式は各 n (> d − 1) に対する無限本の線型方程式に関する連立方程式であり、この形の漸化式を満たす列は線型回帰数列 (linear recursive sequence) と呼ばれ、あるいは短く "LRS" とも呼ばれる。d-階の線型再帰列は初期値 a₀, ..., a_d−1 を任意に選ぶ分だけの自由度 d を持ち、それら初期値に対して一意に決定される。

この形の線型漸化式と同じ係数を持つ、漸化式の固有多項式または特性多項式 (characteristic polynomial) あるいは補助多項式 (auxiliary polynomial) と呼ばれる多項式

${\displaystyle p(t):=t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}}$

は、その d 個の根が漸化式を満たす数列を求め、理解するのにきわめて重要な役割を果たす。

有理母関数

線型再帰列は、その母函数が有理函数となるような数列として特徴付けられる。母函数の分母は（適当な変換をうける違いを除いて）特性多項式であり、分子は初期値から決まる。

もっとも単純なものは、a_n = a_n−d なる周期数列 a₀, a₁, ..., a_d−1, a₀, a₁, ... の場合であり、この列の母函数は幾何数列の和

${\displaystyle {\begin{aligned}&{\frac {a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}}{1-x^{d}}}\\[9pt]&=\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)\\&\qquad +\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)x^{d}\\&\qquad +\left(a_{0}+a_{1}x^{1}+\cdots +a_{d-1}x^{d-1}\right)x^{2d}+\cdots \end{aligned}}}$

として表される。もっと一般に、漸化式

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d}}$

と母函数

${\displaystyle a_{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots }$

が与えられたとき、多項式

${\displaystyle 1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d}}$

を使って、母函数級数の a_d 以降の係数を消去することができる。つまり、母函数に先の多項式を掛け合わせれば

${\displaystyle b_{n}:=a_{n}-c_{1}a_{n-1}-c_{2}a_{n-2}-\cdots -c_{d}a_{n-d}}$

が xⁿ の係数となり、これは特に n ≥ d のとき（漸化式によって）0 となる。したがって、

${\displaystyle (a_{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots {})(1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d})=(b_{0}+b_{1}x^{1}+b_{2}x^{2}+\cdots +b_{d-1}x^{d-1})}$

が成立し、両辺を割り算すれば

${\displaystyle a_{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots ={\frac {b_{0}+b_{1}x^{1}+b_{2}x^{2}+\cdots +b_{d-1}x^{d-1}}{1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d}}}}$

という母函数の有理式表示を得る。

分母 x^dp(1/x) は特性多項式を変換したもの（あるいは同じことだが、係数の順番を逆順にしたもの）である。これに何かを掛けたものを使うこともできるが、特性多項式から簡単に求められて、b₀ = a₀ となるように正規化してある。

狭義の差分方程式との関係

実数列 (a_n)_n=1^∞ が与えられたとき、この数列の第一階差 (first difference) Δ(a_n) は

${\displaystyle \Delta (a_{n}):=a_{n+1}-a_{n}}$

で与えられ、第二階差 (second difference) Δ²(a_n) が

${\displaystyle \Delta ^{2}(a_{n}):=\Delta (a_{n+1})-\Delta (a_{n})}$

あるいは簡約化して

${\displaystyle \Delta ^{2}(a_{n}):=a_{n+2}-2a_{n+1}+a_{n}}$

で与えられる。もっと一般に、数列 (a_n) の第 k-階差 (k^th difference) Δ^k(a_n) が

${\displaystyle \Delta ^{k}(a_{n}):=\Delta ^{k-1}(a_{n+1})-\Delta ^{k-1}(a_{n})}$

で帰納的に定義される。狭い意味での差分方程式とは数列 (a_n) およびその各階の階差数列との間に成り立つ等式のことをいう。広い意味では「差分方程式」を「漸化式」と同義に用いる（たとえば有理差分方程式（英語版）および線型差分方程式を参照）。

線型漸化式は狭い意味での差分方程式であり、逆もいえる。それはこれらが単純かつ共通した形の再帰性をもつからであり、文献によっては両者を逆に呼んでいるものもある。たとえば差分方程式

${\displaystyle 3\Delta ^{2}(a_{n})+2\Delta (a_{n})+7a_{n}=0}$

は、漸化式

${\displaystyle 3a_{n+2}=4a_{n+1}-8a_{n}}$

と同値である。よって、多くの漸化式は差分方程式として読み替えて解くことができるし、差分方程式ならば常微分方程式の解法と類似の手法で解くことができる。しかし、アッカーマン関数などは差分方程式に直すことが非常に困難であり、微分方程式の観点から得られるものは少ない。

このような微分方程式に対する微分方程式論の一意化については時間尺度微分積分学を参照せよ。

微分方程式に対をなすように積分方程式が考えられるのと同様、差分方程式の対となる和分方程式が考えられる。

格子点と多重数列

一変数（一元）漸化式は（一次元整格子点 (grid) の上で定義される函数としての）数列について記述するものである。多変数（n-元）漸化式は同様に n-次元整格子点 (n-grid) 上で定まる概念であると理解することができる。n-次元整格子点上で定義される函数（n-重数列）についても偏差分方程式 (partial difference equations) を考えることができる^[3]。