Jump to content

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

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

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

[ редактировать ]

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

[ редактировать ]

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

то величины k 1 и k 2 называются более низкая пропускная способность и верхняя полоса пропускания соответственно. [1] полоса пропускания матрицы равна максимуму k 1 и k 2 ; другими словами, это число k такое, что если . [2]

Приложения

[ редактировать ]

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

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

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

[ редактировать ]

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

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

хранится как матрица 6х3

Дальнейшая экономия возможна, когда матрица симметрична. Например, рассмотрите симметричную матрицу 6х6 с верхней пропускной способностью 2:

Эта матрица хранится как матрица 6х3:

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

[ редактировать ]

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

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

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

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

См. также

[ редактировать ]

Примечания

[ редактировать ]
  • Аткинсон, Кендалл Э. (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 .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: f1aa687bfccf9c11bb6f57e311470499__1714453140
URL1:https://arc.ask3.ru/arc/aa/f1/99/f1aa687bfccf9c11bb6f57e311470499.html
Заголовок, (Title) документа по адресу, URL1:
Band matrix - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)