Методы работы с разреженными матрицами произвольного вида. Глушакова Т.Н - 18 стр.

                                                                          18
   Важное свойство разреженного исключения                 описывается
соотношением (13), которое указывает на то, что малое число операций,
производимое над каждым элементом, приводит к не столь уж большому
накоплению ошибки. Именно это свойство делает возможным решение очень
больших разреженных систем прямыми методами без чрезмерного роста
ошибок округления. Для того чтобы осуществить систематический анализ
указанного свойства, определим матрицу с целочисленными элементами nij:
                                                               m
                                                        nij =∑ nij( k ) ,                                               (14)
                                                               k =1

где nij( k ) =1 , если и lik, и ukj отличны от нуля;
    nij( k ) =0 , в противном случае;
   m = min(i, j).
   Каждый раз, когда на k-м шаге произведение likukj вычисляется и затем
вычитается из элемента, расположенного в позиции (i, j), к этому элементу
прибавляется ошибка eij(k ) . Если j > i, то (i, j)-й элемент изменятся последний
раз на i – 1-м шаге, а на i-м шаге этот элемент делится на диагональный
элемент lii и запоминается в качестве значения uij. Таким образом, операции,
выполненные над элементом, для которого j > i, дают следующий результат:

         ((a   ij                                                                            ) )
                    −l i1u1 j +eij(1) −l i 2 u 2 j +eij( 2) −Κ −l i ,i −1u i −1, j +eij( i −1) / l ii (1 +ε ) =u ij ,     (15)

где множитель (1 + ε) введен для того, чтобы учесть, согласно соотношению
(5), ошибку, возникающую при выполнении деления на lii. Уравнение (15)
можно переписать в виде
                                                 i −1                 i
                                                                                          ε
                                          aij +∑ eij( k ) =∑ lik u kj −lii u ij              ,                           (16)
                                                 k =1              k =1                 1 +ε

где в частном случае i = 1 суммирование в левой части опускается.
Определим матрицу ошибок E с элементами eij следующим образом:
                                                        i −1
                                                                                 ε
                                              eij =∑ eij( k ) +lii u ij             ,                                   (17)
                                                        k =1                   1 +ε
где j > i.
    Если элемент uij является ненулевым, то число вычитаемых членов в
уравнении (15) равно в точности nij – 1 (так как lii ≠ 0 и поэтому в формуле
(14) nij( i ) =1 ). Сумма в формуле (17) фактически содержит nij – 1 слагаемых.
Если же элемент uij равен нулю, то заполнение не происходит и nij( k ) =0 при k
< i; кроме того, nij( i ) =0 в силу uij = 0; таким образом, nij = 0.
    Рассмотрение случая j ≤ i проводится аналогично. Операции,
выполненные над элементом aij, приводят к следующему результату:
                    aij −li1u1 j +eij(1) −li 2 u 2 j +eij( 2 ) −Κ −l i , j −1u j −1, j +eij( j −1) =lij . (18)