Когда большая доля коэффициентов матрицы состоит из нулей, вполне очевидно, что нам не хотелось бы хранить в памяти компьютера все эти нули. Поэтому матричные алгоритмы должны проектироваться таким образом, чтобы обрабатывались только ненулевые элементы и чтобы на основании предварительного знания о расположении ненулевых элементов избегались операции типа сложения с нулем или умножения на нуль. Таким образом число операций, производимых машиной при исполнении алгоритма, пропорционально числу ненулевых элементов, а не числу всех элементов матрицы. Серьезную проблему при работе с разреженными матрицами представляет численная устойчивость [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.