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

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

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

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

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

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

13

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

Лекция 24

9.2.3.2. Алгоритм Рапперта и его модификации.

Снова напомним, что к сетке МКЭ предъявляется ряд основных требований. Во-первых, треугольники не должны быть сильно вытянутыми, т.к. наличие таких треугольников отрицательно сказывается на точности результатов расчета. Во-вторых, должен быть учтен характер работы конструкции и ее геометрия, т.е. в местах концентрации напряжений сетка должна сгущаться. Все эти требования учтены в алгоритме генерации треугольных иррациональных конечно-элементных сеток Рапперта.

Этот алгоритм довольно новый, он был опубликован в 1994 году. Его разработал Джим Рапперт еще будучи студентом в рамках проекта, поддерживаемым NASA. Алгоритм адаптирован для метода конечных элементов и перечисленные выше требования, предъявляемые к конечно-элементным сеткам удовлетворяются автоматически. К его преимуществам можно отнести и то, что алгоритм легко параметризируется и управляется.

Если говорить точнее, этот алгоритм не является алгоритмом генерации, а лишь алгоритмом улучшения качеств сетки (refinement). В нашем случае входными данными для него будут являться геометрия конструкции в виде замкнутых полигонов и первичное разбиение конструкции на треугольники. В этом пункте, при описании алгоритма, будем считать, что первоначальное разбиение уже создано. Более подробно на генерации первоначального разбиения мы остановимся ниже (см. п. 5).

При описании своего алгоритма Рапперт вводит свою терминологию, которой будем придерживаться и мы.

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

Узел (node) — точка в которой сходятся грани и соприкасаются несколько элементов. В отличие от вершин элементов узел общий для всех соприкасающижся в одной точке элементов.

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

Грань (edge) — это отрезок по которому граничат два соприкасающихся треугольника. Используя предыдущее определение можно сказать, что все множество отрезков, соединяющих вершины элементов, в любой момент работы алгоритма складывается из сегментов и граней.

Включенная точка (encroached point) — любая вершина текущей сетки, которая находится внутри окружности, радиусом которой является любой сегмент.

"Неправильный треугольник" (bad triangle) — это треугольник неудовлетворяющий глобальным условиям, которые накладываются на генерируемую сетку.

Вытянутый треугольник (skinny triangle) — треугольник, имеющий одну сторону, намного отличающуюся от других двух. То есть треугольник слишком вытянут вдоль некоторой прямой. На критериях "вытянутости" мы остановимся ниже.

Алгоритм опирается на две базовые процедуры: разбиение неправильного треугольника с введением нового узла и разбиение сегмента, принадлежащего границе области разбиения с введением нового узла.

a) разбиение неправильного треугольника с введением нового узла

При разбиении неправильного треугольника происходит следующее:

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

  2. В эту точку добавляется новый узел.

  3. У
    даляется треугольник, подлежащий разбиению и прилегающие и добавляются новые, как показано на рисунке 7-Р.

b) разбиение сегмента, принадлежащего границе области разбиения с введением нового узла.

Вторая базовая процедура состоит в следующем:

  1. Если в окружность, диаметром которой является сегмент, принадлежащий границе области разбиения попадает точка, не принадлежащая этому сегменту, то сегмент делится на две части.

  2. У
    даляется треугольник, которому принадлежал первоначальный сегмент и добавляются два новых треугольника (см. рис. 8-Р).

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

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

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

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

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

  1. Производится поиск включенной (encroached) точки перебором всех точек и сегментов (только сегментов, но не граней).

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

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

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

  5. Производится поиск треугольника максимальной площадью.

  6. Если максимальная площадь больше заданного параметра, то над таким треугольником производится процедура деления и производится возврат на шаг 1. В противном случае происходит переход на следующий шаг.

  7. Все условия удовлетворены. Конец работы алгоритма

Автор в своей работе приводит строгие математические доказательства, гарантирующие правильную работу алгоритма при минимальном угле α < 20°.

Модификация алгоритма Рапперта

В работе для Journal of Algorithms раскрыт только лишь чисто математический аспект проблемы, хотя вероятней всего алгоритм разрабатывался для решения прикладных задач и для генерации конечно-элементной сетки в том числе. К тому же, и математическая сторона была раскрыта не полностью, а только лишь с точки зрения сходимости и некоторых особенностей. Ряд самых неочевидных подводных камней не поднимается на обсуждение. Видимо это объясняется тем, что это проект NASA и, вероятно, имеет какую-то степень закрытости.

В том варианте, в котором он был предложен автором, алгоритм не обладал хорошей сходимостью и устойчивостью. Опытным путем было установлено, что углы α > 25° были недоступны для него. Для повышения качества работы алгоритма, помимо двух вышеперечисленных процедур была введена еще одна — процедура поворота диагонали. К сожалению, автор опустил этот момент и не упомянул о нем, несмотря на то что, ее роль в работе алгоритма очень высока. Эта процедура, на самом деле, неявно присутствует в оригинальном алгоритме Рапперта (см.рис. 7-Р, 8-Р), но все же эту процедуру лучше выделить в отдельную и остановиться на ней подробно. Это упрощает и понимание работы алгоритма, и его программирование. На рисунках видно, что помимо непосредственного добавления новых треугольников, производятся и еще некоторые операции. Эти операции есть ничто иное, как смена диагонали.

С
уть ее заключается в следующем. Два треугольника, имеющие общую грань, образуют четырехугольник, разделенный диагональю. Внутри такого образования диагональ имеет два возможных положения. На рисунке 9-Р показаны эти положения — отрезки ac и bd.

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

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

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

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

П
ервый, возможно самый очевидный критерий — это длина диагонали
(см. рис. 10-Р). Действительно, зрительно, диагональ ac кажется гораздо более удачной диагонали bd для минимального угла двух треугольников и поменяв эту диагональ мы, вероятно, добьемся улучшения свойств сетки. У этого способа, к тому же, есть преимущества: он не трудоемок в вычислительном плане и его просто запрограммировать. Но есть у него и критический недостаток — он неадекватен. На рисунке 10-Р показан случай, где использование критерия минимальной длины диагонали может привести к серьезному ухудшению свойств сетки.

Диагональ bd короче диагонали ac, поэтому, по критерию минимальной длины диагонали, диагональ ac надо поменять на bd. Но это приведет к появлению очень тонкого треугольника, а их появление крайне нежелательно, а часто и вовсе становится критическим. Этот случай уже не так просто формализуется, и запрограммировав его, легко убедиться, что это дополнительное условие сильно "утяжеляет" алгоритм, сводя на нет все его преимущества.

Следующий очевидный критерий можно получить сравнивая минимальные углы в двух треугольниках до и после смены диагонали, для предсказания эффективности этого действия (см. рис. 11-Р). Такой критерий является абсолютно адекватным, т.к. он совпадает с основным глобальным критерием сетки — критерием минимального угла и это его существенное преимущество.

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



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

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