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

                                    9
внутри ленты в ленточной матрице, также         рассматриваются       как
ненулевые. В обоих случаях можно опускать операции над нулевыми
элементами, выполняя тем самым меньшее число операций, чем указанное в
таблицах. Однако такой способ обработки требует дополнительной проверки
для каждого элемента, и суммарная стоимость вычислений скорее
увеличится, чем уменьшится, если доля нулевых элементов невелика.
   Главные элементы выбираются на диагонали в порядке возрастания
номера, если принят «диагональный выбор главного элемента. Однако, когда
матрица несимметричная, обычно необходимым является выбор k-го
главного элемента из k-го столбца редуцированной матрицы с последующей
его перестановкой в диагональную позицию посредством перестановки двух
строк. Требуемая память в этом случае должна быть достаточна для хранения
нижней полуленты ширины β и верхней полуленты ширины до 2β. Этот
случай выделен в таблицах 1 и 2 как «частичный выбор главного элемента»,
и приведенные там формулы дают лишь верхние оценки объема памяти и
числа операций, так как реальная ширина верхней полуленты может не
достигать значения 2β.
    В таблице 1 для матрицы A приводятся данные, отвечающие
факторизации A=LU. Оценка объема памяти включает все те элементы,
которые рассматриваются как ненулевые, но не включает накладные затраты
памяти, подчас весьма ощутимые, если применяются связные списки или
разреженные форматы хранения. Во всех случаях дополнительно требуются
n ячеек памяти для выполнения прямой или обратной подстановки.
Результаты для факторизации матрицы и для решения системы даются
отдельно друг от друга, так как в прикладных задачах может потребоваться
выполнить факторизацию заданной матрицы только один раз и затем решить
большое количество линейных систем с различными правыми частями.

      2. Методы решения разреженных систем
      алгебраических уравнений. Гауссово исключение
     Для отыскания решения х системы

                                        Ax = b,            (1)

где А – невырожденная квадратная вещественная матрица размеров n×n, а b –
заданный вектор, существует большое количество алгоритмов. Эти
алгоритмы можно разделить на два класса: прямые методы и итерационные
методы. Прямые методы основаны на гауссовом исключении: в результате
выполнения последовательности шагов уравнения или неизвестные системы
модифицируются до тех пор, пока не будет найдено решение. В
итерационных методах обычно выбирается начальное приближение для х,
которое затем улучшается, пока не будет достигнута достаточная точность. В
каждом частном случае оба этих подхода имеют как преимущества, так и
недостатки, и трудно установить общие правила для определения того, какой