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

                                      20
Следовательно,
                            x −~
                               x = A −1r ≤ A −1 r ,

и если доступна оценка для нормы ||А-1||, то можно найти границу нормы
погрешности решения x −~x .

      2.6 Численная устойчивость и выбор главных
      элементов
      Исследуем теперь наиболее распространенные стратегии выбора
главного элемента с точки зрения численной устойчивости. Активная
подматрица на k-м шаге включает в себя все элементы aij(k ) , для которых i ≥
k, j ≥ k. Элементы активной подматрицы будем называть активными
элементами. Для изложения нам потребуются следующие четыре
подмножества элементов активной подматрицы:
  Spc – подмножество, состоящее из тех ненулевых элементов активной
  подматрицы, среди которых осуществляется поиск. Это подмножество
  определяется с целью сокращения объема поиска при выборе главного
  элемента, что приводит к уменьшению трудоемкости выбора;
  Sst – подмножество элементов из Spc, удовлетворяющих некоторому
  условию устойчивости;
  Ssp – подмножество элементов из Spc, удовлетворяющих некоторому
  критерию сохранения разреженности;
  Spiv = Sst 1 Ssp – множество, из которого выбирается главный элемент.
  Элементы этого множество удовлетворяют как требованиям сохранения
  разреженности, так и условиям устойчивости.
   Определения множеств Sst и Ssp не обязаны быть независимыми. Иногда Sst
определяется как подмножество Ssp, или наоборот. Главный элемент
выбирается из множества Spiv. Если это множество содержит более одного
элемента, вновь принимаются во внимание соображения разреженности, и на
их основе производится окончательный выбор. Таким образом, трудоемкость
понижается настолько, насколько это возможно, за счет улучшения
разреженности, в то время как условия устойчивости по-прежнему
удовлетворяются. Если на некотором этапе оказывается, что множество Spiv
пусто, то требования разреженности ослабляются, и множество Ssp
переопределяется. Выбранный критерий устойчивости не должен быть
слишком жестким с тем, чтобы множество Sst было достаточно широким. На
практике явное определение указанных четырех множеств обычно не
производится, так как оказывается возможным использование упрощенных
процедур.
   При полном выборе главного элемента множество Spc на k-м шаге состоит
из всех ненулевых элементов активной подматрицы. Ненулевой элемент,
имеющий наибольшую абсолютную величину, скажем aij(k ) , выбирается в
качестве k-го главного элемента и перемещается в позицию (k, k) путем
перестановки i-й и k-й строк и j-го и k-го столбцов. Множество Sst состоит из