Алгоритмы и программное обеспечение для решения систем линейных алгебраических уравнений при анализе электромагнитного излучения проводных структур

• Автор: Куксенко, Сергей Петрович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Томск
• Количество страниц: 112 с. : ил.

1. РЕШЕНИЕ СИСТЕМЫ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ

УРАВНЕНИЙ: ОБЗОР

1.1 Важность решения СЛАУ

1.2 Необходимость использования итерационных методов для решения

СЛАУ с плотной матрицей

1.3 Итерационные методы

1.3.1 Общий подход к построению проекционных методов

1.3.2 Подпространства Крылова

1.3.3 Предобусловливание

1.3.4 Пред фильтрация

1.3.5 Методы крыловского типа

1.4 Обзор программного обеспечения
1.5 Цель работы и формулировка задач исследования
2. РАЗРАБОТКА И РЕАЛИЗАЦИЯ АЛГОРИТМОВ
2.1 Новые способы предфильтрации
2.1.1 Предфильтрация, основанная на норме строк исходной матрицы
2.1.2 Предфильтрация, основанная на норме исходной матрицы
2.2 Совершенствование известных способов алгебраической предфильтрации
2.3 Реализация методов решения СЛАУ в виде отдельных функций
2.4 Разработка модуля матричных операций для единой системы моделирования
2.4.1 Функциональные возможности системы TALGAT
2.4.2 Функциональные возможности модуля MATRIX
2.5 Основные результаты главы
3. ИССЛЕДОВАНИЕ РАБОТЫ ИТЕРАЦИОННЫХ МЕТОДОВ
3.1 Сравнение итерационных методов без использования предобусловливания
3.2 Сравнение итерационных методов при использовании предобусловливания
3.3 Оптимизация допуска обнуления при решении СЛАУ итерационными методами
3.4 Ускорение получения заданных характеристик за счет снижения
точности вычисления
3.5 Сравнение способов предфильтрации
3.6 Совершенствование способов предфильтрации
3.7 Сравнение новых и усовершенствованных способов предфильтрации с известными
3.8 Рекомендации по использованию итерационных методов решения
СЛАУ
3.9 Основные результаты главы
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЯ

Актуальность работы. Решение системы линейных алгебраических уравнений (СЛАУ) имеет большое значение, поскольку к нему сводится решение широкого круга сложных практических задач. В линейной алгебре эту задачу называют первой основной задачей. Так, около 75% всех расчетных математических задач приходится на решение СЛАУ. Хотя эта задача сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать такие системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением компьютера. Как известно, значительная часть численных методов решения различных (в особенности нелинейных) задач включает в себя решение СЛАУ как элементарный шаг соответствующего алгоритма.
Необходимость решения СЛАУ возникает при решении многомерных анизотропных краевых задач, в задачах вычислительной гидродинамики, в теории электрических цепей, при решении уравнений балансов и сохранения в механике, гидравлике и т.п. В геомех анике матрица СЛАУ имеет чрезмерно большие размеры и является плохо обусловленной. Поэтому обычные методы решения СЛАУ здесь оказываются неэффективными. Задача нахождения устойчивых приближенных решений СЛАУ является определяющей задачей для гравиметрии и магнитометрии. Необходимость решения трехдиагональных СЛАУ возникает в оптике, теории теплопроводности, газовой динамике, теории разностных схем и др. Также проблема решения СЛАУ существует в задачах управления и контроля, которые предъявляют высокие требования к скорости получения результатов, пусть даже приближенных. Среди них можно выделить класс задач оценки и предсказания критических ситуаций, связанных, например, с измерением температуры и вычислением плотности теплового потока на поверхности спускаемого летательного аппарата и др.
Особая необходимость в решении СЛАУ возникает при использовании широкого класса моделей и подходов, применяемых при автоматизированном проектировании аппаратуры с учетом электромагнитной совместимости. Например, решение задач излучения или рассеяния электромагнитной волны сложными объектами может быть получено с помощью интегральных уравнений, сводящихся методом моментов к СЛАУ с плотной, комплексной и несимметричной матрицей большой размерности NxN. Достаточно важной задачей является анализ излучения проводных структур, поскольку он необходим при моделировании проводных антенн, аппроксимации излучающей поверхности проводной сеткой, создании различных симуляторов электромагнитного поля и др. Таким образом, вычислительные трудности решения таких СЛАУ во многом обусловлены заполненностью матриц, приводящей к огромному объему вычислений (особенно в трехмерных задачах).
Для решения СЛАУ с плотными матрицами традиционно используются точные методы, например, метод исключения Гаусса. Но их вычислительные затраты, пропорциональные А3, существенно ограничивают круг решаемых

задач даже на высокоскоростных компьютерах. Необходимость решения сложных задач, дающих рост У, привела к широкому применению итерационных методов. Наиболее эффективными и устойчивыми (с точки зрения сходимости к точному решению) среди итерационных методов являются, так называемые, методы крыловского типа. В связи с тем, что матрица СЛАУ, полученная применением метода моментов, является, как правило, плохо обусловленной, использование итерационного метода без предобусловливания не вполне обоснованно, поскольку метод может застопориться или даже оборваться. Использование предфильтрации (игнорирования незначительных элементов) позволяет задать структуру разреженности матрицы СЛАУ, что, в свою очередь, позволяет применить алгоритмы технологии разреженных матриц (предобусловливание) и тем самым уменьшить время решения.
Между тем, ряд возможностей совершенствования решения СЛАУ с плотной матрицей итерационными методами при исследовании проводных структур остаётся неиспользованным. Так, недостаточно разработаны способы выбора структуры разреженности с помощью предфильтрации матрицы СЛАУ, позволяющие добиться ускорения решения за счет более эффективного использования предобусловливания. Следует отметить, что исследователи, решающие СЛАУ с плотными матрицами, как правило, приводят результаты при фиксированных параметрах предфильтрации (в частности, допуске обнуления), без оценки их влияния на общие временные затраты. Кроме того, недостаточно представлено сравнение этих способов между собой, что затрудняет корректный выбор способа предфильтрации и его параметров на практике.
Свободно распространяемое программное обеспечение, позволяющее решать СЛАУ с плотными матрицами эффективными итерационными методами без дополнительной модификации, практически отсутствует. Так, известный и постоянно развиваемый пакет ЬАРАСК (последняя версия 3.1.1 вышла 26.02.2007) использует только прямые методы. В системе 8с1ЬаЬ, являющейся бесплатным аналогом Ма1ЕаЬ, содержатся встроенные средства работы с разреженными матрицами, в т.ч. возможности Ш-разложения. В состав последних версий включены и итерационные методы крыловского типа для решения разреженных СЛАУ. Подобная ситуация наблюдается и в МаИшЬ. Специализированное программное обеспечение для электромагнитного моделирования, как правило, использует только прямые методы решения СЛАУ. Так, один из лучших зарубежных программных продуктов БЕКО использует метод исключения Гаусса. В других не всегда уточняется, каким методом получено решение. Поэтому, характерной чертой такого обеспечения является то, что даже высококвалифицированный пользователь не может добиться изменения некоторых параметров численного метода. В результате эффективность исследований с помощью такой системы часто оставляет желать лучшего, а отсутствие у пользователя возможности ее модернизации делает это

2.3 Реализация методов решения СЛАУ в виде отдельных функций
Программно реализованы в виде функций (в системе Visual C++ 6.0) следующие методы решения СЛАУ.
Точные:
- метод Гаусса (GE);
- метод Гаусса, основанный на LU-разложении матрицы (GE(LU)).
Итерационные:
- метод бисопряженных градиентов (BiCG);
- стабилизированный метод бисопряженных градиентов (BiCGStab);
- метод обобщенных минимальных невязок (GMRES(w)).
Функции, реализующие методы BiCG, BiCGStab и GMRES(w), позволяют использовать эти методы как с предобусловливанием, так и без него. Реализовано предобусловливание, основанное как на полном, так и на неполном LU-разложении ILU(O).
Далее приведено описание реализованных функций.
Метод исключения Гаусса: решение методом Гаусса осуществляется с помощью функции cGAUSS(A, b, р), где 1-й аргумент - адрес первого элемента матрицы (Доо); 2-й - адрес первого элемента вектора свободных членов (Ь0); 3-й
- число неизвестных (порядок матрицы).
Метод Гаусса, основанный на LU-разложении матрицы: данный метод реализуется с помощью функций cLU(A, р) и cSOLVE(A, b, р). Первый и второй аргументы функции cLU аналогичны первому и третьему аргументам функции cGAUSS, а аргументы функции cSOLVE- всем трем аргументам cGAUSS.
Метод бисопряженных градиентов: функция cBiCGpre(A, b, р, ,Tol, Nitmax, ILU, т). Аргументы: 1-й аргумент - адрес первого элемента матрицы; 2-й -адрес первого элемента вектора свободных членов; 3-й - число неизвестных (порядок матрицы); 4-й - точность вычислений; 5-й - максимальное количество итераций; 6-й - тип предобусловливания (NONE (без предобусловливания) или ILU; 7-й - допуск обнуления т (при использовании неполного LU-разложения).
Стабилизированный метод бисопряженных градиентов: функция
cBiCGSTABpre(A, b, р ,Tol, Nitmax, ILU, т). Аргументы совпадают с аргументами функции cBiCGpre.
Метод обобщенных минимальных невязок: функция cGMRESpre(A, b, р, Tol, Nitmax, m, ILU, т). Аргументы: 1-й аргумент - адрес первого элемента матрицы; 2-й - адрес первого элемента вектора свободных членов; 3-й - число неизвестных; 4-й - точность вычислений; 5-й - максимальное количество итераций; 6-й - размерность т; 7-й - тип предобусловливания; 8-й - допуск обнуления (т).