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

                                           22
множество всех элементов a   (k )
                             ij     из Spc, удовлетворяющих          одному       из
следующих условий:
                              aij( k ) ≥u max a (pjk ) ,                      (21а)
                                          k ≤p ≤n



                             aij( k ) ≥u max aiq( k ) .                       (21б)
                                         k ≤q ≤n

Множество Ssp определяется независимо, обычно на основе какого-либо
варианта критерия Марковица. Окончательный выбор главного элемента
производится из множества Spiv = Sst 1 Ssp, причем опять привлекаются
соображения сохранения разреженности. Затем выбранный элемент
перемещается в позицию (k, k) при помощи перестановок. Если множество
Spiv оказывается пустым, то Sst должно быть расширено посредством
уменьшения значения u. На практике, однако, работу этой процедуры
организуют другим способом. Сначала выбирается элемент из Spc,
наилучший с точки зрения сохранения разреженности. Затем проверяется,
выполняются ли условия (21) для этого элемента. Если условия (21)
удовлетворяются, то выбранный элемент принимается в качестве главного. В
противном случае выбирается новый элемент исходя из соображений
сохранения разреженности. Однако последняя ситуация встречается
сравнительно редко и дополнительный поиск не вносит большого вклада в
общие затраты при условии, что выбрано разумное значение u. Значение u=1
отвечает стратегии частичного выбора главного элемента. Считается, что
конкретный выбор u не является очень критичным, и обычно рекомендуется
выбирать значение u = 0.25. Значение u = 0.1 позволяет получить хорошее
сохранение как разреженности, так и устойчивости, однако малые значения,
например u=0.01, можно использовать в случае небольших значений
величины ν = max(nij) – 1, встречающихся в задачах линейного
программирования.
    Пренебрегая величиной eij(k ) в уравнении (11) и предполагая
справедливость условий (21), получаем оценку

                                          (         )
                               aij( k +1) ≤ 1 +u −1 max aij( k ) ,
                                                          i, j



которая гарантирует, что рост элементов матриц на каждом шаге ограничен
множителем (1 + u-1), и общее увеличение происходит не более чем в (1 + u-
1 ν
 ) раз. Действительный рост элементов обычно происходит намного
медленнее. Пороговый выбор главного элемента является весьма популярной
стратегией и используется в большинстве стандартных программ.
    Две другие стратегии выбора главного элемента были предложены
Златевым. Эти стратегии зависят от параметра устойчивости u, выбираемого
в пределах 0