連立漸化式を行列で解く

\begin{align} \begin{cases}a_{1}=3\\b_{1}=4\end{cases} \quad and \quad\begin{cases}a_{n+1} =3a_{n}+b_{n}\\b_{n+1} =2a_{n}+4b_{n}\end{cases} \end{align} ある日目が覚めたら、急に上の漸化式を解きたくなってしまったとしよう。
あなたは悩む。
「\(a_{n+1}+xb_{n+1}=y(a_{n}+xb_{n})\)を満たす実数\((x,y)\)を求めようか。」
「いや、\(b_{n}=a_{n+1}-3a_{n}\)と表現できるから\(b_{n}\)を消去して隣接三項間でも解くか。」
「ここは格好つけて行列でも使ってみるか。」
これ以上会話文(?)を書くと某共通試験の花子太郎並みに鬱陶しいことになるので鍵括弧はここで切り上げる。

さて、 \begin{align} \quad\begin{cases}a_{n+1} =3a_{n}+b_{n}\\b_{n+1} =2a_{n}+4b_{n}\end{cases} \end{align} \begin{align} \iff \left(\begin{array}{c}a_{n+1}\\ b_{n+1}\end{array}\right)=\left(\begin{array}{c}3&1\\2&4\end{array}\right)\left(\begin{array}{c}a_{n}\\ b_{n}\end{array}\right) \end{align} つまり、\(\left(\begin{array}{c}a_{n}\\ b_{n}\end{array}\right)\)の先頭に\(\left(\begin{array}{c}3&1\\2&4\end{array}\right)\)をかけると\(\left(\begin{array}{c}a_{n+1}\\ b_{n+1}\end{array}\right)\)になるということなので、
\begin{align} A=\left(\begin{array}{c}3&1\\2&4\end{array}\right) \end{align} とおくと、 \begin{align} \left(\begin{array}{c}a_{n}\\ b_{n}\end{array}\right)=A^{n-1}\left(\begin{array}{c}a_{1}\\ b_{1}\end{array}\right) \end{align} となり、連立漸化式を解くことができる。よは、\(A^n\)がわかればこの連立漸化式を解くことが出来るということだ。

\(A^n\)を求めたい。計算してみよう。
\begin{eqnarray} A^2&=&\left(\begin{array}{c}3&1\\2&4\end{array}\right)\left(\begin{array}{c}3&1\\2&4\end{array}\right)\\ &=&\left(\begin{array}{c}3\cdot 3+1\cdot 2&3\cdot 1+1\cdot 4\\2\cdot 3+4\cdot 2&2\cdot1+4\cdot 4 \end{array}\right)\\ &=&\left(\begin{array}{c}11&7\\14&18\end{array}\right)\\ A^3&=&...\\ A^n&=&...? \end{eqnarray} このように行列の乗法はかなり面倒なのでn乗は普通には求めにくい。そこで「行列の対角化」を行う。 具体的には\(P^{-1}AP\)が対角行列\(\left(\begin{array}{c}\lambda_{1}&0\\0&\lambda_{2}\end{array}\right)\)になるような都合の良い行列\(P\)を探す。
対角行列であれば、 \begin{align} \left(\begin{array}{c}\lambda_{1}&0\\0&\lambda_{2}\end{array}\right)^n=\left(\begin{array}{c}{\lambda_{1}}^n&0\\0&{\lambda_{2}}^n\end{array}\right) \end{align} となり、n乗の計算が非常に楽になる。また、 \begin{align} (PAP^{-1})^n=PAP^{-1}PAP^{-1}PAP^{-1}PAP^{-1}...PAP^{-1} \end{align} \(P^{-1}P=1\)より、 \begin{align} (PAP^{-1})^n=PA^nP^{-1} \end{align} となるので、先頭の\(P\)と最後の\(P^{-1}\)を消去すれば\(A^n\)が簡単に求められる。

このような都合の良い行列\(P\)を求めるには行列\(A\)の固有ベクトルが必要になる。
まず、\(det(A-\lambda E)=0\)となる\(\lambda\)を求める。(これが行列\(A\)の固有値となる。)
\begin{eqnarray} A-\lambda E&=&\left(\begin{array}{c}3&1\\2&4\end{array}\right)-\lambda \left(\begin{array}{c}1&0\\0&1\end{array}\right)\\ &=&\left(\begin{array}{c}3-\lambda&1\\2&4-\lambda\end{array}\right)\\ \end{eqnarray} \begin{eqnarray} \therefore det(A-\lambda E)&=&(3-\lambda)(4-\lambda)-1\cdot2\\ &=&{\lambda}^2-7\lambda+10\\ &=&(\lambda -2)(\lambda -5) \end{eqnarray} \(\lambda =2\)のとき、
\begin{eqnarray} A-\lambda E=\left(\begin{array}{c}1&1\\2&2\end{array}\right) \end{eqnarray} ここで、 \begin{eqnarray} \left(\begin{array}{c}1&1\\2&2\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)= \left(\begin{array}{c}0\\ 0\end{array}\right) \end{eqnarray} とすることで、
固有ベクトルは、 \begin{eqnarray} \left(\begin{array}{c}1\\ -1\end{array}\right) \end{eqnarray} また、\(\lambda =5\)のとき、
\begin{eqnarray} A-\lambda E=\left(\begin{array}{c}-2&1\\2&-1\end{array}\right) \end{eqnarray} ここで、 \begin{eqnarray} \left(\begin{array}{c}-2&1\\2&-1\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)= \left(\begin{array}{c}0\\ 0\end{array}\right) \end{eqnarray} とすることで、
固有ベクトルは、 \begin{eqnarray} \left(\begin{array}{c}1\\ 2\end{array}\right) \end{eqnarray} ここで、行列\Aを対角化するときは二つの固有ベクトルを並べた\(P=\left(\begin{array}{c}1&1\\ -1&2\end{array}\right)\)とすると上手くいく。 \begin{eqnarray} P^{-1}AP=\left(\begin{array}{c}2&0\\ 0&5\end{array}\right)\\ \end{eqnarray} これで対角化が完了した。

これでうまい具合に対角行列が作れたので、あとは\(A^{n}\)を持てめて計算するだけだ。
\begin{eqnarray} &&P^{-1}A^nP=\left(\begin{array}{c}2^n&0\\ 0&5^n\end{array}\right)\\ &\iff& A^n=P\left(\begin{array}{c}2^n&0\\ 0&5^n\end{array}\right)P^{-1}\\ &\iff& A^n=\frac{1}{3}\left(\begin{array}{c}1&1\\ -1&2\end{array}\right)\left(\begin{array}{c}2^n&0\\ 0&5^n\end{array}\right)\left(\begin{array}{c}2&-1\\ 1&1\end{array}\right)\\ &\iff& A^n=\frac{1}{3}\left(\begin{array}{c}2^{n+1}+5^n&-2^n+5^n\\ -2^{n+1}+2\cdot 5^n&2^n+2\cdot 5^n\end{array}\right)\\ \end{eqnarray} 従って、
\begin{eqnarray} &&\left(\begin{array}{c}a_{n}\\ b_{n}\end{array}\right)=A^{n-1}\left(\begin{array}{c}a_{1}\\ b_{1}\end{array}\right)\\ &\iff& \left(\begin{array}{c}a_{n}\\ b_{n}\end{array}\right)=\frac{1}{3}\left(\begin{array}{c}2^n+5^{n-1}&-2^{n-1}+5^{n-1}\\ -2^n+2\cdot 5^{n-1}&2^{n-1}+2\cdot 5^{n-1}\end{array}\right)\left(\begin{array}{c}3\\ 4\end{array}\right)\\ &\iff& a_{n}=\frac{2^n+7\cdot 5^{n-1}}{3}and \quad b_{n}=\frac{-2^n+14\cdot 5^{n-1}}{3} \end{eqnarray}

お気付きだろうか。
最初の会話文に述べられている通りこの連立漸化式を隣接三項間の漸化式に変更する方向で計算すると、
\(a_{n}\)について、 \begin{eqnarray} &&a_{n+2}-3a_{n+1}=2a_{n}+4a_{n+1}-12a_{n}\\ &\iff& a_{n+2}-7a_{n+1}+10a_{n}=0 \end{eqnarray} 特性方程式を解くと、\(\alpha=2,5\)となり、行列\(A\)の固有値\(\lambda=2,5\)に一致する。
つまり、行列で解くのは隣接三項間漸化式で連立漸化式を解くのと実はほぼ変わらない。


それでは、またいつか。