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