Понятие ленты матрицы. Ленточный метод хранения разреженной матрицы
Пусть 
- симметричная матрица с элементами 
. Для 
-ой строки , 
, обозначим:
, 
.
Число 
- это столбцовый индекс первого ненулевого элемента -ой строки . Если предположить, что матрица еще и положительно определенная, то ее диагональные элементы 
, положительны, и
.
Определим ширину ленты матрицы следующим образом:
.
Число 
называется -ой шириной ленты . Лента определяется следующим образом:
,
т.е. это область матрицы, удаленная от главной диагонали не более, чем на 
позиций.
Пример.Матрица на рис.2 (ненулевые элементы обозначены звездочками) имеет ширину ленты, равную трем.
Рис.2.
Матрица с шириной ленты, равной единице, называется трехдиагональной.
Применение ленточного метода подразумевает, что нули вне 
игнорируются; нули же внутри ленты обычно хранятся. Использование разреженности здесь основано на соотношении:
, (10)
где 
- нижний треугольный множитель Холесского в разложении 
. Действительно, как следует из (10), если при разложении матрицы возникнут заполнения, то они могут возникнуть только всередине ленты, а нули нижнего (верхнего) треугольника матрицы вне ленты останутся нулями в нижнем (верхнем) треугольнике (
), т.е. нули вне ленты можно не хранить.
Исходя из вышесказанного, обычным методом хранения симметричной ленточной матрицы является так называемая диагональная схема хранения. Поддиагонали нижнего треугольника , составляющие , вместе с главной диагональю хранятся по столбцам в прямоугольном массиве с размерами 
(пример представлен на рис.3).
Рис.3.
Дата добавления: 2014-01-11; просмотров: 5930; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!