Способы хранения и представления разреженных матриц, операции над ними. Блатов И.А - 28 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

- 28 -
4. Полагаем
=
−
)
1
(
i
IUP
< номер позиции в
JU
, содержащей столбцовый
индекс первого ненулевого элемента
)
1
(
−
i
-й строки правее главной
диагонали > .
5.
0
1
. С помощью массива
IU
определяем в
JU
описание
i
-й строки
матрицы
U
. В позиции РВН
с номерами столбцовых индексов
выделенного участка (если он непустой) и номером строки
i
засылаем
нули.
0
2
. В
i
-ю позицию РВН
помещаем элемент
)
(
i
AD
. Если
i
-я строка
не пуста, то в позиции РВН, соответствующие портрету
i
-й строки
матрицы
A
из массива
AN
.
6. Просматриваем АС
i
-ого столбца . Если он пустой, то переходим к 7. Если
непустой, то для каждого элемента
j
этого списка делаем следующие
операции:
а) с помощью элементов
)
(
j
IUP
определяем участки массивов
UN
JU
,
, в которых содержится описание элементов
j
-й строки
матрицы
U
, имеющих столбцовые индексы
i
≥
;
б) умножаем элементы выделенного участка (массива
UN
) на число
))(
~
( jDU
ij
⋅− (элемент
ij
U
находим в
UN
);
в ) прибавляем новые значения элементов выделенного участка к содержи-
мому соответствующих ячеек РВН;
г) полагаем
1
)
(
)
(
+
=
j
IUP
j
IUP
;
д) приписываем
j
-ю строку к АС
k
-го столбца , где
k
– столбцовый
индекс ненулевого элемента с номером
)
(
j
IUP
, следующий за
i
-м в
j
-й строке матрицы
U
.
7. Если просмотр АС закончен, то выбираем элемент РВН
)
(
i
X
, соответству-
ющий диагональному элементу этой
i
-й строки, и помещаем его в
i
-ю
позицию массива
D
~
, а содержимое РВН делим на элемент , содержащийся
в
i
-й позиции РВН (то есть на )(
~
jD ), после чего в РВН содержится
i
-
я строка матрицы
U
.
8. Выбираем из РВН ненулевые элементы
i
-й строки матрицы
U
(за
исключением
i
-го столбца , в котором находится 1) и помещаем их в
UN
таким образом, чтобы
j
-ому столбцу соответствовал элемент
)
(
j
X
.
9.
1
+
=
i
i
и переходим к 3.
4.1.3. Примеры
Задача 29. Найти треугольное разложение для матрицы
A
. 
                                  - 28 -

4. Полагаем IUP(i −1) =< номер позиции в JU , содержащей столбцовый
   индекс первого ненулевого элемента (i −1) -й строки правее главной
   диагонали > .
    0
5. 1 . С помощью массива IU определяем в JU описание i -й строки
   матрицы U . В позиции РВН X с номерами столбцовых индексов
   выделенного участка (если он непустой) и номером строки i засылаем
   нули.
    2 0 . В i -ю позицию РВН X помещаем элемент AD(i ) . Если i -я строка
   не пуста, то в позиции РВН, соответствующие портрету i -й строки
   матрицы A из массива AN .
6. Просматриваем АС i -ого столбца. Если он пустой, то переходим к 7. Если
   непустой, то для каждого элемента j этого списка делаем следующие
  операции:
    а) с помощью элементов IUP( j ) определяем участки массивов
   JU , UN ,         в которых содержится описание элементов j -й строки
   матрицы U , имеющих столбцовые индексы ≥i ;
   б) умножаем элементы выделенного участка (массива UN ) на число
            ~
   (−U ij ⋅ D( j )) (элемент U ij находим в UN );
   в) прибавляем новые значения элементов выделенного участка к содержи-
   мому соответствующих ячеек РВН;
   г) полагаем IUP( j ) =IUP ( j ) +1;
   д) приписываем j -ю строку к АС k -го столбца, где k – столбцовый
   индекс ненулевого элемента с номером IUP( j ) , следующий за i -м в
    j -й строке матрицы U .

7. Если просмотр АС закончен, то выбираем элемент РВН X (i ) , соответству-
   ющий диагональному элементу этой i -й строки, и помещаем его в i -ю
                     ~
   позицию массива D , а содержимое РВН делим на элемент, содержащийся
                                    ~
   в i -й позиции РВН (то есть на D ( j ) ), после чего в РВН содержится i -
   я строка матрицы U .
8. Выбираем из РВН ненулевые элементы i -й строки матрицы U (за
   исключением i -го столбца, в котором находится 1) и помещаем их в UN
   таким образом, чтобы j -ому столбцу соответствовал элемент X ( j ) .
9. i =i +1 и переходим к 3.

 4.1.3. Примеры
     Задача 29. Найти треугольное разложение для матрицы A .

Страницы