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

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

Ширина смуги

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

$a_{i,j}=0\quad {\mbox{if}}\quad j<i-k_{1}\quad$або$\quad j>i+k_{2};\quad k_{1},k_{2}\geq 0.\,$

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

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

Приклади

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

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

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

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

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

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

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

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

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

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

Джерела

• Гантмахер Ф. Р. Теория матриц. — 5-е. — М: : Физматлит, 2010. — 559 с. — ISBN 5-9221-0524-8.(рос.)
• Ланкастер П. Теория матриц. — 2. — Москва : Наука, 1982. — 272 с.(рос.)
• Р.Хорн, Ч.Джонсон. Матричный анализ. — М: : Мир, 1989. — 653 с.(рос.)
• Atkinson, Kendall E. (1989), An Introduction to Numerical Analysis, John Wiley & Sons, ISBN 0-471-62489-6.
• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (вид. 3rd), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.