Смугова матриця

Смугова матриця - це розріджена матриця чиї ненульові елементи обмежені діагональною смугою, що складається з головної діагоналі і нуля або більше діагоналей з кожного боку.

Ширина смуги

Формально, розглянемо n×n матрицю A=(a_i,j ). Якщо всі елементи матриці, що не належать смузі чий діапазон визначається сталими k₁ і k₂:

$a_{i,j}=0\text{if}j<i-k_1$або$j>i+k_2;k_1,k_2\ge 0.$

нульові, тоді величини k₁ і k₂ називаються нижня ширина смуги (Шаблон:Lang-en) і верхня ширина смуги (Шаблон:Lang-el), відповідно.Шаблон:Sfn Ширина смуги (Шаблон:Lang-en) матриці - це найбільше зі значень k₁ і k₂; інакше кажучи, це число k таке, що $a_{i,j}=0$ якщо $|i-j|>k$.Шаблон:Sfn

Існують алгоритми зменшення ширини смуги матриці, наприклад алгоритм Катхілл-Маккі. Задача знаходження представлення матриці з найменшою шириною смуги - NP-складна.

Приклади

• Смугова матриця з k₁ = k₂ = 0 —це діагональна матриця
• смугова матриця з k₁ = k₂ = 1 —це тридіагональна матриця
• трикутні матриці
  • для k₁ = 0, k₂ = n−1, маємо означення верхньої трикутної матриці
  • аналогічно, для k₁ = n−1, k₂ = 0 маємо означення нижньої трикутної матриці.

Застосування

У чисельних методах, матриці із задач скінченних елементів або скінченних різниць часто смугові. Такі матриці можна розглядати як опис прямої взаємодії між змінними задачі; смуговість відповідає факту, що змінні не взаємодіють напряму на довільно великих відстанях.

Оптимізація вимог до пам'яті

Смугові матриці зазвичай зберігаються у вигляді діагоналей; інші елементи нулі.

Наприклад тридіагональну матрицю

$\left[\begin{array}{cccccc}{B}_{11}& B_{12}& 0& \cdots & \cdots & 0\\ B_{21}& B_{22}& B_{23}& \ddots & \ddots & ⋮\\ 0& B_{32}& B_{33}& B_{34}& \ddots & ⋮\\ ⋮& \ddots & B_{43}& B_{44}& B_{45}& 0\\ ⋮& \ddots & \ddots & B_{54}& B_{55}& B_{56}\\ 0& \cdots & \cdots & 0& B_{65}& B_{66}\end{array}\right]$

можна зберігати так:

$\left[\begin{array}{ccc}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{array}\right].$

Додаткову економію пам'яті можна отримати якщо матриця симетрична.

Джерела

• Шаблон:Гантмахер.Теорія матриць
• Шаблон:Ланкастер.Теорія матриць
• Шаблон:Хорн.Джонсон.Матричний аналіз
• Шаблон:Citation.
• Шаблон:Citation.