مصفوفة النطاقات

في الرياضيات ، وخاصة نظرية المصفوفات ، فإن مصفوفة النطاق أو المصفوفة النطاقية هي مصفوفة متفرقة تقتصر مدخلاتها غير الصفرية على نطاق قطري ، يتألف من القطر الرئيسي وصفر أو أكثر من الأقطار على كلا الجانبين.

• مصفوفة النطاق التي يكون فيها k ₁ = k ₂ = 0 هي مصفوفة قطرية ، بعرض نطاق 0.
• مصفوفة النطاق التي يكون فيها k ₁ = k ₂ = 1 هي مصفوفة ثلاثية الأقطار ، بعرض نطاق 1.
• بالنسبة لـ k ₁ = k ₂ = 2، يكون لدينا مصفوفة خماسية الأقطار وهكذا.
• المصفوفات المثلثية
  • بالنسبة لـ _k1 = 0 و _k2 = n − 1 ، نحصل على تعريف المصفوفة المثلثية العلوية
  • وبالمثل، بالنسبة لـ k ₁ = n − 1، k ₂ = 0، نحصل على مصفوفة مثلثية سفلية.
• مصفوفات هيسنبرغ العليا والسفلى
• مصفوفات توبليتز عندما يكون عرض النطاق الترددي محدودًا.
• المصفوفات القطرية الكتلية
• مصفوفات الإزاحة ومصفوفات القص
• المصفوفات في الشكل الطبيعي لجوردان
• مصفوفة الأفق ، وتسمى أيضًا "مصفوفة النطاق المتغير" - وهي تعميم لمصفوفة النطاق 
• معكوسات مصفوفات ليمر هي مصفوفات ثلاثية الأقطار ثابتة، وبالتالي فهي مصفوفات نطاقية.

في التحليل العددي ، غالبًا ما تكون المصفوفات الناتجة عن مسائل العناصر المحدودة أو الفروق المحدودة مصفوفات نطاقية. يمكن اعتبار هذه المصفوفات بمثابة وصف للترابط بين متغيرات المسألة؛ وتدل خاصية النطاقية على أن المتغيرات لا ترتبط عبر مسافات كبيرة جدًا. يمكن تقسيم هذه المصفوفات إلى فئات فرعية ، فعلى سبيل المثال، توجد مصفوفات نطاقية يكون فيها كل عنصر في النطاق غير صفري. 

تؤدي المسائل في الأبعاد الأعلى أيضًا إلى مصفوفات نطاقية، وفي هذه الحالة يميل النطاق نفسه إلى أن يكون متفرقًا. على سبيل المثال، ينتج عن معادلة تفاضلية جزئية على مجال مربع (باستخدام الفروق المركزية) مصفوفة بعرض نطاق يساوي الجذر التربيعي لبُعد المصفوفة، ولكن داخل النطاق، خمسة عناصر قطرية فقط غير صفرية. لسوء الحظ، يؤدي تطبيق حذف غاوس (أو ما يعادله من تحليل LU ) على مثل هذه المصفوفة إلى امتلاء النطاق بالعديد من العناصر غير الصفرية.

عادة ما يتم تخزين مصفوفات النطاق عن طريق تخزين الأقطار في النطاق؛ أما الباقي فهو صفر ضمنيًا.

على سبيل المثال، المصفوفة ثلاثية الأقطار لها عرض نطاق يساوي 1. المصفوفة 6×6

${\displaystyle {\begin{bmatrix}B_{11}&B_{12}&0&\cdots &\cdots &0\\B_{21}&B_{22}&B_{23}&\ddots &\ddots &\vdots \\0&B_{32}&B_{33}&B_{34}&\ddots &\vdots \\\vdots &\ddots &B_{43}&B_{44}&B_{45}&0\\\vdots &\ddots &\ddots &B_{54}&B_{55}&B_{56}\\0&\cdots &\cdots &0&B_{65}&B_{66}\end{bmatrix}}}$

يتم تخزينها كمصفوفة 6×3

${\displaystyle {\begin{bmatrix}0&B_{11}&B_{12}\\B_{21}&B_{22}&B_{23}\\B_{32}&B_{33}&B_{34}\\B_{43}&B_{44}&B_{45}\\B_{54}&B_{55}&B_{56}\\B_{65}&B_{66}&0\end{bmatrix}}.}$

يمكن تحقيق توفير إضافي عندما تكون المصفوفة متناظرة. على سبيل المثال، لنفترض مصفوفة متناظرة 6×6 ذات عرض نطاق علوي يبلغ 2:

${\displaystyle {\begin{bmatrix}A_{11}&A_{12}&A_{13}&0&\cdots &0\\&A_{22}&A_{23}&A_{24}&\ddots &\vdots \\&&A_{33}&A_{34}&A_{35}&0\\&&&A_{44}&A_{45}&A_{46}\\&sym&&&A_{55}&A_{56}\\&&&&&A_{66}\end{bmatrix}}.}$

يتم تخزين هذه المصفوفة كمصفوفة 6×3:

${\displaystyle {\begin{bmatrix}A_{11}&A_{12}&A_{13}\\A_{22}&A_{23}&A_{24}\\A_{33}&A_{34}&A_{35}\\A_{44}&A_{45}&A_{46}\\A_{55}&A_{56}&0\\A_{66}&0&0\end{bmatrix}}.}$

من الناحية الحسابية، يُفضّل التعامل مع المصفوفات النطاقية دائمًا على التعامل مع المصفوفات المربعة ذات الأبعاد المماثلة . يمكن تشبيه المصفوفة النطاقية من حيث التعقيد بمصفوفة مستطيلة يكون بُعد صفها مساويًا لعرض نطاق المصفوفة النطاقية. وبالتالي، ينخفض ​​الجهد المبذول في إجراء عمليات مثل الضرب بشكل ملحوظ، مما يؤدي غالبًا إلى توفير كبير في وقت الحساب والتعقيد .

نظراً لأن المصفوفات المتفرقة تُتيح حساباً أكثر كفاءة من المصفوفات الكثيفة، فضلاً عن استخدامها الأمثل لمساحة التخزين الحاسوبية، فقد ركزت العديد من الأبحاث على إيجاد طرق لتقليل عرض النطاق الترددي (أو تقليل التعبئة مباشرةً) من خلال تطبيق التباديل على المصفوفة، أو غيرها من تحويلات التكافؤ أو التشابه. ^{[ 3 ]}

يمكن استخدام خوارزمية كوثيل-مكي لتقليل عرض النطاق الترددي للمصفوفة المتناظرة المتفرقة . مع ذلك، توجد مصفوفات يكون أداء خوارزمية كوثيل-مكي العكسية فيها أفضل. وهناك العديد من الطرق الأخرى المستخدمة.

تُعتبر مشكلة إيجاد تمثيل لمصفوفة بأقل عرض نطاق ترددي عن طريق تباديل الصفوف والأعمدة مشكلة صعبة من نوع NP . ^{[ 4 ]}

• المصفوفة القطرية
• عرض نطاق الرسم البياني
• مصفوفة عشوائية

• أتكينسون، كيندال إي. (1989)، مقدمة في التحليل العددي ، جون وايلي وأولاده، رقم ISBN 0-471-62489-6.
• ديفيس، تيموثي أ. (2006)، الطرق المباشرة للأنظمة الخطية المتفرقة ، جمعية الرياضيات الصناعية والتطبيقية، ISBN 978-0-898716-13-9.
• فيج، أورييل (2000)، "التعامل مع صعوبة NP لمسألة عرض نطاق الرسم البياني"، نظرية الخوارزميات - SWAT 2000 ، سلسلة محاضرات في علوم الحاسوب، المجلد  1851، الصفحات 129-145 ، doi : 10.1007/3-540-44985-X_2 .
• جولوب، جين هـ .؛ فان لون، تشارلز ف. (1996)، حسابات المصفوفات (  الطبعة الثالثة)، بالتيمور: جونز هوبكنز، ISBN 978-0-8018-5414-9.
• بريس، دبليو إتش؛ تيوكولسكي، إس إيه؛ فيترلينغ، دبليو تي؛ فلانري، بي بي (2007)، "القسم 2.4" ، وصفات عددية: فن الحوسبة العلمية (  الطبعة الثالثة)، نيويورك: مطبعة جامعة كامبريدج، رقم ISBN 978-0-521-88068-8تمت أرشفة هذا النص من المصدر الأصلي بتاريخ 4 مارس 2016 ، وتمت مراجعته بتاريخ 8 أغسطس 2011..

• معلومات تتعلق بـ LAPACK ومصفوفات النطاقات
• دليل تعليمي حول المصفوفات الشريطية وأنواع المصفوفات المتفرقة الأخرى