Смугова матриця - це розріджена матриця чиї ненульові елементи обмежені діагональною смугою, що складається з головної діагоналі і нуля або більше діагоналей з кожного боку.
Ширина смуги
Формально, розглянемо n×n матрицю A=(ai,j ). Якщо всі елементи матриці, що не належать смузі чий діапазон визначається сталими k1 і k2:
або
нульові, тоді величини k1 і k2 називаються нижня ширина смуги () і верхня ширина смуги (), відповідно. Ширина смуги () матриці - це найбільше зі значень k1 і k2; інакше кажучи, це число k таке, що якщо .
Існують алгоритми зменшення ширини смуги матриці, наприклад алгоритм Катхілл-Маккі. Задача знаходження представлення матриці з найменшою шириною смуги - NP-складна.
Приклади
Смугова матриця з k1 = k2 = 0 —це діагональна матриця смугова матриця з k1 = k2 = 1 —це тридіагональна матриця трикутні матриці для k1 = 0, k2 = n−1, маємо означення верхньої трикутної матриці аналогічно, для k1 = n−1, k2 = 0 маємо означення нижньої трикутної матриці.
Застосування У чисельних методах, матриці із задач скінченних елементів або скінченних різниць часто смугові. Такі матриці можна розглядати як опис прямої взаємодії між змінними задачі; смуговість відповідає факту, що змінні не взаємодіють напряму на довільно великих відстанях.
Оптимізація вимог до пам'яті Смугові матриці зазвичай зберігаються у вигляді діагоналей; інші елементи нулі.
Наприклад тридіагональну матрицю
можна зберігати так:
Додаткову економію пам'яті можна отримати якщо матриця симетрична.
Джерела
. .
Примітки