Ленточная матрица

В математике , в частности , теории матриц , в ленточной матрицы или ленточной матрицы является разреженной матрицей , чьи ненулевые элементы заключены в диагональной полосы , включающий главной диагонали и ноль или более диагоналей с обеих сторон.

Матрица полос [ править ]

Пропускная способность [ править ]

Формально рассмотрим матрицу размера n × n A = ( a _{i, j} ). Если все элементы матрицы равны нулю за пределами полосы с диагональной границей, диапазон которой определяется константами k ₁ и k ₂ :

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

тогда величины k ₁ и k ₂ называются соответственно нижней и верхней полосой пропускания . ^[1] Полоса пропускания матрицы - максимум k ₁ и k ₂ ; другими словами, это число k такое, что если . ^[2]${\ displaystyle a_ {i, j} = 0}$${\ displaystyle | ij |> k}$

Примеры [ править ]

• Зонная матрица с k ₁ = k ₂ = 0 является диагональной матрицей
• Зонная матрица с k ₁ = k ₂ = 1 является трехдиагональной матрицей
• При k ₁ = k ₂ = 2 получается пятидиагональная матрица и так далее.
• Треугольные матрицы
  • При k ₁ = 0, k ₂ = n −1 получаем определение верхнетреугольной матрицы
  • аналогично, при k ₁ = n −1, k ₂ = 0 получается нижняя треугольная матрица.
• Верхняя и нижняя матрицы Гессенберга
• Матрицы Теплица при ограниченной пропускной способности.
• Блочно-диагональные матрицы
• Матриц сдвига и сдвига матрицы
• Матрицы в жордановой нормальной форме
• Матрица горизонта , также называемая «переменная матрица группы» - обобщение ленточной матрицы
• Матрицы, обратные матрицам Лемера, являются постоянными трехдиагональными матрицами и, таким образом, являются ленточными матрицами.

Приложения [ править ]

В численном анализе матрицы из задач конечных элементов или конечных разностей часто являются ленточными. Такие матрицы можно рассматривать как описание связи между переменными проблемы; свойство полосатости соответствует тому факту, что переменные не связаны на сколь угодно больших расстояниях. Такие матрицы могут быть дополнительно разделены - например, существуют ленточные матрицы, в которых каждый элемент в ленте отличен от нуля. Они часто возникают при выделении одномерных задач. ^{[ необходима цитата ]}

Проблемы в более высоких измерениях также приводят к полосчатым матрицам, и в этом случае сама полоса также имеет тенденцию быть разреженной. Например, уравнение в частных производных в квадратной области (с использованием центральных разностей) даст матрицу с шириной полосы, равной квадратному корню из размерности матрицы, но внутри полосы только 5 диагоналей ненулевые. К сожалению, применение исключения Гаусса (или, что эквивалентно, разложения LU ) к такой матрице приводит к тому, что полоса заполняется множеством ненулевых элементов.

Band Storage [ править ]

Матрицы полос обычно сохраняются путем сохранения диагоналей в полосе; остальное неявно равно нулю.

Например, трехдиагональная матрица имеет пропускную способность 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]

Алгоритм Cuthill-Макки может быть использован , чтобы уменьшить ширину полосы разреженной симметричной матрицы . Однако существуют матрицы, для которых обратный алгоритм Катхилла – Макки работает лучше. Есть много других используемых методов.

Задача нахождения представления матрицы с минимальной шириной полосы с помощью перестановок строк и столбцов является NP-трудной . ^[4]

См. Также [ править ]

• Диагональная матрица
• Пропускная способность графика

Заметки [ править ]

Ссылки [ править ]

• Аткинсон, Кендалл Э. (1989), Введение в численный анализ , John Wiley & Sons, ISBN 0-471-62489-6.
• Дэвис, Тимоти А. (2006), Прямые методы для разреженных линейных систем , Общество промышленной и прикладной математики, ISBN 978-0-898716-13-9.
• Feige, Уриэль (2000), "Борьба с NP-Твердость графа Bandwidth задачи", теория алгоритмов - Спецназ 2000 , Lecture Notes в области компьютерных наук, 1851 , стр 129-145,. DOI : 10.1007 / 3-540-44985 -X_2.
• Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Балтимор: Джонс Хопкинс, ISBN 978-0-8018-5414-9.
• Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, Б.П. (2007), «Раздел 2.4» , Численные рецепты: Искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN. 978-0-521-88068-8.

Внешние ссылки [ править ]

• Информация, относящаяся к LAPACK и матрицам полос
• Учебник по ленточным матрицам и другим форматам разреженных матриц