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

                                     10
из них окажется более подходящим. Мы           ограничимся   рассмотрением
прямых методов для решения уравнения (1).

      2.1 Гауссово исключение. Постановка задачи
     Решение уравнения (1) может быть записано в виде x=A-1b, но явное
использование этой формы записи производится только в случае небольших
значений n (скажем, n ~ 100 и меньше). Матрица A-1 часто является плотной,
даже если A – разреженная матрица, и ее явное вычисление ведет к потере
преимуществ, свойственных разреженному случаю. Для большинства систем
указанные преимущества извлекаются из того факта, что нет необходимости
получать A-1 в явном виде; достаточно выразить A-1 через произведение
матриц, которые простым способом умножаются на вектор. Конечно, такая
процедура оказывается более удобной, так как матричные сомножители
являются разреженными и при хранении все они могут быть помещены в
значительно меньший объем памяти, чем одна матрица A-1. Кроме того,
произведение матричных сомножителей на вектор b требует меньше
операций, чем вычисление произведения A-1b.
   Обычным способом решения уравнения (1) прямым методом является
вычисление треугольного разложения матрицы А:

                                          A = LU,                    (2)

где U – верхняя треугольная матрица с диагональными элементами, равными
единице, а L – нижняя треугольная. В этом случае A-1 = U-1L-1 и x = U-1ω, где
ω=L-1b. Таким образом, решение уравнения (1) определяется в результате
решения линейной системы

                                          Lω = b                      (3)

относительно ω, а затем – линейной системы

                                      Ux = ω                        (4)
относительно x.
    Если матрица A разрежена, то разреженными будут также и матрицы L и
U, хотя степень их разреженности обычно меньше по сравнению с матрицей
A. Разложение (2) единственно, если оно существует и матрица A
невырождена. Часто из матрицы L выносится в качестве множителя
диагональная матрица D, так что L=L'D, где L' является нижней треугольной
матрицей, все диагональные элементы которой равны единице. Уравнение (2)
в этом случае принимает следующий вид: A=L'DU.
    Решение системы (3) называется прямой подстановкой. Так как матрица L
– нижняя треугольная, то первое уравнение имеет следующий вид: l11ω1 = b1,
где l11≠0 в силу того, что мы предполагаем невырожденность матрицы A.
Отсюда получаем ω1=b1/l11. Теперь можно вычесть первый столбец матрицы
L, умноженный на ω1, из вектора b. Уравнение (3) преобразуется в