Введение к работе
Актуальность проблемы. Решение системы линейных алгебраических уравнений (СЛАУ) является одной из наиболее важных задач вычислительной математики. По некоторым оценкам1 свыше 75% всех расчетных математических задач сводится к решению СЛАУ.
В настоящее время существуют два принципиально различных подхода к решению СЛАУ: прямые методы и итерационные методы. Прямые методы достаточно эффективны, если матрица системы имеет относительно низкий порядок или специальную структуру. Для решения СЛАУ большого порядка наибольшее распространение получили итерационные методы. В литературе2 описано большое количество итерационных методов для решения СЛАУ. Однако, каждый итерационный процесс имеет свои особенности и свою ограниченную область применимости. Итерационный процесс может оказаться расходящимся для данной СЛАУ, или сходимость процесса может быть настолько медленной, что практически оказывается невозможным достигнуть удовлетворительной точности приближенного решения. Необходимо также отметить, что некоторые методы, используемые на практике, получили достаточное теоретическое обоснование только для узкого класса СЛАУ. Кроме того, бурное развитие параллельных вычислительных систем в настоящее время предъ-
'Е. Валях, Последовательно-параллельные вычисления, М.: Мир, 1985.
2Д.К.Фаддеев, В.Н.Фаддеева, Вычислительные методы линейной алгебры, М.: Физматгиз, 1960.
Г.И.Марчук, Методы вычислительной математики, М.: Наука, 1980. А.А.Самарский, Е.С.Николаев, Методы решения сеточных уравнений, М.: Наука, 1978. В.В.Воеводин, Ю.А.Кузнецов, Матрицы и вычисления, М.: Наука, 1984. Дж.Ортега, В.Рейнболят, Итерационные иетоды решения нелинейных систем уравнений со многими неизвестными, М.: Мир, 1975.
Л. Хейгеман, Л. Янг, Прикладные итерационные методы, М.: Мир, 1986. R.S. Varga, Matrix Iterative Analysis, New Jersy: Prentice Hall, Englewood Cliffs, 1962.
являет повышенные требования к уровню параллелизма итерационных алгоритмов. Поэтому разработка итерационных методов с высоким уровнем параллелизма для решения широкого класса СЛАУ, теоретическое обоснование их сходимости и получение оценок асимптотической скорости сходимости представляет актуальную проблему в области вычислительной математики.
Цель исследования. Работа преследует две основные цели. Первая — сконструировать достаточно широкое семейство итерационных алгоритмов (в общем случае нестационарных) для решения СЛАУ, которое наряду с новыми алгоритмами содержит ряд известных итерационных процедур. Вторая — в рамках этого общего подхода обосновать сходимость и получить оценки асимптотической скорости сходимости итерационных алгоритмов для класса СЛАУ, матрицы коэффициентов которых имеют обобщенное строгое диагональное преобладание.
Методика исследования. Метод свободных групповых итераций (СГИ) идейно близок подходам, предложенным в работах3 некоторых других авторов. Обоснование сходимости и получение оценок асимптотической скорости сходимости метода СГИ опирается на технику исследования спектральных свойств матриц итерационных алгоритмов, развитую Д.К.Фаддеевым, В.В.Воеводиным, А.А.Самарским, Г.И.Марчуком, Ю.А.Кузнецовым, Дж.М.Ортега, Д.М. Янгом, Р.С.Варгой. В диссертации используются понятия и методы функционального анализа, линейной алгебры, теории разностных схем.
*Л.Ю. Колотилина, 06 одном семействе явных переобусловливаний систем линейных алгебраических уравнений с разреженными матрицами, Препринт ЛОМИ АН СССР, N Р-8-86, Л., 1986,
Jinchao Xu, Iterative Methods by Space Decomposition and Subspace Correction, SIAM Review, 1992, v.34, n.12, pp.581-613.
Практическая ценность. Все результаты диссертации, которые выносятся на защиту, получены автором самостоятельно и являются новыми. Эти результаты могут быть использованы при конструировании и исследовании сходимости стационарных и нестационарных итерационных методов решения систем разностных уравнений, которые возникают при численном интегрировании задач математической физики методом конечных разностей или конечных элементов в областях со сложной геометрией. Метод СГИ типа Якоби имеет высокий уровень параллелизма, что может позволить эффективно использовать его на параллельных вычислительных системах. Изменение настройки в нестационарном методе СГИ позволяет динамически балансировать загрузку процессорных элементов этих вычислительных систем, сохраняя при этом сходимость к точному решению. Полученные в диссертации аналитические результаты для модельных задач могут быть использованы в тестах при проверке корректности итерационных процедур, а также для оптимизации их параметров.
Апробация работы. Основные результаты диссертации опубликованы в работах [1]-[6], доложены на VIII, IX и X Всесоюзных семинарах "Теоретические основы и конструирование алгоритмов решения задач математической физики" (Москва, 1990,1992,1994), на семинарах в Институте прикладной математике им. М.В.Келдыша РАН и Институте математики и механике УрО РАН.
Структура И Объем работы. Диссертация состоит из введения, трех глав, заключения, библиографии и приложения. Каждая глава завершается выводами. Объем работы составляет 154 страницы машинописного текста. Библиография включает 52 наименования. Приложение содержит 10 таблиц.
