Перегляд вихідного коду сторінки Смугова матриця

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

==Ширина смуги==

Формально, розглянемо ''n''&times;''n'' матрицю ''A''=(''a''<sub>''i,j'' </sub>). Якщо всі елементи матриці, що не належать смузі чий діапазон визначається сталими ''k''<sub>1</sub> і ''k''<sub>2</sub>: 

:<math>a_{i,j}=0 \quad\mbox{if}\quad j<i-k_1 \quad</math>або<math>\quad j>i+k_2; \quad k_1, k_2 \ge 0.\,</math>

нульові, тоді величини ''k''<sub>1</sub> і ''k''<sub>2</sub> називаються '''нижня ширина смуги''' ({{lang-en|lower bandwidth}}) і '''верхня ширина смуги''' ({{lang-el|upper bandwidth}}), відповідно.{{sfn|Golub|Van Loan|1996|loc=§1.2.1}} Ширина смуги ({{lang-en|bandwidth}}) матриці - це найбільше зі значень ''k''<sub>1</sub> і ''k''<sub>2</sub>; інакше кажучи, це число ''k'' таке, що <math> a_{i,j}=0 </math> якщо <math> |i-j| > k </math>.{{sfn|Atkinson|1989|p=527}}

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

==Приклади==

*Смугова матриця з ''k''<sub>1</sub> = ''k''<sub>2</sub> = 0&nbsp;—це [[діагональна матриця]]
*смугова матриця з ''k''<sub>1</sub> = ''k''<sub>2</sub> = 1&nbsp;—це [[тридіагональна матриця]]
*[[трикутна матриця|трикутні матриці]]
**для ''k''<sub>1</sub> = 0, ''k''<sub>2</sub> = ''n''&minus;1, маємо означення верхньої трикутної матриці
**аналогічно, для ''k''<sub>1</sub> = ''n''&minus;1, ''k''<sub>2</sub> = 0 маємо означення нижньої трикутної матриці.

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

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

Наприклад тридіагональну матрицю
:<math>
\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}
</math>
можна зберігати так:
:<math>
\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}.
</math>
Додаткову економію пам'яті можна отримати якщо матриця симетрична.

== Джерела ==
* {{Гантмахер.Теорія матриць}}
* {{Ланкастер.Теорія матриць}}
* {{Хорн.Джонсон.Матричний аналіз}}
* {{Citation | last = Atkinson | first = Kendall E. | title = An Introduction to Numerical Analysis | year = 1989 | publisher = John Wiley & Sons | isbn = 0-471-62489-6 }}.
* {{Citation | first1=Gene H. | last1=Golub | first2=Charles F. | last2=Van Loan | year=1996 | title=Matrix Computations | edition=3rd | publisher=Johns Hopkins | place=Baltimore | isbn=978-0-8018-5414-9 }}.

== Примітки ==
{{reflist}}

[[Категорія:Розріджені матриці]]