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

                                  - 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 .