漸化式の数理 - 微分方程式との類似から

9 min read読了の目安(約8200字

先日 Fibonacci 数列の一般項を計算する記事を書いたのですが,それに関連して M 項間(線形)漸化式の解き方について,初等微分方程式論と完全にパラレルになるよう解説してみます.
おそらくプログラミングにはまったく役立ちません.(なぜなら,特性方程式が代数的に解けるとは限らないので.)

次の M 項間漸化式を解く,というタスクを考えます:

\begin{cases} x_n = a_n, & (0 \leqslant n \leqslant M - 2), \\ \displaystyle x_{n + M - 1} = \sum_{i = 0}^{M - 2} \lambda_i x_{n + i} + c, & (n \geqslant 0). \end{cases}

ここで,a_0, \dotsc, a_{M - 2} \in \mathbb{C} は与えられた初期値で,c, \lambda_0, \dotsc, \lambda_{M - 2} \in \mathbb{C} は漸化式の係数です.もちろん \lambda_0 \neq 0 を仮定します.(\lambda_0 = 0 なら M - 1 項間漸化式になってしまうので.)

M = 1 のときは自明な漸化式 x_n = c となり面白くないので,以下 M \geqslant 2 とします.(大半の議論は M = 1 でも成り立ちます.)

簡単のため,(初期条件を無視した)漸化式 x_{n + M - 1} = \sum_{i = 0}^{M - 2} \lambda_i x_{n + i} + c を (RE) と呼び(recurrence equation),(RE) からさらに定数項 c を除いたもの x_{n + M - 1} = \sum_{i = 0}^{M - 2} \lambda_i x_{n + i} を (RE-h) と呼びましょう(homogeneous).
この (RE) の解き方は M 階常微分方程式と同じです:

  1. (RE-h) の解(斉次解)のうち,線形独立なもの M 個を探す;
  2. (RE) の解(特解)を一つ見つける;
  3. 「斉次解の線型結合と特解の和」のうち,初期条件を満たすものが求める解である.

以下では複素数体 \mathbb{C} 上で考えますが,一般の体(と特性多項式の分解体)上でも同じ議論が成立します.

(注:正標数の体にも拡張することを念頭に置いているので,議論がやや冗長な部分もあります.)

解の線形性

この (RE-h) の解全体のなす集合(解空間

X := \left\{ (x_n)_{n = 0}^\infty \subset \mathbb{C} \mid \text{satisfies (RE-h)} \right\}

\mathbb{C} 上のベクトル空間となります.すなわち,(x_n)_n, (y_n)_n \in X を (RE-h) の解,\lambda \in \mathbb{C} をスカラーとしたとき,(x_n + y_n)_n, (\lambda x_n)_n もまた (RE-h) の解となります.

このベクトル空間 X は,より大きなベクトル空間

S := \mathrm{Map} (\mathbb{Z}_{\geqslant 0}, \mathbb{C}) = \left\{ (x_n)_{n = 0}^\infty \subset \mathbb{C} \right\}

の部分空間となっています.

差分演算子

この空間 S における線形独立性を調べるために,まず差分演算子というものを導入します.

差分演算子とは,次の式で定まる S 上の線形作用素 p : S \to S のことです:

p x_\bullet = x_\bullet [1] - x_\bullet \quad (x_\bullet = (x_n)_n \in S).

ただし,一般に整数 k \in \mathbb{Z} に対し,数列 x_\bullet = (x_n)_n \in Sk シフト x_\bullet [k] \in S(x_\bullet [k])_n = x_{n + k} で定義されます.

言い換えれば,差分演算子とは (p x_\bullet)_n = x_{n + 1} - x_n のことです.
あるいは,x_{n + 1} = (p x_\bullet)_n + x_n であるとも言えます.

つまり x_\bullet [1] = (p + 1) x_\bullet が成り立つ(1 \in \mathrm{End}_{\mathbb{C}} (S) は恒等作用素を表す)ので,一般に x_\bullet [k] = (p + 1)^k x_\bullet となります.

注:p という記号は,物理学の運動量演算子を元にしています.もちろん,p でなく D でも構いません.

続いて,q という線形作用素を,

(q x_\bullet)_n = n x_n \quad (x_\bullet \in S)

で定義します.(q という記号も,やはり物理学の座標演算子が元になっています.)

一般に,多項式 P (t) = \sum a_i t^i \in \mathbb{C} [t] に対して,P (q) という線形作用素を P (q) = \sum a_i q^i で定義します.つまり

(P (q) x_\bullet)_n = \left( \sum a_i n^i \right) x_n

となっています.ただし,(q^0 x_\bullet)_n = n^0 x_n が成り立つように,便宜上 0^0 = 1 としておきましょう.

差分演算子の固有値

さて,零でない複素数 \psi \in \mathbb{C}^\times = \mathbb{C} \setminus \{ 0 \} に対して,その冪列 \psi^\bullet = (\psi^n)_n \in S を考えましょう.

簡単に分かるように

(p \psi^\bullet)_n = \psi^{n + 1} - \psi^n = (\psi - 1) \psi^n

なので,\psi^\bulletp固有値 \psi - 1 に属する固有ベクトルとなります.

より一般に,零でない任意の多項式 0 \neq P (t) \in \mathbb{C} [t] に対して P (q) \psi^\bullet は固有値 \psi - 1 の一般固有ベクトルであり,(p - \psi + 1)^{\deg P + 1} P (q) \psi^\bullet = 0 が成り立ちます.

そのことを d = \deg P に関する帰納法で確かめてみましょう.

d = 0 のときは P (t) = \mathrm{const} なので,すでに確認したとおりです.

d - 1 次以下の多項式に対して主張が成立したと仮定します.このとき P (t) = t^d に対して (p - \psi + 1)^{d + 1} q^d \psi^\bullet = 0 を示せば十分ですね.

\left( p q^d \psi^\bullet \right)_n = (n + 1)^d \psi^{n + 1} - n^d \psi^n = \left( \psi (n + 1)^d - n^d \right) \psi^n

が成り立つので,

\left( (p - \psi + 1) q^d \psi^\bullet \right)_n = \psi \left( (n + 1)^d - n^d \right) \psi^n = \left( Q (q) \psi^\bullet \right)_n

となります.ただし,Q (t) := \psi ((t + 1)^d - t^d) \in \mathbb{C} [t] と置きました.

Q (t)d - 1 次(以下)の多項式なので (p - \psi + 1)^d Q (q) \psi^\bullet = 0 であり,結局 (p - \psi + 1)^{d + 1} q^d \psi^\bullet = 0 を得ます.

冪の線形独立性

線形代数でよく知られたように,異なる固有値に属する一般固有ベクトルは線形独立です.
つまり,任意の相異なる複素数 \psi_1, \dotsc, \psi_m \in \mathbb{C}^\times と任意の多項式 P_1 (t), \dotsc, P_m (t) \in \mathbb{C} [t] \setminus \{ 0 \} に対して,\{ P_1 (q) \psi_1^\bullet, \dotsc, P_m (q) \psi_m^\bullet \} \subset S は線形独立となります.

さらに,複素数 \psi \in \mathbb{C}^\times に対して,\{ \psi^\bullet, q \psi^\bullet, \dotsc, q^d \psi^\bullet, \dotsc \} \subset S もまた線形独立です.

それを示すために,まずこれらの線型結合が零であるとします:

\sum_{i = 0}^{d - 1} \lambda_i q^i \psi^\bullet = 0.

このとき任意の n \geqslant 0 に対して \sum \lambda_i n^i \psi^n = 0 が成り立つので,両辺を \psi^n で割って \sum \lambda_i n^i = 0 となります.

また,0 \leqslant n \leqslant d - 1 のみを見ることで,(\lambda_0, \dotsc, \lambda_{d - 1}) に関する連立方程式

\begin{pmatrix} 1 & 0 & \cdots & 0 \\ 1 & 1 & \cdots & 1 \\ \vdots & \vdots & & \vdots \\ 1 & d - 1 & \cdots & (d - 1)^{d - 1} \end{pmatrix} \begin{pmatrix} \lambda_0 \\ \vdots \\ \lambda_{d - 1} \end{pmatrix} = 0

を得ます.左辺の行列の行列式は Vandermonde の行列式なので,\neq 0.従って \lambda_0 = \dotsb = \lambda_{d - 1} = 0 となり,\{ \psi^\bullet, q \psi^\bullet, \dotsc \} の線形独立性が分かりました.

以上の議論より,

\left\{ q^d \psi^\bullet \,\middle|\, d \in \mathbb{Z}_{\geqslant 0}, \ \psi \in \mathbb{C}^\times \right\} \subset S

は線形独立となります.

斉次解空間の次元

微分方程式の場合と同じように,漸化式 (RE-h) の解空間 X の次元は M - 1 となります.
このことを確かめましょう.

次の写像を考えます:

\mathbb{C}^{M - 1} \ni a = (a_i) \mapsto x (a)_\bullet \in X.

ただし,x (a)_\bullet は,x_i = a_i を初期値とするような (RE-h) の解を表します.このような解が(ただ一つ)存在することは明らかなので,上の写像は線形同型となります.

解の構成

一般斉次解

上の議論より,もし (RE-h) の線形独立な解 x_\bullet^1, \dotsc, x_\bullet^{M - 1} \in X が見つかれば,(x_\bullet^1, \dotsc, x_\bullet^{M - 1})X の基底となるので,(RE-h) の任意の解はその線型結合 \sum C_i x_\bullet^i で書けます.
そして初期条件 x_n = a_n から係数 C_n を求めれば,最終的な解も分かります.

最も重要なのは,この線形独立な M - 1 個の解を見つける作業です.
とは言っても,やはり線形常微分方程式と同じです.

ここでは特性方程式を用いた解法でいきましょう.

漸化式 (RE-h)

x_{n + M - 1} = \sum_{i = 0}^{M - 2} \lambda_i x_{n + i}

特性多項式characteristic polynomial\chi (t) \in \mathbb{C} [t] を,\chi (t) = t^{M - 1} - \sum_{i = 0}^{M - 2} \lambda_i t^i で定義します.特性方程式とは \chi (t) = 0 という方程式のことです.

さて,(RE-h) を,数列のシフトを用いて

x_\bullet [M - 1] = \sum \lambda_i x_\bullet [i]

と書き直してみましょう.上述したように x_\bullet [k] = (p + 1)^k x_\bullet でしたから,(RE-h) は

(p + 1)^{M - 1} x_\bullet = \sum \lambda_i (p + 1)^i x_\bullet

と書けます.これは \chi (p + 1) x_\bullet = 0 に他なりませんね.

特性多項式の(相異なる)根を \psi_1, \dotsc, \psi_\ell \in \mathbb{C}^\times として(\lambda_0 \neq 0 なので \chi (t)0 を根に持ちません),それぞれの重複度を m_1, \dotsc, m_\ell とします:

\chi (t) = (t - \psi_1)^{m_1} \dotsm (t - \psi_\ell)^{m_\ell}.

このとき,m_i - 1 次以下の任意の多項式 P (t) \in \mathbb{C} [t] に対して,P (q) \psi_i^\bullet \in S は (RE-h) の解となります.
実際,このような P (t) に対して (p - \psi_i + 1)^{m_i} P (q) \psi_i^\bullet = 0 であることは既に示したので,

\chi (p + 1) P (q) \psi_i^\bullet = \left( \prod_{j \neq i} (p - \psi_j + 1)^{m_j} \right) (p - \psi_i + 1)^{m_i} P (q) \psi_i \bullet = 0.

これによって (RE-h) の解が M - 1 個手に入りました:

\left\{ q^d \psi_i^\bullet \,\middle|\, 1 \leqslant i \leqslant \ell, \ 0 \leqslant d \leqslant m_i - 1 \right\}.

既に見たようにこれらは線形独立なので,X の基底を成します.

従って,(RE-h) の一般解は \sum C_{i, d} q^d \psi_i^\bullet という形で書くことができます(C_{i, d} \in \mathbb{C}).

(RE) の一般解

なんらかの方法で (RE) の特解(particular solution\pi_\bullet \in S を一つ求められたとしましょう.
たとえば,もし 1 - \sum \lambda_i \neq 0 なら

\pi_n = \frac{c}{1 - \sum \lambda_i}

という定数列が特解となります.

容易に分かるように,(RE-h) の任意の解 x_\bullet \in X に対して,\pi_\bullet + x_\bullet は (RE) の解となります.逆に,(RE) の任意の解 y_\bullety_\bullet - \pi_\bullet \in X を満たします.

よって,(RE) の一般解は \pi_\bullet + \sum C_{i, d} q^d \psi_i^\bullet となります.

あとは,与えられた初期値 (a_0, \dotsc, a_{M - 2}) \in \mathbb{C}^{M - 1} に対して,\pi_n + \sum C_{i, d} q^d \psi_i^n = a_n となるように定数 C_{i, d} を求めれば終わりです.

さらなる一般化へ……

以上の話を,微分方程式論を参考にして一般化してみると,次のような感じでしょうか:

  • 非線形項を加える — x_{n + 1} = 1/x_n など;
  • 変数の数を増やす — x_n から x_{n, m, \dotsc, \ell}
  • ベクトル値にする — x_n \in \mathbb{C} から x_n \in \mathbb{C}^N
  • Weyl 代数の類似を作る — pq で生成される代数が連接なら、「佐藤の哲学」が活きる;
  • 層や多様体に相当する概念を定義し,その上で差分演算子を考える;
  • etc.

最後の方針は,有理整数環 \mathbb{Z} 自身は特に面白い幾何構造を持たないので,微妙かもしれません.

代数畑の人間なので,関数解析的な方面への一般化はあまり分かりません…….

いずれにせよ,これらの一般化に関して面白い話題が見つかれば,また記事を書こうと思います.