2014年05月25日00時02分53秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
一般に $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月26日02時21分18秒
Last modified: 2014年05月25日00時02分53秒 (by laycrs)
Tags: no_tags
トップページに戻る
Logged in as: unknown user (not login)