مصفوفة توبليتز: الفرق بين النسختين

تم حذف المحتوى تمت إضافة المحتوى

مضمن

نسخة 01:22، 17 يونيو 2017

مصفوفة توبلتز في الج في الجبر الخطي، والمسماة نسبة لأوتو توبلتز، هي مصفوفة تكون فيها الأقطار مرتبة تنازليا، بحيث يحتوي كل قطر على نفس العناصر. على سبيل المثال: المصفوفة التالية تمثل مصفوفة توبلتز لأنها تحتوي نفس العناصر على أقطارها (البداية تكون من اليسار العلوي إلى اليمين السفلي).

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

المصفوفة A ذات الأبعاد n×n تعتبر مصفوفة توبلتز بشكلها العام.

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 بالرمز Ai,j ، عندها تنطبق الصيغة التالية:

A_{i,j}=A_{i+1,j+1}=a_{i-j}.\

مثلا لو نظرنا إلى العنصر a_1 الأول من اليسار (الصف 1 والعمود 1)، ثم زدنا عدد الصفوف والأعمدة بقيمة 1 فإننا ننتقل إلى الصف الثاني والعمود الثاني لنجد نفس العنصر a_1 وهكذا حتى نهاية المصفوفة. مصفوفة توبلتز ليست بالضرورة مصفوفة مربعة.

خصائص عامة

مصفوفة توبليتز يمكن تعريفها كمصفوفة A ذات العناصر Ai,j = ci−j للقيم c1−n … cn−1.

يمكن إتمام عملية الجمع لمصفوفتين توبليتز في زمن قدره O(n) والضرب بزمن O(n²)، كما أن مصفوفة توبلتز مرتبطة بشكل قوي بمصفوفات فورير.

إذا كانت مصفوفة توبليتز مربعة ومنتظمة بحيث تكون عناصر الأقطار مساوية لعناصر الأقطار المقابلة تسمى هذه الخاصية persymmetry.

ترتبط مصفوفة توبليتز أيضا بشكل قوي بمصفوفة فورييه، لان عملية الضرب للمصفوفة بمتجه معين تقابل عملية الإلتفاف (convolution) ببعد مخفض. على سبيل المثال لو تم إرسال إشارة رقمية x ذات العناصر {4,4,1,1,1} عبر نظام خطي غير متغير زمنيا (LTI system) والذي له استجابة نبضية رقمية قيمتها h={3,2,2,3}، فبدلا من تطبيق الإلتفاف الذي يصبح معقدا بين إشارة المدخل x والإستجابة النبضية للنظام h، نحصل على نفس النتيجة بعملية ضرب بين مصفوفة توبليتز المكونة من h بالمتجه x.

Discrete convolution

عملية الإلتفاف الرياضية يمكن أيضا تطبيقها باستخدام الضرب المصفوفي، بحيث يتم تحويل أحد المدخلين (إشارة المدخل أو الاستجابة نبضية) إلى مصفوفة توبليتز وتضرب هذه المصفوفة بالمدخل الآخر لنحصل على النتيجة لعملية الإلتفاف. على سبيل المثال،ضرب إلتفاف استجابة نظام معين النبضية h لإشارة مدخلية x يعطي قيمة المخرج y.

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

يمكن توسعة هذه الصيغة لحساب الترابط التلقائي أو الترابط المتداخل (cross-correlation) أو الوسيط المتغير.

انظر أيضا

مصفوفة هانكل

Notes

References

"Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices"، Numerische Mathematik، ج. 13: 404–424، 1969، DOI:10.1007/BF02163269 {{استشهاد}}: الوسيط |first= يفتقد |first= (مساعدة)الوسيط |first1= يفتقد |last1= في Authors list (مساعدة)
Brent، R.P.؛ Hoog، F.R. De؛ Sweet، D.R. (1995)، "On the stability of the Bareiss and related Toeplitz factorization algorithms"، SIAM Journal on Matrix Analysis and Applications، ج. 16: 40–57، DOI:10.1137/S0895479891221563 {{استشهاد}}: الوسيط |first= يفتقد |first= (مساعدة)الوسيط |first1= يفتقد |last1= في Authors list (مساعدة)
Grudsky، Sergei M. (2012)، Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis، Birkhäuser، ص. 1–، ISBN:978-3-0348-8395-5 {{استشهاد}}: الوسيط |first= يفتقد |first= (مساعدة)الوسيط |first1= يفتقد |last1= في Authors list (مساعدة)
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).
Jin، X.-Q. (2007)، An Introduction to Iterative Toeplitz Solvers، SIAM {{استشهاد}}: الوسيط |first= يفتقد |first= (مساعدة)الوسيط |first1= يفتقد |last1= في Authors list (مساعدة) .
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 {{استشهاد}}: الوسيط |first= يفتقد |first= (مساعدة)الوسيط |first1= يفتقد |last1= في Authors list (مساعدة)
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 {{استشهاد}}: الوسيط |first= يفتقد |first= (مساعدة)الوسيط |first1= يفتقد |last1= في Authors list (مساعدة)
Golub G.H., van Loan C.F. (1996), Matrix Computations (Johns Hopkins University Press) §4.7—Toeplitz and Related Systems.
Gray R.M., Toeplitz and Circulant Matrices: A Review (Now Publishers).
Wang، Y. (1993)، "The Split Levinson Algorithm is weakly stable"، SIAM Journal on Numerical Analysis، ج. 30 ع. 5: 1498–1508، DOI:10.1137/0730078 {{استشهاد}}: الوسيط |first= يفتقد |first= (مساعدة)الوسيط |first1= يفتقد |last1= في Authors list (مساعدة) .
Numerical Methods of Statistics، Cambridge University Press، 2011 {{استشهاد}}: الوسيط |first= يفتقد |first= (مساعدة)الوسيط |first1= يفتقد |last1= في Authors list (مساعدة) .
Pan، Victor Y. (2001)، Structured Matrices and Polynomials: unified superfast algorithms، Birkhäuser، ISBN:0817642404
Teukolsky، S.A.؛ Vetterling، W.T.؛ Flannery، B.P. (2007)، Numerical Recipes: The Art of Scientific Computing (ط. Third)، Cambridge University Press، ISBN:978-0-521-88068-8 {{استشهاد}}: الوسيط |first= يفتقد |first= (مساعدة)الوسيط |first1= يفتقد |last1= في Authors list (مساعدة) .

"A superfast Toeplitz solver with improved numerical stability"، SIAM Journal on Matrix Analysis and Applications، ج. 25: 669–693، 2003، DOI:10.1137/S089547980241791X {{استشهاد}}: الوسيط |first= يفتقد |first= (مساعدة)الوسيط |first1= يفتقد |last1= في Authors list (مساعدة)