工学系院試でもよく出る漸化式と固有値の関係についてです。
極端ですが、工学系の院試で出る線形代数はこれだけだと言う人もいるみたいです。
それは極端すぎる主張ですが、実際に下記の内容が院試にそのまま出題されたこともあり、そう言われるだけある大事な内容です。
隣接3項間の漸化式は「今日・明日・明後日」
次の隣接3項間の漸化式を考えます。
(「隣接3項間」は、今日・明日・明後日のように3つが隣り合うものを意味しています。)
次の漸化式から、$x_0\,,x_1$ を用いて $x_n\,(n\geq 2)$ を表せ。
\begin{align}
x_{n+2}=a x_{n+1} + b x_{n} \quad (n=0\,,1\,,2\,,\,\cdots)\label{recur}\,.
\end{align}
\eqref{recur}を $n=1$ に着目して図で表したものが次です。

これは例えば、横軸の $n=0\,,1\,,\cdots$ を今日・明日・明後日…の日付だと思えば、 $x_n$ は今日・明日・明後日…の数値(気温や株価など)を表していると見ることもできます。
$n=1$ のときを考えると今は、明日・明後日・明々後日の数値 $x_1,\,x_2,\,x_3$ について、
「明々後日の数値 $x_3$ は、明後日の数値 $x_2$ の $a$ 倍と明日の数値 $x_1$ の $b$ 倍を足した結果求められる」
と言っています。
つまり\eqref{recur}は、次のような意味を持っています。
- $n$ (ある日)と $n+1$ (その翌日)の情報さえわかれば、 $n+2$ (その翌々日)のことがわかる
- しかもそれは $n=1,\,2,\,3,\,\cdots$ (全ての3日の間)で成り立つ
これはなかなかすごいことを言っているように思いませんか?
なぜなら、$x_0\,,x_1$ の値を決めただけで、それから後の $x_3\,, x_4\,, \cdots$の全ての値が決まってしまうためです。
では、これから$x_0\,,x_1$ のみから残りの$x_n$ を求める方法の1つについてご説明します。
漸化式からベクトルと行列の方程式への書き換え
さっそく、\eqref{recur}からあたりまえに成り立つ式を書きます。
\begin{align}
\begin{pmatrix}
x_{n+2} \cr
x_{n+1} \cr
\end{pmatrix}=
\begin{pmatrix}
a & b \cr
1 & 0 \cr
\end{pmatrix}
\begin{pmatrix}
x_{n+1} \cr
x_{n} \cr
\end{pmatrix} \quad (n=0\,,1\,,2\,,\,\cdots)\label{recur2}\,.
\end{align}
「なぜこれが当たり前に成り立つのか?」と思うかもしれませんが、ちょっとだけ考えてみてください。
第1行は\eqref{recur}から、第2行は $x_{n+1}=x_{n+1}$ を書きかえただけだということがわかると思います。
あらためて、\eqref{recur2}を次のように書き直します。
\begin{align}
\Bs{y}_{n+1}=A \Bs{y}_{n}\,,\quad
\text{ただし、}
A:=
\begin{pmatrix}
a & b \cr
1 & 0 \cr
\end{pmatrix}\,,
\Bs{y}_{n}:=
\begin{pmatrix}
x_{n+1} \cr
x_{n} \cr
\end{pmatrix}
\quad (n=0\,,1\,,2\,,\,\cdots)\,.\label{recur3}
\end{align}
\eqref{recur3}は\eqref{recur2}を文字を使って整理しただけで、新しいことは何もしていません。
さて、後はこの式をどう使えば $\Bs{y}_0$ から $\Bs{y}_n\,(n=1\,,2\,,\cdots)$ が求められるでしょうか。
おそらく次図のように最も単純に考えると、 $\Bs{y}_0$ に $A$ を $N$ 回かければ $A_N$ が求められる気がします。

確かにそれでも $\Bs{y}_n\,(n=1\,,2\,,\cdots\,,N)$ は計算できますが、実は大事なことを見落としてしまいます。
それは、線形代数における「固有値」と「対角化」です。
行列のべき乗は固有値と対角化で計算
今回は意味を無視して、計算だけ行います。
固有多項式というものを解いて固有値を求めて、それから求まる固有ベクトルを並べると正則行列 $P$ が得られます。
このとき、行列 $A$ を対角化すると、
\begin{align}
A=P\Lambda P^{-1}\,.
\end{align}
今の状況を図で表すと次のようになっています。

更にこの図を見て、 $\Bs{y}_0$ から $\Bs{y}_N$ までたどり着く矢印を見ると、次の図のような関係があることがわかります。

\begin{align}
A^N=P\Lambda^N P^{-1}\,. \label{A_power}
\end{align}
したがって、初期値 $\Bs{y}_0$ から求めたい $\Bs{y}_N$ は、\eqref{A_power}を用いて次のように計算できます。
\begin{align}
\Bs{y}_N=A^N\Bs{y}_0=P\Lambda^N P^{-1}\Bs{y}_0\,.\label{recur_sol}
\end{align}
計算のまとめ
整理しましょう。
やりたいこと:漸化式\eqref{recur}から $x_n$ を計算したい。
- 初期値として $x_0\,,x_1$ が与えられている。
- 漸化式\eqref{recur}を行列の形\eqref{recur2}にする。
- \eqref{recur2}を\eqref{recur3}のように文字で書き直す。
- \eqref{recur3}から行列 $A$ の $N$ 乗を計算する。
- 固有方程式を解いて行列 $A$ の固有値を計算する。
- 求めた固有値から固有ベクトルを見つけ、それを並べて正則行列 $P$ を作る。
- \eqref{A_power}を用いて行列 $A^N$ を計算する。
- \eqref{recur_sol}によって $\Bs{y}_0$ から $\Bs{y}_N$ が計算できる。
すなわち、$x_0\,,x_1$ から $x_N\,,x_{N+1}$ が計算できる。
具体例:フィボナッチ数列
漸化式\eqref{recur}で、$a=1\,,b=1\,,x_0=1\,,x_1=1$ として、 $x_n\,(n=1\,,2\,,\cdots)$ を表せ。
\begin{align*}
x_n=\dfrac{1}{\sqrt{5}}\Curl{\Pare{\dfrac{1+\sqrt{5}}{2}}^{n+1} – \Pare{\dfrac{1-\sqrt{5}}{2}}^{n+1}}\,.
\end{align*}
コメント