テプリッツ行列のソースを表示

'''テプリッツ行列'''（テプリッツぎょうれつ、{{lang-en-short|Toeplitz Matrix}}）は、左から右の各下降対角線に沿って要素が一定であるような[[行列]]である。'''対角一定行列'''（たいかくいっていぎょうれつ、{{lang-en-short|Diagonal-Constant Matrix}}）とも。名前の由来は数学者 {{ill|オットー・テプリッツ|en|Otto Toeplitz}}。テプリッツ行列は次のような行列である。

:<math>
\begin{bmatrix}
a & b & c & d & e \\
f & a & b & c & d \\
g & f & a & b & c \\
h & g & f & a & b \\
j & h & g & f & a 
\end{bmatrix}
</math>

任意の ''n''&times;''n'' 行列 '''''A''''' が次のような形式であれば、それをテプリッツ行列と呼ぶ。

:<math>
\boldsymbol{A} =
\begin{bmatrix}
  a_{0} & a_{-1} & a_{-2} & \ldots & \ldots  &a_{-n+1}  \\
  a_{1} & a_0  & a_{-1} &  \ddots   &  &  \vdots \\
  a_{2}    & a_{1} & \ddots  & \ddots & \ddots& \vdots \\ 
 \vdots &  \ddots & \ddots &   \ddots  & a_{-1} & a_{-2}\\
 \vdots &         & \ddots & a_{1} & a_{0}&  a_{-1} \\
a_{n-1} &  \ldots & \ldots & a_{2} & a_{1} & a_{0}
\end{bmatrix}
</math>

''i'' 行目、''j'' 列目の ''A'' の要素を ''A''<sub>''i'',''j''</sub> と記述するとき、以下が成り立つ。

:<math>A_{i,j} = A_{i-1,j-1}</math> 

== 特性 ==
行列を使った方程式の一般形

:<math>\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}</math>

は、''n''元[[線型方程式系]]を表す。この ''A'' がテプリッツ行列であった場合、その系はやや特殊となる（[[自由度]]が ''n''<sup>2</sup> ではなく 2''n''&nbsp;&minus;&nbsp;1 になる）。したがって、テプリッツ系は通常より解きやすいと期待される。

これは次の変形で調べることができる。

:<math>\boldsymbol{A} \boldsymbol{U}_n - \boldsymbol{U}_m \boldsymbol{A}</math>

これは[[行列の階数|階数]]が2で、<math>\boldsymbol{U}_k</math> は down-shift operator である。特に単純な計算で次のように示すことができる。

:<math>
\boldsymbol{A} \boldsymbol{U}_n - \boldsymbol{U}_m \boldsymbol{A} =
\begin{bmatrix}
a_{-1} & \cdots & a_{-n+1} & 0 \\
\vdots & \ddots &          & -a_{-n+1} \\
\vdots &        & \ddots & \vdots \\
 0     & \cdots & \cdots & -a_{n-n-1}
\end{bmatrix}
</math>

ここで、行列の空の場所はゼロに置換されている。

== 特性 == 
2つのテプリッツ行列の加算は [[ランダウの記号|O]](''n'') の時間でなされ、テプリッツ行列とベクトルの乗算は O(''n'' log ''n'')、2つのテプリッツ行列の乗算は O(<math>n^2</math>) の時間でなされる。

テプリッツ系 <math>\boldsymbol{A} \boldsymbol{x} = \boldsymbol{b}</math> は、{{Ill|レビンソン＝ダービン・アルゴリズム|en|Levinson recursion}}で Θ(<math>n^2</math>) の時間で解ける。このアルゴリズムのバリエーションは James Bunch 的意味で弱安定性を有する（すなわち、良条件の線型系で[[数値的安定性]]を示す）。

有限次元空間に圧縮された三角関数多項式による乗算演算子はテプリッツ行列で表すことができるので、テプリッツ行列は[[フーリエ級数]]とも密接に関連する。

テプリッツ行列が <math>a_i=a_{i+n}</math> という属性も持つ場合、それを[[巡回行列]]と呼ぶ。

テプリッツ行列は {{Ill|Persymmetric行列|en|Persymmetric matrix|label=persymmetric}}である。対称テプリッツ行列は{{Ill|中心対称行列|en|Centrosymmetric matrix|label=中心対称}}であり、かつ{{Ill|両対称行列|en|Bisymmetric matrix|label=両対称}}である。

[[畳み込み]]は行列の積で表すことができ、その際の入力の1つはテプリッツ行列に変換される。例えば、<math>\boldsymbol{h}</math> と <math>\boldsymbol{x}</math> の畳み込みは次のようになる。

:<math>\begin{align}
  \boldsymbol{y} &= \boldsymbol{h} \ast \boldsymbol{x} \\
  &= \begin{bmatrix}
    h_1 & 0 & \ldots & 0 & 0 \\
    h_2 & h_1 & \ldots & \vdots & \vdots \\
    h_3 & h_2 & \ldots & 0 & 0 \\
    \vdots & h_3 & \ldots & h_1 & 0 \\
    h_{m-1} & \vdots & \ldots & h_2 & h_1 \\
    h_m & h_{m-1} & \vdots & \vdots & h_2 \\
    0 & h_m & \ldots & h_{m-2} & \vdots \\
    0 & 0 & \ldots & h_{m-1} & h_{m-2} \\
    \vdots & \vdots & \vdots & h_m & h_{m-1} \\
    0 & 0 & 0 & \ldots & h_m \\
  \end{bmatrix}
  \begin{bmatrix}
    x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \\
  \end{bmatrix} \\
  \boldsymbol{y}^{\intercal} & =
    \begin{bmatrix}
      h_1 & h_2 & h_3 & \ldots & h_{m-1} & h_m \\
    \end{bmatrix}
    \begin{bmatrix}
      x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & 0& \ldots & 0 \\
      0 & x_1 & x_2 & x_3 & \ldots & x_n & 0 & 0 & \ldots & 0 \\
      0 & 0 & x_1 & x_2 & x_3 & \ldots & x_n & 0  & \ldots & 0 \\
      \vdots & \vdots & \vdots & \vdots & \vdots & \ldots & \vdots & \vdots  & \ldots & 0 \\
      0 & \ldots & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_{n} & \vdots \\
      0 & \ldots & 0 & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_{n} \\
    \end{bmatrix}
\end{align}</math>

この手法は、[[自己相関]]、[[相互相関関数|相互相関]]、[[移動平均]]などの計算にも拡張できる。

== 関連項目 ==
*[[巡回行列]]

== 外部リンク ==
*[http://ee.stanford.edu/~gray/toeplitz.pdf Toeplitz and Circulant Matrices: A Review, by R. M. Gray]

{{Normdaten}}
{{DEFAULTSORT:てふりつつきようれつ}}

[[Category:行列]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]