Matrico de Toeplitz

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

En lineara algebro, diagonalo-konstanta matrico, aŭ matrico de Toeplitz, nomita post Otto Toeplitz, estas matrico en kiu ĉiu diagonalo demaldekstre desupre dekstren suben estas konstanta. Ekzemple, la sekva matrico estas matrico de Toeplitz:


\begin{bmatrix}
a & b & c & d & e \\
f & a & b & c & d \\
g & f & a & b & c \\
h & g & f & a & b \\
i & h & g & f & a 
\end{bmatrix}

Ajna n×n matrico A de la formo


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}

estas matrico de Toeplitz. Se la elemento i, j de A estas indikita kiel Ai, j, tiam por ĉiuj i>1 kaj j>1

Ai, j = Ai-1, j-1

Trajtoj[redakti | redakti fonton]

Ĝenerale, matrico-ekvacio

Ax = b

estas la ĝenerala sistemo de n de linearaj ekvacioj. Se A estas m×n matrico de Toeplitz, tiam la sistemo estas sufiĉe speciala (havas nur m+n+1 gradojn de libereco, sed ne mn). Oni povis tial atendi ke solvado de Toeplitz-sistemo estus pli facila.

Tio povas esti esplorata per la transformo

AU_n-U_mA

kiu havas rangon 2, kie Uk estas la malsupren-ŝova-operatoro. Specife, oni povas de simpla kalkulado montri ke


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}

kie malplenaj lokoj en la matrico estas nuloj.

Diskreta kunfaldo[redakti | redakti fonton]

La kunfalda operacio povas esti konstruata kiel matrica multipliko, kie unu el la enigaĵoj estas konvertita en matricon de Toeplitz. Ekzemple, la kunfaldo de h kaj x povas esti formulita kiel:


    \begin{matrix}
        y & = & h \ast 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} \\
        y^T & = &
            \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{matrix}

Ĉi tiu aliro povas esti etendata por komputi memkorelacion, kruco-korelacion, moviĝantan meznombron ktp.

Notoj[redakti | redakti fonton]

Du matricoj de Toeplitz povas esti adiciitaj en tempo O(n). Matrico de Toeplitz povas esti multiplikita per vektoro en tempo O(n log n), kaj la matrica multipliko de du matricoj de Toeplitz povas esti farita en tempo O(n2).

Sistemo de formo Ax = b kun matrico de Toeplitz A povas esti solvita per de la algoritmo de Levinson-Durbin en tempo Θ(n2). Variaĵoj de ĉi tiu algoritmo estis montritaj esti malforte stabilaj, kio estas ke ili havas ciferecan stabilecon por bon-kondiĉigitaj linearaj sistemoj.

Matricoj de Toeplitz ankaŭ estas proksime ligitaj kun serioj de Fourier, ĉar la multiplika operatoro de trigonometria polinomo, kunpremita al finidimensia spaco, povas esti prezentata per ĉi tia matrico.

Se matrico de Toeplitz havas la aldonan propraĵon ke iu ai=ai+n, tiam ĝi estas cikleca matrico.

Simetriaj matricoj de Toeplitz estas kaj centrosimetriaj kaj dusimetriaj.

Ĉiuj matricoj de Toeplitz komutiĝas asimptote. Ĉi tio signifas ke ili diagonaligiĝas en la sama bazo kiam la vica kaj kolumna dimensioj strebas al malfinio.

Vidu ankaŭ[redakti | redakti fonton]

Eksteraj ligiloj[redakti | redakti fonton]