数学の基礎概念である「写像」について詳しく解説します。集合間の対応関係から始まり、単射・全射・全単射の性質、そして実用例まで幅広く網羅。数学を学ぶ上で避けて通れない写像の概念を理解することで、あなたの数学力はどう変わるでしょうか？
漸化式と行列による高速計算と特性方程式の関係性
漸化式を行列で表現することで高次の項を効率的に求める方法を解説します。特性方程式との関連性や実際の応用例まで詳しく紹介していますが、あなたは行列を使った漸化式の解法をマスターできるでしょうか？
漸化式を解く方法はいくつかありますが、行列を用いた解法は特に高次の項を求める際に非常に効率的です。この方法の核心は、漸化式を行列形式で表現することにあります。
例えば、フィボナッチ数列のような2項間漸化式 $a_{i+2} = pa_{i+1} + qa_i$ を考えてみましょう。この漸化式は以下のように行列で表現できます。
\begin{pmatrix}
a_{i+2} \\
a_{i+1}
\end{pmatrix} =
\begin{pmatrix}
p & q \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
a_{i+1} \\
a_{i}
\end{pmatrix}
この表現方法の最大の利点は、行列の累乗計算によって高次の項を直接求められることです。例えば、$a_n$ を求めるためには、係数行列の $(n-1)$ 乗を計算し、初期値ベクトルに掛けるだけで済みます。
行列累乗は分割統治法を用いることで $O(\log n)$ の計算量で実行できるため、$n$ が非常に大きい場合（例えば $n = 10^{16}$ など）でも効率的に計算できます。これは通常の再帰的な計算方法では不可能な規模の問題を解決できることを意味します。
漸化式を行列で表現する際に重要なのが、その行列の固有値と固有ベクトルです。実は、漸化式の特性方程式は行列の固有方程式と一致します。
例えば、2項間漸化式 $a_{i+2} = pa_{i+1} + qa_i$ に対応する行列
A = \begin{pmatrix}
p & q \\
1 & 0
\end{pmatrix}
の固有方程式は次のようになります。
|A - λE| = 0
これを展開すると、
(p - λ)(0 - λ) - q・1 = 0
λ^2 - pλ - q = 0
となり、これは漸化式の特性方程式 $λ^2 - pλ - q = 0$ と一致します。
この固有値を $λ_1, λ_2$ とすると、漸化式の一般項は $a_n = C_1λ_1^n + C_2λ_2^n$ の形で表されます。ここで $C_1, C_2$ は初期条件から決まる定数です。
この関係性を理解することで、行列の対角化を用いて漸化式を効率的に解くことができます。特に、行列の $n$ 乗を計算する際に対角化を活用すると、計算量をさらに削減できる場合があります。
行列累乗を用いた漸化式の解法の最大の強みは、高速計算が可能な点です。特に $n$ が非常に大きい場合、通常の再帰的な計算では時間がかかりすぎますが、行列累乗なら効率的に計算できます。
行列の累乗計算は以下のアルゴリズムで実装できます。
// 2×2行列の累乗計算（mod付き）
Matrix matrixPow(Matrix A, long long n, long long mod) {
Matrix res = {{1, 0}, {0, 1}}; // 単位行列
while (n > 0) {
if (n & 1) {
res = matrixMultiply(res, A, mod);
}
A = matrixMultiply(A, A, mod);
n >>= 1;
}
return res;
}
このアルゴリズムは繰り返し二乗法と呼ばれ、$O(\log n)$ の計算量で行列の $n$ 乗を計算できます。例えば、$n = 10^{18}$ のような巨大な数でも、約60回程度の行列乗算で結果を得られます。
また、行列の乗算部分は次のように実装できます。
// 2×2行列の乗算（mod付き）
Matrix matrixMultiply(Matrix A, Matrix B, long long mod) {
Matrix C = {{0, 0}, {0, 0}};
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
}
}
}
return C;
}
この方法は競技プログラミングでもよく使われ、大きな $n$ に対する漸化式の値を求める問題で重宝されます。
2項間漸化式だけでなく、3項間や一般の多項間漸化式も行列を用いて解くことができます。例えば、3項間漸化式 $a_{i+3} = pa_{i+2} + qa_{i+1} + ra_i$ は次のような行列で表現できます。
\begin{pmatrix}
a_{i+3} \\
a_{i+2} \\
a_{i+1}
\end{pmatrix} =
\begin{pmatrix}
p & q & r \\
1 & 0 & 0 \\
0 & 1 & 0
\end{pmatrix}
\begin{pmatrix}
a_{i+2} \\
a_{i+1} \\
a_{i}
\end{pmatrix}
一般的に、$m$ 項間漸化式 $a_{i+m} = \sum_{j=0}^{m-1} p_j a_{i+j}$ は、$m \times m$ の行列で表現できます。
A = \begin{pmatrix}
p_{m-1} & \cdots & p_1 & p_0 \\
1 & \cdots & 0 & 0 \\
\vdots & \ddots & \vdots & \vdots \\
0 & \cdots & 1 & 0
\end{pmatrix}
この拡張により、より複雑な漸化式も同様のアルゴリズムで解くことができます。ただし、行列のサイズが大きくなるため、計算量は $O(m^3 \log n)$ となります。
多項間漸化式の例として、トリボナッチ数列（直前の3項の和）を考えてみましょう。この数列は $a_{i+3} = a_{i+2} + a_{i+1} + a_i$ という漸化式で定義され、初期値が $a_0 = 0, a_1 = 0, a_2 = 1$ のとき、数列は $0, 0, 1, 1, 2, 4, 7, 13, 24, 44, ...$ となります。この数列の第 $n$ 項も行列累乗で効率的に計算できます。
行列を用いた漸化式の解法は、連立漸化式の解法にも応用できます。例えば、次のような連立漸化式を考えてみましょう。
a_{n+1} = pa_n + qb_n
b_{n+1} = ra_n + sb_n
これは以下のように行列で表現できます。
\begin{pmatrix}
a_{n+1} \\
b_{n+1}
\end{pmatrix} =
\begin{pmatrix}
p & q \\
r & s
\end{pmatrix}
\begin{pmatrix}
a_n \\
b_n
\end{pmatrix}
この表現を用いると、$n$ ステップ後の値は次のように計算できます。
\begin{pmatrix}
a_n \\
b_n
\end{pmatrix} =
\begin{pmatrix}
p & q \\
r & s
\end{pmatrix}^n
\begin{pmatrix}
a_0 \\
b_0
\end{pmatrix}
連立漸化式を解く別の方法として、一方の変数を消去して単一の高次漸化式に帰着させる方法もあります。例えば、上記の連立漸化式から $b_n$ を消去すると、$a_n$ に関する2階の漸化式が得られ、これを前述の方法で解くことができます。
この方法は、マルコフ連鎖や人口動態モデルなど、様々な分野の問題に応用できます。例えば、ある生態系における2種の生物の個体数変化や、経済モデルにおける複数の変数の時間発展などを解析する際に役立ちます。
連立漸化式の詳細な解法については、学びTimesの記事が参考になります
連立漸化式の解法は、単一の漸化式よりも複雑に見えますが、行列の考え方を用いれば統一的に扱うことができます。これは線形代数の美しさと実用性を示す好例と言えるでしょう。
行列の対角化を用いると、漸化式の一般項をより直接的に求めることができます。対角化のプロセスは以下の通りです。
対角行列の累乗は各対角成分の累乗を取るだけなので、計算が非常に簡単になります。
例として、フィボナッチ数列の漸化式 $a_{n+2} = a_{n+1} + a_n$ （$p=1, q=1$ の場合）を考えてみましょう。対応する行列は。
A = \begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
この行列の固有値は $\lambda_1 = \frac{1+\sqrt{5}}{2}, \lambda_2 = \frac{1-\sqrt{5}}{2}$ であり、対応する固有ベクトルから行列 $P$ を構成できます。
P = \begin{pmatrix}
\lambda_1 & \lambda_2 \\
1 & 1
\end{pmatrix}
これにより、フィボナッチ数列の一般項は次のように表されます。
a_n = \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n)
この方法は、特に固有値が異なる場合（重解でない場合）に有効です。固有値が重解を持つ場合は、ジョルダン標準形を用いるなど、より高度な処理が必要になります。
対角化による方法は、漸化式の一般項を閉じた形で表現したい場合に特に有用です。また、この方法を理解することで、漸化式と線形代数の深い関連性を実感できるでしょう。
行列の対角化による漸化式の解法の詳細は、こちらの記事が参考になります
以上のように、行列を用いた漸化式の解法は、効率的な計算方法を提供するだけでなく、漸化式の背後にある数学的構造への深い洞察をもたらします。特に線形代数の知識を持つ読者にとっては、これらの手法は強力なツールとなるでしょう。