Научная статья на тему «Решение плохо обусловленных разреженных систем линейных алгебраических уравнений с помощью крыловского подпространства»

Когда большая доля коэффициентов матрицы состоит из нулей, вполне очевидно, что нам не хотелось бы хранить в памяти компьютера все эти нули. Поэтому матричные алгоритмы должны проектироваться таким образом, чтобы обрабатывались только ненулевые элементы и чтобы на основании предварительного знания о расположении ненулевых элементов избегались операции типа сложения с нулем или умножения на нуль. Таким образом число операций, производимых машиной при исполнении алгоритма, пропорционально числу ненулевых элементов, а не числу всех элементов матрицы. Серьезную проблему при работе с разреженными матрицами представляет численная устойчивость [1, с. 195].

Когда методы типа гауссова исключения требуют слишком много времени или памяти для решения систем уравнений используются итерационные методы. При решении плохо обусловленных разрежен­ных СЛАУ возникает необходимость выбора метода, который позволит получить при решении точный результат и наименьшее заполнение (возникновение новых ненулевых элементов) [3, с. 29]. Наиболее эффективными и устойчивыми среди итерационных методов решения таких систем уравнений являются так называемые проекционные методы, и особенно тот их класс, который связан с проектированием на подпространства Крылова. Эти методы обладают целым рядом достоинств: они устойчивы, допускают эффективное распараллеливание, работу с различными строчными (столбцовыми) форматами и предобуславливателями разных типов.

Постановка задачи

Рассмотрим систему линейных алгебраических уравнений

 ,                                                                (1)

где:  — плохо обусловленная разреженная матрица,

.

В данной работе проводится сравнительный анализ итерацион­ных методов для решения плохо обусловленных разреженных СЛАУ. В качестве исследуемых методов выбраны: метод сопряженных градиентов (CG) , метод минимальных невязок (MinRes), сдвоенный метод сопряженных направлений (CGS), квазиминимальных невязок (QMR) [6, с. 2].

В вопросах выбора того или иного способа решения СЛАУ важно учитывать структуру матрицы A [4, с. 2; 5, с. 47]. Это связано с тем, что не каждый метод дает возможность получить гарантированный результат для определенной системы линейных уравнений.

Таким образом, критерием сравнения итерационных методов решения СЛАУ будут: погрешность результатов, скорость сходимости, структура матрицы.

Результаты численных исследований показали, что для решения СЛАУ с матрицей A являющейся симметричной/несимметричной и хорошо обусловленной к нормальным уравнениям лучше применять метод CG. Если матрица А- симметричная и плохо обусловленная, то лучшую сходимость показал метод MinRes. Для А- несимметрич­ной, плохо обусловленной — метод квазиминимальных невязок [7].

Для улучшения скорости сходимости итерационных методов используют предобуславливание матрицы системы. Оно заключается в том, что подбирается такая матрица предообуславливания, что при этом процедура решения СЛАУ является не слишком трудоемкой и численно устойчивой [2, с. 313]. Правильный выбор предобуславливателя, зависящий от конкретной задачи, может в огромной степени ускорить сходимость [9, с. 211]. В действитель­ности, хороший предобуславливатель часто необходим для того, чтобы итерационный метод вообще сходился.

В данной работе было рассмотрено несколько видов предобус­лавливания для метода квазиминимальных невязок с разреженными плохо обусловленными матрицами: левое и правое предобус­лавливание с использованием QR — разложения, левое и правое предобуславливание с использованием LU — разложения, а также с использованием модификации LU — разложения [8, с. 315].

Таблица 1.

Сравнение относительной погрешности предобуславливателей

Заключение

Нужна помощь в написании статьи?

Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Цена статьи

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

Список литературы:

1.Голуб Дж., Ван Лоун Ч. Матричные вычисления/ Под ред. В.В. Воеводина. — М.: «Мир», 1999. — 548 с.

2.Деммель Дж. Вычислительная линейная алгебра. Теория и приложения / Пер. с англ.Х.Д. Икрамова. — М.: «Мир», 2001. — 430 c.

3.Писсанецки С. Технология разреженных матриц/ Под ред. Х.Д. Икрамова — М.: «Мир», 1988. — 410 с.

4.Станкевич, И.В. Хранение и использование разреженных матриц в конечно- элементной технологии. Журнал «Наука и Образование». — 2005. — 10 октября.

5.Тьюарсон Р. Разреженные матрицы/ Под ред. Х.Д. Икрамова. — М.: «Мир», 1977. — 172 с.

6.Bucker Martin, Basermann Achim. A comparison of QMR, CGS and TFQMR on a distributed memory machine / Bucker Martin //Mathematics of computation. — 1994 — 31 may

7.Harwell-Boeing Collection — [Электронный ресурс] – Режим доступа. — URL: http://math.nist.gov/MatrixMarket/data/Harwell-Boeing/ (дата обращения: 15.12.2012)

8.Roland W. Freund, Noel M. Nachtigal. QMR: a Quasi-Minimal Residual Method for Non—Hermitian Linear Systems / Roland W. Freund, Noel M. Nachtigal // Journal Math. — 1991. — №60. — p. 315—339.

9.Saad, Y. Iterative methods for sparse linear systems / Y. Saad. // SIAM. — 2003. — 447 p.