Алгебраические многосеточные методы для задач с малым параметром

• Автор: Падий, Александр Викторович
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Москва
• Количество страниц: 80 с. : ил.

Оглавление
Введение
1 Алгебраические методы многоуровневых итераций (АММИ)
1.1 Двухуровневый метод. Усиленное неравенство Коши-Буняковского
1.2 Многоуровневый метод. Стабилизация числа обусловленности
2 Аддитивная версия АММИ для анизотропной задачи диффузии
2.1 Постановка задачи
2.2 Аддитивная версия АММИ с внутренними итерациями
2.3 Обобщенный метод сопряженных градиентов

2.4 Алгоритм построения аппроксимаций к блокам Ап
2.5 Численные эксперименты
3 Модельный анализ проекционного переобуславливателя
3.1 Постановка задачи
3.2 Модифицированный проекционный переобуславливатель
3.3 Алгоритм построения блока V
3.4 Численные эксперименты
4 Алгебраический многосеточный метод для трехмерных задач, дискретизированных на сетках, состоящих из призм
4.1 Постановка задачи
4.2 Оценка параметра а
4.3 Алгоритм построения блоков
4.4 Численные эксперименты
5 Применение АММИ для решения задач теории упругости
5.1 Постановка задачи
5.2 Стандартная конечно-элементная дискретизация
5.3 Дискретизация на основе смешанной формулировки
5.4 Численные экперименты
Введение
Разработка эффективных итерационных методов решения систем линейных алгебраических уравнений, возникающих при дискретизации эллиптических краевых задач второго порядка, по-прежнему является одной из насущных проблем вычислительной математики. Проблема построения эффективных численных алгоритмов является особенно актуальной в случае сложной геометрии задачи, разрывности либо анизотропности коэффициентов эллиптического оператора, а также в случае проведения дискретизации на существенно неравномерных конечно-элементных сетках. Необходимость использования современных параллельных ЭВМ для решения возникающих на практике задач также накладывает дополнительные требования на разрабатываемые методы решения: необходимо учитывать эффективность их реализации на многопроцессорных системах.
Важной особенностью рассматриваемого класса алгебраических задач является то, что они, как правило, имеют очень большую размерность, но при этом являются сильно разреженными, с количеством ненулевых элементов в матрице системы, пропорциональным количеству неизвестных. В связи с этим применение прямых методов для их решения обычно затруднено. Одним из наиболее эффективных средств для решения этих ресурсоемких задач являются итерационные методы.
Использованию итерационных методов в вычислительной практике посвящена обширная литература. Подробное изложение теории итерационных методов можно найти, например, в работах [14], [17], [21], [25]. Простейшими итерационными методами являются метод Ричардсона, метод Якоби, метод Гаусса-Зейделя, а также метод последовательной верхней релаксации. Для класса алгебраических систем, порождаемых конечноэлементной дискретизацией эллиптических уравнений второго порядка, скорость сходимости упомянутых выше итерационных методов зависит от параметра дискретизации к (размера шага дискретизационной сетки) и значительно ухудшается при стремлении И к нулю. Скорость сходимости основных итерационных методов можно существенно улучшить, применив к ним процедуры ускорения, такие как чебышевское ускорение или ускорение по методу сопряжённых градиентов. У каждой из упомянутых процедур ускорения есть свои достоинства и недостатки. Реализация чебышевского итерационного метода более проста, при его использовании не требуется вычисления скалярных произведений, что наиболее ценно при проведении рассчетов на параллельных компьютерах. С другой стороны, существенным недостатком чебышевского итерационного метода является необходимость иметь достаточно хорошие оценки границ спектра матрицы, которые, как правило, недоступны. Поэтому метод сопряжённых градиентов является одним из наиболее привлекательных методов для решения систем линейных алгебраических уравнений с симметричными положительно определёнными (и полуопределёнными) матрицами.
И для чебышевского метода, и для метода сопряжённых градиентов скорость сходи-

мости существенно зависит от спектральных свойств итерируемой матрицы. Как известно (см. [3], например), приближенное решение х&, полученное с использованием метода сопряженных градиентов, удовлетворяет следующим оценкам:
||х — х*||а < 2ак ||х — хо||а, ||х — х*||2 < 2 у/как ||х - х0||2,
где х — точное решение, а = (л/к - 1), а к = Amax(A)/Amin(A) - - спектральное
число обусловленности матрицы системы. Аналогичная оценка справедлива также и для чебышевского итерационного метода:
||х-х*||2 < 2ак ||х — ХоЦг-
Заметим, что спектральное число обусловленности матриц, порождаемых конечно-элементной дискретизацией эллиптических краевых задач второго порядка, пропорционально Ьг2. Это приводит к резкому падению скорости сходимости итерационного процесса при уменьшении h. Одним из способов улучшения сходимости является использование переобуславливания. Вместо исходной алгебраической системы

рассматривается система
М~1Ах — М~1Ь (либо, альтернативно, система АМ~1у ~Ъ, х = М~1у)
с матрицей М, выбранной таким образом, что, с одной стороны, обращение М легко реализуемо и, с другой стороны, число обусловленности матрицы М~УА значительно меньше числа обусловленности исходной матрицы А. Для достижения скорости сходимости, не зависящей от параметров рассматриваемой алгебраической задачи (в том числе не зависящей от шага h дискретизационной сетки) необходимо построить спектрально эквивалентный переобуславливатель М такой, что к(М_1А) < Const. Для обеспечения приемлимых арифметических затрат при решении возникающих в современной вычислительной практике систем большой размерности (где количество неизвестных достигает сотен тысяч и даже миллионов) желательно также, чтобы стоимость умножения на переобуславливатель росла не более чем линейно с ростом размерности задачи.
При решении самосопряжённых эллиптических задач одним из возможных способов построения переобуславливателей, удовлетворяющих указанным выше требованиям, является использование многосеточных методов. Впервые многосеточный метод был предложен Р. П. Федоренко в работах [19] и [20], где была рассмотрена итерационная процедура решения уравнения Пуассона и был доказан оптимальный порядок ее вычислительной сложности. Исследование скорости сходимости многосеточного метода для разностных эллиптических операторов второго порядка с переменными коэффициентами было проведено Н. С. Бахваловым [2]. Для случая конечно-элементной аппроксимации эллиптического уравнения сходимость многосеточного метода была доказана Н. Г. Астраханцевым [1]. Среди первых работ, посвящённых данной тематике, отметим также работы [13], [15], где В. И. Лебедевым был предложен KP-метод, близкий по своей структуре к многосеточным методам. В дальнейшем интерес к многосеточным методам начал стремительно нарастать. Упомянем следующие работы, внесшие существенный вклад в развитие теории многосеточных методов: W. Hackbusch [63], [64], [65]; A. Brandt [57], [58]; D. Braess [49], [50], [51]; R. E. Bank, T. Dupont [43], [44], [45]; S. McCormick [77], [78], [79]; J.-F. Maitre,

При проведении численных экспериментов для дискретизации задач (2.31) - (2.33) были использованы конформные кусочно-линейные конечные элементы. Возникающие системы линейных уравнений решались с использованием алгебраического метода многоуровневых итераций с оптимально выбранным расстоянием между уровнями регуляризации. Размер шага самой грубой сетки выбирался таким образом, чтобы вычислительные затраты на решение задач на ней были сравнимыми с затратами на умножение с матрицей жесткости самого верхнего уровня. Данный выбор номера нижнего уровня соответствует так называемой “короткой” версии АММИ (см.[32]). Система уравнений на самой грубой сетке решалась методом сопряженных градиентов с использовнием проекционного переобуславливателя, описанного в главе 3.
Заметим, что эффективность рассматриваемой версии АММИ зависит от надлежащего выбора стабилизационных точек в многоуровневой структуре (см. Рис. 2.1). Достаточно точная аппроксимация к структуре уровней регуляризации может быть получена с использованием ассимптотических формул (2.9) - (2.11), которые, как показала практика, применимы даже при сравнительно небольшом количестве уровней. Применимость ассимптотических формул даже для задач сравнительно небольшой размерности проиллюстрирована на Рис. 2.14, где графически изображена зависимость времени вычислений, необходимого для решения задачи (2.31) с помощью АММИ, имеющего только два уровня регуляризации, от расстояния между ними. Прямоугольниками на Рис. 2.14 обозначены расстояния между уровнями регуляризации, полученные с использованием ассимптотических формул (2.9) - (2.11). Как видно, оцененные по ассимптотическим формулам величины близки к наблюдаемым на практике и, следовательно, могут быть успешно использованы при проведении численных экспериментов.
Критерий остановки внешнего итерационного процесса был выбран следующим:
< 1(Г6,
где — начальная невязка, а — невязка после проведения к итераций. Ортогонали-зация направлений поиска с*) в обобщенном методе сопряженных градиентов производилась с использованием только одного предыдущего направления поиска (см. раздел 2.3). Критерий остановки итерационного процесса на самом грубом уровне, а также на всех уровнях регуляризации был выбран следующим:
< 1(Г3.
Производительность АММИ была сравнена с производительностью диагонального пе-реобуславливания по методу Якоби, а также проекционного переобуславливателя (см. главу 3). Общее число операций с плавающей запятой, потребовавшееся для сходимости вышеуказанных итерационных процедур, в зависимости от размерности решаемой задачи представлено на Рис. 2.15 и 2.16. Как и ожидалось, производительность АММИ оказалась значительно выше производительности остальных методов. При проведении данной серии численных экспериментов дискретизация осуществлялась на последовательности равномерных триангулированных декартовых сеток.
Для того, чтобы продемонстрировать устойчивость АММИ по отношению к параметрам используемых конечно-элементных сеток, алгоритм был применен для решения