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

در جبر خطی، یک ماتریس توپلیتس یا ماتریس قطر-ثابت ، یک ماتریس است که در آن هر زیرقطر از سمت چپ به سمت راست دارای مقدار ثابت است. این ماتریس‌ها نخستین بار به وسیله ریاضیدان آلمانی اتو توپلیتس معرفی و به کار گرفته شدند.
برای نمونه، ماتریس زیر را در نظر بگیرید:
\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 را با A i,j نشان دهیم، آنگاه خواهیم داشت
پاسخ سیستم توپلیتس
اگر A یک مارتیس توپلیتس باشد، رابطه مارتیس به شکل زیر سیستم توپلیتس خوانده می‌شود
اگر A یک ماتریس توپلیتس باشد، آنگاه درجه آزادی سیستم به جای n 2 ، تنها 2n−1 خواهد بود. در این حالت انتظار داریم که حل سیستم توپلیتس ساده باشد، که واقعا همینطور نیز هست.
سیستم توپلیتس را می‌توان با استفاده از الگوریتم بازگشتی لوینسون در
(n 2 )
مرحله حل کرد
هم خانواده‌های این الگوریتم نشان داده‌اند که پایداری کمی دارند (این الگوریتم‌ها تنها برای سیستم‌های پایداری عددی تنها برای سیستم‌های خطی خوش رفتار ممکن است).
این الگوریتم را می‌توان برای پیدا کردن دترمینان ماتریس توپلیتس در O(n 2 ) مرحله نیز استفاده کرد
یک ماتریس توپلیتس را می‌توان در O(n 2 ) مرحله تجزیه (فاکتوریزه کردن) کرد
الگوریتم باریس برای یک تجزیه LU پایداری (عددی) خود را نشان داده است
تجزیه LU یک روش سریع برای محاسبه دترمینان، و همچنین حل سیستم توپلیتس است. الگوریتم‌های سریعتر از باریس و لوینسون نیز وجود دارد
خواص عمومی
یک ماتریس توپلیتس را می‌توان یک ماتریس نوعی A تعریف کرد که به ازای اعداد ثابت‌های
c 1−n … c n−1
داشته باشیم
A i,j = c i−j .
مجموعه nxn ماتریس توپلیتس، یک
زیرفضا
از ماتریس nxn
بردار فضایی است که با استفاده از عملیات ضرب و جمع بدست می‌آیند.
دو ماتریس توپلیتس را می‌توان در
O(n)
مرحله جمع و در
O(n 2 )
مرحله ضرب کرد.
ماتریس‌های توپلیتس
پرسیمتریک
هستند. ماتریس‌های توپلیتس متقارن، هم
سنتروسیمتریک
و
بایسیمتریک
هستند.
ماتریس‌های توپلیتس به سری فوریه بسیار نزدیک هستند، زیرا
عملگر ضرب
به کمک
چندجمله‌ای مثلثاتی،
به یک فضا با ابعاد محدود
فشرده
می‌شود را می‌توان با این گونه ماتریس‌ها نمایش داد.
تمام ماتریس‌های توپلیتس به طور
مجانبی
جابجاپذیر
هستند.
کانولوشن گسسته
عمل کانولوشن را می‌توان با استفاده از ضرب ماتریسی انجام داد. برای انجام این کار یکی از ورودی‌ها باید به شکل ماتریس توپلیتس دربیاید. برای مثال، کانولوشن
و
را می‌توان به شکل زیر فرموله کرد
\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
References
A.W. Bojanczyk, R.P. Brent, F.R. De Hoog, D.R. Sweet (1995), "On the stability of the Bareiss and related Toeplitz factorization algorithms", SIAM Journal on Matrix Analysis and Applications, 16: 40-57.
Brent R.P. (1999), "Stability of fast algorithms for structured linear systems", Fast Reliable Algorithms for Matrices with Structure (editors—T. Kailath, A.H. Sayed), ch.4 (SIAM).
Chan R.H.-F., Jin X.-Q. (2007), An Introduction to Iterative Toeplitz Solvers (SIAM).
Chandrasekeran S., Gu M., Sun X., Xia J., Zhu J. (2007), "A superfast algorithm for Toeplitz systems of linear equations", SIAM Journal on Matrix Analysis and Applications, 29: 1247-1266.
Chen W.W., Hurvich C.M., Lu Y. (2006), "On the correlation matrix of the discrete Fourier transform and the fast solution of large Toeplitz systems for long-memory time series", Journal of the American Statistical Association, 101: 812-822.
Golub G.H., van Loan C.F. (1996), Matrix Computations (انتشارات دانشگاه جانز هاپکینز), Section 4.7—Toeplitz and Related Systems.
Gray R.M., ( ).
The Split Levinson Algorithm is weakly stable
Monahan J.F. (2011), Numerical Methods of Statistics (انتشارات دانشگاه کمبریج), §4.5—Toeplitz systems.
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Numerical Recipes: The Art of Scientific Computing, Third edition (Cambridge University Press), .
Stewart M. (2003), "A superfast Toeplitz solver with improved numerical stability", SIAM Journal on Matrix Analysis and Applications, 25: 669-693.