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

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

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

برای نمونه، ماتریس زیر را در نظر بگیرید:


\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[ویرایش]