Toeplitz矩陣

出自維基百科,自由嘅百科全書
跳去: 定向搵嘢

線性代數入面,Toeplitz矩陣,(個名來自Otto Toeplitz),又叫常對角矩陣(diagonal-constant matrix),即係每條左上到右下嘅對角線都係常值嘅嘅(唔一定要四方形,長方都得)矩陣。例如:


\begin{bmatrix}
a & b & c & d & k \\
f & a & b & c & d \\
g & f & a & b & c \\
h & g & f & a & b \\
j & h & g & f & a 
\end{bmatrix}

任何咁樣嘅n×n 矩陣 A


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}

都係個Toeplitz矩陣。若我地叫A 嘅 i,j元做Ai,j,咁

A_{i,j} = a_{i-j}.

性質[編輯]

通常,矩陣方程

Ax=b

可以睇做一般解n線性方程嘅問題。如果 A 係個 Toeplitz 矩陣,咁套方程就好特別(自由度得 2n − 1 ,而唔係 n2)。 所以Toeplitz系統我哋可以預咗會易解的。

呢方面可以借以下嘅 2階(rank)轉換

AU_n-U_mA,

來研究;其中 U_k向下郁算子( down-shift operator)。尤其,由簡短計算,我地可知:


AU_n-U_mA=
\begin{bmatrix}
a_{-1} & \cdots & a_{-n+1} & 0 \\
\vdots &        &          & -a_{-n+1} \\
\vdots &        &          & \vdots \\
 0     & \cdots &          & -a_{n-n-1}
\end{bmatrix}

其中空咗嘅都係零。

[編輯]

呢啲矩陣嚮電算有用,因為可以證: 加埋兩個 Toeplitz 矩陣只使O(n)時間; Toeplitz 矩陣 x 向量要用 O(n log n) 時間;而兩隻 Toeplitz 矩陣 x Toeplitz矩陣可以只用 O(n^2) 時間。

Toeplitz 系統 Ax=b 可以用 Levinson-Durbin Algorithm 解,需時 Θ(n^2) 。 呢套算法嘅變種,可證係喺 James Bunch 嘅意義上弱穏定(weakly stable) 嘅,(即係話,喺 well-condition 嘅線性系統,佢哋有 numerical stability )。

Toeplitz 矩陣同富理埃級數關係好密,因為「乘以一三角多項式」嘅 算子質埋入一有限維嘅空間時,可以用呢種矩陣表示。

If a Toeplitz matrix has the additional property that a_i=a_{i+n}, then it is a circulant matrix.

Toeplitz matrices are persymmetric. Symmetric Toeplitz matrices are centrosymmetric.

卷積 operation can be constructed as a matrix multiplication, where one of the inputs is converted into a Toeplitz matrix. For example, the convolution of  x and h can be formulated as:

\begin{matrix}y & = & x \ast h \\ & = & \begin{bmatrix}h_1\\h_2 \\h_3\\ \vdots \\ 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} & 0 \\  0 & 0 & \ldots & 0 & 0 & x_1 & \ldots & x_{n-2} & x_{n-1} & x_{n} \\ \end{bmatrix}                   \end{matrix} .

This approach can be extended to compute autocorrelation, cross-correlation, moving average etc [1].

睇吓[編輯]

出面網頁[編輯]

  1. Using Toeplitz matrices in MATLAB [1]