И другие программы этой серии
Причем форми-
Рис.5.2. Пример применения функции symmmd
руется такая перестановка r, что S(r,r) будет концентрировать ненулевые элементы вблизи диагонали. Это хорошее упорядочение как перед LU-разложением, так и перед разложением Холецкого. Упорядочение применимо как для симметрических, так и для несимметрических матриц. Для вещественной симметрической разреженной матрицы S (такой, что S=ST) собственные значения S(r,r) совпадают с собственными значениями S, но для вычисления eig(S(r,r)) требуется меньше времени, чем для вычисления eig(S). Пример:
>> B=bucky;p=symrcm(B); R=B(p,p);
>> subplot(1,2,1),spy(B);subplot(1,2,2),spy(R)
На рис. 5.3 приведен пример концентрации ненулевых элементов разреженной матрицы вблизи главной диагонали.
Рис.5.3. Пример применения функции symrcm
5.2. Применение разреженных матриц
5.2.1. Смежные матрицы и графы
Во многих приложениях математики используются графы. Их можно определить как совокупность точек (узлов) со спецификацией соединений между ними. Графы можно экономно представлять с помощью разреженных смежных матриц. Эти матрицы имеют в основном нулевые элементы, но часть последних имеет единичные значения и используется для факта соединения вершин графов, что и создает те или иные фигуры.
Пример представления графа – фигуры ромба, имеющего 4 узла, – с помощью смежной матрицы A представлен на рис. 5.4.
Полное описание графа требует, кроме задания смежной матрицы, указания списка xy координат узлов, например:
246
Типы данных – массивы специального вида
Применение разреженных матриц
247
Рис.5.4. Пример представления графа с помощью разреженной смежной матрицы
A=[0 1 0 1; 1 0 1 0; 0 1 0 1; 1 0 1 0]l; xy=[1 2; 2 1; 3 3; 2 5]
Тогда с помощью графической функции gplot можно построить граф:
gplot(A,xy)
Узлы графа при этом будут построены по явно заданным координатам.
5.2.2. Пример построения фигуры bucky
Аналогичным описанному способом можно строить довольно сложные фигуры.
Начало в части 1