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

                                    41
размерность n – k. Рассмотрим матрицу crT, это квадратная матрица
порядка n – k и ранга 1. K-й шаг гауссово исключения состоит в вычитании
crT из подматрицы, расположенной в строках и столбцах k +1, …, n. Вектор c
становится k-м подстолбцом L, а вектор (1, rT) – k-й строкой U. Пусть n(v)
обозначает число ненулевых элементов вектора v. Стратегию Марковица
можно теперь переформулировать следующим образом: выбрать в активной
подматрице и перевести в позицию (k, k) посредством соответствующих
перестановок строк и столбцов тот ненулевой элемент, для которого
произведение n(c)n(r) минимально. Так как n(c)n(r) – это число ненулевых
элементов матрицы crT, то становится понятно, в каком смысле стратегия
Марковица пытается локально уменьшить заполнение.
    Следует сделать три замечания. Можно рассудить, что произведение
n(c)n(r) минимально, когда минимален каждый из сомножителей, так что
было бы достаточно выбрать на роль главного элемент, стоящий в строке и
столбце с наименьшим числом ненулевых элементов. Такой элемент, однако,
может оказаться нулем и, следовательно, непригодным в качестве главного.
В действительности, во многих случаях все шансы за то, что такой элемент
будет нулевым как раз потому, что он находится в строке и столбце с
наибольшим числом нулей. Ситуация становится еще хуже, когда в расчет
принимают соображения численной устойчивости, так как теперь
отвергаются не только нули, но и слишком малые ненулевые элементы.
Однако, все же верно то, что приемлемый ненулевой элемент,
минимизирующий произведение n(c)n(r), часто соответствует малым n(c) и
n(r). Учтем, что n(c) и n(r) – это в точности число внедиагональных
ненулевых элементов соответственно в k-м столбце L и k-й строке U. Это
проясняет то обстоятельство, что стратегия Марковица по существу пытается
сохранить разреженность L и U.
    Пусть C – множество позиций ненулевых элементов в матрице crT, D –
аналогичное множество для подматрицы, расположенной в A(k) в строках и
столбцах k + 1, …, n. Обычно C1D ≠ ι, поэтому множество F элементов
заполнения, внесенного в A(k+1) на k-м шаге, выражается формулой: F = C –
C1D.
Второе наше замечание относится к тому, что стратегия Марковица
минимизирует |C| = n(c)n(r), но не |F|. Однако минимизация |C| имеет
тенденцию уменьшать и |F|. С другой стороны, число |C| = n(c)n(r) равно
числу умножений и числу сложений (если засчитывать сложения с нулями),
выполняемых на k-м шаге. Следовательно, метод Марковица локально
минимизирует число умножений и сложений. Число делений за шаг равно
n(r), это число очень мало.
    Наше третье замечание касается вопроса устойчивости. Стратегия
Марковица сама по себе не гарантирует численной устойчивости. Типичным
является следующее правило, сочетающее стратегию Марковица с одним из
критериев устойчивости: на каждом шаге среди всех ненулевых элементов
активной      подматрицы,     удовлетворяющих      принятому    критерию
устойчивости, выбрать в качестве главного тот, для которого минимально