漸化式
数学における漸化式(ぜんかしき、英: recurrence relation; 再帰関係式)は、各項がそれ以前の項の関数として定まるという意味で数列を再帰的に定める等式である。
ある種の漸化式はしばしば差分方程式 (difference equation) と呼ばれる。また、「差分方程式」という言葉を単に「漸化式」と同義なものとして扱うことも多い。
漸化式の例として、ロジスティック写像
x n + 1 = r x n ( 1 − x n ) {\displaystyle x_{n+1}=rx_{n}(1-x_{n})}
が挙げられる。このような単純な形の漸化式が、しばしば非常に複雑な(カオス的な)挙動を示すことがあり、このような現象についての研究は非線型解析学などと呼ばれる分野を形成している。
漸化式を解くとは、 添字 n に関する非再帰的な函数として、一般項を表す閉じた形(英語版)の式を得ることをいう。
非線型一階漸化式
x n = f ( x n − 1 ) {\displaystyle x_{n}=f(x_{n-1})}
を考える。この漸化式は(不動点 x の十分近くにある点は不動点 x に収斂するという意味で)局所安定であるための必要十分条件は、x の近傍で f の傾きの絶対値が 1 よりも小さいこと、つまり
| f ′ ( x ∗ ) | < 1 {\displaystyle |f'(x^{*})|<1}
が成り立つことである。非線型漸化式は複数の不動点を持つことができ、ある不動点は局所安定だが別の不動点は局所安定でないということも起こりうることに注意。f が連続なら隣接するふたつの不動点がともに局所安定となることはできない。
非線型漸化式は k > 1 なる k を周期とするサイクルをもつこともありうる。そのようなサイクルが(測度正の初期条件集合を吸引するという意味で)安定となる十分条件は、f の k 回合成
g ( x ) := f ∘ f ∘ ⋅ ⋅ ⋅ ∘ f ( x ) {\displaystyle g(x):=f\circ f\circ \cdot \cdot \cdot \circ f(x)}
が上記と同様の判定条件
| g ′ ( x ∗ ) | < 1 {\displaystyle |g'(x^{*})|<1}
に従って局所安定となることである。ここで x はサイクルの任意の点。
カオス的漸化式においては、変数 x がある有界領域に留まるが不動点にも吸引的サイクルにも収束しない。そのような方程式において任意の不動点やサイクルは不安定である。 ロジスティック写像、二進変換(英語版)、テント写像なども参照。
興味深いのは、この方法が線型微分方程式の解法とよく似ていることである。定数係数線型微分方程式で用いられる解法では、λ を複素数として e を解を求めたい方程式に代入し、方程式を満足する複素数 λ を決定する(して λe の線型結合を考える)。
これは偶然の一致ではない。線型微分方程式の解のテイラー級数
∑ n = 0 ∞ f ( n ) ( a ) n ! ( x − a ) n {\displaystyle \sum _{n=0}^{\infty }{\frac {f^{(n)}(a)}{n!}}(x-a)^{n}}
を考えれば、この級数の係数は f(x) の n-階導函数の x = a における値であることがわかる。与えられた微分方程式は、この級数の係数の間に成り立つ線型漸化式を導く。
この同値性は線型微分方程式の冪級数解の係数に対する漸化式を直ちに解くために利用できる。方程式は適当な多項式を掛けて点 0 における初項が 0 でないようにしておく。対応規則は
y ( k ) → f ( n + k ) {\displaystyle y^{(k)}\to f(n+k)}
および一般に
x m ∗ y ( k ) → n ( n − 1 ) ( n − m + 1 ) f ( n + k − m ) {\displaystyle x^{m}*y^{(k)}\to n(n-1)(n-m+1)f(n+k-m)}
で与えられる。