Проблема заполнения разреженной матрицы системы при исключениях

Понятие разреженной матрицы

Разреженной называется матрица, большинство элементов которой – нули. Например,

.

Матрицы такого вида возникают, например, при решении дифференциальных уравнений с частными производными конечно-разностными и конечно-элементными методами, с которыми мы ознакомимся в последующих лекциях. Кроме того, существенная часть линейных систем, возникающих в научных и инженерных рассчетах, имеют симметричные положительно определенные разреженные матрицы.

Для разреженных матриц большого размера возникает вопрос: можно ли не хранить нулевые элементы матрицы, а ненулевые хранить в какой-либо специальной структуре данных или генерировать по мере их необходимости? В общем случае ответ на этот вопрос зависит от конкретики той задачи, в которой фигурирует разреженная матрица, и от выбора алгоритма решения рассматриваемой задачи.

Проблема заполнения разреженной матрицы системы при исключениях

Пусть рассматривается задача о решении неоднородной СЛАУ

,

где матрица системы является разреженной симметричной и положительно определенной. В силу симметричности и положительной определенности рассматривую систему имеет смысл решать методом Холесского (см.лекцию 7). Для простоты изложения рассмотрим простой пример.

Пусть требуется решить СЛАУ

.

Матрица системы разреженная, симметричная, положительно определенная. Построим для нее симметричное разложение:

.

При проведении симметричного разложения, мы получим:

.

Решая систему , получаем . Затем, решая систему находим .

Этот пример иллюстрирует очень важный факт, относящийся к применению метода Холесского для системы с разреженной матрицей : матрица обычно претерпевает заполнение. Это означает, что имеет ненулевые элементы в позициях, где в нижней треугольной части стояли нули. Это приводит к тому, что при хранении разреженной матрицы ее нули также прийдется хранить, т.к. в процессе исключения эти нули станут ненулевыми элементами и внесут свой вклад при решении СЛАУ.

Предположим теперь, что мы перенумеровали переменные в соответствии с правилом: , и переупорядочили уравнения так, чтобы последнее стало первым, второе снизу - вторым сверху и т.д., пока, наконец, бывшее первое уравнение не станет последним. Мы получим СЛАУ, эквивалентную данной:

.

Проведенная перенумерация неизвестных и переупорядочение уравнений равносильны симметричной перестановке строк и столбцов матрицы (симметричная перестановка строк и столбцов означает: если в матрице меняются местами -ая и -ая строки, то меняются местами также -ый и -ый столбец. В матричном виде симметричная перестановка будет означать умножение матрицы на соответствующую матрицу перестановки справа и слева), причем та же перестановка применяется и к .Эту новую систему обозначим . Применяя к ней метод Холесского, разложим матрицу , где нижний треугольный множитель будет иметь вид:

.

Решая системы и , получим решение , которое есть лишь переупорядоченная форма . Важнейший момент состоит в том, что переупорядочение уравнений и переменных привело к треугольному множителю , который разрежен в точности в той мере, что и нижний треугольник . В этом случае нулевые элементы можно не хранить, т.к. они останутся нулями и после исключения и не внесут никакого вклада в решение треугольных систем, полученных после проведения разложения Холесского.

Хотя на практике редко удается достигнуть столь полного успеха, для большинства задач с разреженными матрицами разумное упорядочение строк и столбцов матрицы коэффициентов может дать огромное сокращение заполнения и, следовательно, экономию машинного времени и памяти (при условии, что разреженность используется).