LEC-23 (Материалы к лекциям)

2017-06-17СтудИзба

Описание файла

Файл "LEC-23" внутри архива находится в следующих папках: Материалы к лекциям, Lecturessemestr7. Документ из архива "Материалы к лекциям", который расположен в категории "". Всё это находится в предмете "методы решения задач механики сплошных сред" из 7 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "лекции и семинары", в предмете "методы решения задач механики сплошных сред" в общих файлах.

Онлайн просмотр документа "LEC-23"

Текст из документа "LEC-23"

12

В.А. Столярчук. “Моделирование систем”. Конспект лекций. Лекция №23

Лекция №23

9.2.3. Оптимизация сетки конечных элементов

Оптимизация СКЭ предполагает изменение геометрических параметров разбиения области с целью улучшения качества сетки.

Q  min (Q =  + T( K, N, K ,  N ))

Геометрическая оптимизация СКЭ возможна с изменением и без изменения топологической модели ( количество узлов, элементов, тип КЭ).

Во втором случае задача оптимизации состоит в сопровождении координат узлов сетки, обеспечивающих min Q при T( K, N, K ,  N ) = const

При изменении топологической модели СКЭ удается достичь наименьшего значения оценки качества , однако величина Q здесь может оказаться существенно большей, чем найденная при T( K, N, K ,  N ) = const ввиду усложнения алгоритма оптимизации и, как следствие, увеличения объема вычислений.

Для получения необходимой точности в зонах большой кривизны искомого решения можно производить локальное изменение топологической модели СКЭ. Чаще всего прибегают к измельчению сетки без изменения аппроксимирующих свойств отдельных элементов.

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

Охарактеризуем наиболее известные способы оптимизации СКЭ.

1. При отсутствии информации о решении краевой задачи треугольная сетка должна стремиться к конфигурации из равносторонних треугольников.

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

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

2. Для максимизации минимальных углов треугольников, образующих СКЭ, также используют разные алгоритмы, основанные, в частности, на использовании метода локальных вариаций.

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



Звездой, соответствующей данному узлу, называется совокупность элементов, содержащих этот узел.

Операции, объединенные в блок 4, выполняются по-разному, в зависимости от того, в каком виде хранится информация о связях узлов. Наиболее ответственной частью рассматриваемой процедуры являются операции блока 5. В Sigma они реализованы на основе метода локальных вариаций. Более подробно алгоритм можно описать по этапам:

1- определить граничные и внутренние узлы (выделить внутренние узлы)

2- организовать перебор внутренних узлов

3- для текущего внутреннего узла определить звезду.

4- организовать перебор элементов звезды.

5- определить минимальный угол и минимальную сторону в каждом из элементов и выбрать из них минимальный угол (назовем 1-й угол) и соответствующую ему сторону.

6- на основе полученной минимальной стороны определить шаг и направление сдвига.

6а- изменить координату текущего внутреннего узла на шаг.

7- определить минимальный угол(назовем 2-й угол) и сторону звезды при новом положении узла.

8- если 2-й угол больше 1-го, то запомнить новое положение текущего узла, присвоить значение 2-го угла 1-му углу и повторить пункты 6а,7; иначе если 2-й угол не больше 1-го, то изменить направление сдвига и выполнить пункты 6а,7.

9- по завершении перебора всех узлов если была изменена координата хотя бы одного узла и число проходов меньше 100 (можно задать любое другое число) вделать еще один проход, то есть выполнить пункты 2-9.

3. Также используют алгоритмы, основанные на процедуре минимизации энергетических функционалов МКЭ с учетом неизвестных координат узлов сетки.

Все эти методы имеют один общий признак - они не изменяют топологической модели СКЭ, т.е. остается неизменным количество узлов и элементов, тип КЭ.

П
риведём примеры результатов оптимизации сеток.

9.2.3.1 Алгоритмы Делоне.

Некоторые общие замечания

Т
риангуляция для конечного набора точек S является задачей триангуляции выпуклой оболочки CH(S), охватывающей все точки набора S. Отрезки прямых линий при триангуляции не могут пересекаться — они могут только встречаться в общих точках, принадлежащих набору S. Поскольку отрезки прямых линий замыкают треугольники, мы будем считать их ребрами. Ранее, при рассмотрении методов предварительного нанесения узлов сетки был приведён пример различных вариантов триангуляции. Повторим этот рисунок, временно игнорируя проведённые на нём окружности.

Для данного набора точек S мы можем видеть, что все точки из набора S могут быть подразделены на граничные точки — те точки, которые лежат на границе выпуклой оболочки CH(S), и внутренние точки — лежащие внутри выпуклой оболочки CH(S). Также можно классифицировать и ребра, полученные в результате триангуляции S, как ребра оболочки и внутренние ребра. К ребрам оболочки относятся ребра, расположенные вдоль границы выпуклой оболочки CH(S), а к внутренним ребрам — все остальные ребра, образующие сеть треугольников внутри выпуклой оболочки. Отметим, что каждое ребро оболочки соединяет две соседние граничные точки, тогда как внутренние ребра могут соединять две точки любого типа. В частности, если внутреннее ребро соединяет две граничные точки, то оно является хордой выпуклой оболочки CH(S). Заметим также, что каждое ребро триангуляции является границей двух областей: каждое внутреннее ребро находится между двумя треугольниками, а каждое ребро оболочки — между треугольником и бесконечной плоскостью.

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

Теорема о триангуляции набора точек. Предположим, что набор точек S содержит n>3 точек и не все из них коллинеарны. Кроме того, i точек из них являются внутренними (т. е. лежащими внутри выпуклой оболочки CH(S). Тогда при любом способе триангуляции набора S будет получено

точно n + i – 2 треугольников.

Для доказательства теоремы рассмотрим сначала триангуляцию n-i граничных точек. Поскольку все они являются вершинами выпуклого полигона, то при такой триангуляции будет получено (n - i) - 2 треугольников. (В этом нетрудно удостовериться и, более того, можно показать, что любая триангуляция произвольного m-стороннего полигона - выпуклого или невыпуклого — содержит m - 2 треугольника). Теперь проверим, что будет происходить с триангуляцией при добавлении оставшихся i внутренних точек, каждый раз по одной. Мы утверждаем, что добавление каждой такой точки приводит к увеличению числа треугольников на два. При добавлении внутренней точки могут возникнуть две ситуации, показанные на рис. 2. Во-первых, точка может оказаться внутри некоторого треугольника и тогда такой треугольник заменяется тремя новыми треугольниками. Во-вторых, если точка совпадает с одним из ребер триангуляции, то каждый из двух треугольников, примыкающих к этому ребру, заменяется двумя новыми треугольниками. Из этого следует, что после добавления всех г точек, общее число треугольников составит (n - i - 2) + (2i), или просто n + i - 2.

Рис. 2: Две ситуации, возникающие при триангуляции после добавления новой внутренней точки

Триангуляция Делоне

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

Она применяется во многих ГИС системах для построения моделей рельефа.

Делоне Борис Николаевич (1890-1980) - российский математик, член-корреспондент АН СССР (1929). Труды по геометрии, теории чисел, математической кристаллографии.

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

система взаимосвязанных неперекрывающихся треугольников имеет наименьший периметр, если ни одна из вершин не попадает внутрь ни одной из окружностей, описанных вокруг образованных треугольников (рис. 3-Д).


 

 

 

 

 

 

 

 

 

 

 

 

 

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

Т
ак, например, триангуляцию, изображенную на рис. 1а, можно отнести к типу триангуляции Делоне, а на рис. 1б триангуляция содержит несколько сильно вытянутых треугольников и ее нельзя отнести к типу Делоне.

На рис. 4-Д показан пример триангуляции Делоне для набора большого числа точек.

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

К триангуляции Делоне (к сетке, удовлетворяющей критерию Делоне) можно отнести несколько свойств, в частности:

  • триангуляция Делоне обладает наибольшей суммой минимальных углов всех своих треугольников.

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

Для формирования триангуляции Делоне потребуется несколько новых определений. Набор точек считается круговым, если существует некоторая окружность, на которой лежат все точки набора. Такая окружность будет описанной для данного набора точек. Описанная окружность для треугольника проходит через все три ее (не коллинеарные) вершины. Говорят, что окружность будет свободной от точек в отношении к заданному набору гочек S, если внутри окружности нет ни одной точки из набора S. Но, однако, точки из набора S могут располагаться на самой свободной от точек окружности.

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

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





Алгоритмы построения триангуляции Делоне

 

Базовый алгоритм

Этот алгоритм – классический, часто используется для построения триангуляции Делоне (иногда его называют декрементным).

Алгоритм содержит следующие операции:

  • выбор произвольной начальной точки;

  • поиск второй ближайшей точки, соединяющий точки отрезок является

исходной базой для дальнейших построений;

  • поиск в левой полуплоскости от базового отрезка точки, из которой

базовый отрезок виден под максимальным углом (если а левой полуплоскости нет точек, попытка повторяется для правой полуплоскости);

  • в дальнейшем в качестве базовых отрезков принимаются стороны

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

  • процесс продолжается до тех пор, пока вершинами треугольников не

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

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

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5057
Авторов
на СтудИзбе
456
Средний доход
с одного платного файла
Обучение Подробнее