Ленточная матрица
В математике , особенно в теории матриц , ленточная матрица или полосчатая матрица — это разреженная матрица , ненулевые элементы которой ограничены диагональной полосой , состоящей из главной диагонали и нуля или более диагоналей с каждой стороны.
Ленточная матрица
[ редактировать ]Пропускная способность
[ редактировать ]Формально рассмотрим ) размера n × n матрицу A = ( a i,j . Если все элементы матрицы равны нулю за пределами полосы с диагональной границей, диапазон которой определяется константами k 1 и k 2 :
то величины k 1 и k 2 называются более низкая пропускная способность и верхняя полоса пропускания соответственно. [1] полоса пропускания матрицы равна максимуму k 1 и k 2 ; другими словами, это число k такое, что если . [2]
Примеры
[ редактировать ]- Ленточная матрица с k 1 = k 2 = 0 является диагональной матрицей
- Ленточная матрица с k 1 = k 2 = 1 является трехдиагональной матрицей.
- При k 1 = k 2 = 2 имеем пятидиагональную матрицу и так далее.
- Треугольные матрицы
- Для k 1 = 0, k 2 = n −1 получаем определение верхнетреугольной матрицы
- аналогично, для k 1 = n −1, k 2 = 0 получается нижняя треугольная матрица.
- Верхняя и нижняя матрицы Хессенберга
- Матрицы Теплица при ограничении полосы пропускания.
- Блочные диагональные матрицы
- Матрицы сдвига и матрицы сдвига
- Матрицы в жордановой нормальной форме
- Матрица линий горизонта , также называемая «матрицей переменных полос» — обобщение полосовой матрицы.
- Обратные к матрицам Лемера являются постоянными трехдиагональными матрицами и, следовательно, являются ленточными матрицами.
Приложения
[ редактировать ]В численном анализе матрицы из задач конечных элементов или конечных разностей часто объединяются. Такие матрицы можно рассматривать как описания связи между переменными задачи; полосчатое свойство соответствует тому факту, что переменные не связаны на сколь угодно больших расстояниях. Такие матрицы можно разделить дальше - например, существуют полосовые матрицы, в которых каждый элемент в полосе не равен нулю.
Проблемы в более высоких измерениях также приводят к полосчатым матрицам, и в этом случае сама полоса также имеет тенденцию быть разреженной. Например, уравнение в частных производных в квадратной области (с использованием центральных разностей) даст матрицу с шириной полосы, равной квадратному корню из размера матрицы, но внутри полосы только 5 диагоналей отличны от нуля. К сожалению, применение метода исключения Гаусса (или, что эквивалентно, LU-разложения ) к такой матрице приводит к тому, что полоса заполняется множеством ненулевых элементов.
Хранение браслета
[ редактировать ]Матрицы ленты обычно сохраняются путем хранения диагоналей в полосе; остальное неявно равно нулю.
Например, трехдиагональная матрица имеет полосу пропускания 1. Матрица 6х6
хранится как матрица 6х3
Дальнейшая экономия возможна, когда матрица симметрична. Например, рассмотрите симметричную матрицу 6х6 с верхней пропускной способностью 2:
Эта матрица хранится как матрица 6х3:
Ленточная форма разреженных матриц
[ редактировать ]С вычислительной точки зрения работа с ленточными матрицами всегда предпочтительнее работы с квадратными матрицами аналогичного размера . По сложности ленточную матрицу можно сравнить с прямоугольной матрицей, размерность строки которой равна полосе пропускания ленточной матрицы. вычислений Таким образом, объем работы, связанной с выполнением таких операций, как умножение, значительно сокращается, что часто приводит к огромной экономии времени и сложности .
Поскольку разреженные матрицы позволяют более эффективно выполнять вычисления, чем плотные, а также более эффективно использовать компьютерную память, было проведено много исследований, направленных на поиск способов минимизировать пропускную способность (или напрямую минимизировать заполнение) путем применения перестановок к матрица или другие подобные преобразования эквивалентности или подобия. [3]
Алгоритм Катхилла-Макки можно использовать для уменьшения пропускной способности разреженной симметричной матрицы . Однако существуют матрицы, для которых обратный алгоритм Катхилла – Макки работает лучше. Существует множество других методов.
Задача нахождения представления матрицы с минимальной пропускной способностью посредством перестановок строк и столбцов является NP-трудной . [4]
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ Голуб и Ван Лоан 1996 , §1.2.1.
- ^ Аткинсон 1989 , с. 527.
- ^ Дэвис 2006 , §7.7.
- ^ Файги 2000 .
Ссылки
[ редактировать ]- Аткинсон, Кендалл Э. (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 .