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

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

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

{\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_{i,j}=A_{i+1,j+1}\

پاسخ سیستم توپلیتز

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

Ax=b\

اگر A یک ماتریس توپلیتز $n\times n$

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

سیستم توپلیتز را می توان با استفاده از الگوریتم بازگشتی لوینسون در Θ(n) مرحله حل کرد . هم خانواده های این الگوریتم نشان داده اند که پایداری کمی دارند (این الگوریتم ها تنها برای سیستم های پایداری عددی تنها برای سیستم های خطی خوش رفتار ممکن است). این الگوریتم را می توان برای پیدا کردن دترمینان ماتریس توپلیتز در O(n) مرحله نیز استفاده کرد

یک ماتریس توپلیتز را می توان در O(n) مرحله تجزیه (فاکتوریزه کردن) کرد الگوریتم بارِیس برای یک تجزیه LU پایداری (عددی) خود را نشان داده است تجزیه LU یک روش سریع برای محاسبه دترمینان، و همچنین حل سیستم توپلیتز است. الگوریتم های سریعتر از بارِیس و لوینسون نیز وجود دارد

خواص عمومی

یک ماتریس توپلیتز را می توان یک ماتریس نوعی A تعریف کرد که به ازای اعداد ثابت های c_1−n … c_n−1 داشته باشیم A_i,j = c_i−j. مجموعه nxn ماتریس توپلیتز، یک زیرفضا از ماتریس nxn بردار فضایی است که با استفاده از عملیات ضرب و جمع بدست می آیند.

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

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

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

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

کانولوشن گسسته

عمل کانولوشن را می توان با استفاده از ضرب ماتریسی انجام داد. برای انجام این کار یکی از ورودی ها باید به شکل ماتریس توپلیتز دربیاید. برای مثال، کانولوشن $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}}

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

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

ماتریس گردشی: ماتریس توپلیتزی که ویژگی $a_{i}=a_{i+n}$ را داراست.
ماتریس هنکل: یک ماتریس توپلیتز که وارونگی بالا به پایین دارد.
عملگر توپلیتز یک ماتریس توپلیتز با بینهایت سطر و ستون.

Notes

↑ Press et al. (2007).
↑ Krishna & Wang (1993).
↑ Monahan (2011).
↑ Brent (1999).
↑ Bojanczyk et al. (1995).
↑ Stewart (2003).
↑ Chen et al. (2006)
↑ Chan & Jin (2007).
↑ Chandrasekeran et al. (2007).

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. doi:10.1137/040617200
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. doi:10.1198/016214505000001069
Golub G.H., van Loan C.F. (1996), Matrix Computations (انتشارات دانشگاه جانز هاپکینز), Section 4.7—Toeplitz and Related Systems.
Gray R.M., Toeplitz and Circulant Matrices: A Review (Now Publishers).
Krishna, H. (1993). "The Split Levinson Algorithm is weakly stable". SIAM Journal on Numerical Analysis. 30 (5): 1498–1508. doi:10.1137/0730078.
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), §2.8.2—Toeplitz matrices. ISBN 978-0-521-88068-8
Stewart M. (2003), "A superfast Toeplitz solver with improved numerical stability", SIAM Journal on Matrix Analysis and Applications, 25: 669-693. doi:10.1137/S089547980241791X

[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).