一般に $x_{n+1} = A x_{n}$ という形の差分方程式．ここで，$x_k \in {\mathbb R}^d$ はベクトル，$A \in M_d({\mathbb R})$ は行列である．
一般項は $x_n = A^n x_0$ と書けるため，$A^n$ を計算することで一般項を求めることができる．
$A^n$ はバイナリ法により $O(\log n)$ 回の行列乗算で，つまり時間計算量 $O(d^3 \log n)$ で計算することができる．
$x_k, a_k$ を実数として，$x_{n+d} = a_1 x_{n+d-1} + a_2 x_{n+d-2} + \cdots + a_d x_n$ という線形差分方程式はコンパニオン行列を用いることで上の行列，ベクトルを用いた形に書き直せる．
$\displaystyle
\begin{pmatrix}
x_n \\
x_{n+1} \\
x_{n+2} \\
\vdots \\
x_{n+d-1} \\
x_{n+d}
\end{pmatrix}
=
\begin{pmatrix}
0 & 1 & 0 & \cdots & 0 & 0 \\
0 & 0 & 1 & \cdots & 0 & 0 \\
0 & 0 & 0 & \cdots & 0 & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & \cdots & 0 & 1 \\
a_d & a_{d-1} & a_{d-2} & \cdots & a_2 & a_1 \\
\end{pmatrix}
\begin{pmatrix}
x_{n-1} \\
x_{n} \\
x_{n+1} \\
\vdots \\
x_{n+d-2} \\
x_{n+d-1}
\end{pmatrix}$
Current time: 2024年04月19日08時16分46秒
Last modified: 2015年03月31日22時25分48秒 (by laycrs)
Tags: no_tags
トップページに戻る
Logged in as: unknown user (not login)