Построение алгоритмов дискретизации областей для двумерных и трехмерных задачах электрофизики тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

т 51ч

9 \ "

1 российская академия наук

сибирское отделение вычислительный центр

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

кузнецов александр юрьевич

удк 519.633

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

Специальность: 01.01.07 - вычислительная математика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск - 1993

Работа выполнена в Вычислительном центре Сибирского отделения Российской академии наук

Научный руководитель: .доктор физико-математических наук, . профессор Ильин В.П.

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

Василенко В.А.

кандидат физико-математических наук Лисейкин В.Д.

Ведущая организация: Институт Математики и Механики,

УрО РАН, г.Екатеринбург

Зашита состоится■" 3 " 1Э93года в ч. ^О мин,

на заседании Специализированного совета К 002.10.01 по присуждению ученой степени кандидата наук при Вычислительном центре Сибирского отделения Российской АН по адресу:

630090, г.Новосибирск-90, проспект ак.Лаврентьева, 6

С диссертацией можно ознакомиться в читальном зале отделения ГПНТБ (Новосибирск-90, пр. ак. Лаврентьева, 6).

Автореферат разослан " 6 " -«Л».сЦ 1993года

Ученый секретарь \

Специализированного Совета | / л

доктор физико-математических наук / «¿^-^у Ю.И.Кузнецов

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

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

Сложность расчета электростатических полей большинства электрофизических устройств заключается: I) в большой разномасштаб-ности элементов этих конструкций; 2) в наличии большого числа изоляционных материалов с различной диэлектрической проницаемостью; 3) в наличии разнородных граничных условий заданных на сложных границах, 4) в наличии больших градиентов решения, что может привести к большой погрешности полученного численного решения.

Для решения задачи расчета полей с учетом перечисленных осо-беннностей широко применяется метод конечных элементов. Трудоемкость дискретизации области в методе конечных элементов для реальных задач часто превосходит затраты на получение численного решения. Этап дискретизации области является недостаточно изученным и требует разработки новых алгоритмов постро-

ения сеток, отвечающих современным требованиям автоматизации и надежности.

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

Целью диссертационной работы является исследование математических основ построения дискретизаций двумерных областей с учетом неравномерного распределения точек в области на основе разбиений Б.Н.Делоне и задаваемых функций'плотности, построение алгоритмов дискретизации трехмерных областей со сложной геометрией, разработка методов численного контроля корректности произвольных трехмерных сеток, практическая реализация разработанных алгоритмов и проведение численного моделирования двумерных и трехмерных электростатических полей на основе построенных дискретизаций.

Научная новизна изложенных в работе результатов заключается в еле душем:

Разработаны алгоритмы построения триангуляции Делоне с учетом функций плотности точек. ,

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

Предложен алгоритм построения трехмерных сеток на основе локально-модифицированного подхода и поверхностных триангуляций Делоне.

Разработаны, подходы и алгоритмы численного тестирования

трхмерных сеток на основе геометрических, топологических и комбинаторных свойств.

Предложенные подхода и алгоритмы реализованы в разработанных программах: интерактивной системе 5ге11а-2В и ППП РАМЗЕС-З, предназначенных, соответственно, для моделирования двумерных и трехмерных электростатических полей. На основе практического использования выработаны направления дальнейшего развития предложенных алгоритмов.

Практическая ценность. Интерактивная система stella-2D позволяет эффективно проводить расчеты электростатических полей сложных электрофизических конструкций. Автоматический выбор точек сгущения позволяет получать сетки для метода конечных .элемейтов с учетом особенностей решения и геометрии расчетной области. Поэлементные итерационные методы позволяют рассчитывать сложные реальные задачи в ограниченной оперативной памяти. ППП РАМЗЕС-З позволяет строить и тестировать трехмерные сетки . сетки в сложных областях и проводить расчет электростатических полей в трехмерной постановке.

Система Stella-2D и ППП РАМЗЕС-З Енедрены в следующих организациях СНГ: НПО "Исток" г.Москва, ФТЦ ШФ г.Липецк. ВНИИЭФ г.С.-Петербург, СибНИИЭ г.Новосибирск, ИГиЛ г.Новосибирск.

Публикации. Основные результаты, изложенные в диссертации, опубликованы в работах (1-123.

Апробация работы. Основные результаты работы докладывались на семинарах ВЦ СО АН СССР г. Новосибирск, Сибирской Школе

по комплексам программ з г. Томске (1984г.) Шушенском (1986г.), Всесоюзных семинарах по методам построения сеток в г. Свердловске (1987г., 1930) и Челябинске-70 (1992г.), Всесоюзной конференции "Актуальные проблемы вычислительной и прикладной математики" в г.Новосибирске (1987г.), Всесоюзных семинарах "Методы расчета электронно- оптических систем" в г.Ташкенте (1988г.) и Львове (1990г.), Сибирской школе по вычислительной математике (1989г.), Дальневосточной школе по вычислительной математике (1989г.), Всесоюзном семинаре-совещании "Автоматизация проектирования и моделирования электронно- оптических систем" в г.Винница (1991г.), университетах за рубежом: г.Павиа (1990г., Италия, проф. Э.Маженес), г.ТкОинген (1990г., ФРГ, проф. Э.Каспер), Мэриленд (1992г., США, проф. И.Бабушка).

Структура к объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложений. Объем содержательной части диссертации - 148 страниц, списка литературы - 10 страниц, приложений - 22 страниц. Работа включает 27 рисунков, список литературы из 94 наименований.

II. СОДЕРЖАНИЕ РАБОТЫ

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

Для подхода к построению сеток на основе разбиений Б.Н.Делоне

приводится обзор фундаментальных и современных результатов.

Сформулирована задачи исследования и . описана структура диссертационной работы.

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

В §_!.!. дано методическое описание постановки задач 'для построения разбиений Вороного и Делоне, вводятся критерии сравнения триангуляций, на основе критерия оптимальности Лаусона показывается геометрическая оптимальность двумерной триангуляции Делоне, приводятся необходимые определения для п-мерного случая.

В п. 1.1.1 описывается разбиение Вороного на плоскости, для конечного набора р из N дискретных точек как набора ячеек вида

уЦЫхеи2! <3(х,р1)«г(х,р3), з=1,' .... м. Триангуляция Делоне вводится как разбиение, двойственное к разбиению Вороного и приводится результат о эквивалентности данного определения и критерия описанного круга.

В п. 1.1.2 на основе индекса триангуляции еводится критерий сравнения триангуляций, а з п. 1.1.3 с использованием процедуры Лаусона локальной оптимизации углов показано, что только триангуляция Делоне удовлетворяет этому критерию..

В п. 1.1.4 приводятся обще определения п-мерных разбиений Делоне и приводятся классические результаты.

В § 1.2 для двумерных областей строятся алгоритмы генерации множества дискретных точек Ръ в области с учетом контроля

минимального расстояния между ними. Предлагаются 3 подхода к генерации точек равномерно в области: прямоугольная равноугольная и хаотическая структура и для рассматриваемых подходов приводятся оценки максимального расстояния между точками.

В § 1.3 вводится понятие функции плотности точек и предлагаются подхода к генерации точек в области с учетом условия неравномерного.распределения точек на основе функций плотности со значениями в заданных точках. Для получения непрерывных функций плотности го значениям в заданных точках предлагаются три подхода: кусочно-линейное восполнение на основе вспомогательной триангуляции Делоне, радиальное восполнение и восполнение на основе* квадро-деревьев.

В § 1.4 на основе модификации алгоритма Ватсона предложен алгоритм построения двумерной триангуляции Делоне. При этом, в целях повышения эффективности, используются вспомогательные структуры, использованные в п.1.2 для контроля минимального расстояния между точками. Для предложенного алгоритма приводятся апостериорные оценки на основе оценки быстродействия порядка 'ОСЫ*1). В этом случае параметр а определяется

экспериментально для конкретных задач как

log (Т/Т,,)

а = log (N/V • и в результате экспериментов получено значение а<1.2.

В § 1.5 вводится понятие динамических n-мерных триангуляции Делоне как последовательности триаягуляций Делоне

DT± = MtPtt^d)) с различными функциями плотности h±(x) для заданной области. Для таких триангуляций рассматривается задача построения DT± по DTj,_1. Для эффективного решения этой задачи доказывается

теорема об удалении точек из триангуляции Делоне с сохранением условия Делоне:

Теорема. Для произвольной точки q множества Р разбиение DT(P-q) = DT(P) - N(q) + DT(ÎI(q)), построенное по множеству P-q является разбиением Делоне, где N(q) - набор многогранников с вершиной q, и DT(H(q)) - разбиение Делоне многогранника, образованного элементами из N(q).

Вторая глава посвящена построении алгоритмов дискретизации трехмерных областей, описанию алгоритма построения квазирегулярных сеток и описанию построения методов тестирования трехмерных сеток.

В § 2.1 описываются основные требования и подхода к построению алгоритмов дискретизации трехмерных областей и описаны: недостатки разбиений Делоне в трехмерном случае.

В § 2.2 предлагается алгоритм гостроения трехмерных сеток на основе локально-модифицированного подхода и рассматриваются соответствующие геометрические задачи. В п. 2.2.Г вводится определение логический функции области и приведены общие подхода к заданию таких функций. В п. 2.2.2 описан класс рассматриваемых поверхностей, в п". 2.2.3 решается задача сдвига околограничной точки на поверхность второго порядка, а в п. 2.2.4 описано решение задачи локализации точки в области на основе введенных описаний. В п. 2.2.5 введено общее определение сетки в трехмерном пространства и доказана его эквивалентность классическим определениям. В п. 2.2.6- п. 2.2.8 описывается алгоритм построения локально-модифицированных сеток и приводится классификация пересечений ячеек с границей. В п. 2.2.9 вводится понятие триангуляции Делоне на поверхности".

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

В § 2.3 строятся подхода и алгоритмы численного тестирования трехмерных сеток на основе топологических характеристик границы и условий согласованности. Для предложенных подходов вводятся необходимые определения и доказываются утверждения о необходимости и достаточности предложенных подходов. Как результат - разработано II универсальных методов, называемых тестами, для автоматического определения корректности произвольных трехмерных сеток.

В п. 2.3.1 вводится общая постановка задачи и приведены необходимые определения. В п. 2.3.2 сформулированы два условия проверки и доказано, что их выполнение является достаточным для согласованности сетки. В п. 2.3.3 описано условие проверки топологии внутренних узлов сетки. В п. 2.3.4- п. 2.3.5 на основе теории выпуклых многогранников строятся необходимые и достаточные условия проверки топологии граничных компонент сетки. В п. 2.3.6 приведены условия тестирования глобальных топологических характеристик границы сетки - ориентируемости, замкнутости и топологического класса.

Третья глава посвящена задачам автоматизации процесса моделирования двумерных и трехмерных электростатических полей методом конечных элементов в системе Stвlla-2D и ППП РАМЗЕС-З.

В § 3.1 описаны постановка задачи и особенности реализации алгоритмов в указанных программных системах. Особое внимание уделяется описанию поэлементной реализации итерационных методов при решении систем линейных уравнений, возникающих в МКЭ. В качестве предобуславливаицих матриц предлагается

использовать различные варианты матриц методов расщеплений (переменных направлений).

В § 3.2 описывается интерактивная система Stella-2D для расчета электростатических полей в плоской и осесимметричной постановках на персональных компьютерах. Система stella-2D построена на основе - графической системы меню и включает графический редактор, базу данных материалов, генератор сеток, расчетный блок и блок графического анализа решения. В качестве примеров использования системы stella-2D приводятся результаты практических расчетов изолирующей подвески ЛЭП и полимерного опорного изолятора, имеющих сложную геометрию области с соотношением размеров порядка Ю2- Ю3.

В § 3.3 описывается пакет прикладных программ РАМЗЕС-З для решения трехмерных электростатических задач. Приводятся общее описание пакета, схема вычислительного процесса, структура входного языка АИДА для описания геометрии, описание систем возникающих уравнений. Приводятся примеры описания трехмерной ' области на входном языке, примеры сеток для различных областей и пример использования пакета для решения стационарной задачи теплопроводности.

В заключении формулируются основные результаты работы.

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

III. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Исследована задача построения триангуляций в трехмерных областях сложной формы. Предложены способы представления данных и алгоритмы построения трехмерных триангуляций на основе локально-модифицированного подхода с параметром сдвига. Для построения триангуляции на границе области введено понятие триангуляции Делоне на поверхности.

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

5. На основе предложенных алгоритмов разработаны прикладные программы моделирования электростатических полей: двумерная интерактивная графическая система steiia-2D для персональных

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

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

1. А.Ю.Кузнецов Алгоритмы построения сеток метода конечных элементов для расчета стационарных полей в трехемерных областях. - В кн.: Пакеты программ для задач математической физики. Новосибирск, 1985, с.67-81.

2. А.Ю.Кузнецов Автоматизация построения трехмерных сеток в ППП РАМЗЕС-З. Препринт 707, ВЦ СОАН СССР, Новосибирск, 1986,20с.

3. Л.А.Голубева, АРЮ.Кузнецов Входной язык АИДА, для описания геометрии области в ППП РАМЗЕС-З. -В кн.: Пакеты программ для задач математической физики. Новосибирск, 1986, с.39-48.

4. А.Ю.Кузнецов Автоматизация построения трехмерных сеток метода конечных элементов, Комплексы программ математической физики и архитектуа ЭВМ (Труды школы-семинара, п.Шушенское, 1986), - ВЦ СОАН СССР, Красноярск, 1988, с.208-217.

5. А.Ю.Кузнецов Об одном методе тестирования трехмерных сеток для метода конечных элементов. -В кн.: Технология вычислительного эксперимента. Новосибирск, 1988, с.63-69.

6. А.Ю.Кузнецов, И.К.Никулина Методы тестирования трехмерных сеток. Препринт 869, ВЦ СОАН СССР, Новосибирск, 1989, -23с.

7. А.Ю.Кузнецов. Алгоритмы построения двумерной триангуляции

. Делоне, Новосибирск, 1990, Препринт 909, ВЦ СОАН СССР, 43с.

8. А.Ю.Кузнецов, А.В.Руссков Моделирование двумерных электростатических полей на 1ВМ РС, Вычислительный эксперимент в задачах математической физики, ВЦ СО АН СССР, Новосибирск, 1990, с.99-106

9. А.Ю.Кузнецов Построение динамических триангуляции Делоне, В сб. Вариационные метода в задачачах численного моделирования, 1991, с.76-83.

10. А.Ю.Кузнецов Алгоритмы тестирования трехмерных • сеток, основанные на достаточных условиях, Вопросы Атомной Науки и

Техники, Сер. мат. моделир. физ. процессов, Москва, 1991, I, с.92-94.

11. А.Ю.Кузнецов 0 некоторых подходах к реализации алгоритмов в ППП РАМЗЕС-З. -В сб.: Технология моделирования задач математической физики, ВЦ СОАН СССР, 1989, с.89-97.

12. А.Ю.Кузнецов, А.В.Руссков Разработка на С++ интерактивных прикладных систем для решения задач численного моделирования, Вычислительный эксперимент в задачах математической физики, ВЦ СОАН СССР, Новосибирск, 1991, с.164-171.

\