LEC-23 (Материалы к лекциям)
Описание файла
Файл "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 точки на одной описанной окружности позволяют реализовать две различные триангуляции Делоне.
Алгоритмы построения триангуляции Делоне
Базовый алгоритм
Этот алгоритм – классический, часто используется для построения триангуляции Делоне (иногда его называют декрементным).
Алгоритм содержит следующие операции:
-
выбор произвольной начальной точки;
-
поиск второй ближайшей точки, соединяющий точки отрезок является
исходной базой для дальнейших построений;
-
поиск в левой полуплоскости от базового отрезка точки, из которой
базовый отрезок виден под максимальным углом (если а левой полуплоскости нет точек, попытка повторяется для правой полуплоскости);
-
в дальнейшем в качестве базовых отрезков принимаются стороны
треугольников, которые не имеют сопряженных треугольников, поиск нужных вершин всегда ведется в левой полуплоскости относительно базового отрезка;
-
процесс продолжается до тех пор, пока вершинами треугольников не
будут закреплены все точки исходного множества.
Алгоритм работает путем постоянного наращивания текущей триангуляции по одному треугольнику за один шаг. Вначале текущая триангуляция состоит из единственного ребра оболочки, по окончании работы алгоритма текущая триангуляция становится триангуляцией Делоне.