Вычислительные методы алгебры и оценивания. Семушин И.В. - 86 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

5 Разреженные формы LU-разложения
Это можно сделать, если применить метод Гаусса непосредственно к упако-
ванной форме хранения матрицы A, т. е. только к ее ненулевым э ле м ентам.
Поскольку стандартный метод Гаусса (см. подразд. 3.1) оперирует со
строками матрицы A, разреженные матрицы удобно хранить по строкам.
Это позво лит эффективно организовать такие операции, как нормировка
строки, умножение строки на число, вычитание строки, потому что в этом
случае все ненулевые элементы каждой строки матрицы A в упакован-
ной форме хранения образуют непрерывную пос ле дова т ельность. Следова-
тельно, операции нормировки, умножения и вычитания строки можно про-
водить только для ненулевых элеме нтов .
Такой подход подразумевает, что ненуле вые элементы матрицы A моди-
фицируются в том порядке, в кот о ром они хранятся в упакованной форме,
что исключает затраты на поиск нужного элемента. Модификация проис-
ходит следующим об разом. Берется очередной ненулев ой элемент матрицы
A. Определяется его местоположение в матрице, т. е. индексы i и j. Затем
с помощью дополнительных масс ивов обратных перестановок определяется
местоположение это го элемента в м а т рице с переставленными сто лбцами и
строками. Если в результате этот эле м ент лежит в активной подматрице,
то он изменяется по изв естным формулам метода Гаусса. Здесь надо преду-
смотреть процедуру вставки элемента на случай появления нового ненуле-
вого элемента и процедуру удаления элемента из упакованной формы, если
ненулевой элемент с тал нулевым. После этог о обрабатывается следующий
ненулевой элемент матрицы A .
Оптимизация по времени процедуры решения системы линейных алгеб-
раических уравнений позволяет значительно повысить эффективность про-
граммы. Однако этого недостаточно. Оптимальной по быстродействию будет
лишь та программа, где дополнительно оптимизирована процедура выбора
главного элемента. Во-первых, надо подумать над эффективным вычисле-
нием элементов матрицы G
k
(или
ˆ
G
k
). Во-вторых, надо организовать вычис-
ление этой матрицы так, чтобы исключить поиск элементов в упаков анной
форме. Только уче т всех этих осо бенностей решения систем линейных ал-
гебраических уравнений с разреженной матрицей коэффициентов позволит
написать эффективную по затратам машинного времени программу.
86

Страницы