用語説明 - 線形差分方程式

一般に $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: 2017年11月23日18時26分10秒
Last modified: 2015年03月31日22時25分48秒 (by laycrs)
Tags: no_tags
トップページに戻る

Logged in as: unknown user (not login)

ログイン: