Понятие ленты матрицы. Ленточный метод хранения разреженной матрицы

Пусть - симметричная матрица с элементами . Для -ой строки , , обозначим:

, .

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

.

Определим ширину ленты матрицы следующим образом:

.

Число называется -ой шириной ленты . Лента определяется следующим образом:

,

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

Пример. Матрица на рис.2 (ненулевые элементы обозначены звездочками) имеет ширину ленты, равную трем.

Рис.2.

Матрица с шириной ленты, равной единице, называется трехдиагональной.

Применение ленточного метода подразумевает, что нули вне игнорируются; нули же внутри ленты обычно хранятся. Использование разреженности здесь основано на соотношении:

, (10)

где - нижний треугольный множитель Холесского в разложении . Действительно, как следует из (10), если при разложении матрицы возникнут заполнения, то они могут возникнуть только всередине ленты, а нули нижнего (верхнего) треугольника матрицы вне ленты останутся нулями в нижнем (верхнем) треугольнике (), т.е. нули вне ленты можно не хранить.

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

Рис.3.

Дата добавления: 2014-01-11