Бессеточные методы

20 точек и их Вороного ячейки

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

Мотивация

Численные методы, такие как метод конечных разностей , метод конечных объемов и метод конечных элементов , изначально были определены на сетках точек данных. В такой сетке каждая точка имеет фиксированное количество предопределенных соседей, и эту связь между соседями можно использовать для определения математических операторов, таких как производная . Эти операторы затем используются для построения уравнений для моделирования, таких как уравнения Эйлера или уравнения Навье–Стокса .

Но в симуляциях, где моделируемый материал может перемещаться (как в вычислительной гидродинамике ) или где могут происходить большие деформации материала (как при моделировании пластиковых материалов ), связность сетки может быть трудно поддерживать без внесения ошибок в симуляция. Если сетка запутывается или вырождается во время моделирования, определенные в ней операторы больше не могут давать правильные значения. Сетка может быть воссоздана во время моделирования (процесс, называемый повторным созданием сетки), но это также может привести к ошибке, поскольку все существующие точки данных должны быть сопоставлены с новым и другим набором точек данных. Методы Meshfree призваны решить эти проблемы. Бессеточные методы также полезны для:

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

Пример

В традиционном моделировании с помощью конечных разностей областью одномерного моделирования будет некоторая функция. $u(x,t)$, представленный как сетка значений данных $u_{i}^{n}$ в точках $x_{i}$, где

$i=0,1,2...$

$n=0,1,2...$

$x_{i+1}-x_{i}=h\ \forall i$

$t_{n+1}-t_{n}=k\ \forall n$

Мы можем определить производные, которые встречаются в моделируемом уравнении, используя некоторые формулы конечных разностей в этой области, например

${\partial u \over \partial x}={u_{i+1}^{n}-u_{i-1}^{n} \over 2h}$

и

${\partial u \over \partial t}={u_{i}^{n+1}-u_{i}^{n} \over k}$

Тогда мы можем использовать эти определения $u(x,t)$ и его пространственные и временные производные, чтобы записать моделируемое уравнение в форме конечной разности, а затем смоделировать уравнение с помощью одного из многих методов конечных разностей .

В этом простом примере шаги (здесь пространственный шаг $h$ и временной шаг $k$) постоянны по всей сетке, а соседи слева и справа от значения данных в сетке $x_{i}$ значения в $x_{i-1}$ и $x_{i+1}$, соответственно. Как правило, в конечных разностях можно очень просто допустить переменность шагов вдоль сетки, но все исходные узлы должны быть сохранены, и они могут перемещаться независимо, только деформируя исходные элементы. Если даже только два из всех узлов изменят свой порядок или даже только один узел будет добавлен в симуляцию или удален из нее, это создаст дефект в исходной сетке, и простая аппроксимация конечной разностью больше не будет работать.

Гидродинамика сглаженных частиц (SPH), один из старейших бессеточных методов, решает эту проблему, рассматривая точки данных как физические частицы с массой и плотностью, которые могут перемещаться во времени и нести некоторую ценность. $u_{i}$ с ними. Затем SPH определяет значение $u(x,t)$ между частицами

$u(x,t_{n})=\sum _{i}m_{i}{\frac {u_{i}^{n}}{\rho _{i}}}W(|x-x_{i}|)$

где $m_{i}$ это масса частицы $i$, $\rho _{i}$ плотность частиц $i$, и $W$ — это функция ядра, которая работает с близлежащими точками данных и выбирается из соображений плавности и других полезных качеств. В силу линейности мы можем записать пространственную производную как

${\partial u \over \partial x}=\sum _{i}m_{i}{\frac {u_{i}^{n}}{\rho _{i}}}{\partial W(|x-x_{i}|) \over \partial x}$

Тогда мы можем использовать эти определения $u(x,t)$ и его пространственные производные, чтобы записать моделируемое уравнение как обыкновенное дифференциальное уравнение и смоделировать уравнение одним из многих численных методов . С физической точки зрения это означает расчет сил между частицами, а затем интегрирование этих сил во времени для определения их движения.

Преимущество SPH в этой ситуации состоит в том, что формулы для $u(x,t)$ и его производные не зависят от какой-либо информации о смежности частиц; они могут использовать частицы в любом порядке, поэтому не имеет значения, движутся ли частицы или даже меняются местами.

Одним из недостатков SPH является то, что для определения ближайших соседей частицы требуется дополнительное программирование. Поскольку функция ядра $W$ возвращает ненулевые результаты только для соседних частиц в пределах удвоенной «длины сглаживания» (поскольку мы обычно выбираем функции ядра с компактной поддержкой ), было бы пустой тратой усилий вычислять приведенные выше суммирования по каждой частице в большой симуляции. Поэтому обычно симуляторам SPH требуется дополнительный код для ускорения расчета ближайшего соседа.

История

Одним из первых бессеточных методов является гидродинамика сглаженных частиц , представленная в 1977 году. Либерский и др. первыми применили СПГ в механике твердого тела. Основными недостатками SPH являются неточные результаты вблизи границ и нестабильность натяжения, которая впервые была исследована Свеглом.

В 1990-х годах появился новый класс бессеточных методов, основанный на методе Галеркина . Этот первый метод называется методом диффузного элемента. (DEM), впервые разработанная Нейролесом и др., использовала приближение MLS в решении Галеркина уравнений в частных производных с приближенными производными функции MLS. После этого Беличко впервые применил метод Галеркина без элементов (EFG). в котором использовалась MLS с множителями Лагранжа для обеспечения соблюдения граничных условий, числовая квадратура более высокого порядка в слабой форме и полные производные приближения MLS, которые давали лучшую точность. Примерно в то же время был разработан метод воспроизведения ядерных частиц . (RKPM), аппроксимация частично побудила исправить оценку ядра в SPH: обеспечить точность вблизи границ, при неравномерной дискретизации и точность более высокого порядка в целом. Примечательно, что параллельно с этим методы Материальной точки . примерно в то же время были разработаны которые предлагают аналогичные возможности. Методы материальных точек широко используются в киноиндустрии для моделирования механики твердого тела с большими деформациями, таких как снег в фильме « Холодное сердце» . RKPM и другие бессеточные методы были широко разработаны Ченом, Лю и Ли в конце 1990-х годов для множества приложений и различных классов задач. В течение 1990-х годов и впоследствии было выведено несколько других сортов, в том числе перечисленные ниже.

Список методов и сокращений

Следующие численные методы обычно считаются подпадающими под общий класс «бессеточных» методов. Сокращения приведены в скобках.

• Гидродинамика сглаженных частиц (SPH) (1977)
• Метод диффузного элемента (DEM) (1992 г.)
• Диссипативная динамика частиц (DPD) (1992)
• Безэлементный метод Галеркина (EFG/EFGM) (1994 г.)
• Метод воспроизводства ядерных частиц (РКПМ) (1995)
• Метод конечных точек (FPM) (1996)
• Метод конечных точек (FPM) (1998)
• hp-облака
• Метод природных элементов (NEM)
• Метод материальной точки (МПМ)
• Бессеточный местный Петров Галеркин (МЛПГ) (1998)
• Формулировка без сетки обобщенной деформации (GSMF) (2016 г.)
• Полунеявное движение движущихся частиц (MPS)
• Обобщенный метод конечных разностей (GFDM)
• Частица в ячейке (PIC)
• Метод конечных элементов движущихся частиц (MPFEM)
• Метод конечных облаков (FCM)
• Метод граничных узлов (БНМ)
• Бессеточный метод интерполяции Кригинга (МК)
• Метод граничного облака (BCM)
• Метод фундаментальных решений (МФС)
• Метод частного решения (МПС)
• Метод конечных сфер (МФС)
• Дискретный вихревой метод (ДВМ)
• Воспроизведение метода частиц ядра (RKPM) (1995)
• Обобщенный/градиентный метод ядра частиц (2011)
• Метод конечных масс (МММ) (2000)
• Метод интерполяции сглаженной точки (S-PIM) (2005 г.).
• локальной Бессеточный метод радиальной точечной интерполяции (RPIM).
• Метод коллокации локальных радиальных базисных функций (LRBFCM)
• Метод вязких вихревых доменов (ВВД)
• Метод крекирующих частиц (CPM) (2004 г.)
• Дискретный бессеточный метод наименьших квадратов (DLSM) (2006 г.)
• Метод погруженных частиц (IPM) (2006)
• Бессеточный метод оптимальной транспортировки (OTM) (2010 г.)
• Метод повторной замены (РМЗ) (2012 г.)
• Метод интегрального уравнения радиального базиса
• Бессеточный метод коллокации наименьших квадратов (2001)
• Метод экспоненциальных базисных функций (EBF) (2010)

Связанные методы:

• Перемещение наименьших квадратов (MLS) - обеспечивает общий метод аппроксимации для произвольного набора узлов.
• Разделение методов единства (PoUM) - обеспечивает общую формулировку аппроксимации, используемую в некоторых бессеточных методах.
• Метод непрерывного смешивания (обогащение и объединение конечных элементов и бессеточные методы) – см. Huerta & Fernández-Méndez (2000).
• eXtended FEM , Generalized FEM (XFEM, GFEM) – варианты FEM (метода конечных элементов), сочетающие в себе некоторые бессеточные аспекты.
• Сглаженный метод конечных элементов (S-FEM) (2007)
• Метод градиентного сглаживания (GSM) (2008 г.)
• Локальная максимальная энтропия (LME) – см. Arroyo & Ortiz (2006).
• Метод пространственно-временной бессеточной коллокации (STMCM) – см. Нетужилов (2008) , Нетужилов и Зилиан (2009).
• Метод конечных элементов без сетки интерфейса (MIFEM) (2015) - гибридный метод конечных элементов без сетки для численного моделирования задач фазового превращения и многофазного потока.

Последние разработки

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

Что касается квадратуры , обычно предпочтительнее узловое интегрирование, которое обеспечивает простоту, эффективность и сохраняет метод без сетки свободным от какой-либо сетки (в отличие от использования квадратуры Гаусса , которая требует сетки для создания квадратурных точек и весов). Однако узловое интегрирование страдает численной нестабильностью из-за недооценки энергии деформации, связанной с коротковолновыми модами. а также дает неточные и несходящиеся результаты из-за недостаточного интегрирования слабой формы. Одним из основных достижений в области численного интегрирования стала разработка стабилизированного согласованного узлового интегрирования (SCNI), который обеспечивает метод узлового интегрирования, не страдающий ни от одной из этих проблем. Метод основан на сглаживании деформации, которое удовлетворяет требованиям патч-теста первого порядка . Однако позже выяснилось, что в СКНИ все же присутствуют низкоэнергетические режимы, и были разработаны дополнительные методы стабилизации. Этот метод применялся для решения множества задач, включая тонкие и толстые пластины, поромеханику, проблемы с преобладанием конвекции и другие. Совсем недавно была разработана структура для прохождения патч-тестов произвольного порядка, основанная на методе Петрова-Галеркина .

Одно из недавних достижений в области бессеточных методов направлено на разработку вычислительных инструментов для автоматизации моделирования и моделирования. Это становится возможным благодаря так называемой ослабленной слабой формулировке (W2), основанной на теории G-пространства . Формулировка W2 предлагает возможности формулировать различные (равномерно) «мягкие» модели, которые хорошо работают с треугольными сетками. Поскольку треугольная сетка может быть создана автоматически, ее повторное создание сетки становится намного проще и, следовательно, обеспечивает автоматизацию моделирования и симуляции. Кроме того, модели W2 можно сделать достаточно мягкими (единообразным образом), чтобы давать решения для верхних границ (для задач о движении сил). Вместе с жесткими моделями (такими как полностью совместимые модели FEM) можно удобно связать решение с обеих сторон. Это позволяет легко оценивать ошибки для обычно сложных задач, если можно создать треугольную сетку. Типичными моделями W2 являются методы интерполяции сглаженной точки (или S-PIM). S-PIM может быть основан на узлах (известен как NS-PIM или LC-PIM). периферийный (ES-PIM), и на основе ячеек (CS-PIM). NS-PIM был разработан с использованием так называемой техники SCNI. Затем было обнаружено, что NS-PIM способен производить раствор с верхней границей и без объемной блокировки. ES-PIM превосходит по точности, а CS-PIM ведет себя где-то между NS-PIM и ES-PIM. Более того, формулировки W2 позволяют использовать полиномиальные и радиальные базисные функции при создании функций формы (они учитывают прерывистые функции смещения, пока они находятся в пространстве G1), что открывает дополнительные возможности для будущих разработок. Формулировка W2 также привела к развитию комбинации бессеточных методов с хорошо разработанными методами FEM, и теперь можно использовать треугольную сетку с превосходной точностью и желаемой мягкостью. Типичной такой формулировкой является так называемый сглаженный метод конечных элементов (или S-FEM). S-FEM — это линейная версия S-PIM, но обладающая большинством свойств S-PIM и намного проще.

Распространено мнение, что бессеточные методы намного дороже, чем аналоги FEM. Однако недавнее исследование показало, что некоторые бессеточные методы, такие как S-PIM и S-FEM, могут быть намного быстрее, чем аналоги FEM.

S-PIM и S-FEM хорошо подходят для решения задач механики твердого тела. Для задач CFD формулировка может быть проще, используя строгую формулировку. Методы градиентного сглаживания (GSM) также были недавно разработаны для задач CFD, реализуя идею градиентного сглаживания в сильной форме. GSM похож на [FVM], но использует операции сглаживания градиента исключительно вложенными способами и является общим численным методом для PDE.

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

См. также

• Механика сплошных сред
• Сглаженный метод конечных элементов
• G пространство
• Ослабленная слабая форма
• Метод граничных элементов
• Метод погруженных границ
• Код трафарета
• Метод частиц

Дальнейшее чтение

• Гарг, Сахил; Пант, Мохит (24 мая 2018 г.). «Методы Meshfree: комплексный обзор приложений». Международный журнал вычислительных методов . 15 (4): 1830001. doi : 10.1142/S0219876218300015 .
• Лю, МБ; Лю, гр.; Зонг, З. (20 ноября 2011 г.). «Обзор гидродинамики сглаженных частиц». Международный журнал вычислительных методов . 05 (1): 135–188. дои : 10.1142/S021987620800142X .
• Лю, гр.; Лю, МБ (2003). Гидродинамика сглаженных частиц, бессеточный метод и метод частиц . Всемирная научная. ISBN  981-238-456-1 .
• Атлури, С.Н. (2004). Бессеточный метод (MLPG) для дискретизации доменов и BIE . Tech Science Press. ISBN  0-9657001-8-6 .
• Арройо, М.; Ортис, М. (26 марта 2006 г.). «Схемы аппроксимации локальной максимальной энтропии: бесшовный мост между конечными элементами и бессеточными методами». Международный журнал численных методов в технике . 65 (13): 2167–2202. Бибкод : 2006IJNME..65.2167A . CiteSeerX   10.1.1.68.2696 . дои : 10.1002/nme.1534 . S2CID   15974625 .
• Беличко Т., Чен Дж. С. (2007). Meshfree и методы частиц , John Wiley and Sons Ltd. ISBN   0-470-84800-6
• Беличко Т.; Уэрта, А.; Фернандес-Мендес, С; Рабчук, Т. (2004), «Бессеточные методы», Энциклопедия вычислительной механики, том. 1 Глава 10, Джон Уайли и сыновья . ISBN   0-470-84699-2
• Лю, GR, 1-е изд., 2002. Методы без сетки , CRC Press. ISBN   0-8493-1238-8 .
• Ли, С., Лю, В.К. (2004). Методы бессеточных частиц , Берлин: Springer Verlag. ISBN   3-540-22256-1
• Уэрта, Антонио; Фернандес-Мендес, Соня (20 августа 2000 г.). «Обогащение и объединение методов конечных элементов и бессеточных методов». Международный журнал численных методов в технике . 48 (11): 1615–1636. Бибкод : 2000IJNME..48.1615H . doi : 10.1002/1097-0207(20000820)48:11<1615::AID-NME883>3.0.CO;2-S . hdl : 2117/8264 . S2CID   122813651 .
• Нетужилов, Х. (2008), «Пространственно-временной бессеточный метод коллокации для связанных задач в областях неправильной формы», Диссертация, Брауншвейгский технический университет, CSE - Вычислительные науки в технике ISBN   978-3-00-026744-4 , также в электронном издании. .
• Нетужилов Геннадий; Зилиан, Андреас (15 октября 2009 г.). «Метод бессеточной коллокации пространства-времени: методология и применение к начально-краевым задачам». Международный журнал численных методов в технике . 80 (3): 355–380. Бибкод : 2009IJNME..80..355N . дои : 10.1002/nme.2638 . S2CID   122969330 .
• Альхури, Ю.; Наджи, А.; Уазар, Д.; Тайк, А. (26 августа 2010 г.). «Бессеточный метод на основе RBF для крупномасштабного моделирования мелководья: экспериментальная проверка» . Математическое моделирование природных явлений . 5 (7): 4–10. дои : 10.1051/mmnp/20105701 .
• Соуза, Вашингтон; де Оливейра, Родриго (апрель 2015 г.). «Метод дискретизации закона Кулона: новая методология пространственной дискретизации для метода радиальной точечной интерполяции». Журнал IEEE «Антенны и распространение» . 57 (2): 277–293. Бибкод : 2015IAPM...57..277S . дои : 10.1109/MAP.2015.2414571 .
• Гросс, Би Джей; Траск, Н.; Кубери, П.; Ацбергер, П.Дж. (15 мая 2020 г.). «Бессеточные методы на многообразиях для гидродинамических потоков на искривленных поверхностях: подход обобщенного скользящего наименьших квадратов (GMLS)». Журнал вычислительной физики . 409 : 109340. arXiv : 1905.10469 . Бибкод : 2020JCoPh.40909340G . дои : 10.1016/j.jcp.2020.109340 . S2CID   166228451 .
• Гросс, Би Джей; Кубери, П.; Ацбергер, П.Дж. (15 марта 2022 г.). «Статистика времени первого прохождения на поверхностях общей формы: решатели PDE для поверхностей с использованием метода обобщенных скользящих наименьших квадратов (GMLS)» . Журнал вычислительной физики . 453 : 110932. arXiv : 2102.02421 . Бибкод : 2022JCoPh.45310932G . дои : 10.1016/j.jcp.2021.110932 . ISSN   0021-9991 . S2CID   231802303 .

Внешние ссылки

• Блог USACM о методах Meshfree