مصفوفة توبليتز

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

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

أي${\displaystyle n\times n}$مصفوفة${\displaystyle A}$من الشكل

${\displaystyle A={\begin{bmatrix}a_{0}&a_{-1}&a_{-2}&\cdots &\cdots &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}&\cdots &\cdots &a_{2}&a_{1}&a_{0}\end{bmatrix}}}$

هي مصفوفة توبليتز . إذا${\displaystyle i,j}$عنصر من${\displaystyle A}$يُشار إليه بـ${\displaystyle A_{i,j}}$ثم لدينا

${\displaystyle A_{i,j}=A_{i+1,j+1}=a_{ij}.}$

مصفوفة توبليتز ليست بالضرورة مربعة .

معادلة مصفوفية على الشكل

${\displaystyle Ax=b}$

يُطلق عليه نظام توبليتز إذا${\displaystyle A}$هي مصفوفة توبليتز. إذا${\displaystyle A}$هو${\displaystyle n\times n}$إذا كانت مصفوفة توبليتز، فإن النظام يحتوي على الأكثر على 1000 مصفوفة توبليتز فقط. ${\displaystyle 2n-1}$قيم فريدة، بدلاً من${\displaystyle n^{2}}$لذلك قد نتوقع أن يكون حل نظام توبليتز أسهل، وهذا هو الحال بالفعل.

يمكن حل أنظمة توبليتز بواسطة خوارزميات مثل خوارزمية شور أو خوارزمية ليفينسون في${\displaystyle O(n^{2})}$^{[ 1 ]} [ ^{2 ] وقد ثبت أن} متغيرات هذه الطريقة الأخيرة مستقرة بشكل ضعيف (أي أنها تُظهر استقرارًا عدديًا للأنظمة الخطية جيدة التكييف ). ^{[ 3 ]} ويمكن أيضًا استخدام الخوارزميات لإيجاد محدد مصفوفة توبليتز في${\displaystyle O(n^{2})}$الوقت. ^{[ 4 ]}

يمكن أيضًا تحليل مصفوفة توبليتز (أي تحليلها إلى عوامل)${\displaystyle O(n^{2})}$^{[ 5 ]} خوارزمية Bareiss لتحليل LU مستقرة. [ ^{6 ] يوفر} تحليل LU طريقة سريعة لحل نظام Toeplitz، وكذلك لحساب المحدد. باستخدام رتبة الإزاحة، نحصل على طريقة تتطلب${\displaystyle {\tilde {O}}({\alpha ^{\omega -1}}n)}$العمليات باستخدام خوارزميات ضرب المصفوفات السريعة ، حيث${\displaystyle \alpha }$هي الرتبة و${\displaystyle ^{\sim}2.37\leq \omega <3}$^{[ 7 ]}​

• أن${\displaystyle n\times n}$يمكن تعريف مصفوفة توبليتز على أنها مصفوفة${\displaystyle A}$أين${\displaystyle A_{i,j}=c_{ij}}$، بالنسبة للثوابت${\displaystyle c_{1-n},\ldots ,c_{n-1}}$مجموعة​​${\displaystyle n\times n}$مصفوفات توبليتز هي فضاء جزئي من الفضاء المتجهي لـ${\displaystyle n\times n}$المصفوفات (في ظل جمع المصفوفات والضرب القياسي).
• يمكن إضافة مصفوفتين من نوع توبليتز في${\displaystyle O(n)}$الوقت (عن طريق تخزين قيمة واحدة فقط لكل قطر) وضربه في${\displaystyle O(n^{2})}$وقت.
• مصفوفات توبليتز متناظرة حول المحور . مصفوفات توبليتز المتناظرة متناظرة مركزياً وثنائية التناظر .
• ترتبط مصفوفات توبليتز ارتباطًا وثيقًا بمتسلسلات فورييه ، إذ يمكن تمثيل عملية الضرب بمتعددة حدود مثلثية ، بعد ضغطها إلى فضاء محدود الأبعاد، بواسطة هذه المصفوفة. وبالمثل، يمكن تمثيل الالتفاف الخطي كضرب بمصفوفة توبليتز.
• تُعتبر مصفوفات توبليتز مكافئة تقاربياً للمصفوفات الدائرية مع ازدياد الأبعاد، وهي نتيجة تُعرف باسم نظرية غريناندر-سيغو . ^{[ 8 ]} هذه الخاصية الدائرية التقاربية هي السبب في أن تحويل فورييه المنفصل يُقطّر مصفوفات توبليتز الكبيرة تقريبًا، وهي أساس فعالية تقدير الكثافة الطيفية القائم على تحويل فورييه المنفصل للعمليات المستقرة .
• تتبادل مصفوفات توبليتز تقاربياً . وهذا يعني أنها تقطر في نفس الأساس عندما يؤول بُعد الصف والعمود إلى اللانهاية.
• بالنسبة لمصفوفات توبليتز المتناظرة، يوجد التفكيك

${\displaystyle {\frac {1}{a_{0}}}A=GG^{\operatorname {T} }-(GI)(GI)^{\operatorname {T} }}$

أين${\displaystyle G}$هو الجزء المثلث السفلي من${\displaystyle {\frac {1}{a_{0}}}A}$.

• معكوس مصفوفة توبليتز المتناظرة غير المنفردة له التمثيل التالي

${\displaystyle A^{-1}={\frac {1}{\alpha _{0}}}(BB^{\operatorname {T} }-CC^{\operatorname {T} })}$

أين${\displaystyle B}$و${\displaystyle C}$هي مصفوفات توبليتز المثلثية السفلية و${\displaystyle C}$هي مصفوفة مثلثية سفلية تمامًا. ^{[ 9 ]}

يمكن بناء عملية الالتفاف كضرب مصفوفات، حيث يتم تحويل أحد المدخلات إلى مصفوفة توبليتز. على سبيل المثال، التفاف${\displaystyle h}$و${\displaystyle x}$يمكن صياغتها على النحو التالي:

${\displaystyle y=h\ast x={\begin{bmatrix}h_{1}&0&\cdots &0&0\\h_{2}&h_{1}&&\vdots &\vdots \\h_{3}&h_{2}&\cdots &0&0\\\vdots &h_{3}&\cdots &h_{1}&0\\h_{m-1}&\vdots &\ddots &h_{2}&h_{1}\\h_{m}&h_{m-1}&&\vdots &h_{2}\\0&h_{m}&\ddots &h_{m-2}&\vdots \\0&0&\cdots &h_{m-1}&h_{m-2}\\\vdots &\vdots &&h_{m}&h_{m-1}\\0&0&0&\cdots &h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\vdots \\x_{n}\end{bmatrix}}}$

${\displaystyle y^{T}={\begin{bmatrix}h_{1}&h_{2}&h_{3}&\cdots &h_{m-1}&h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}&0&0&0&\cdots &0\\0&x_{1}&x_{2}&x_{3}&\cdots &x_{n}&0&0&\cdots &0\\0&0&x_{1}&x_{2}&x_{3}&\ldots &x_{n}&0&\cdots &0\\\vdots &&\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\cdots &0&0&x_{1}&\cdots &x_{n-2}&x_{n-1}&x_{n}&0\\0&\cdots &0&0&0&x_{1}&\cdots &x_{n-2}&x_{n-1}&x_{n}\end{bmatrix}}.}$

يمكن توسيع هذا النهج لحساب الارتباط الذاتي ، والارتباط المتبادل ، والمتوسط ​​المتحرك، وما إلى ذلك.

مصفوفة توبليتز ثنائية اللانهاية (أي المدخلات مفهرسة بواسطة${\displaystyle \mathbb {Z} \times \mathbb {Z} }$)${\displaystyle A}$يُحدث مؤثرًا خطيًا على${\displaystyle \ell ^{2}}$.

${\displaystyle A={\begin{bmatrix}&\vdots &\vdots &\vdots &\vdots \\\cdots &a_{0}&a_{-1}&a_{-2}&a_{-3}&\cdots \\\cdots &a_{1}&a_{0}&a_{-1}&a_{-2}&\cdots \\\cdots &a_{2}&a_{1}&a_{0}&a_{-1}&\cdots \\\cdots &a_{3}&a_{2}&a_{1}&a_{0}&\cdots \\&\vdots &\vdots &\vdots &\vdots \end{bmatrix}}.}$

يكون المؤثر المستحث محدودًا إذا وفقط إذا كانت معاملات مصفوفة توبليتز${\displaystyle A}$هي معاملات فورييه لدالة محدودة أساسًا${\displaystyle f}$.

في مثل هذه الحالات،${\displaystyle f}$يُطلق عليه رمز مصفوفة توبليتز${\displaystyle A}$والمعيار الطيفي لمصفوفة توبليتز${\displaystyle A}$يتزامن مع${\displaystyle L^{\infty }}$معيار رمزه. يمكن إيجاد البرهان في النظرية 1.1 من بوتشر وغرودسكي. ^{[ 10 ]}

• المصفوفة الدائرية ، وهي مصفوفة توبليتز مربعة ذات خاصية إضافية تتمثل في${\displaystyle a_{i}=a_{i+n}}$
• مصفوفة هانكل ، وهي مصفوفة توبليتز "مقلوبة" (أي معكوسة الصفوف).
• نظريات حد Szegő – محدد مصفوفات Toeplitz الكبيرة 
• مشغل توبليتز