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

                                                    21
единственного элемента a , и множество Ssp обязательно должно
                                        (k )
                                        ij

содержать этот элемент. В случае полного выбора главного элемента рост
элементов матриц ограничен следующим образом

                                    (
                 aij( k −1) ≤k 1 / 2 2131 / 2 Κ k 1 /( k −1)    )
                                                                1/ 2
                                                                       a 0 <2k (ln k +2 ) / 4 a 0 ,

где a0 = max|aij|. Истинная верхняя граница намного меньше. Указанная
стратегия гарантирует тесные границы для величин aij в (12), но не является
удовлетворительной с точки зрения сохранения разреженности, так как не
дает никакой свободы для управления степенью заполнения. Полный выбор
главного элемента рекомендуется применять лишь для плотных матриц
небольшого размера, когда главной целью является достижение наилучшей
численной устойчивости.
   Частичный выбор главного элемента заключается в отыскании
наибольшего по модулю элемента в каком-либо столбце (или строке)
активной подматрицы с последующим выполнением соответствующих
перестановок. Линия выбора главного элемента (под линией подразумевается
строка или столбец) определяется из соображений сохранения
разреженности. Таким образом, множество Spc содержит все активные
ненулевые элементы, так как для отыскания линии выбора главного элемента
нужно произвести просмотр всей активной подматрицы. Множество Ssp
содержит в точности все ненулевые элементы линии выбора главного
элемента. Множество Sst в этом случае является подмножеством Ssp: оно
содержит наибольшие по модулю элементы из Ssp. Множество Spiv совпадает
с Sst. Из уравнения (11) (пренебрегая величиной eij(k ) ) можно вывести
следующую оценку, справедливую, если используется частичный выбор
главного элемента:
                                          aij( k +1) ≤2 max aij( k ) .
                                                         i, j

Эта оценка гарантирует, что на каждом шаге элементы могут увеличиться не
более чем в два раза, и, таким образом, в итоге увеличение произойдет не
более чем в 2ν раз, где ν = max(nij) – 1 – максимальное число операций,
выполненных над каждым отдельно взятым элементом. Однако
действительный рост элементов оказывается, как правило, гораздо более
медленным, и если требуется получить более точные границы ошибок, то
необходимо осуществлять контроль величины элементов матриц или
использовать хороший способ оценки величины элементов.
   Частичный выбор главного элемента позволяет использовать некоторые
преимущества разреженного случая, однако возможности этой схемы все же
слишком ограничены. Без существенного ухудшения результатов удается
получить более гибкую схему, если использовать стратегию порогового
выбора главного элемента. В этой стратегии все ненулевые элементы
активной подматрицы включаются в множество Spc. Выбирается параметр
допустимости u, лежащий в полуинтервале 0 < u ≤ 1, и Sst определяется как