автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Алгоритмы и программное обеспечение для решения систем линейных алгебраических уравнений при анализе электромагнитного излучения проводных структур

На правах рукописи

Куксенко Сергей Петрович

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

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание учёной степени кандидата технических наук

Томск - 2007

Работа выполнена в Томском государственном университете систем управления и радиоэлектроники

Научный руководитель - канд. техн. наук старший научный сотрудник

Газизов Тальгат Рашитович

Официальные оппоненты: д-р физ.-мат. наук профессор

Дмитренко Анатолий Григорьевич (Томский государственный университет); д-р физ.-мат. наук профессор Гошин Геннадий Георгиевич (Томский государственный университет систем управления и радиоэлектроники)

Ведущая организация - ОАО «Научно-производственный центр «Полюс»

(г. Томск)

Защита состоится 14 ноября 2007 года в 15.00 на заседании диссертационного совета Д 212.268.02 при Томском государственном университете систем управления и радиоэлектроники по адресу: 634034, г. Томск, ул. Белинского, 53

С диссертацией можно ознакомиться в библиотеке Томского государственного университета систем управления и радиоэлектроники

Автореферат разослан « 10 » октября 2007 года

Ученый секретарь диссертационного совета

Клименко А.Я.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы Решение системы линейных алгебраических уравнений (СЛАУ) имеет большое значение, поскольку к нему сводится решение широкого круга сложных практических задач. В линейной алгебре эту задачу называют первой основной задачей. Так, около 75% всех расчетных математических задач приходится на решение СЛАУ. Необходимость решения СЛАУ возникает при решении многомерных анизотропных краевых задач, в задачах вычислительной гидродинамики, в теории электрических цепей, в задачах управления и контроля, при решении уравнений балансов и сохранения в механике, гидравлике, в задачах оценки и предсказания критических стуаций и др.

Особая необходимость в решении СЛАУ возникает при использовании широкого класса моделей и подходов, применяемых при автоматизированном проектировании аппараяуры с учетом электромагнитной совместимости. Например, решение задач излучения или рассеяния электромагнитной волны сложными объектами может быть получено с помощью интегральных уравнений, сводящихся методом моментов к СЛАУ с плотной, комплексной и несимметричной матрицей большой размерности N х N Достаточно важной задачей является анализ излучения проводных структур, поскольку он необходим при моделировании проводных антенн, аппроксимации излучающей поверхности проводной сеткой, создании различных симуляторов электромагнитного поля и др. Вычислительные трудности решения таких СЛАУ во многом обусловлены заполненностью матриц, приводящей к огромному объему вычислений (особенно в трехмерных задачах).

Для решения СЛАУ с плотными матрицами традиционно используются точные методы, например, метод исключения Гаусса. Но их вычислительные затраты, пропорциональные Л^3, существенно ограничивают круг решаемых задач даже на высокоскоростных компьютерах Необходимость решения сложных задач, дающих рост ТУ, привела к широкому применению итерационных методов Наиболее эффективными и устойчивыми (с точки зрения сходимости к точному решению) среди итерационных методов являются, так называемые, методы крыловского типа В связи с тем, что матрица СЛАУ, полученная применением метода моментов, является, как правило, плохо обусловленной, использование итерационного метода без предобусловливания не вполне обоснованно, поскольку метод может застопориться или даже оборваться Использование пред-фильтрации (игнорирования незначительных элементов) позволяет задать структуру разреженности матрицы СЛАУ, что, в свою очередь, позволяет применить алгоритмы технологии разреженных матриц (предобусловливание) и тем самым уменьшить время решения

Между тем, ряд возможностей совершенствования решения СЛАУ с плотной матрицей итерационными методами при исследовании проводных структур остаётся неиспользованным Так, недостаточно разработаны способы выбора структуры разреженности с помощью предфильтрации матрицы СЛАУ, позволяющие добиться ускорения решения за счет более эффективного использования предобусловливания Следует отметить, что исследователи, решающие

СЛАУ с плотными матрицами, как правило, приводят результаты при фиксированных параметрах предфильтрации (в частности, допуске обнуления), без оценки их влияния на общие временные затраты Кроме того, недостаточно представлено сравнение этих способов между собой, что затрудняет корректный выбор способа предфильтрации и его параметров на практике

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

Цель работы — разработка алгоритмов и комплекса программ для решения систем линейных алгебраических уравнений, возникающих в задачах анализа электромагнитного излучения проводных структур Для достижения поставленной цели необходимо решить следующие задачи

1 Разработать новые алгоритмы предфильтрации

2 Усовершенствовать известные способы предфильтрации

3 Разработать комплекс программ, реализующий новые и известные алгоритмы предфильтрации, методы решения СЛАУ и способы предобусловлива-ния

4 Апробировать основные способы алгебраической предфильтрации на задаче анализа излучения проводных структур.

5 Произвести сравнение результатов, полученных при использовании разных способов предфильтрации на нескольких конфигурациях.

В работе использовались теория матриц, прямые и итерационные методы решения СЛАУ, объектно-ориентированное программирование.

Достоверность результатов подтверждается проверкой корректности программной реализации на примере нахождения заведомо известного решения, совпадением результатов, полученных несколькими методами

Научная новизна

1 Разработаны два новых способа алгебраической предфильтрации

2 Предложено усовершенствование известных способов алгебраической предфильтрации

3 Показано, что при использовании предложенных способов предфильтра-ции существует оптимальное значение допуска обнуления по критерию минимизации времени решения СЛАУ

4 Выявлена стабильность (при изменении частоты) и установлена контролируемая зависимость (от изменения дискретизации) оптимального значения допуска обнуления (по критерию минимизации времени решения СЛАУ) при использовании предложенного способа предфильтрации на примере определения токов в проводной антенне

Практическая значимость

1 Программно реализован модуль матричных операций единой системы компьютерного моделирования электромагнитной совместимости, позволяющий использовать широкий ряд прямых и итерационных методов решения СЛАУ как в виде функций, так и в виде DHTML диалогов Возможности модуля позволяют его использовать для решения других задач, требующих решения СЛАУ с плотной матрицей

2 Выполнено сравнение способов алгебраической предфильтрации при решении СЛАУ итерационными методами, позволяющее оценить изменение оптимального значения порога/допуска обнуления для каждого из способов, на примере определения токов в проводной антенне, как при изменении частоты, так и при изменении дискретизации.

3 Приведены рекомендации по использованию итерационных методов

4 Результаты работы активно используются в учебном процессе

Апробация результатов Результаты диссертационной работы представлялись

и докладывались в материалах следующих симпозиумов и конференций Всероссийская научно-техническая конференция студентов и молодых ученых "Наг учная сессия ТУ СУР", г Томск, 2004, XII Туполевские чтения Международная молодежная научная конференция, г Казань, 2004, Всероссийская научно-практическая конференция "Проблемы информационной безопасности общества и личности", г Томск, 2004, 2005, Международная научно-практическая конференция "Электронные средства и системы управления", г Томск, 2005, Международный симпозиум по ЭМС и электромагнитной экологии, г Санкт-Петербург, 2005, 2007, Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых "Научная сессия ТУСУР", посвященная 45-летию ТУСУРа, г Томск, 2007

Публикации По результатам исследований, представленных в диссертации, опубликовано 19 научных работ 6 статей в журналах из перечня ВАК, 10 докладов и 1 тезисы в материалах симпозиумов и конференций, 1 свидетельство об отраслевой регистрации разработки; 1 монография.

Структура и объем диссертации В состав диссертации входят введение, 3 главы, заключение, список литературы из 109 наим , 3 приложения с актами внедрения Объем диссертации составляет 103 стр, в том числе 24 рис и 23 табл

Личный вклад Все результаты работы получены автором лично или при непосредственном его участии

Внедрение результатов работы

1 Реализованный комплекс программ использовался для оценки паразитных электромагнитных эффектов в печатных платах и в кабелях аппаратуры, разрабатываемой в НПЦ «Полюс»

2 Разработанный комплекс программ использован для выполнения проекта «Разработка системы компьютерного моделирования электромагнитной совместимости» (Заключительный отчет ВТК-15 по мероприятию 3 1 За инновационной программы ТУ СУР, 2006 г и свидетельство об отраслевой регистрации разработки № 8376)

3 Результаты использованы в учебном процессе ТУСУРа (одна лабораторная работа, две авторские лекции, учебно-методическое пособие, монография)

4 Реализованные итерационные методы использованы при выполнении проекта 06-08-01242 «Исследование новых модальных явлений в структурах многопроводных линий передачи с неоднородным диэлектрическим заполнением», поддержанного Российским фондом фундаментальных исследований.

Положения, выносимые на защиту

1 Для решения СЛАУ итерационными методами с предобусловливанием предложен новый способ предфильтрации, показавший стабильность оптимального (по критерию минимизации времени решения СЛАУ) значения допуска обнуления при изменении частоты и его контролируемую зависимость от изменения дискретизации при решении задачи определения токов в проводной антенне

2 За счет выбора способа предфильтрации и оптимального значения порога/допуска обнуления можно сократить время решения СЛАУ итерационными методами с предобусловливанием на 40%

3 При решении СЛАУ итерационными методами с предобусловливанием в сочетании с предфильтрацией, поиск максимального элемента не по всей матрице, а только на главной диагонали, позволяет уменьшить время решения на 13%

4 Выбором оптимального значения допуска обнуления предфильтрации, при решении СЛАУ итерационными методами с предобусловливанием, можно ускорить решение по сравнению с методом Гаусса до 20 раз

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ 1. РЕШЕНИЕ СЛАУ: ОБЗОР

В работе рассмотрено численное решение векторно-матричного уравнения

Ах=Ь, (11)

где Ь - вектор свободных членов, х - вектор неизвестных (вектор-решение) и А- матрица (МхЫ) коэффициентов данной системы Все методы решения СЛАУ можно условно разбить на два класса прямые и итерационные Прямыми называются методы, которые приводят к решению за конечное число арифметических операций Если операции реализуются точно, то и решение будет точным Итерационными являются методы, в которых точное решение может быть получено лишь в результате бесконечного повторения единообразных действий

Последние десятилетия ознаменованы развитием численных методов, нашедших отражение в книгах Г И Марчука, А А Самарского, С К Годунова, Дж Голуба, О Аксельсона, Ю Саада, X Ворста и др Несмотря на имеющиеся в этой области теоретические достижения, а также на бурный рост мировых вычислительных мощностей, проблема разработки и исследования новых быстрых алгоритмов решения СЛАУ не теряет своей аклуальности, и поток публикаций по этой тематике только увеличивается

Для решения задач электромагнитного поля существуют различные подходы, которые сводятся к аналитическому или численному решению соответствующих интегральных или дифференциальных уравнений в частотной или временной области, из которых особо выделяется метод моментов. Поэтому, метод моментов разрабатывался очень интенсивно, и в первую очередь применительно к задаче анализа проводных структур

В практических приложениях метода моментов обусловленность матрицы СЛАУ ухудшается с приближением частоты воздействия к частотам собственных колебаний исследуемой структуры Анализ показывает, что применение итерационных методов является первым и весьма плодотворным шагом для эффективного решения СЛАУ с плохо обусловленной матрицей

Наиболее эффективными и устойчивыми среди итерационных методов являются, так называемые, методы крыловского типа Эти методы обладают рядом достоинств, они устойчивы, допускают эффективное распараллеливание и работу с предобусловливагелями разных типов Данные методы исторически разрабатывались для решения разреженных систем Проведенный обзор, позволил в работе привести алгоритмы (готовые для программной реализации) шести итерационных методов крыловского типа

Вычисление итерационными методами зависит от обусловленности матрицы А, оцениваемой числом обусловленности аи^А^ЩАН-ЦА""1!! С ростом сопс!А обусловленность ухудшается, и для ряда проблем сходимость может оказаться очень медленной, и поэтому итерационный процесс может застопорится или даже оборваться. Однако применение предобусловливания улучшает сходимость к требуемому решению

Пусть М - некоторая невырожденная (Л/хЛ1) матрица Домножив (11) на матрицу Мч, получим систему

М~1Ах=1УГ1Ь, (1.2)

которая в силу невырожденности М имеет то же точное решение Процесс перехода от (1 1) к (1 2) с целью улучшения характеристик матрицы для ускорения сходимости к решению называется предобусловливанием Очень важным является то, что матрица М должна быть по возможности близка к матрице А

Способы предобусловливания можно разбить на два вида явные и неявные. Для представления системы Ах=Ь с явным предобусловливанием удобно воспользоваться записью (12). Неявно предобусловленную систему Ах=Ь удобно представить в виде уравнения МАх=МЬ Известно, что предобусловливание может быть введено в схему метода (крыловского типа) без необходимости явного вычисления матричного произведения Так, явное

предобусловливание требует нахождения матрицы М-1 и умножения матрицы предобусловливания на вектор в каждой итерации Для неявного необходимо решать СЛАУ с матрицей М в каждой итерации Большинство способов предобусловливания обоих видов основано на известном представлении матрицы в виде произведения двух матриц Ь и и (Ьи-разложение)

Известно, что если исходная матрица разреженная, то матрицы Ь и II являются более плотными Основываясь на Щ - разл ожен и и, матрицу предобусловливания можно формировать несколькими способами Первый основан на нахождении матрицы М из матрицы А с помощью Ш-разложения и обнуления по ходу вычислений незначительных элементов в треугольных матрицах Ь и и (постфильтрация) Второй, более выигрышный, основан на предфильтрации, когда игнорированием некоторых элементов исходной матрицы получают разреженную матрицу А1 (а,] = 0 , если а,, игнорируется и а], = а„ в противном случае) и потом производят ее Ш-разложение, тем самым формируя искомую матрицу М=Ы1 Таким образом, использование предфильтрации (игнорирования незначительных элементов) позволяет задать структуру разреженности матрицы СЛАУ, что, в свою очередь, позволяет применить алгоритмы технологии разреженных матриц (предобусловливание) После того, как матрица М сформирована, происходит решение предобусловленной СЛАУ Как было замечено выше, второй подход приводит к тому, что матрица М оказывается более плотной (заполнение без ограничений), чем матрица А'1, что соответствует увеличению требуемой памяти

Альтернативой полному является неполное разложение, применяемое к матрице А* Данное разложение заключается в представлении

М=ьи+К, (13)

где Ь и и - как и прежде, нижне- и верхнетреугольные матрицы, соответственно, а матрица К является матрицей ошибки Тогда приближенное представление М«Ы1 называется неполным Ы1-разложением матрицы М или коротко, её 1Ьи-разложением Самой простой версией данного разложения является 1ЫД0) Оно заключается в применении Ьи-разложения к матрице А\ но если а,, =0, то сразу полагается Г,,= 0 или щ=0 Если №?(А5) - структура разреженности матрицы А5, а №?(М) — матрицы М, то очевидно, что данный способ приводит к тому, что их структуры совпадают (Чтобы подчеркнуть тот факт, что в данной постановке задачи в структуру не вводятся новые ненулевые элементы, такую факторизацию часто называют факторизацией с нулевым заполнением.) Поскольку полное разложение приводит к заполнению структуры матрицы без каких-либо ограничений, а 1Ьи(0)-разложение - к нулевому заполнению, очевидно, что еще одним вариантом может служить разложение с неким уровнем заполнения Такими способами являются 11ХГ(/>)-разложение, 1ШТ и др Проведенный обзор позволил привести в работе готовые для программной реализации способы предобусловливания

Так как вычислительные затраты, возникающие при компьютерном моделировании, состоят из затрат на формирование матрицы и собственно решение

СЛАУ, снижение каждой из составляющих является важной практической задачей Общее время решения СЛАУ с плотной матрицей итерационным методом с предобусловливанием состоит из трех составляющих затрат на выбор структуры разреженности с помощью предфильтрации (получение из матрицы А матрицы А5), затрат на формирование из матрицы А4 матрицы предобусловли-вания М и затрат на Ы„ итераций, необходимых для получения решения с требуемой точностью Отметим, что первая составляющая этих затрат во многом определяет другие затраты Так, выбор структуры разреженности определяет количество арифметических операций, требуемых для формирования матрицы предобусловливания, что, в свою очередь, повлияет на затраты каждой итерации, поскольку в каждой итерации необходимо один или два раза решать СЛАУ с матрицей М (при использовании неявного предобусловливания) Наконец, выбор структуры разреженности повлияет и на количество итераций, поскольку он меняет обусловленность результирующей матрицы М-1 А Таким образом, выбор структуры (портрета) разреженности матрицы предобусловливания является важной практической задачей Рассмотрим ее подробнее

Одной из простейших стратегий является выбор заранее известной структуры, например, ленточной или блочно-диагональной, те элементы матрицы А8 совпадают с ленточной (блочно-диагональной) частью матрицы А и равны нулю вне данной структуры Такая предфильтрация характеризуется шириной ленты (размером блока) и, таким образом, основана на позиции элемента в матрице (структурная предфильтрация), а не на его значении

Более часто используемой стратегией является динамическое определение структуры разреженности, например, с помощью некоторого порога (алгебраическая предфильтрация) Она заключается в задании (нахождении) определенного порога, с помощью которого происходит игнорирование малозначащих элементов путем сравнения модуля каждого элемента с данным (полученным) значением

Упомянутый порог обнуления, в свою очередь, может быть получен многими способами Самым простым из них является проверка на малость модулей элементов матрицы с заданным порогом обнуления (е)

а„ = а„, если |а</| > е, г,у = 1,. , N (14)

Он является простейшим, с точки зрения вычислений, и требует наименьшего времени на формирование разреженной матрицы А5, поскольку порог обнуления задается непосредственно, без необходимости его вычисления

Другой способ предфильтрации, предложенный Л Ю. Колотилиной-

а'1 = а,Р если |Яу/йтах| > е, г,у = 1, , /V, (15)

где сГ'х - максимальный элемент матрицы Понятно, что при использовании данного способа достаточно много времени требуется на поиск наибольшего элемента в матрице Способ был предложен для применения явного предобусловливания при решении СЛАУ с плотной матрицей Первоначально происходило обнуление малозначащих элементов исходной матрицы, те первоначально плотную матрицу приводили к разреженному виду, тем самым становилось

возможным применение технологий разреженных матриц Далее на основе полученной структуры разреженности матрицы строилась матрица предобусловливания Таким образом, решение СЛАУ с плотной матрицей было сведено к решению разреженной системы итерационным методом с предобусловливани-ем Позже, вместо разреживания исходной матрицы исследователи стали применять данный подход для формирования матрицы предобусловливания, те использовать его как предфильтрацию Данный способ широко применялся и применяется, как правило, при построении явного предобусловливания для решения плотных СЛАУ, получаемых методом граничных элементов В работах В. Carpentien, I S Duff, M Benzi и M Tuma приведены результаты при двух значениях порога обнуления: 0,05 и 0,075. Стоит отметить, что автору не известны работы, в которых решалась бы СЛАУ (полученная методом моментов) с использованием этого способа предфильтрации для формирования матрицы предобусловливания.

Используется также обнуление, основанное на бесконечной норме матрицы, а,; = а,„ если \а,\ > s = ЦаЦ^ x[N, i,j=\, , N, (1 6)

где ¡AL = JaJ, a т— допуск обнуления Очевидно, что значительные

временные затраты при использовании данного способа связаны с поиском наибольшей суммы строки.

Способ использовался следующим образом Первоначально система с плотной матрицей преобразовывалась с помощью вейвлетов, после чего она остается достаточно плотной, но большая часть ее элементов имеет небольшие абсолютные значения Обнуление элементов, по описанному выше правилу, приводило к получению разреженной матрицы СЛАУ. Таким образом, плотная матрица СЛАУ приводилась к разреженному виду, позволяющему применение эффективных итерационных алгоритмов, ориентированных на разреженные системы

В последующем в работах О Franza, R Wagner и W С Chew было предложено использовать этот подход при решении задачи излучения, где была показана его эффективность Вычисления производились на примере задачи излучения цилиндра при использовании метода моментов Было показано, что выбор т = 0,1-0,2 является оптимальным для минимизации времени решения СЛАУ Поскольку такое упрощение, дающее ускорение, не всегда обоснованно и приемлемо для некоторых классов задач, то исследователи стали использовать это правило обнуления, как способ определения структуры разреженности матрицы предобусловливания, те стали использовать его как предфильтрацию

Известен способ выбора структуры разреженности, предложенный VV Prakash и R Mittra, основанный на нахождении наибольшего элемента в строке,

а], = а„, если |д;,/<аГах| > £, hJ = h ,N, (17)

где fir,™ - максимальный элемент в г-й строке Поскольку способ основан на нахождении максимального элемента в каждой строке, порог обнуления является

разным для каждой из строк После того, как максимальный элемент найден, происходит процесс, подобный описанному при использовании подхода (1 5), но вместо всей матрицы сканируется строка матрицы Очевидно, что при использовании как данного, так и подхода (15), значительные затраты времени связаны с поиском максимальных или максимального элементов В работе, где была предложена данная предфильтрация, в качестве исследуемой использовалась только одна конфигурация, специальная антенная решетка Решение задачи излучения было сведено к СЛАУ методом моментов Все вычисления проводились при фиксированном значении 8=0,01 В работе не приведены рекомендации по заданию порога обнуления при изменении рассматриваемой конфигурации Автору не известны другие работы, в которых использовался бы данный способ предфильтрации Как видно из приведенных (в хронологическом порядке) основных способов, с течением времени исследователи пытались найти предфильтрацию, адаптивную к различным задачам

Отметим, что алгебраическая предфильтрация может сочетаться практически со всеми другими видами, как со структурной, так и с другими способами динамической. Также понятно, что приведенные способы алгебраической предфильтрации могут быть использованы как постфильтрация при формировании матрицы предобусловливания Таким образом, данный вид предфильтрации является, пожалуй, самым универсальным

Упомянутые способы алгебраической предфильтрации можно разделить на две группы Способы глобальной предфильтрации (1.4)-{1.6) задают общий порог обнуления для всех элементов матрицы К способам локальной предфильтрации относится способ (1.7), определяющий для каждой строки свой порог обнуления Априорно трудно сказать, какой подход предпочтительнее, как с точки зрения минимизации времени решения СЛАУ, так и стабильности допуска/порога обнуления

Таким образом, благодаря проведенному обзору были собрано воедино готовые для программной реализации алгоритмы итерационных методов, способов предобусловливания и предфильтрации

В заключении гл 1 приведен обзор программного обеспечения и сформулированы цель и задачи работы (см. с 4)

2. РАЗРАБОТКА И РЕАЛИЗАЦИЯ АЛГОРИТМОВ Предложен способ локальной предфильтрации, основанный на идее постфильтрации при формировании матрицы предобусловливания с помощью 1ЬиТ-разложения Предлагаемый способ состоит в том, что разреженная матрица Ая формируется из матрицы А путем игнорирования некоторых элементов (кроме диагональных) согласно следующему правилу Перед предфильтрацией 1-й строки вычисляется ее евклидова норма, умножением которой на задаваемый допуск обнуления т получают г-й порог обнуления б, После того, как все элементы строки будут проверены на малость, необходимо повторить те же действия со следующей (н-1)-й строкой Процесс закончится после того, как все строки матрицы А будут обработаны подобным образом. Данный процесс можно представить в виде

al = a4, если; =7 или \а,\ > е, = |к4 х' г>-/=1>. (2.1)

где ||д„||2 = fe'Jaf - евклидова норма /-Й строки Таким образом, порог обнуления является своим для каждой из строк, т.е данный способ относится к группе способов локальной предфильтрации

Предложенный способ глобальной предфильтрации, заключается в следующем Разреженная матрица As получается из матрицы А путем игнорирования некоторых элементов этой матрицы (кроме диагональных) согласно следующему правилу

а', = а,„ если t =у или \а,\ > е = ||А| т, i,j = 1, , N, (2 2)

где || А|г=^ ^Г ^ |2 ™ евклидова норма (также называемая нормой Фробе-

ниуса) матрицы А, а т - задаваемый допуск обнуления Таким образом, структура разреженности сформированной матрицы А8 может быть использована для формирования матрицы предобусловливания Временные затраты на реализацию данного способа предфильтрации меньше затрат на предфильтрацию (2 1), поскольку здесь необходимо всего один раз осуществить операцию извлечения квадратного корня

Из теоретических основ метода моментов и опыта моделирования проводных структур известно, что максимальные элементы матрицы СЛАУ группируются у главной диагонали. Используя это, можно ускорить процесс предфильтрации уже известных способов Так, время предфильтрации (1.5) при использовании этого подхода сократится за счет поиска только на главной диагонали, а не по всей матрице В способе (1 6) можно положить, что максимальной суммой обладает главная диагональ, т.е

а], = а,,, если i-j или \а,\ > £ = ^ |в„| х/N, i,j= 1, , N, (2 3) и не тратить время на поиски наибольшей суммы строк Для способа (1 7) можно ограничиться условием того, что максимальные элементы в строке находятся на главной диагонали, т е воспользоваться правилом

a,j = a,j, если i = j или \а,,1а,\ >в, i,j = 1, , N (2 4)

Программно реализованы в виде функций (в системе Visual С++ 6 0) следующие методы решения СЛАУ метод Гаусса, метод Гаусса, основанный на LU-разложении матрицы, метод бисопряженных градиентов (BiCG), стабилизированный метод бисопряженных градиентов (BiCGStab), метод обобщенных минимальных невязок (GMRES(w)) Реализовано предобусловливание, основанное как на полном LU-разложении, так и на неполном — ILU(0)

Разработан модуль матричных операций, удовлетворяющий требованиям системы компьютерного моделирования электромагнитной совместимости TALGAT, реализующий операции над матрицами (создание, чтение и изменение элементов, изменение размера, добавление и вырезание строк и столбцов, форматированный вывод), 8 прямых методов решения СЛАУ, 6 итерационных методов решения СЛАУ с возможностью задания их параметров, 6 способов

предобусловливания; 10 способов предфильтрации. Для более удобного использования в системе предусмотрена возможность их применения с помощью DHTML диалогов. Стартовый диалог и пример диалога для решения СЛАУ методом BiCGSlab показаны на рис. 2.1. Также реализована визуализация матриц после предфильтрации и формирования предобусловливания. Элементы, абсолютные значения которых ниже заданного порога (обнуляемые), отображаются белым цветом, а выше —черным.

ТА1Ы1. OHIH1 OÖtaj ^ I....A. о,.ГШ Ob»-, — '

TAI.ü AT:

рг м in lu сллу

Методы решения СЛАУ

1 ЛI X ;л | :

Инн IIL« слау

итерационные

i " ¡3iOGSt»>.

GHRE Цкй r S3CG CGS С <J*Sk

=мврять

а

S.l'. Kl ы \М1 200ft

Рис. 2.1. DHTML

PLi) ' L'JP ' CHOL

я мирный я вектора

bmti

чинши 1Ч;>.-Л|' J'lij OUi;Ji>~ г L' 11Ч

Ком Г LUn: Lv'ini ■" LUt i'i f -JJkl '' LUknt " LlAJnt iLUOflr ' lUiftnt '' ILÜ3nrr -" iLUOlc iLUQIan ■" HUGdm

плрвмпр для плр.лчгекпп

' Покдо.

6 тлу; г

s.p. kuksünk« 2006

диалоги: для выбора метода (а), для метода BiCGStab (б)

3. ИССЛЕДОВАНИЕ РАБОТЫ ИТЕРАЦИОННЫХ МЕТОДОВ

Работа итерационных методов исследована на задаче определения гоков в проводной антенне. Первоначально система (1.1) решалась итерационными методами BiCG, BiCGStab, CGS, QMR и GMRES(m) при т=Ю, 20, 40. В качестве исследуемых взяты четыре антенны: широкодиапазонная антенна (N=1261, плотность матрицы dA= 100%); трапециевидная зубчатая антенна (/V = 765, dA= 99,997%); антенна «чайка» (N = 1865, dA= 100%); диполь с углом между лучами 180° (N = 2335, dA = 100%). Общий вид этих антенн (кроме диполя) приведен на рис. 3.1.

3

-ftFfc^

Рис. 3.1. Вид антенн: широкодиапазонной (а), «чайка» (б), трапециевидной ¡убчагой (в) Проведенные вычисления показали, что применение итерационных методов без предобусловливания не эффективно, поскольку в большинстве случаев для получения приемлемого решения итерационному процессу было не достаточно

400 итераций или требовались значительные временные затраты (намного большие, чем при использовании метода Гаусса)

Далее использовались те же методы с предобусловливанием В качестве способов формирования матрицы предобусловливания использовались полное LU-разложение, ILU(O) и ILU^d), при р=1, 2, 3 В качестве предфильтрации использовался предложенный способ (2 1), основанный на нормах строк матрицы. В качестве исследуемых были взяты две антенны диполь и широкодиапазонная антенна (см рис 3.1а) Анализ результатов исследования показал, что наиболее предпочтительными, с точки зрения минимизации времени решения СЛАУ, оказались два метода BiCGStab и CGS при использовании полного LU-разложения и предложенного способа предфильтрации (2 1) Поскольку они показали практически одинаковые результаты, в дальнейших исследованиях чаще использовался один из них метод BiCGStab Также показано, что в качестве способа формирования матрицы предобусловливания предпочтительнее использовать полное LU-разложение, поскольку оно оказалось наиболее работоспособным для каждого метода.

С целью выявления зависимости времени решения СЛАУ от допуска обнуления предложенного способа предфильтрации (2 1) решалась СЛАУ итерационным методом на примере широкодиапазонной антенны (см рис. 3 1а) с матрицами N=243 и N=1023 при т=10~\ 5 10 2, . , 10"4 При формировании матрицы предобусловливания использовалось полное LU-разложение В табл 3 1 приведена выборка результатов вычислений при х=1(Г (Г- время решения СЛАУ, N„ — число итераций, реальная и мнимая части второго и последнего элементов вектора решения, те распределения тока в антенне) методом BiCGStab при разной точности вычислений То! (условие прекращения итераций ||rt||2/||ro||2 < Toi,

где гк и г0 - невязки после к-й итерации и нулевого начального приближения, соответственно), а также методом Гаусса (последняя строка, GE) Из нее видно, что методом BiCGStab решение, например с точностью до 4 знаков после запятой совпадающее с решением методом Гаусса, получается в 6 раз быстрее, чем методом Гаусса При необходимости, более точные результаты легко получить, увеличивая число итераций например решение, совпадающее с точностью до 10 знаков, получается в 4 раза быстрее.

Таблица 3 1 Результаты вычислений при т=10 3 для проводной антенны с матрицей Д£=243

Toi Т, с м, Re(/,)-A Im(ii), А Refe.2), А 1ш(/242), А

10"' 0,16 4 —5,5433315933 10~3 8,5280934358 Ю"4 3,1026158901 10~3 -2,0675906220 10"

10~2 0,22 5 -5,5429392637 10"3 8,5304111642 10"4 3,1019734236 10"3 -2,0697442283 КГ*

кг* 0,22 5 -5,5429392637 10 3 8,5304111642 Ю-4 3,1019734236 10~3 -2,0697442283 Ю-4

ТО"4 0,22 5 -5,5429392637 10""3 8,5304111642 10" 3,1019734236 10""3 -2,0697442283 10 4

ю-"- 0,27 6 -5,5429393543 10~3 8,5304010642 10"1 3,1019740107 10~3 -2,0697295482 10"4

10"6 0,28 7 -5,5429393483 Ю-3 8,5304010471 10"4 3,1019740055 10~3 -2,0697295161 104

ю-7 0,28 7 -5,5429393483 1СГ1 8,5304010471 10"4 3,1019740055 10"3 -2,0697295161 КГ*

10"8 0,33 8 -5,5429393528 10~3 8,5304010530 Ю-4 3,1019740083 10"3 -2,0697295185 10 4

GE 1,37 - -5,5429393528 10"3 8,5304010530 10"4 3,1019740083 103 -2,0697295185 Ю"

Аналогичные вычисления для той же антенны с матрицей N= 1023 показали, что методом BiCGStab решение, с точностью до 4 знаков после запятой совпадающее с решением методом Гаусса, получается за 10 итераций и в 14 раз быстрее, чем методом Гаусса Более точное решение, совпадающее с точностью до 10 знаков, получается в 10 раз быстрее Таким образом, уменьшение заданной точности решения СЛАУ от 10 до 4 знаков ускоряет решение в полтора раза

Зависимости времени решения СЛАУ от т для различных Toi приведены на рис 3 2 Видно, что для всех Toi существует значение т, оптимальное по критерию минимизации времени решения СЛАУ (далее т^)

Рис 3 2 Зависимости времени решения СЛАУ от и для разных Toi при JV=243(a), 1023(б) На рис 3 3 (а) показаны зависимости времени решения СЛАУ (Т, с) с матрицей N=969 от т для диполя с углом между лучами 180° и 15° при 7о/=10~8 Выбор тор1 ускорил решение для угла 180° в 17 раз, а для угла 15° в 10 раз по сравнению с методом Гаусса Существование xopi объясняется различной зависимостью от х двух основных составляющих общего времени решения СЛАУ времени LU-разложения матрицы As, выполняемого только один раз до итераций, и времени на N„ последующих итераций (см. рис 3 3 (б)) Первая составляющая (71, с) пренебрежимо мала слева от тор1, но с удалением вправо от него все более доминирует в общем времени решения СЛАУ Отметим, что в этой части графика характер зависимости Лотт полностью совпадает с характером зависимости процента ненулевых элементов (NonZero) матрицы M Вторая составляющая пропорциональна значению N„ и, как видно, полностью определяет время решения СЛАУ слева от тор1 и все меньше влияет справа В итоге у середины диапазона т общее время решения СЛАУ минимально

Результаты, получаемые итерационными методами, в отличие от прямых, получаются приближенными. Теоретически, при устремлении числа итераций к бесконечности итерационный процесс закончится получением решения, полностью совпадающего с решением, полученным при применении прямого ме-

тода Поскольку зачастую нет необходимости в получении точного решения, то дополнительное ускорение итерационного процесса можно достичь за счет снижения точности до достаточной для получения требуемых характеристик

Рис ? 3 Зависимости характеристик решения СЛАУ от т при N=969 и ТЬМО"8 время решения СЛАУ для угла между лучами диполя 180° и 15° (а), характеристики для угла 15° (6)

Результаты ускорения на примере вычисления диаграммы направленности проводной антенны «чайка» (см 3 16) приведены в табл 3 2В качестве способов формирования матрицы предобусловливания использовалось полное Ьи-разложение, а в качестве способа предфильтрации использовался предложенный автором подход (2 1), основанный на нормах строк матрицы В первой строке таблицы приводится время, затрачиваемое на формирование матрицы предобусловливания В последующих строках приведено время решения СЛАУ методом В1СС81аЬ (тоР1=5 Ю-"5) при увеличении числа итераций а в последней строке - время решения методом Гаусса (ОЕ) Также приведены второй и последний элементы вектора решения (модуля тока в сегментах антенны) Из табл 3 2 видно, что после 14 итераций решение методом В^'С^аЬ, совпадающее с точностью до 5-7 знаков после запятой с решением метода Гаусса, получено в 9 раз быстрее Решение с точностью до 1-2 знаков после запятой получено в 15 раз быстрее, и после 5 итераций Отметим, что после 2 итераций решение получено в 20 раз быстрее чем методом Гаусса, между тем, диаграммы направленности (ДН) для этих случаев практически совпадают (рис 3 4) Таким образом, выбор оптимального значения допуска обнуления ускоряет решение по сравнению с методом Гаусса до 20 раз

Далее проводилось сравнение известных способов предфильтрации (1 4)-(1 7) и предложенных - (2 1) и (2 2) Вычисления методами В1СС, В1СС81аЬ и СвБ производились на примере вычисления токов в трапециевидной зубчатой проводной антенне (см рис 3 1в) В качестве способов формирования матрицы предобусловливания использовались полное ьи-разложение и 11X1(0) (Для способов (1 4), (1 5) и (1 7) полагалось, что е=т ) В табл 3 3 для разных частот приведены характеристики решаемой задачи порядок СЛАУ (А0, относительное число ненулевых элементов матрицы СЛАУ (с!А), время ее заполнения (//„„,) и

100

90

70 60 50 40 30 20 10 0

80

10"' 10~2 10 3 КГ1 10" 10"'

10"' НГ2 ИГ1 10"* 10~5 106

время решения методом Г аусса (7'<;;.). Видно, что с увеличением частоты в общих затратах все больше преобладает время решения СЛАУ. Аналогичные результаты для разной дискретизации и частоты 3 ГГц приведены в табл. 3.4. Таблица3.2. Время решения СЛАУ (AM4II) методом Га- 90°

усса и методом BiCGStab (i„r„=5-l() ') при увеличении чис-

Метод N„ T, с ÏI *14П

(2.1 )+LU 0 11,42 - -

BiCGStab 1 12,19 6,1799428153-Ю 3 3,6922306960 10 3

2 13,34 1,1093077151 10 2 6,4877950767-10 3

3 14,72 6,4470277177-Ю--1 5,5342527383-10"3

4 15,82 8,7150023440-КГ3 6,2481368771 10 3

5 17,08 9,261283465 ПО"3 6,4110392615-10~3

6 18,35 9,2751980061 10 3 6,4162720824-10 3

7 19,67 9,2899504274-10 3 6,4222883724-10 "3

8 20,77 9,2776336596-Ю 6,4186168278 10 3

9 22,14 9,2761160171-Ю-3 6,4180791769-10 3

10 23,23 9,2764746391 Ю"3 6,4181979509-ИГ3

11 24,50 9,2765681960 10 3 6,4182244732-10 3

12 13 25,71 9,276388466810 3 6,4181706239 ■ 10 3

27,08 9,2763808296-10"3 6,4181681950-Ю"-3

14 28,17 9,2763809832 10 3 6,4181682487 • 10 л

GE - 267,54 9,2763810168-10-3 6,4181682591-Ю"3

Рис. 3.4. Д11 (|£ф|, шкала линейная от 0 до 6 В/м) антенны «чайка» в плоскости АТ при решении СЛАУ методом Гаусса (СГ;) и методом ВКХ;8(аЬ при увеличении числа итераций

Анализ полученных данных показывает, что выгоднее использовать полное Ьи-разложение вне зависимости от использованного метода. Также показано, что предложенная автором предфильтрация (2.1) имеет наименьший разброс во времени решения СЛАУ при использовании Ш- и Ши(0)-разложений. Так, выигрыш варьируется от 2% до 10% для метода СС8 и В)СО, соответственно.

На рис. 3.5а приведено время решения СЛАУ методом В1СС81аЬ с пред-фильтрациями (1.4)-(1.7), (2.1) и (2.2) (при т„Р1) при использовании полного И_1-разложения. Показано, что на любой частоте (кроме случая использования полного Ьи-разложения для частоты 10 ГГц) наилучшим (по критерию минимизации времени) является самый простой способ предфильтрации (1.4), причем вне зависимости от вида разложения. Наибольшее расхождение во времени решения СЛАУ при разной предфильтрации для разных частот в зависимости от использованного разложения различно. Так, при использовании полного Ш-разложения получен выигрыш до 40% с предфильтрацией (1.4) по отношению к (1.6) (для 6 ГГц). В случае же 1Ьи(0)-разложения с предфильтрацией (1.4) выигрыш составляет до 37% относительно способа (2.2) (для 10 ГГц). Аналогичные результаты, полученные при использовании метода Св8, показали, что на любой частоте наилучшим (по критерию минимизации времени) является способ (1.4), причем опять же вне зависимости от вида разложения. При использовании полного Ьи-разложения получен тот же самый выигрыш, как и при использовании метода В1С081аЬ, до 40% с предфильтрацией (1.4) по отношению к (1.6) (для 6 ГГц). При замене полного Ш-разложения неполным и использо-

вании предфильтрации (14) выигрыш составляет до 30% относительно способа (2 1) (для 8 ГГц)

Таблица 3 3 Характеристики матрицы

Таблица 3 4 Характеристики матрицы для

/;ггц N ад, % Т/оппу С 7«, с

4 1003 99,9986 7 18

6 1503 99,9989 15 62

8 1981 99,9996 27 142

10 2477 99,9998 42 276

12 2975 99,9997 61 483

Дискретизация N Т/оть С Т<,1, с

я/ю 765 99,9974 4 8

Я/20 1513 99,9991 16 63

Я/30 2247 99,9997 35 206

Я/40 2997 99,9997 62 497

60 Т, с

50

40 :

-*-(1 4)+Ш —•— (1 5)+Ш —-(1 6)+Ш -(1 7)+Ш ——(2 1)+Ьи -(2 2)+Ш

10 -

50 п Г,с

40 -

30 -

20 -

10 -

—-(1 4)+Ш -•-(1 5)+Ш -в-(1 6)+Ш ->~(1 7)+Ш —»—(2 1)+Ш -(2 2>Ш

Дискретизация

Я/10

Я/20

>./30

Я/40

Рис 3 5 Зависимости минимального времени решения СЛАУ методом ВаСТ^аЬ для различных способов предфильтрации от частоты (а) и от дискретизации (б) На рис 3.5б приведено время решения СЛАУ методом ЕМХ^аЬ с пред-фильтрациями (1 4)-(17), (2 1)-(2 2) (при т„Р0 в зависимости от дискретизации для частоты 3 ГГц Наибольший выигрыш способа (1 4) по отношению к (1 7) при Х/40 достигает 30%. Были проведены аналогичные вычисления методом СС8 Полученные зависимости методом СС8 показали, что в большинстве случаев (кроме случая А./40) наилучшим (по критерию минимизации времени) является способ (1.4) Расхождение во времени решения СЛАУ при разных способах предфильтрации оказывается менее существенным, чем при использовании метода БМХ^аЬ Так, при дискретизации Х/40 выигрыш способа (1 7) по отношению к (1 5) достигает 15%

Максимальный выигрыш за счет использования методов С08 и ГМХ^аЬ по сравнению с методом Гаусса при росте частоты возрастает с 9 раз (4 ГГц) до 12 раз (12 ГГц) При увеличении дискретизации выигрыш возрастает с 8 раз (Л/10) до 15 раз (А/40) при использовании метода ХМХ^аЬ, а при использовании СОБ - 8 раз (А/10) до 13 раз (А/40)

В табл 3 5 приведены тор1 для разных частот Видно, что при изменении частоты для предложенной предфильтрации (2 1) и способа (1 7) оптимальное значение допуска обнуления остается одним и тем же, чего нельзя сказать о других способах предфильтрации Способ (2 2) показал стабильность для частот более

4 ГГц Такая стабильность важна, поскольку она минимизирует затраты времени при многовариантном анализе в большом числе частотных точек или при оптимизации по частоте, широко применяемым на практике

В табл 3 6 приведены xopt при разной дискретизации для 3 ГГц Видно, что ни один из способов не показал высокой стабильности тор1 при изменении дискретизации во всем диапазоне Способы (1 6) и (17) показали стабильность при дискретазации более чем Х/10 Для (1 5), (21) и (2 2) шаг изменения дискретизации соответствует примерно шагу изменения xopt

Время решения СЛАУ методом BiCGStab для А/40 (3 ГГц) за счет поиска только на главной диагонали сокращено с 38 с (для способа (1 5)) до 33 с (для усовершенствованного (1 5)) Таким образом, предложенное усовершенствование сократило время решения СЛАУ на 13%

Таблица 3 5 Тор, для предфильтрациий Таблица 3 6 т^,, для предфильтраций

при изменении частоты при изменении дискретизации

4 6 8 10 12

(14) 1040 1<Г° 5 Ю-1 5 10"' 5 10"'

О 5) 5 КГ' 5 10"1 КГ» 5 10"4 5 10"

(16) 10+" 5 10*° 10^ 10+° 10м'

(1 7) 5 10"3 5 10"3 5 10"3 5 10"3 5 10~3

(21) 5 КГ1 5 1(Г3 5 1<Г3 5 10"3 5 10~3

(2 2) 5 10"4 5 10^ 5 10"* 5 10"* 5 10 '

Х/10 то А./30 А/40

(14) 5 Ю+0 5 10"' 5 10"' 10"'

(1 5) 5 Ю'3 10~3 5 10"4 ю-4

(16) Ю^ 5 10"' 5 Ю-1 5 НГ1

О?) 5 КГ1 5 10"4 510"4 5 Ю-4

(21) 5 10~3 5 КГ* 5 10ч ю-4

(2 2) 10"* 5 10"' 5 10 6 5 10^

С целью подтверждения обнаруженной стабильности оптимального значения допуска обнуления (по критерию минимизации времени решения СЛАУ), при использовании предложенного способа (2 1), были проведены вычисления методом BiCGStab в большем количестве частотных точек (4,4,5, 5, , 12 ГГц) В результате была подтверждена обнаруженная стабильность оптимального значения допуска обнуления, равного 5 Ю-1 при использовании с полным LU-разложением и равного 10"1 - с ЕШ(0)-разложением На рис 3 6 показаны полученные частотные зависимости времени заполнения матрицы СЛАУ (form), решения методом Гаусса (GE), решения методом BiCGStab в сочетании с пред-фильтрацией (21) и полным LU-разложением; решения методом BiCGStab с предфильтрацией (2 1) и 1Ш(0)-разложением Видно, что во всем диапазоне частот предпочтительнее использовать метод BiCGStab по сравнению с методом Гаусса, а также что использование полного LU-разложения предпочтительнее ILU(O), поскольку оно приводит к меньшим временным затратам Примечательно также и то, что временные затраты на решение СЛАУ меньше затрат на формирование матрицы вне зависимости от использованного способа предобу-словливания.

В дальнейшем, опять же для подтверждения обнаруженной стабильности оптимального значения допуска обнуления, проводились аналогичные вычисления методом BiCGStab в сочетании с предложенной предфильтрацией (2 1) и полным LU-разложением на примере определения токов в диполе (угол между лучами 180°) на частотах 300, 450, . , 900 МГц Вычисления подтвердили ста-

500 q

бильность оптимального значения допуска обнуления (5 10^) при использовании предложенной предфильтрации

<— Рис 3 6 Частотные зависимости времени заполнения матрицы (form), решения методом Гаусса (GE), решения методом BiCGStab с предложенной предфильтрацией (2 1) и полным LU- и IL.lJ(0)- раз ложа iия м и

Далее проводилось сравнение новых и усовершенствованных способов предфильтрации на примере широкодиапазонной антенны (рис 3 1а) На рис 3 7 приведено время решения СЛАУ, полученное методом BiCGStab с предфильт-рациями (14)-(17), (2 1)-(2 4) (при t„pt), в зависимости от частоты при дискретизации А/10 (а) и от дискретизации для частоты 125 МГц (б) Из графиков трудно выделить преимущество какой-либо предфильтрации Однако расхождение во времени решения СЛАУ при разных способах предфильтрации оказывается существенным Так, для частоты 485 МГц получен выигрыш 23% с предфильтрацией (1 4) по отношению к (2 1), а для дискретизации А./40 - 17% Таким образом, дальнейшее совершенствование предфильтрации актуально Для 165 МГц максимальный временной выигрыш по сравнению с методом Гаусса составляет 5 раз, а для 485 МГц он возрастает до 9 раз Выигрыш же во времени за счет дискретизации возрастает от 7 при А/10 до 9 при А/40

70 -з

60 -

Г, с

-(1 4)+LU -—(1 5)+LU -—(1 6)+LU — (1 7)+LU -—(2 1)+LU

-(2 2)+LU

-(2 3)+LU

—•—(2 4)+LU

/, МГц

Дискретизация

165

245

325

405

485

A/10

mo

mo

АУ40

Рис 3 7 Зависимости минимального времени решения СЛАУ для различных способов предфильтрации от частоты (а) и от дискретизации (б)

В табл 3 7 приведены тор1 для разных частот Аналогичные результаты при разной дискретизации для 125 МГц приведены в табл 3 8 Видно, что при изменении частоты для способов предфильтрации (1 5), (1 6) и (2 1) Tt,pt остается одним и тем же, чего нельзя сказать о других способах предфильтрации Способы (1 4) и (2 2) показали стабильность для частот более 165 МГц При изменении дискретизации только способ (1 5) показал стабильность topi Для способа (2 1), как и ранее для трапециевидной зубчатой антенны, шаг изменения дискретизации соответствует шагу изменения t„pi

Таблица 3 7 тор| для предфильтрации Таблица 3 8 т„р[ для предфильтрации

при изменении частоты при изменении дискретизации

165 245 325 405 485

(14) 5 10 1 10Г1 ю-1 10 1 1(Г'

0 5) 5 Ю-1 5 10"4 5 10"4 5 10" 5 10"4

(16) 5 10'1 5 10"' 5 го~' 5 10"1 5 КГ1

(17) 5 КГ4 10' 5 10"4 10"' 5 Ю-4

(2 1) 5 10^ 5 Ю-4 5 10"4 5 10^ 5 10"4

(2 2) ю-4 5 Ю-4 5 10^ 5 Ю-4 5 Ю-4

(2 3) ю-' ю-' 5 10"4 5 КГ4 5 10-4

(2 4) ю-' 10~3 Ю"1 10"' 5 10"4

Л/10 Х/20 Х./30 V40

(14) 5 Ю-1 ю- ю-1 5 10"2

(1 5) 10"4 ю-4 ю-4 Ю""4

(16) 5 10~2 5 Ю-2 10- 5 10"2

(17) 5 10"4 ю-4 10"4 5 КГ'

(2 1) 5 10"4 КГ1 5 10"' 10 s

(2 2) 5 Ю"6 W" 104' 5 10 7

(2 3) 5 КГ4 10"4 10"4 5 10"'

(2 4) 5 10"4 кг1 10"* 5 10_s

Таким образом, предложенный способ алгебраической предфильтрации, основанный на евклидовых нормах строк матрицы, показал на рассмотренных конфигурациях антенн стабильность оптимального значения допуска обнуления по критерию минимизации времени решения СЛАУ при изменении частоты и его контролируемую зависимость от изменения дискретизации В конце гл 3 предложены рекомендации по использованию итерационных методов, основанные на анализе обзора публикаций и практического опыта автора

ЗАКЛЮЧЕНИЕ

Основные результаты работы заключаются в следующем

1 Разработаны и программно реализованы два новых способа алгебраической предфильтрации Первый, основанный на евклидовых нормах строк, показал (при решении задачи определения токов в проводной антенне) стабильность при изменении частоты и контролируемую зависимость при изменении дискретизации оптимального значения (по критерию минимизации времени) допуска обнуления Его использование позволит минимизировать затраты времени, например, при многовариантном анализе в большом числе частотных точек или при оптимизации по частоте, широко применяемым на практике

2 Показано, что при использовании предложенного способа предфильтрации существует оптимальное значение допуска обнуления по критерию минимизации времени решения СЛАУ На исследованных примерах выбор оптимального значения допуска обнуления, при использовании данного способа, ускорил решение по сравнению с методом Гаусса до 20 раз

3 Предложено усовершенствование (за счет поиска максимального элемента не по всей матрице, а только на главной диагонали) известного способа предфильтрации, позволившее сократить время решения СЛАУ на 13%

4 Разработанный комплекс программ для решения СЛАУ при анализе электромагнитного излучения проводных структур, встроенный в систему компьютерного моделирования электромагнитной совместимости TALGAT, позволяет решать СЛАУ, используя 8 прямых и 6 итерационных методов, 6 способов пре-добусловливания и 10 способов предфильтрации (включая предложенные автором новые и усовершенствованные) Таким образом, возможности комплекса позволяют использовать его для других задач, требующих решения СЛАУ с плотной матрицей, а также в учебном процессе, как средство изучения численных методов Реализована возможность использования методов решения СЛАУ с помощью DHTML диалогов Реализована визуализация матриц, как после предфильтрации, так и после формирования матрицы предобусловливания

5 Выполненное сравнение способов алгебраической предфильтрации при решении СЛАУ итерационными методами позволяет оценить изменение оптимального значения порога/допуска обнуления для каждого из способов, на примере определения токов в проводной антенне, как при изменении частоты, так и при изменении дискретизации Показано, что можно добиться ускорения во времени решения СЛАУ на 40% за счет выбора способа предфильтрации

6 Приведены рекомендации по использованию итерационных методов

Реализованный модуль использовался для оценки паразитных электромагнитных эффектов в печатных платах и в кабелях аппаратуры, разрабатываемой в НПЦ «Полюс», и при выполнении проекта РФФИ Кроме того, все результаты работы активно используются в учебном процессе ТУСУР (две авторские лекции, лабораторная работа, учебно—методическое пособие и монография)

Совокупность этих выводов позволяет считать, что цель диссертационной работы достигнута

ПУБЛИКАЦИИ ПО МАТЕРИАЛАМ ДИССЕРТАЦИИ

1 Куксенко С П Исследование решения системы линейных алгебраических уравнений итерационным методом BiCGstab // Сборник научных трудов всероссийской научно-технической конференции "Научная сессия ТУСУР", г Томск, 2004, часть 1 С 110-113

2 Куксенко С П Повышение эффективности решения системы линейных алгебраических уравнений // Сборник научных трудов международной молодежной научной конференции, Казань, 2004 Т 3 С 160-161

3 Куксенко С П , Газизов Т Р Оптимизация параметров стабилизированного метода бисопряженных градиентов при решении задач вычислительной электродинамики // Материалы Шестой Всероссийской научно-практической конференции "Проблемы информационной безопасности государства, общества и личности", г Томск, 2-4 июня 2004 г С 113-115

4 Газизов Т Р, Куксенко С П Оптимизация допуска обнуления при решении СЛАУ итерационными методами с предобусловливанием в задачах вычислительной электродинамики // Электромагнитные волны и электронные системы №8, 2004 С 26-28

5 Костарев И С, Куксенко С П Увеличение скорости решения системы линейных алгебраических уравнений с помощью быстрого преобразования Фурье // Сборник научных трудов всероссийской научно-технической конференции "Научная сессия ТУСУР", г Томск, 2005, часть 1 С 112-114

6 Куксенко С П , Газизов Т Р Ускорение решения СЛАУ в задачах вычислительной электродинамики И Материалы Седьмой Всероссийской научно-практической конференции "Проблемы информационной безопасности государства, общества и личности", г Томск, 16-18 февраля 2005 г С 54—57

7 Газизов Т Р , Мелкозеров А О , Газизов Т Т , Куксенко С П , Заболоцкий А М Комплексная оптимизация генетическими алгоритмами для обеспечения ЭМС // Сб науч докл VI Межд Симп по электромагнитной совместимости и электромагнитной экологии, г Санкт-Петербург, 21—24 июня 2005 г С 160— 164

8 Куксенко С П, Газизов Т Р Методы решения СЛАУ в задачах вычислительной электродинамики // Вестник Томского государственного педагогического университета Серия Естественные и точные науки Спецвыпуск, №7,2005 С 144-149

9 Костарев И С , Куксенко С П , Газизов Т Р Повышение эффективности решения системы линейных алгебраических уравнений итерационными методами // Вестник Томского государственного педагогического университета Серия Естественные и точные науки Спецвыпуск, №7, 2005 С 150-155

10 Газизов Т Р , Мелкозеров А О , Газизов Т Т , Куксенко С П , Заболоцкий А М Компьютерное моделирование сложных структур проводников при проектировании телевизионно вычислительных систем // Известия вузов Приборостроение №11,2005 Т 48 С 64-67

11 Куксенко С П Использование метода В1СС81аЬ для решения нескольких СЛАУ с одинаковой плотной несимметричной матрицей в задачах вычислительной электродинамики // Сборник научных трудов третьей международной научно-практической конференции «Электронные средства и системы управления» посвященной 60-летию Победы в Великой Отечественной Войне и 110-летию изобретения радио, г Томск, 2005 42 С 128-132

12 Костарев И С , Куксенко С П Увеличение скорости решения системы линейных алгебраических уравнений итерационными методами // Сборник научных трудов третьей международной научно-практической конференции «Электронные средства и системы управления» посвященной 60-летию Победы в Великой Отечественной Войне и 110—летию изобретения радио, г Томск, 2005, Ч 1 С 110-113

13 Куксенко С П , Газизов ТР Сравнение способов предфильтрации при решении СЛАУ с плотной матрицей итерационными методами с предобусловливанием // Инфокоммуникационные технологии, №2, 2007, Т 5 С 61-65

14 Куксенко С П , Газизов ТР Совершенствование способов предфильтрации для решения СЛАУ с плотной матрицей итерационными методами с предобусловливанием в задачах вычислительной электродинамики // Электромагнитные волны и электронные системы №9,2007 С 12—17

15 Куксенко СП Новый способ предфильтрации при решении СЛАУ с плотными матрицами итерационными методами с предобусловливанием // Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых "Научная сессия ТУ СУР", посвященная 45—летию ТУ СУ Ра, г Томск, 3-7 мая 2007 Ч 1 С 341-344

16 Куксенко С П , Сивцев С Т Зависимость оптимального допуска обнуления от дискретизации антенны // Всероссийская научно—техническая конфе-

ренция студентов, аспирантов и молодых ученых "Научная сессия ТУСУР", посвященная 45-летию ТУСУРа, г Томск, 3-7 мая 2007 Ч 1 С 345-347

17 Свидетельство об отраслевой регистрации разработки №8376 от 24 05 2007 г <Система компьютерного моделирования сложных структур проводников и диэлектриков TALGAT> (Газизов Т Р, Мелкозеров А О, Гази-зов Т Т , Куксенко С П, Заболоцкий А М , Костарев И С ), зарегистрированной в Отраслевом фонде алгоритмов и программ Госкоорцентра Минобрнауки РФ с присвоением номера государственной регистрации - per номер ВНТИЦ 50200701103

18 Газизов Т Р , Заболоцкий А М , Мелкозеров А О , Газизов Т Т , Куксенко С П , Горин Е П , Бевзенко И Г Возможности применения новых модальных явлений в целях электромагнитного терроризма и для защиты от него // Труды VII Межд Симп по электромагнитной совместимости и электромагнитной экологии, г Санкт-Петербург, 26-29 июня 2007 г С 266-269

19 Куксенко С П , Газизов Т Р Итерационные методы решения системы линейных алгебраических уравнений с плотной матрицей — Томск Томский государственный университет, 2007 208 с

ь

Тираж 100 экз. Заказ 1291. Томский государственный университет систем управления и радиоэлектроники 634050, г. Томск, пр. Ленина, 40

ВВЕДЕНИЕ.

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. Достаточно важной задачей является анализ излучения проводных структур, поскольку он необходим при моделировании проводных антенн, аппроксимации излучающей поверхности проводной сеткой, создании различных симуляторов электромагнитного поля и др. Таким образом, вычислительные трудности решения таких СЛАУ во многом обусловлены заполненностью матриц, приводящей к огромному объему вычислений (особенно в трехмерных задачах).

Для решения СЛАУ с плотными матрицами традиционно используются точные методы, например, метод исключения Гаусса. Но их вычислительные затраты, пропорциональные N3, существенно ограничивают круг решаемых задач даже на высокоскоростных компьютерах. Необходимость решения сложных задач, дающих рост N, привела к широкому применению итерационных методов. Наиболее эффективными и устойчивыми (с точки зрения сходимости к точному решению) среди итерационных методов являются, так называемые, методы крыловского типа. В связи с тем, что матрица СЛАУ, полученная применением метода моментов, является, как правило, плохо обусловленной, использование итерационного метода без предобусловливания не вполне обоснованно, поскольку метод может застопориться или даже оборваться. Использование предфильтрации (игнорирования незначительных элементов) позволяет задать структуру разреженности матрицы СЛАУ, что, в свою очередь, позволяет применить алгоритмы технологии разреженных матриц (предобусловливание) и тем самым уменьшить время решения.

Между тем, ряд возможностей совершенствования решения СЛАУ с плотной матрицей итерационными методами при исследовании проводных структур остаётся неиспользованным. Так, недостаточно разработаны способы выбора структуры разреженности с помощью предфильтрации матрицы СЛАУ, позволяющие добиться ускорения решения за счет более эффективного использования предобусловливания. Следует отметить, что исследователи, решающие СЛАУ с плотными матрицами, как правило, приводят результаты при фиксированных параметрах предфильтрации (в частности, допуске обнуления), без оценки их влияния на общие временные затраты. Кроме того, недостаточно представлено сравнение этих способов между собой, что затрудняет корректный выбор способа предфильтрации и его параметров на практике.

Свободно распространяемое программное обеспечение, позволяющее решать СЛАУ с плотными матрицами эффективными итерационными методами без дополнительной модификации, практически отсутствует. Так, известный и постоянно развиваемый пакет LAPACK (последняя версия 3.1.1 вышла 26.02.2007) использует только прямые методы. В системе SciLab, являющейся бесплатным аналогом MatLab, содержатся встроенные средства работы с разреженными матрицами, в т.ч. возможности LU-разложения. В состав последних версий включены и итерационные методы крыловского типа для решения разреженных СЛАУ. Подобная ситуация наблюдается и в MatLab. Специализированное программное обеспечение для электромагнитного моделирования, как правило, использует только прямые методы решения СЛАУ. Так, один из лучших зарубежных программных продуктов FEKO использует метод исключения Гаусса. В других не всегда уточняется, каким методом получено решение. Поэтому, характерной чертой такого обеспечения является то, что даже высококвалифицированный пользователь не может добиться изменения некоторых параметров численного метода. В результате эффективность исследований с помощью такой системы часто оставляет желать лучшего, а отсутствие у пользователя возможности ее модернизации делает это обеспечение весьма неэффективным. Еще одним недостатком такого обеспечения является его высокая стоимость.

Цель работы - разработка алгоритмов и комплекса программ для решения систем линейных алгебраических уравнений, возникающих в задачах анализа электромагнитного излучения проводных структур.

Для достижения поставленной цели необходимо решить следующие задачи:

1. Разработать новые алгоритмы предфильтрации.

2. Усовершенствовать известные способы предфильтрации.

3. Разработать комплекс программ, реализующий новые и известные алгоритмы предфильтрации, методы решения СЛАУ и способы предобусловливания.

4. Апробировать основные способы алгебраической предфильтрации на задаче анализа излучения проводных структур.

5. Произвести сравнение результатов, полученных при использовании разных способов предфильтрации на нескольких конфигурациях.

В работе использовались: теория матриц, прямые и итерационные методы решения СЛАУ, объектно-ориентированное программирование.

Достоверность результатов подтверждается проверкой корректности программной реализации на примере нахождения заведомо известного решения, совпадением результатов, полученных несколькими методами.

Научная новизна

1. Разработаны два новых способа алгебраической предфильтрации.

2. Предложено усовершенствование известных способов алгебраической предфильтрации.

3. Показано, что при использовании предложенных способов предфильтрации существует оптимальное значение допуска обнуления по критерию минимизации времени решения СЛАУ.

4. Выявлена стабильность (при изменении частоты) и установлена контролируемая зависимость (от изменения дискретизации) оптимального значения допуска обнуления (по критерию минимизации времени решения СЛАУ) при использовании предложенного способа предфильтрации на примере, определения токов в проводной антенне.

Практическая значимость

1. Программно реализован модуль матричных операций единой системы компьютерного моделирования электромагнитной совместимости, позволяющий использовать широкий ряд прямых и итерационных методов решения СЛАУ как в виде функций, так и в виде DHTML диалогов. Возможности модуля позволяют его использовать для решения других задач, требующих решения СЛАУ с плотной матрицей.

2. Выполнено сравнение способов алгебраической предфильтрации при решении СЛАУ итерационными методами, позволяющее оценить изменение оптимального значения порога/допуска обнуления для каждого из способов, на примере определения токов в проводной антенне, как при изменении частоты, так и при изменении дискретизации.

3. Приведены рекомендации по использованию итерационных методов.

4. Результаты работы активно используются в учебном процессе.

Апробация результатов

Результаты диссертационной работы представлялись и докладывались в материалах следующих симпозиумов и конференций:

Всероссийская научно-техническая конференция студентов и молодых ученых "Научная сессия ТУСУР", г. Томск, 2004;

XII Туполевские чтения: Международная молодежная научная конференция, г. Казань, 2004;

Всероссийская научно-практическая конференция "Проблемы информационной безопасности общества и личности", г. Томск, 2004, 2005;

Международная научно-практическая конференция "Электронные средства и системы управления", г. Томск, 2005;

Международный симпозиум по ЭМС и электромагнитной экологии, г. Санкт-Петербург, 2005, 2007;

Всероссийская научно-техническая конференция студентов, аспирантов и молодых ученых "Научная сессия ТУСУР", посвященная 45-летию ТУСУРа, г. Томск, 2007.

Публикации. По результатам исследований, представленных в диссертации, опубликовано 19 научных работ: 6 статей в журналах из перечня ВАК; 10 докладов и 1 тезисы в материалах симпозиумов и конференций; 1 свидетельство об отраслевой регистрации разработки; 1 монография.

Структура и объём диссертации. В состав диссертации входят введение, 3 главы, заключение, список литературы из 109 наим., 3 приложения с актами внедрения. Объём диссертации составляет 103 стр., в том числе 24 рис. и 23 табл.

Личный вклад. Все результаты работы получены автором лично или при непосредственном его участии совместно со следующими сотрудниками:

Исследование итерационных методов выполнено совместно с Газизовым Талъгатом Рашитовичем, Костаревым Игорем Степановичем и Сивцевым Семеном Степановичем.

Программная реализация системы компьютерного моделирования электромагнитной совместимости выполнена совместно с Газизовым Талъгатом Рашитовичем, Мелкозеровым Александром Олеговичем, Газизовым Тимуром Талъгатовичем и Заболоцким Александром Михайловичем.

Внедрение результатов работы

1. Реализованный комплекс программ использовался для оценки паразитных электромагнитных эффектов в печатных платах и в кабелях аппаратуры, разрабатываемой в НПЦ «Полюс» (ПРИЛОЖЕНИЕ 1).

2. Разработанный комплекс программ использован для выполнения проекта «Разработка системы компьютерного моделирования электромагнитной совместимости». (Заключительный отчет ВТК-15 по мероприятию 3.1.3а инновационной программы ТУ СУР, 2006 г. и свидетельство об отраслевой регистрации разработки № 8376) (ПРИЛОЖЕНИЕ 2).

3. Результаты использованы в учебном процессе ТУСУРа (одна лабораторная работа, две авторские лекции, учебно-методическое пособие, монография) (ПРИЛОЖЕНИЕ 3).

4. Реализованные итерационные методы использованы при выполнении проекта 06-08-01242 «Исследование новых модальных явлений в структурах многопроводных линий передачи с неоднородным диэлектрическим заполнением», поддержанного Российским фондом фундаментальных исследований.

Положения, выносимые на защиту

1. Для решения СЛАУ итерационными методами с предобусловливанием предложен новый способ предфильтрации, показавший стабильность оптимального (по критерию минимизации времени решения СЛАУ) значения допуска обнуления при изменении частоты и его контролируемую зависимость от изменения дискретизации при решении задачи определения токов в проводной антенне.

2. За счет выбора способа предфильтрации и оптимального значения порога/допуска обнуления можно сократить время решения СЛАУ итерационными методами с предобусловливанием на 40%.

3. При решении СЛАУ итерационными методами с предобусловливанием в сочетании с предфильтрацией, поиск максимального элемента не по всей матрице, а только на главной диагонали, позволяет уменьшить время решения на 13%.

4. Выбором оптимального значения допуска обнуления предфильтрации, при решении СЛАУ итерационными методами с предобусловливанием, можно ускорить решение по сравнению с методом Гаусса до 20 раз.

Краткое содержание работы. В гл. 1 выполнен обзор проблемы решения СЛАУ с плотной матрицей, а также сформулированы конкретные вопросы, подлежащие исследованию для решения этой проблемы. В гл. 2 приведены новые способы, совершенствования известных способов алгебраической предфильтрации, а также представлены результаты реализации созданного комплекса программ. В гл. 3 выявлены новые закономерности решения СЛАУ при использовании новых способов предфильтрации и приведено сравнение способов предфильтрации между собой. Приведены рекомендации по использованию итерационных методов. В заключении сделаны выводы по работе. Далее приведён список литературы. В приложениях представлены копии документов, подтверждающих использование результатов работы.

1. РЕШЕНИЕ

СИСТЕМЫ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ:

ОБЗОР

Основные результаты работы заключаются в следующем:

1. Разработаны и программно реализованы два новых способа алгебраической предфильтрации. Первый, основанный на евклидовых нормах строк, показал (при решении задачи определения токов в проводной антенне) стабильность при изменении частоты и контролируемую зависимость при изменении дискретизации оптимального значения (по критерию минимизации времени) допуска обнуления. Его использование позволит минимизировать затраты времени, например, при многовариантном анализе в большом числе частотных точек или при оптимизации по частоте, широко применяемым на практике.

2. Показано, что при использовании предложенного способа предфильтрации существует оптимальное значение допуска обнуления по критерию минимизации времени решения СЛАУ. На исследованных примерах выбор оптимального значения допуска обнуления, при использовании данного способа, ускорил решение по сравнению с методом Гаусса до 20 раз.

3. Предложено усовершенствование (за счет поиска максимального элемента не по всей матрице, а только на главной диагонали) известного способа предфильтрации, позволившее сократить время решения СЛАУ на 13%.

4. Разработанный комплекс программ для решения СЛАУ при анализе электромагнитного излучения проводных структур, встроенный в систему компьютерного моделирования электромагнитной совместимости TALGAT, позволяет решать СЛАУ, используя 8 прямых и 6 итерационных методов, 6 способов предобусловливания и 10 способов предфильтрации (включая предложенные автором новые и усовершенствованные). Таким образом,[jj, возможности комплекса позволяют использовать его для других задач, требующих решения СЛАУ с плотной матрицей, а также в учебном процессе, как средство изучения численных методов. Реализована возможность использования методов решения СЛАУ с помощью DHTML диалогов. Реализована визуализация матриц, как после предфильтрации, так и после формирования матрицы предобусловливания.

5. Выполненное сравнение способов алгебраической предфильтрации при решении СЛАУ итерационными методами позволяет оценить изменение оптимального значения порога/допуска обнуления для каждого из способов, на примере определения токов в проводной антенне, как при изменении частоты, так и при изменении дискретизации. Показано, что можно добиться ускорения во времени решения СЛАУ на 40% за счет выбора способа предфильтрации.

6. Приведены рекомендации по использованию итерационных методов.

Реализованный модуль использовался для оценки паразитных электромагнитных эффектов в печатных платах и в кабелях аппаратуры, разрабатываемой в НПЦ «Полюс», и при выполнении проекта РФФИ. Кроме того, все результаты работы активно используются в учебном процессе ТУСУР две авторские лекции, лабораторная работа, учебно-методическое пособие и монография).

Совокупность этих выводов позволяет считать, что цель диссертационной работы достигнута.

ЗАКЛЮЧЕНИЕ

1. Ильин В.П. Линейная алгебра: от Гаусса до суперкомпьютеров будущего. Природа. No 6,1999, С. 11-18.

2. Фадеев Д.К., Фадеева В.Н. Вычислительные методы линейной алгебры. М.: ФМ, 1963, 656 С.

3. Вержбицкий В.М. Основы численных методов. М.: Высшая школа, 2002.

4. Крицкий О.Л. Анализ итерационных методов решения многомерных анизотропных краевых задач. Конференция молодых ученых, посвященная 10-летию ИВТ СО РАН, г. Новосибирск, 25-26 декабря, 2000.

5. Пирумов У.Г. Численные методы. М.: Дрофа, 2003.

6. ШашкинК.Г. Использование эффективных алгоритмов больших систем линейных алгебраических уравнений в задачах геотехники. Интернет-журнал. Реконструкция городов и геотехническое строительство. No.3,2000.

7. Barrett R., Berry M., Chan T.F., Demmel J., Donato J., Dongarra J,, Eijkhout V., Pozo R., Romine C., and van der Vorst H. Templates for the solution of linear systems: building block for iterative methods. SIAM, Philadelphia, 1994, P. 124.

8. Axellson O. Iterative Solution Methods. Cambridge University Press, New York, 1994, P. 166.

9. Saad Y. Iterative methods for sparse linear systems. Second edition. January 3rd, 2000, P. 447.

10. Van der Vorst H. Iterative Krylov methoda for large linear system. Cambridge University Press, New York, 2003, P. 221.

11. Ильин В.П. Методы неполной факторизации для решения линейных систем. М.: Физмат, 1995.

12. Харрингтон Р.Ф. Применение матричных методов к задачам теории поля, Труды ИИЭР, №2,1967. С. 5-19.

13. CuiT.J., ChewW.C. Accurate model of arbitrary wire antennas in free space, above or inside groud. IEEE Trans, on Antennas and Propag., vol.48, no.4, April 2000, P.482-493.

14. Пименов A.C. Вейвлет-анализ в численном моделировании тонкопроволочных антенн. Вестник СамГУ, №2, 2006. С. 44-61.

15. Tesche F.M., Ianoz M.V., Karlsson Т. EMC analysis methods and computational models. A Wiley-Interscience publication, 1992. 623 p.

16. Газизов T.P. Уменьшение искажений электрических сигналов в межсоединениях и преднамеренных электромагнитных помех. Диссертация на соискание ученой степенидоктора технических наук, г. Томск, 2005.

17. Harrington R.F. Origin and Development of the Method of Moments for Field Computation, IEEE Antennas and Propagation Society Magazine, pp.31-36, June 1990.

18. Канторович JI.B., Крылов B.M. Приближенные методы высшего анализа.-М.-Л.: Физматгиз, 1962.

19. Канторович Л.В., Акилов Г.П. Функциональный анализ в нормированных пространствах.-М.: Физматгиз, 1959.

20. Harrington R.F. Field Computation by Moment Methods, New York, The MacMillian Co., 1968; reprinted by Krieger Publishing Co., Malabar, Fl., 1982.

21. Antonini G., Orlandi A., and Ruehli A.E. Analytical integration of quasi-static potential integrals on nonorthogonal coplanar quadrilaterals for the PEEC method, IEEE Trans. Electromagn. Compat., vol.44, no.2, May 2002, pp.399-403.

22. SarkarT.K. at al. Survey of numerical methods for solution of large systems of linear equations for electromagnetic field problems, IEEE Trans. Antennas Propagat., vol.29, pp.847-856., Nov. 1981.

23. OlyslagerF. at all. Numerical and experimental study of the shielding effectiveness of a metallic enclosure. IEEE Trans, on Electromagn. Compat., vol.41, no.3, August 1999. P.202-213.

24. Carpes W.P., Pichon L. and Razek A. Analysis of the coupling of an incident wave with a wire inside a cavity using an FEM in frequency and time domains. IEEE Trans, on Electromagn. Compat. vol.44, no.3, August 2002. P. 470-475.

25. Correira L.M. A comparison of integral equation with unique solution in the resonance region for scattering by conducting bodies. IEEE Trans, on Antennas and Propagat., vol.41, no. 1, Jan. 1993, P.52-58.

26. Ji Y., Hubing Т.Н. On the interior resonance problem when applying a hybrid FEM/MoM approach to model printed circuit boards. IEEE Trans, on Electromagn. Compat. vol. 44, no. 2, May 2002, P.318-323.

27. ShengX.-Q. at all. On the formulation of hybrid finite-element and boundary-integral methods for 3-D scattering. IEEE Trans, on Antennas and Propagat., vol.46, no. 3, March 1998, P.303-311.

28. Carpes W.P., Pichon L. and Razek A. Analysis of the coupling of an incident wave with a wire inside a cavity using an FEM in frequency and time domains. IEEE Trans, on Electromagn. Compat. vol.44, no.3, August 2002. P. 470-475.

29. Nayanthara K., Rao S., and Sarkar T. Analysis of two-dimensional conducting and dielectric bodies utilizing the conjugate gradient method. IEEE Trans, on Antennas and Propag., vol.35, no.4, April 1987, P.451^153.

30. Singer H. The method of moments (MOM) and related codes. Supplement to Proc. of the 13th Int. Zurich Symp. on EMC. Zurich, Switzerland, February 16-18,1999, pp. 11-19.

31. Chew W.C., Jin J.-M., Lu C-C., Michielssen E., Song J.M. Fast solution methods in electromagnetics. IEEE Trans, on Antennas and Propag. Vol. 45, No. 3, March 1997. P. 533-543.

32. Форсайт Дж., МоулерК. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969.

33. Голуб Дж., Лоун Ч.В. Матричные вычисления. М: Мир, 1999.

34. Saad Y., van der Vorst H. Iterative solution of linear systems in the 20-th century. Journal of Computational and Applied Mathematics, Vol. 123, No 1,1 November 2000, pp. 1-33.

35. Колотилина Л.Ю. Явно предобусловленные системы линейных алгебраических уравнений с плотной матрицей. Советская математика, №43, 1988, с. 2566-2573.

36. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. -М.: Мир, 1991.

37. Benzi M. Preconditioning techniques for large linear systems: a survey. Journal of computation physics, No 182, pp. 418-447, 2002.

38. Chen K. Matirx preconditioning techniques and applications. Cambridge University Press, New York, 2005, P.576.

39. Saad Y. ILUT: a dual threshold incomplete LU factorization, Numer. Linear Algebra Appl. 1(4), 1994, pp. 387-402.

40. SaadY., Zhang J. BILUTM: a domain-based multilevel block ILUT preconditioner for general sparse matrices. SIAM J. Matrix Anal. Appl. Vol. 21, No. 1, pp. 279-299,1999.

41. Li N., Saad Y., Chow E. Crout Versions of ILU for General Sparse Matrices, SIAM Journal on Scientific Computing, Vol. 25, N. 2, 2003, pp. 716-728.

42. Lee J., Zhang J., Lu C. Incomplete LU preconditioning for large scale dense complex linear systems from electromagnetic wave scattering problems. In: J. of Comput. Phys., 185, 2003, pp. 158-175.

43. BangtssonE., NeytchevaM. Approaches to reduce the computational cost when solving linear systems of equations arising in Boundary Element Method discretizations. Uppsala University, Department of Information Technology, TR/2003-053.

44. Antonini G., Orlandi A., Ruehli A. Fast iterative solution for the wavelet-PEEC method, in Proc. of 14th International Zurich Symposium on EMC, Zurich, Switzerland, February 2022,2001.

45. Rahola J., Tissari S. Iterative solution of dense linear systems arising from the electrostatic integral equation in MEG. Physics in medicine and biology, No.47,, 2002, pp. 961-975.

46. Zunoubi M.R. A combined BI-CGSTAB(Z) and wavelet transform method for EM problems using method of moments. Progress in electromagnetics research, PIER 52, 2005, pp. 205224.

47. Carpentieri В., Duff I.S., Giraud L. Some sparse pattern selection strategies for robust Flobenius norm minimization preconditioners in electromagnetism. RAL-TR-2000-009.

48. Benzi M., Tuma M. Numerical experiments with two approximate inverse preconditioners. CERFACS TR/PA/97/11.

49. Benzi M., Tuma M. A comparative study of sparse approximate inverse preconditioners. Los Alamos national laboratory technical report LA-UR-98-0024.

50. Chow E., Saad Y. Approximate inverse preconditioners via sparse-sparse iterations. SIAM J. on Scientific Computing, 1998, Vol. 19, Issue 3, pp. 995-1023.

51. Grote M., Huckle T. Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput., No 18,1997, pp. 838-853.

52. Kolotilina L.Yu.,. Yeremin A.Yu. Factorized sparse approximate inverse preconditioning I. Theory, SIAM J. Matrix Anal. Appl. Nol4,1993, pp. 45-58.

53. EweW.-B., LiL.-W., Wu Q., LeongM.-S. Preconditioners for adaptive integral method implementation. IEEE Transactions on Antennas and Propagation, Vol. 53, No. 7, July 2005, pp.2346-2350.

54. Poirier J.R, Boderies P., Mittra R., Varadarajan V. Numerically efficient solution of dense linear system of equations arising in a class electromagnetic scattering problems. Trans. On Antennas and propagation, Vol. 46, No. 8,1998, pp. 1169-1175.

55. Alleon G„ Benzi M., Giraud L. Sparse Approximate Inverse Preconditioning for dense Linear Systems Arising in Computation of Electromagnetics. Numerical algorithm, No. 16, 1997, pp. 1-15

56. Писсанецки С. Технология разреженных матриц. М. Мир, 1988.

57. Carpentieri В., Duff I.S., Giraud L., Magolu M. Made. Sparse symmetric preconditioners for dense linear systems in electromagnetism. CERFACS TR/PA/01/35.

58. Bruno Carpentieri. Sparse preconditioners for dense linear systems from electromagnetic applications. CERFACS TH/PA/02/48

59. Alpet В., Beylkin G., Coifman R., Rokhlin V. Wavelet-like bases for the fast solution of second-kind integral equation. SIAM, Sci. Comput., Vol. 14, No. 1,1993, pp. 159-184.

60. FranzaO., Wagner R., ChewW.C. Wavelet-like bases for solvingscattering integral equation. IEEE, 1994.

61. Wagner R.L., Chew W.C. A stydy of wavelets for the solution of electromagnetic integral equations. IEEE Transactions on Antennas and Propagation, Vol. 43, No. 8, August 1995, pp.802-810.

62. Prakash V.V.S., Mittra R. An efficient preconditioner for iterative solvers. Turk J. Elec. Engin., Vol. 10, №2 2002, pp. 371-375.

63. Chen K. Discrete wavelet transforms accelerated sparse preconditioners for dense boundary element systems. Electronic transactions on numerical analysis. Vol. 8,1999, pp. 138-153.

64. Ford l.M. An improved DWT-based preconditioner for dense matrix problem. Manchester centre for computational mathematics numerical analysis reports. Numerical analysis report No. 412, 2002.

65. Sertel K., Volakis J.L. "Incomplete LU preconditioner for FMM implementations," 2000 Applied Computational Electromagnetics Society, Monterey, CA, pp. 859-866.

66. Saad Y., Schultz M.H. GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Scientific and Statistical Computing, No. 7,1986, pp. 856-869.

67. Fletcher R. Conjugate gradient methods for indefinite systems. In G.A. Watson, editor, Proceedings of Dundee Biennal Conference on Numerical Analysis, 1974, pp. 73-89.

68. Van der VorstH. Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for solution of nonsymmetric linear systems. SIAM J. Scientific and Statistical Computing, No. 13,1992, pp. 631-644.

69. Freund R.W., Nachtigal N.M. QMR: a quasi-minimal residual method for non-hermitian linear system. Num.Math., 60,1991, pp. 315-339.

70. Sonneveld P. CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 10,1989, pp. 36-52.

71. Hestenes M.R., Steifel E. Methods of conjugate gradient for solving linear systems, J. of Res. Nat. Bureau Standards, No. 49, 1952, pp. 409-436.

72. Ewen T.L. Mixed product Krylov subspace methods for solving linear systems. MASTER of Science, 1999, P. 98.

73. Норенков И.П. Автоматизированное проектирование. М.: 2000.86. www.feko.co.za.87 www.emss.co.za. '88. www.poynting.co.za.

74. Каплун А.Б., Морозов Е.М., Олферьева М.А. ANSYS в руках инженера: Практическое руководство. Изд. 2-е, испр. М.: Едиториал УРСС, 2004. С. 272.

75. ШимковичД.Г. Расчет конструкций в MSC/NASTRAN for Windows. М.: ДМК Пресс, 2001. С. 448.91. http://www.mscsoftware.com/products/.

76. Алямовский А.А. SolidWorks/COSMOSWorks. Инженерный анализ методом конечных элементов. М.: ДМК Пресс, 2004. С. 432.93. http://www.soIidworks.com/

77. Газизов Т.Р., Куксенко С.П. Оптимизация допуска обнуления при решении СЛАУ итерационными методами с предобусловливанием в задачах вычислительной электродинамики. Электромагнитные волны и электронные системы. №8, 2004. С. 2628.

78. Kominami М., Rokushima К. On the integral equation of piecewise linear antennas, IEEE Trans. Antennas Propagat., vol. 29, pp. 787-792, September 1981.

79. Рыбин А.П., Лощилов А.Г., Малютин Н.Д. Моделирование и экспериментальное исследование широкополосных антенн в ДКМВ диапазоне. Сборник научных трудов всероссийской научно-технической конференции «Научная сессия ТУСУР -2004», 2004, С. 122-125.

80. Куксенко С.П. Исследование решения системы линейных алгебраических уравнений итерационным методом BiCGstab. Сборник научных трудов всероссийской научно-технической конференции "Научная сессия ТУСУР", г. Томск, 2004, ч. 1, С. 110-113.

81. Куксенко С.П. Повышение эффективности решения системы линейных алгебраических уравнений. Сборник научных трудов международная молодежная научная конференция, Казань, 2004, Т. 3, С. 160-161.

82. Куксенко С.П., Газизов Т.Р. Сравнение способов предфильтрации при решении СЛАУ с плотной матрицей итерационными методами с предобусловливанием. Инфокоммуникационные технологии, 2007, Том 5, No. 2. С. 14-18

83. Duffl.S., GiraudL., LangouJ., Martin E. Using spectral low preconditioned for large electromagnetic calculations. CERFACS TR/PA/03/95.

84. Еремин А.Ю., Никишин A.A. Переобусловливание линейных систем с несимметричными матрицами с помощью факторизованных разреженных приближенных обратных. Записки научных семинаров ПОМИ. Т.284, 2002, С. 18-35.