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

                                                     14
                                     lik =a   (k )
                                              ik          при i ≥ k.       (4')

    Можно получить формулу, показывающую, как выражается A(k+1) через
A(k):

                          aij( k +1) =aij( k ) −lik u kj , i >k , j >k ,

   откуда можно вывести полные выражения для элементов матрицы A(k):
                                                k −1
                          a   (k )
                              ij     =aij −∑ lim u mj , i >k , j >k .
                                                m =1


      2.3 Гауссово исключение по строкам
      Для разреженных матриц, хранящихся в строчном формате,
исключение по строкам намного более эффективно, чем исключение по
столбцам. В обоих случаях получаются одинаковые численные результаты, и
затрачивается одно и то же количество арифметических операций.
Повышение эффективности достигается за счет того, что элементы матрицы
используются в естественном порядке, т.е. в том порядке, в каком хранятся.
Гауссово исключение для матрицы А по строкам выполняется в n шагов. В
начале k-го шага имеется матрица A(k), содержащая в строках с первой по (k –
1)-ю нулевые элементы левее диагонали и единицы в первых (k – 1) позициях
на диагонали. На k-м шаге производится исключение ненулевых элементов k-
й строки, расположенных левее диагонали, путем вычитания взятых с
соответствующими множителями первой строки, второй строки, …, (k – 1)-й
строки в указанном порядке. Затем каждая строка нормируется путем
деления всех ее элементов на диагональный элемент.

      2.4 Исключение Гаусса – Жордана
        Алгоритм исключения Гаусса – Жордана по столбцам аналогичен
гауссову исключению по столбцам; главное отличие состоит в том, что перед
k-м шагом матрица A(k) имеет нулевые элементы в столбцах от первого до k-
го как ниже, так и выше диагонали. Шаг с номером k алгоритма состоит в
исключении ненулевых элементов k-го столбца матрицы A(k), расположенных
как выше, так и ниже диагонали. Сначала нормируется k-я строка, для чего
все ее элементы делятся на диагональный элемент, находящийся в позиции
(k, k). Затем нормированная k-я строка умножается на подходящие скаляры и
вычитается из всех строк, имеющих ненулевые элементы в k-м столбце как
выше, так и ниже диагонали. Таким образом, получается матрица A(k+1) с
нулями во внедиагональных позициях первых k столбцов. Описанный
процесс продолжается до тех пор, пока в результате выполнения последнего
шага не получится единичная матрица A(n+1) ≡ I.
    Исключение Гаусса – Жордана может также производиться по строкам.
Столбцовая версия использует сложение k-й строки, умноженной на