ماتریس توپلیتس

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در جبر خطی، یک ماتریس توپلیتس یا ماتریس قطر-ثابت، که Otto 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}

هر ماتریس 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}

یک ماتریس توپلیتز است. اگر عنصر i,j ماتریس A را با Ai,j نشان دهیم، آنگاه خواهیم داشت

A_{i,j} = A_{i+1,j+1}\

پاسخ سیستم توپلیتس[ویرایش]

اگر A یک مارتیس توپلیتس باشد، رابطه مارتیس به شکل زیر سیستم توپلیتس خوانده می شود

Ax=b\

اگر A یک ماتریس توپلیس n\times n باشد، آنگاه درجه آزادی سیستم به جای n2، تنها 2n−1 خواهد بود. در این حالت انتظار داریم که حل سیستم توپلیتس ساده باشد، که واقعاً همینطور نیز هست.

سیستم توپلیتس را می توان با استفاده از الگوریتم بازگشتی لوینسون در Θ(n2) مرحله حل کرد .[۱] هم خانواده های این الگوریتم نشان داده اند که پایداری کمی دارند (این الگوریتم ها تنها برای سیستم های پایداری عددی تنها برای سیستم های خطی خوش خلق ممکن است). [۲] این الگوریتم را می توان برای پیدا کردن دترمینان ماتریس توپلیتز در O(n2) مرحله نیز استفاده کرد[۳]

یک ماتریس توپلیتز را می توان در O(n2) مرحله تجزیه (فاکتوریزه کردن) کرد [۴] الگوریتم بارِیس برای یک تجزیه LU پایداری (عددی) خود را نشان داده است [۵] تجزیه LU یک روش سریع برای محاسبه دترمینان، و همچنین حل سیستم توپلیتز است. الگوریتم های سریعتر از بارِیس و لوینسون نیز وجود دارد [۶][۷][۸][۹]

خواص عمومی[ویرایش]

یک ماتریس توپلیتز را می توان یک ماتریس نوعی A تعریف کرد که به ازای اعداد ثابت های c1−ncn−1 داشته باشیم Ai,j = ci−j. مجموعه nxn ماتریس تولیپز، یک زیرفضا از ماتریس nxn بردار فضایی است که با استفاده از عملیات ضرب و جمع بدست می آیند.

دو ماتریس توپلیتس را می توان در O(n مرحله جمع و در (O(n2 مرحله ضرب کرد.

ماتریس های توپلیتس پرسیمتریک هستند. ماتریس های توپلیتس متقارن، هم سنتروسیمتریک و بایسیمتریک هستند.

ماتریس های توپلیتس به سری فوریه بسیار نزدیک هستند، زیرا عملگر ضرب به کمک چندجمله ای مثلثاتی، به یک فضا با ابعاد محدود فشرده می شود را می توان با این گونه ماتریس ها نمایش داد.

تمام ماتریس های توپلیتس به طور مجانبی جابجاپذیر هستند.

کانولوشن گسسته[ویرایش]

عمل کانولوشن را می توان با استفاده از ضرب ماتریسی انجام داد. برای انجام این کار یکی از ورودی ها باید به شکل ماتریس توپلیتس دربیاید. برای مثال، کانولوشن  h و  x را می توان به شکل زیر فرموله کرد


    \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}

این روش را می توان به منظور محاسبه خودهمبستگی، همبستگی عرضی، میانگین متحرک و غیره بسط داد.

پیوندهای مرتبط[ویرایش]

Notes[ویرایش]

  1. Press et al. (2007).
  2. Krishna & Wang (1993).
  3. Monahan (2011).
  4. Brent (1999).
  5. Bojanczyk et al. (1995).
  6. Stewart (2003).
  7. Chen et al. (2006)
  8. Chan & Jin (2007).
  9. Chandrasekeran et al. (2007).

References[ویرایش]