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

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

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

Пропускная способность

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

$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 ₂ называются более низкая пропускная способность и верхняя полоса пропускания соответственно. полоса пропускания матрицы равна максимуму k ₁ и k ₂ ; другими словами, это число k такое, что $a_{i,j}=0$ если $|i-j|>k$.

Примеры

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

Приложения

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

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

Хранение браслета

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

Например, трехдиагональная матрица имеет полосу пропускания 1. Матрица 6х6

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

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

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

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

Ленточная форма разреженных матриц

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

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

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

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

См. также

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

Ссылки

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

Внешние ссылки

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