漸化式 漸化式の解法

ウィキペディア

漸化式

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

漸化式の解法

一般的な方法

一階の漸化式については特段の理論を要しない。漸化式

$a_{n}=ra_{n-1}$

は明らかに初期値 a₀ = 1 に対して a_n = rⁿ を解にもち、一般に a₀ = k とすれば一般解 a_n = krⁿ が得られる。この漸化式の特性多項式を 0 に等しいとおいて得られる特性方程式（固有方程式）は、単に t − r = 0 で与えられることに注意。

高階の漸化式の解は、しばしば a_n = rⁿ がちょうど t = r が特性多項式の根となるような漸化式の解となるという事実を用いて、機械的に求めることができる。方法としては直接、あるいは母函数（形式的冪級数）、行列などを用いる。

たとえば

$a_{n}=Aa_{n-1}+Ba_{n-2}$

という形の漸化式を考えよう。この漸化式が a_n = rⁿ と同じ形の解の一般形をもつのはどのようなときだろうか。実際に代入してみれば

$r^{n}=Ar^{n-1}+Br^{n-2}$

が任意の n (> 1) について成り立たなければならないことがわかる。両辺を rⁿ⁻² で割れば、意味はそのままに方程式 r² − Ar − B = 0 に簡約することができる。これがこの漸化式の特性方程式である。これを r について解けば、二つの根 λ₁, λ₂ が得られる。これらの根は、特性方程式あるいは漸化式の特性根あるいは固有値として知られるものである。異なる解が得られるかは特性根の様子に依存するが、二つの特性根が相異なるならば、一般解

$a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}$

が得られる。一方、特性根が重根 (A² + 4B = 0) のとき、

$a_{n}=C\lambda ^{n}+Dn\lambda ^{n}$

が一般解を与える。これらは今考えている漸化式の解を全て尽くしており、二つの定数 C, D は初期条件 a₀, a₁ の選び方に依存して一意に決まり、これにより解がひとつに特定される。

特性根が複素数となる場合は（もちろん一般解のパラメータ C, D も複素数値となるが）、三角函数を用いた形に書けば、複素数を使用しない形にすることができる。この場合は特性根を λ_k = α ± β（各 k = 1, 2 に ± の何れか一方をそれぞれ割り当てる）の形に書いてやれば、たとえば a_n = Cλ₁ⁿ + Dλ₂ⁿ の形の一般解が

$a_{n}=2M^{n}(E\cos(n\theta )+F\sin(n\theta ))=2GM^{n}\cos(n\theta -\delta )$

の形に書きなおせることが示せる。ここで、各定数は

${\begin{aligned}&M:={\sqrt {\alpha ^{2}+\beta ^{2}}},\quad \cos \theta :={\frac {\alpha }{M}},\quad \sin \theta :={\frac {\beta }{M}},\\&C,D:=E\mp Fi,\\&G:={\sqrt {E^{2}+F^{2}}},\quad \cos \delta :={\frac {E}{G}},\quad \sin \delta :={\frac {F}{G}}\end{aligned}}$

で与えられるものである。E, F（あるいは同じことだが G, δ）は初期条件から決まる実定数である。

注意すべきは、特性根が相異なる実根の場合も、実重根の場合も、互いに共軛な複素根の場合も、すべての場合で方程式が安定である（つまり、変数 a が特定の値（特に 0）に収束する）ための必要十分条件は二つの特性根の絶対値が「ともに」1 より小さいこと、となることである。今考えている二階漸化式の場合、特性根に関するこの条件は |A| < 1 − B < 2 に同値であることが示せる。

上記の例は定数項の無い斉次の場合であった。定数項 K を加えて、非斉次の場合の漸化式

$b_{n}=Ab_{n-1}+Bb_{n-2}+K\,$

を考えよう。これは次のようにして斉次の場合に帰着することができる。不動点 b^∗ は b_n = b_n−1 = b_n−2 = b* と置くことによって、

$b^{*}={\frac {K}{1-A-B}}$

と求められる。これにより、先ほどの非斉次漸化式は

$[b_{n}-b^{*}]=A[b_{n-1}-b^{*}]+B[b_{n-2}-b^{*}]$

なる形の斉次漸化式に書き直すことができる（これは上述のように解くことができる）。

二階の場合に特性根の言葉で述べた安定性条件は、一般の n-階でもやはり有効であることに注意。つまり漸化式の解が安定であるための必要十分条件は、漸化式の特性多項式の全ての根が 1 より小さい絶対値を持つことである。

線型代数を用いた解法

線型漸化式 T_n = c_d−1Tⁿ⁻¹ + c_d−2Tⁿ⁻² + … + c₀T_n−d が与えられたとき、その特性多項式の同伴行列の転置

${\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &1\\-c_{0}&-c_{1}&-c_{2}&\cdots &-c_{d-1}\end{pmatrix}}$

を C とすると、明らかに

${\begin{pmatrix}a_{n}\\\vdots \\a_{n+(d-1)}\end{pmatrix}}=C^{n}{\begin{pmatrix}a_{0}\\\vdots \\a_{d-1}\end{pmatrix}}$

が成り立つ。固有値 λ₁, ..., λ_d に対応する固有基底 v₁, ..., v_d を決めれば、線型再帰列の初期値を固有ベクトルの線型結合

${\begin{pmatrix}a_{0}\\\vdots \\a_{d-1}\end{pmatrix}}=b_{1}v_{1}+\cdots +b_{d}v_{d}$

として表せるので、結局

${\begin{pmatrix}a_{n}\\\vdots \\a_{n+(d-1)}\end{pmatrix}}=C^{n}{\begin{pmatrix}a_{0}\\\vdots \\a_{d-1}\end{pmatrix}}=C^{n}(b_{1}v_{1}+\cdots +b_{d}v_{d})=\lambda _{1}^{n}b_{1}v_{1}+\cdots +\lambda _{d}^{n}b_{d}v_{d}$

となることがわかる。行列を用いたこの記述は、本質的には既に述べた一般的方法となんらかわるものではないが、より簡潔である。また、行列を用いた記述は

${\begin{cases}a_{n}=a_{n-1}-b_{n-1}\\b_{n}=2a_{n-1}+b_{n-1}\end{cases}}$

のような連立漸化式に対してもなお有効である。

Z変換による解法

ある種の差分方程式、とくに定数係数線型差分方程式は、Z変換を用いて解くことができる。z-変換は積分変換の一種で代数的操作がしやすく、解がより容易に求まる。解が直接には、まったくというわけではないが不可能な場合でも、積分変換をうまく選べば容易に解けることもある。

定理

階数 d の定数係数斉次線型漸化式が与えられたとき、p(t) をその特性多項式

$t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}$

とし、λ を重複度 r の特性根とする（つまり (t − λ)^r が p(t) を割り切る）。このとき、

r 個の数列 λⁿ, nλⁿ, n²λⁿ, ..., n^r−1λⁿ は与えられた漸化式をおのおの満たす。これを p(t) の相異なる全ての根 λ に亘って考えたものは、与えられた漸化式の任意の解を生成する。

この定理の帰結として、定数係数斉次線型漸化式は次の手順に従って解くことができる。

1. 漸化式の特性多項式 p(t) を求める。
2. p(t) の根とその重複度を求める。
3. a_n を未定係数 b_i を持つ（上で述べたように重複度を考慮した）全ての根の冪の線型結合
   ${\begin{aligned}a_{n}=&(b_{1}\lambda _{1}^{n}+b_{2}n\lambda _{1}^{n}+\cdots +b_{r}n^{r-1}\lambda _{1}^{n})\\&\quad +\cdots +(b_{d-q+1}\lambda _{*}^{n}+b_{d-q+2}n\lambda _{*}^{n}+\cdots +b_{d}n^{q-1}\lambda _{*}^{n})\end{aligned}}$
   として書く（q は λ_* の重複度である）。これがもとの漸化式の一般解を与えるものとなる。
4. 前段の一般解で n = 0, 1, ..., d として a₀, a₁, ..., a_d をもとの漸化式における（初期値として与えられている）既知の a₀, a₁, ..., a_d に一致させる。ただしここで、もとの漸化式の a_n の値として連続した番号のものでなくとも、どこでもいいから d 個わかってさえいればいいということには注意（つまり、考えている漸化式が三階であれば、たとえば a₀, a₁ と a₄ を使うことができる）。これにより、d 個の未知数を含む d 本の連立一次方程式が得られる。これを一般解における未定係数 b₁ , b₂, ..., b_d に対して解いて、一般解に代入してもとの漸化式の特殊解を得、それらがもとの漸化式の初期条件を満たす（したがって任意の a₀, a₁, a₂, ... についてもとの漸化式からえられる値に一致する）ことを確かめる。

興味深いのは、この方法が線型微分方程式の解法とよく似ていることである。定数係数線型微分方程式で用いられる解法では、λ を複素数として e^λ を解を求めたい方程式に代入し、方程式を満足する複素数 λ を決定する（して λⁱe^λ の線型結合を考える）。

これは偶然の一致ではない。線型微分方程式の解のテイラー級数

$\sum _{n=0}^{\infty }{\frac {f^{(n)}(a)}{n!}}(x-a)^{n}$

を考えれば、この級数の係数は f(x) の n-階導函数の x = a における値であることがわかる。与えられた微分方程式は、この級数の係数の間に成り立つ線型漸化式を導く。

この同値性は線型微分方程式の冪級数解の係数に対する漸化式を直ちに解くために利用できる。方程式は適当な多項式を掛けて点 0 における初項が 0 でないようにしておく。対応規則は

$y^{(k)}\to f(n+k)$

および一般に

$x^{m}*y^{(k)}\to n(n-1)(n-m+1)f(n+k-m)$

で与えられる。

例

方程式

$(x^{2}+3x-4)y'''-(3x+1)y''+2y=0$

のテイラー級数解の係数の満たす漸化式は

$n(n-1)f(n+1)+3nf(n+2)-4f(n+3)-3nf(n+1)-f(n+2)+2f(n)=0$

で与えられる。整理すると、

$-4f(n+3)+2nf(n+2)+n(n-4)f(n+1)+2f(n)=0$

となる。この例は非常に簡単に解くことができるふつうのクラスの微分方程式でも、冪級数解を用いた解法ではなんとも扱いづらいものとなってしまうことがあることを示すものとなっている。

例

微分方程式

$ay''+by'+cy=0$

y = e^ax を解に持つ。この微分方程式をテイラー係数の満たす漸化式に書き換えれば

$af(n+2)+bf(n+1)+cf(n)=0$

となる。e^ax の n-階導函数の点 x = 0 における値が aⁿ であることをみるのは易しい。

非斉次漸化式の解法

漸化式が非斉次の場合、特殊解は未定係数法で求めることができて、一般の解は対応する斉次漸化式の一般解と先ほど得た特殊解の和として得られる。非斉次漸化式のほかの解法としては、記号微分 (symbolic differentiation) の方法がある。たとえば、次のような漸化式

$a_{n+1}=a_{n}+1$

を考える。これは非斉次の漸化式である。n → n + 1 と置き換えれば、漸化式

$a_{n+2}=a_{n+1}+1$

を得る。もとの漸化式から辺々引いて整理すれば、

$a_{n+2}=2a_{n+1}-a_{n}$

が得られる。これは斉次の漸化式であるから、既に述べた方法によって解くことができる。一般に、線型漸化式が

$a_{n+k}=\lambda _{k-1}a_{n+k-1}+\lambda _{k-2}a_{n+k-2}+\cdots +\lambda _{1}a_{n+1}+\lambda _{0}a_{n}+p(n)$

という形（λ₀, λ₁, ..., λ_k−1 は定数の係数で、p(n) が非斉次成分）で与えられて、P(n) が r-次の多項式ならば、記号微分の方法を r 回適用することにより、この非斉次漸化式を斉次漸化式に帰着することができる。

一般の斉次線型漸化式

多くの斉次線型差分方程式は一般化超幾何級数を使って解くことができる。その特殊な場合として、差分方程式から直交多項式系や特殊函数が解として現れてくる。たとえば、

$J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1}$

の解はベッセル関数

$J_{n}=J_{n}(z)\,$,

によって与えられる。 一方、

$(b-n)M_{n-1}+(2n-b-z)M_{n}-nM_{n+1}=0$

は合流型超幾何級数

$M_{n}=M(n,b;z)$

によって解ける。

有理差分方程式の解法

有理差分方程式は

$w_{t+1}={\frac {aw_{t}+b}{cw_{t}+d}}$

というような形をしている。このような方程式は w_t を、それ自身は線型に増加する別の変数 x_t の非線型変換として書くことで解くことができる。したがって、x_t に関する線型差分方程式を解くのに、標準的な方法が使える。