Тип работы:
Предмет:
Язык работы:


ПРЕДОБУСЛОВЛЕННЫЙ МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ В СХЕМАХ МКЭ

Работа №32852

Тип работы

Магистерская диссертация

Предмет

математика

Объем работы39
Год сдачи2018
Стоимость4900 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
511
Не подходит работа?

Узнай цену на написание


ВВЕДЕНИЕ 3
1 Научно-исследовательская часть 5
1.1 Метод сопряженных градиентов 5
1.2 Предобусловленный метод сопряженных градиентов 6
2 Разреженные матрицы 8
2.1 Хранение разреженной матрицы 10
3 Предобусловливание 14
3.1 Метод декомпозиции области 19
3.2 Разложение Холецкого 20
3.3 Блочный алгоритм метода Холецкого 23
4 Практическая часть 25
4.1 Численные эксперименты 25
4.2 Тестовая инфраструктура 28
ЗАКЛЮЧЕНИЕ 29
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 31
ПРИЛОЖЕНИЕ А


Рассмотренная в данной научно-исследовательской работе задача с функциональной точки зрения следующая - это численное решение систем линейных алгебраических уравнений с разреженными матрицами среднего и большого порядка, возникающими при различных приближениях многомерных краевых задач с нетривиальными свойствами границ предобусловленным методом сопряженных градиентов. Такие задачи все чаще решаются не на кластерах, мощных рабочих станциях и компьютерных сетях, а на многоядерных настольных компьютерах. При решении соответствующей задачи возникают проблемы сходимости, времени счета и необходимого объема памяти компьютера. Проблема построения соответствующих эффективных численных методов сохраняет свою актуальность, так как во многих важных прикладных областях продолжают возникать новые постановки таких задач. При этом наблюдается тенденция к росту размера матриц п, увеличению их заполненности ненулевыми элементами, усложнению структуры разреженности, а также к ухудшению обусловленности. По этой причине появилась необходимость разработки современных итерационных методов решения систем линейных алгебраических уравнений (СЛАУ) с разреженными симметричными матрицами, возникающих при применении метода конечных элементов. Численное решение уравнений методом конечных разностей или методом конечных элементов приводит к системе линейных алгебраических уравнений с разреженной матрицей большой размерности, поэтому предпочтительнее использовать итерационные методы вместо прямых (метод Гаусса или факторизация Холецкого). Как правило, в численных методах для ускорения итерационных процессов используются следующие методы:
1) ускорение сходимости решения систем линейных алгебраических уравнений при помощи подпространств Крылова;
2) ускорение сходимости при помощи многосеточных методов;
3) ускорение сходимости при помощи предобусловливателей.
Метод сопряженных градиентов (CG) является одним из лучших хорошо известных методов для решения систем с симметричными, положительно определенными матрицами. Для повышения эффективности алгоритма применяется предобусловливатель. Предобуславливание состоит в замене исходной системы уравнений на эффективно решаемую систему, имеющую то же самое решение. Предобусловленный метод сопряженных градиентов успешно применяется для плохо обусловленных задач.
Целью данной работы является продемонстрировать практическую реализацию, а также проанализировать метод сопряженных градиентов для симметричных разреженных матриц с применением предобусловливателя. Задачами работы являются:
1) Изучение предобусловленного метода сопряженных градиентов для разреженных матриц;
2) Разработка последовательной реализации метода. Анализ ее сходимости;
3) Применение предобусловливателя, полученного на основе неполного разложения Холецкого, для улучшения сходимости метода. Анализ сходимости, времени счета и затрат памяти;
4) Изучение и применения метода декомпозиции области с использованием разложения Холецкого.
Работа состоит из введения, четырех глав, заключения, приложения. Введение раскрывает актуальность, определяет цель и задачи научно-исследовательской работы. В первых трех главах рассматриваются общие теоретические вопросы, необходимые для понятия и раскрытия темы магистерской диссертации. Во четвертой главе рассматривается практическая часть, создание программного решения, а также представляются графики. В заключении подводятся итоги научно-исследовательской работы, формируются окончательные выводы по рассматриваемой теме.


Возникли сложности?

Нужна помощь преподавателя?

Помощь студентам в написании работ!


Поставленные задачи были выполнены в полном объеме. Результаты численных вычислений проиллюстрированы. Экспериментальные решения доказывают целесообразность, в некоторых случаях и необходимость проведения предобуславливания. Указанная процедура позволяет понизить число обусловленности на несколько порядков. Показано, что неполная обобщенная факторизация Холецкого вместе с алгоритмами перенумерации элементов матрицы, уменьшающими заполнение обобщенных множителей Холецкого, можно использовать для построения эффективных предобусловливателей. Апробация данного метода также актуальна. Продемонстрирована хорошая эффективность метода. Показана возможность использования данного алгоритма при одновременном моделировании для нескольких источников. При этом наблюдается существенная экономия времени расчёта по сравнению с последовательным решением всей задачи для каждого источника. Чтобы эффективно реализовать решения задач с плотными положительно определенными симметричными матрицами рекомендуется использовать не стандартный алгоритм разложения Холецкого, а известную модификацию без извлечения квадратных корней - факторизацию матрицы в произведении LDLT. Что касается оценки трудоемкости, то по результатам исследовательской работы можно утверждать следующее - если верно выбрать размер блока, матричные, эффективно распараллеливающиеся операции будут составлять большую часть вычислений.
Этот метод основан на предобусловливании при помощи факторизации обратной матрицы. Он обладает незначительным числом межпроцессорных обменов и, при правильном выборе структуры матрицы, значительно уменьшает число итераций метода сопряженных градиентов. Более того, с ростом заполненности матриц, используемых для факторизации
Любой из рассмотренных методов обладает как своими достоинствами, так и изъянами. Обычно не удается предварительно подобрать определенный метод для конкретной задачи. По этой причине нынешние программы, работающие с методом конечных элементов, должны включать в себя как прямые методы, так и стабильные к плохой обусловленности итерационные методы.
В ситуациях, когда применяется метод декомпозиции области, в частности, неполное разложение Холецкого, используемое в качестве предобусловливания в методе сопряженных градиентов, показывается хороший результат для задач с матрицами средней и большой размерности.



1) Ортега Дж. Введение в параллельные и векторные решения линейных систем. М.:Мир, 1991. С. 367.
2) Ильин В.П. Методы неполной факторизации для решения алгебраических систем. М.: Физматлит, 1995. С. 288.
3) Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений. М.:Мир, 1984.
4) Kaporin I.E. New convergence results and preconditioning strategies for the conjugate gradient method.// Numer. Linear. Algebra Appls. V.1. N.2. 1994. - P.179210.
5) Капорин И.Е. Предобусловленный метод сопряженных градиентов для решения дискретных аналогов дифференциальных задач // Дифференц. уравнения. 1990. T. 26. № 7. - С. 1225-1236.
6) Милюкова О.Ю. Параллельные варианты некоторых итерационных методов с факторизованной матрицей предобусловливания.// Ж. вычисл. матем. и матем. физики. 2001. Т.41. №11. - C.1619-1636.
7) Y. Saad. Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics, 2 edition, 2003.
8) Голуб Дж., Ван Лоан Ч. Матричные вычисления. М.: Мир, 1993.
9) Chow E. Parallel implementation and practical use of sparse approximate inverse preconditioners with a priori sparsity patterns // Internat. J. High Performance Comput. Appl. 2001. V.15. N.1. - P.56-74.
10) Axelsson O. Iterative solution methods. New York: Cambridge Univ. Press, 1994.
11) R. Blaheta. Space decomposition Preconditioners and Parallel Solvers. In: M. Feistauer et al eds., Numerical Mathematics and Advanced Applications, SpringerVerlag, Berlin, 20-38 (2004).
12) Баландин, М. Ю. Методы решения СЛАУ большой размерности / М. Ю. Баландин, Э. П. Шурина. - Новосибирск: Изд-во НГТУ, 2000. - С. 70.
13) Saad Y. Iterative Methods for Sparse Linear Systems, second edn / Y. Saad. - SIAM, Philadelphia, PA, 2003. - 547 p.
14) Manteuffel T. A. An incomplete factorization technique for positive difinite linear systems / T. A. Manteuffel // Mathematics of computation. - 1980. - V. 34(150). - P. 473-497.
15) Масловская Л.В. Обобщенный алгоритм Холесского для смешанных дискретных аналогов эллиптических краевых задач / Л. В. Масловская // ЖВМ и МФ. - 1989. - Т. 29, № 1. - С. 67-74.
16) Benzi M. Some Preconditioning Techniques for Saddle Point Problems / M. Benzi, A. J. Wathen // Mathematics in Industry. - 2008. - V. 13. - P. 195-211.
17) Амосов А.А., Дубинский Ю.А., Копченова Н.П. Вычислительные методы для инженеров. - М.: Мир, 1998.
18) Horn Roger A.; Johnson Charles R., Matrix Analysis, Cambridge University Press, 1985, ISBN 0-521-38632-2.
19) J. I. Aliaga, M. Bollhofer, A. F. Martin, E. S. Quintana-Orti, Exploiting Thread- level Parallelism in the Iterative Solution of Sparse Linear Systems", Parallel Comput., Vol. 37, pp. 183-202, 2011.
20) T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms", The MIT Press, Cambridge, MA, 2nd Ed., 2001.
21) Вержбицкий, В. М. Вычислительная линейная алгебра. - М.: Высшая школа, 2009. - 351 с.
22) Вержбицкий, В. М. Численные методы (линейная алгебра и нелинейные уравнения), 2-е изд., испр. - М.: ООО "Издательский дом "ОНИКС 21 век", 2005.
- 432 с.
23) Амосов, А. А Вычислительные методы / А. А. Амосов, Ю. А. Дубин- ский, Н. В. Копчёнова. - 3-е изд., перераб. и доп. - М.: Издательский дом МЭИ, 2008. - 672 с.
24) Ануфриев, И. Е. MATLAB 7 / И. Е. Ануфриев, А. Б. Смирнов, Е. Н. Смирнова.
- СПб.: БХВ-Петербург, 2005. - 1104 с.
25) Хант, Б. Р. Matlab: официальный учебный курс Кембриджского университета / Б. Р. Хант, Р. Л. Липсмен, Д. М. Розенберг. - М.: Триумф, 2007. - 352 с.
26) Kolotilina L.Yu., Yeremin A.Yu. Factorized sparse approximate inverse preconditionings. I.~Theory // SIAM J. Matrix Anal. Appl. 1993. V.14. - P.45-58.
27) Капорин И.Е., Милюкова О.Ю. Массивно-параллельный алгоритм предобусловленного метода сопряженных градиентов для численного решения систем линейных алгебраических уравнений // Сб.трудов отдела проблем прикладной оптимизации ВЦ РАН (под ред. В.Г.Жадана). М.: Из-во ВЦ РАН. 2011. - С. 132-157.
28) Anzt H., Huckle T.K., Brackle J., Dongarra J. Incomplete Sparse Approximate Inverses for Parallel Preconditioning //Parallel Computing. 2018. V.71 -P.1-22.
29) Капорин И.Е. Предобусловливание итерационных методов решения систем линейных алгебраических уравнений. Дисс. на соиск. ученой степени д.ф.-м.н. 2011. Москва. 216 С.
30) Axelsson O., Kaporin I. On the sublinear and superlinear rate of convergence of conjugate gradient methods. // Numerical Algorithms. 2000. №25 - P. 1-22.
31) Gustafsson I. A Class of First Order Factorization Methods // BIT. 1978. V.18. - P.142-156.
32) Meijerink J. A., van der Vorst H. A. An Iterative Solution Method for Linear Systems, of which the Coefficient Matrix is a Symmetric M-matrix // Math. Comp.
1977. V.31. N 137. - P. 148-162.
33) Davis T.A., Hu Y.F.University of Florida sparse matrix collection // ACM Trans. on Math. Software, 2011. V.38
(URL:http://www.cise.ufl.edu/research/sparse/matrices)
34) Капорин И.Е., Милюкова О.Ю. Массивно-параллельный алгоритм предобусловленного метода сопряженных градиентов для численного решения систем линейных алгебраических уравнений // Сб. трудов отдела проблем прикладной оптимизации ВЦ РАН (под ред. В.Г. Жадана). М.: Из-во ВЦ РАН. 2011. - С.32-49.
35) Милюкова О.Ю. Некоторые параллельные итерационные методы с факторизованными матрицами предобусловливания для решения эллиптических уравнений на треугольных сетках // Ж. вычисл. матем. и матем. физики. 2006. T.46. №6. - C.1096-1112.
36) Уоткинс, Д. С. Основы матричных вычислений. - М.: БИНОМ. Лаборатория знаний, 2006. - 664 с.
37) Деммель, Дж. Вычислительная линейная алгебра. Теория и приложения. -М.: Мир, 2001. - 430 с.
38) Barrett R. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods / R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra,
V. Eijkhout, R. Pozo, C. Romine, H. Van der Vorst. - Philadelphia: SIAM, 1994 // http: //www.netlib .org/linal g/html templates/Templates. html
39) Фадеев А. К., Фадеева В. Н. Вычислительные методы линейной алгебры.
Изд. 3_е, стереотипное. - СПб.: Лань, 2002.
40) Дьяконов В. П. Компьютерная математика. Теория и практика. - М.: Но_ лидж, 2000.
41) Дьяконов В.П. MATLAB: Учебный курс. - СПб.: ПИТЕР, 2001.
42) Потемкин В. Г. Вычисления в среде MATLAB. - М.: ДИАЛОГ_МИФИ, 2004.
43) Nepomnyashchikh S.V. Domain decomposition methods // Radon Series Comp. Appl. Math. 2007. N 1. 89-159.
44) Ильин В.П. Проблемы высокопроизводительных технологий решения больших разреженных СЛАУ // Вычис- лительные методы и программирование. 2009. 10, № 1. 130-136
45) Ильин В.П. Методы и технологии конечных элементов. Новосибирск: ИВМиМГ СО РАН, 2007.
46) Bramble J.H., Pasciak J.E., Wang J., Xu J. Convergence estimates for product iterative methods with applications to domain decomposition // Math. Comp. 1991. 57, N 195. 1-21.


Работу высылаем на протяжении 30 минут после оплаты.




©2024 Cервис помощи студентам в выполнении работ