Архив публикаций

Тезисы

XIV-ая конференция

Прямой проекционный метод для решения систем линейных уравнений с разреженными неструктурированными матрицами

Гоголева С.Ю.

Самарский государственный аэрокосмический университет имени академика С.П. Королева, кафедра прикладной математики, Россия, 443086, г. Самара, Московское шоссе, 34. т. (846) 332-56-07, E-mail: gogoleva_s@mail.ru.

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

В данной работе рассматривается прямой проекционный метод (ППМ) [1] решения СЛАУ. В этом методе, если проводить аналогию с методами, основанными на разложении матриц (LU-разложение), матрица системы уравнений A раскладывается на две матрицы L_A и R [1]. Для реализации ППМ возможно хранить в оперативной памяти лишь матрицу R, что требует соответственно n(n+1)/2 машинных слов. Таким образом, ППМ дает выигрыш в требуемом объеме оперативной памяти в два раза, по сравнению с вычислительной схемой, основанной на LU – разложении, что выгодно использовать при решении больших разреженных СЛАУ. Общее число арифметических операций, требуемых для реализации ППМ, оценивается величиной 2n³/3+O(n²). Это почти столько же, сколько в методе, основанном на LU – разложении.

При решении СЛАУ с разреженными матрицами ППМ заполнение происходит только в матрице R, тогда как в LU – разложении заполнение может происходить, как в матрице L, так и в матрице U.

В случае для СЛАУ с разреженными неструктурированными матрицами были проведены численные исследования ППМ на примерах, рассмотренных в [2]. Результаты численных исследований показали, что при решении СЛАУ с данными матрицами ППМ превосходит LU – разложение по числу арифметических операций и оперативной памяти.