テプリッツ行列について詳しく解説

導入

線形代数では、テプリッツ行列(オットー テプリッツにちなんで) または定対角行列は、左から右に降下する対角線上の係数が同じ行列です。たとえば、次の行列はテプリッツ行列です。

$$ { \begin{pmatrix} 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{pmatrix}. } $$

m行n列の形式の任意の行列A

$$ { A = \begin{pmatrix} 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_{m-1} & \ldots & \ldots & a_{2} & a_{1} & a_{0} \end{pmatrix} } $$

はテプリッツ行列です。 Aの行iと列jの交点にある要素をA _{i , jと}表すと、次のようになります。

A _{i , j} = a _{i − j} 。

プロパティ

一般に、行列方程式は、

A x = b

は、解くべきn 個の線形方程式系に対応します。 Aがテプリッツ行列の場合、システムは特殊です。一般的な場合のn ²の代わりに、非常に特殊な方法で配置された 2 n − 1 個の情報のみが含まれます。

このプロパティは、行列を観察することで確認できます。

A U _n − U _n A 、 .

ここでU _{n は}次のように与えられます。

$$ {U_n=\begin{pmatrix} 0 & \cdots & 0 & 1 \\ 1 & 0 & & 0 \\ \vdots & \ddots & \ddots & \vdots \\ 0 & \cdots & 1 & 0 \end{pmatrix}.} $$

U _nにベクトルvを乗算すると、 vのすべての係数が 1 行下にシフトされ、最後の係数が最初の行に上がります。

単純な計算では、

$$ {D(A)= AU_n-U_nA= \begin{pmatrix} a_{-1} & \cdots & a_{-n+1} & 0 \\ \vdots & & & -a_{-n+1} \\ \vdots & & & \vdots \\ 0 & \cdots & & -a_{n-n-1} \end{pmatrix} } $$

ここで、空のボックスはゼロに置き換えることができます。ランクが最大 2 であることがわかります。D ( A )がAの変位行列であるとします。

Aが反転可能でテプリッツである場合、 Aが三角形でない限り、その反転はテプリッツではありません。ただし、 Aの逆数には依然として興味深い特性があります。 D ( A ) に A の逆数を乗算すると、 − D ( A ^{− 1} )が得られます。したがって、これもランクが最大 2 になります。

このため、 A がA U _n − U _n Aのような行列、つまりランクrの行列である場合、それは変位ランクrのテプリッツ型であると言えます。

テプリッツ行列を使用した計算

これらの行列は、計算の複雑さの観点から非常に興味深いものです。2 つのテプリッツ行列の加算はO( n ) 演算で実行でき、2 つのテプリッツ行列の行列積はO( n log nで実行できることを示します)。 ）の操作。

行列がテプリッツである線形システムの解決は、いくつかのアルゴリズム プロセスを組み合わせることで、通常はO ( n log ( n ) ² ) 回の演算で非常に高速に行うことができます。これらの方法はテプリッツ型行列に拡張されており、 O ( n r ² log( n ) ² )の演算でアルゴリズムを提供するため、 nの前の変位ランクr が小さい行列にとって興味深いものです。 ³ )任意の完全な行列に対する演算。

ただし、テプリッツ行列は条件が非常に悪い場合があるため、浮動小数点数で計算した場合、または有理数で正確に計算した場合に巨大な分数で計算した場合、得られる解の相対誤差は大きくなります。

これらの行列は、有限次元空間に圧縮された(制限された) 三角多項式による乗算演算子をこのような行列で表現できるため、フーリエ級数とも密接に関係しています。

テプリッツ行列がa _i = a _{i + n を}さらに満たす場合、それは循環行列になります。