Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65

Статья опубликована в рамках: I Международной научно-практической конференции «Естественные и математические науки в современном мире» (Россия, г. Новосибирск, 24 декабря 2012 г.)

Наука: Математика

Секция: Вычислительная математика

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Гусева Ю.С., Гоголева С.Ю. РЕШЕНИЕ ПЛОХО ОБУСЛОВЛЕННЫХ РАЗРЕЖЕННЫХ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ С ПОМОЩЬЮ КРЫЛОВСКОГО ПОДПРОСТРАНСТВА // Естественные и математические науки в современном мире: сб. ст. по матер. I междунар. науч.-практ. конф. – Новосибирск: СибАК, 2012.
Проголосовать за статью
Дипломы участников
У данной статьи нет
дипломов
Статья опубликована в рамках:
 
 
Выходные данные сборника:

 

 

РЕШЕНИЕ ПЛОХО ОБУСЛОВЛЕННЫХ РАЗРЕЖЕННЫХ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ С ПОМОЩЬЮ КРЫЛОВСКОГО ПОДПРОСТРАНСТВА

Гусева Юлия Сергеевна

студент Самарского государственного аэрокосмического университета имени С.П. Королева,

 г. Самара

Е-mail: 

Гоголева Софья Юрьевна

доцент Самарского государственного аэрокосмического университета имени С.П. Королева,

 г. Самара

Е-mail: 


 

Введение


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

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

Матрица

LU- разложение

LU- разложение(модификация)

QR- разложение

(левое)

(правое)

(левое)

(правое)

SHL_0

4,9e-07

1,3e-10

1,1e-010

1,2e-09

1,9e-10

BCSSTK14

1,9е-11

1,6е-11

3,12е-12

1,12е-11

1,10е-11

BCSSTK20

7,7е-11

6,8е-11

4,5е-13

4,4е-13

2,2е-12

WEST 0132

6,9е-06

1,5е-05

5,3е-010

4,3е-09

2,4е-08

NOS5

2,5е-15

2,7е-15

4,9е-16

4,8е-16

4,8е-16

NOS7

1,9е-10

2,2е-10

3,6е-15

2,6е-15

4,6е-16

BCSSTK19

1,5е-09

1,6е-09

7,1е-10

7,3е-11

6,1е-11

MCCA

5,1е-07

2,6е-07

1,6е-07

3,1е-07

MCFE

5,7е-09

7,5е-12

4,5е-11

5,01е-11

ARC130

1,1е-05

8е-10

2,3е-10

2,5е-09

6,8е-10

GR_30_30

1,1e-14

1,3e-15

3,4e-14

9,4e-15

1,2e-15


 

Заключение


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

Проголосовать за статью
Дипломы участников
У данной статьи нет
дипломов

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом