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

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

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

Full description

Saved in:
Bibliographic Details
Date:2013
Main Author: Смелая, Т.Г.
Format: Article
Language:Russian
Published: Інститут технічної механіки НАН України і НКА України 2013
Series:Техническая механика
Online Access:http://dspace.nbuv.gov.ua/handle/123456789/88375
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Выбор расчетной сетки при моделировании течений разреженного газа методом пробных частиц / Т.Г. Смелая // Техническая механика. — 2013. — № 1. — С. 45-60. — Бібліогр.: 85 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-88375
record_format dspace
spelling irk-123456789-883752015-11-14T03:01:24Z Выбор расчетной сетки при моделировании течений разреженного газа методом пробных частиц Смелая, Т.Г. Из-за исключительной сложности уравнения Больцмана в задачах динамики разреженного газа, для его решения приходится использовать численные методы. При этом одним из ключевых моментов является дискретизация расчетной области. Целью настоящей статьи является выбор наиболее рациональной расчетной сетки статистического метода пробных частиц (МПЧ) решения уравнения Больцмана. Через виняткову складність рівняння Больцмана в задачах динаміки розрідженого газу, для його розв'язку доводиться використовувати чисельні методи. При цьому одним із ключових моментів є дискретизація розрахункової області. Метою цієї статті є вибір найбільш раціональної розрахункової сітки статистичного методу пробних часток (МПЧ) розв'язку рівняння Больцмана. Numerical methods have to use for solution of the Boltzmann equation for problems of the rarefied gas dynamics due to its exceptional complexity. In so doing discretization of the calculated region is one of the key moments. The aim of this paper is to choose the most rational calculation mesh of the statistical test particles method (TPM) for solution of the Boltzmann equation. 2013 Article Выбор расчетной сетки при моделировании течений разреженного газа методом пробных частиц / Т.Г. Смелая // Техническая механика. — 2013. — № 1. — С. 45-60. — Бібліогр.: 85 назв. — рос. 1561-9184 http://dspace.nbuv.gov.ua/handle/123456789/88375 519.172.1:.6/519.245/533.5 ru Техническая механика Інститут технічної механіки НАН України і НКА України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description Из-за исключительной сложности уравнения Больцмана в задачах динамики разреженного газа, для его решения приходится использовать численные методы. При этом одним из ключевых моментов является дискретизация расчетной области. Целью настоящей статьи является выбор наиболее рациональной расчетной сетки статистического метода пробных частиц (МПЧ) решения уравнения Больцмана.
format Article
author Смелая, Т.Г.
spellingShingle Смелая, Т.Г.
Выбор расчетной сетки при моделировании течений разреженного газа методом пробных частиц
Техническая механика
author_facet Смелая, Т.Г.
author_sort Смелая, Т.Г.
title Выбор расчетной сетки при моделировании течений разреженного газа методом пробных частиц
title_short Выбор расчетной сетки при моделировании течений разреженного газа методом пробных частиц
title_full Выбор расчетной сетки при моделировании течений разреженного газа методом пробных частиц
title_fullStr Выбор расчетной сетки при моделировании течений разреженного газа методом пробных частиц
title_full_unstemmed Выбор расчетной сетки при моделировании течений разреженного газа методом пробных частиц
title_sort выбор расчетной сетки при моделировании течений разреженного газа методом пробных частиц
publisher Інститут технічної механіки НАН України і НКА України
publishDate 2013
url http://dspace.nbuv.gov.ua/handle/123456789/88375
citation_txt Выбор расчетной сетки при моделировании течений разреженного газа методом пробных частиц / Т.Г. Смелая // Техническая механика. — 2013. — № 1. — С. 45-60. — Бібліогр.: 85 назв. — рос.
series Техническая механика
work_keys_str_mv AT smelaâtg vyborrasčetnojsetkiprimodelirovaniitečenijrazrežennogogazametodomprobnyhčastic
first_indexed 2025-07-06T16:07:52Z
last_indexed 2025-07-06T16:07:52Z
_version_ 1836914388324319232
fulltext УДК 519.172.1:.6/519.245/533.5 Т.Г. СМЕЛАЯ ВЫБОР РАСЧЕТНОЙ СЕТКИ ПРИ МОДЕЛИРОВАНИИ ТЕЧЕНИЙ РАЗРЕЖЕННОГО ГАЗА МЕТОДОМ ПРОБНЫХ ЧАСТИЦ Из-за исключительной сложности уравнения Больцмана в задачах динамики разреженного газа, для его решения приходится использовать численные методы. При этом одним из ключевых моментов являет- ся дискретизация расчетной области. Целью настоящей статьи является выбор наиболее рациональной расчетной сетки статистического метода пробных частиц (МПЧ) решения уравнения Больцмана. С помо- щью информационно-аналитического метода проанализированы все достоинства и недостатки различных типов расчетных сеток (РС) с точки зрения их применимости к задачам моделирования течений разрежен- ного газа МПЧ. Сделан вывод, что при использовании этого метода наиболее приемлемы адаптивные де- картовы прямоугольные сетки, характеризующиеся локальным изменением размеров ячеек в отдельных областях. Удобнее всего организовать такие РС с помощью иерархических блочных структур, для которых мелкая равномерная сетка находится внутри более грубой равномерной РС. Кратность разбиения корневых ячеек может быть различной и зависит от параметров локального режима течения, например от местных длин свободного пробега молекул. Таким РС присущи основные преимущества структурированных и не- структурированных сеток. Для МПЧ особенно важно, что они сочетают в себе высокоэффективный доступ ко всем элементам сетки, возможность векторизации алгоритма для многомерных задач и её локального сгущения. Результаты работы будут использованы при построении рабочих алгоритмов моделирования траекторий движения молекул МПЧ, что позволит более эффективно осуществлять экспертизу и сопрово- ждение отдельных проектов Национальной космической программы Украины. Через виняткову складність рівняння Больцмана в задачах динаміки розрідженого газу, для його роз- в'язку доводиться використовувати чисельні методи. При цьому одним із ключових моментів є дискрети- зація розрахункової області. Метою цієї статті є вибір найбільш раціональної розрахункової сітки статис- тичного методу пробних часток (МПЧ) розв'язку рівняння Больцмана. За допомогою інформаційно- аналітичного методу проаналізовано всі переваги та недоліки різних типів розрахункових сіток (РС) з точки зору їх застосування до задач моделювання течій розрідженого газу МПЧ. Зроблено висновок, що при використанні цього методу найбільш прийнятні адаптивні декартові прямокутні сітки, що характери- зуються локальною зміною розмірів чарунок в окремих областях. Найбільш перспективно організувати такі РС за допомогою ієрархічних блокових структур, для яких дрібна рівномірна сітка перебуває усереди- ні більш грубої рівномірної РС. Кратність розбивання кореневих чарунок може бути різною й залежить від параметрів локального режиму течії, наприклад від місцевих довжин вільного пробігу молекул. Таким РС властиві головні переваги структурованих і неструктурованих сіток. Для МПЧ найбільш важливо, що вони поєднують у собі високоефективний доступ до всіх елементів сітки, можливість векторизації алгоритму для багатомірних задач та її локального згущення. Результати роботи будуть використані при побудові робочих алгоритмів моделювання траєкторій руху молекул МПЧ, що дозволить більш ефективно здійсню- вати експертизу й супровід окремих проектів Національної космічної програми України. Numerical methods have to use for solution of the Boltzmann equation for problems of the rarefied gas dynamics due to its exceptional complexity. In so doing discretization of the calculated region is one of the key moments. The aim of this paper is to choose the most rational calculation mesh of the statistical test particles method (TPM) for solution of the Boltzmann equation. All advantages and disadvantages of different types of calculated meshes (CMs) are analyzed using an information and analytical method as regards their implementation for problems of the MTP rarefied gas flow simulation. It may be inferred that Cartesian adaptive rectangle meshes characterizing by local variations in mesh sizes in separate regions are most reasonable with this method. Use of hierarchy block systems, where a fine uniform mesh resides into a cruder uniform CM, is most promising for such CMs. The multiplicity of root cells division can be various and dependent on parameters of a local flow regime, for example, on local lengths of a molecular free path. Such CMs have the basic advantages of structurizated and nonstructurized meshes. Of prime importance for the TPM are a high-efficient access to all mesh elements and the possibility of vectorization of an algorithm for multidimensional problems and its local concentration. The research results will be used for construction of operational algorithms for simulation of motion trajectories of TPM molecules allowing a more efficient expertise and support for certain projects of the National Space Program of Ukraine. Решение интегро-дифференциального уравнения Больцмана – основного уравнения кинетической теории разреженных газов – является ключевым мо- ментом при моделировании течений разреженного газа. Функция распреде- ления, для которой записано это уравнение, зависит от семи переменных – пространственных координат, компонентов скорости и времени, а стоящий в правой части уравнения интеграл столкновений является пятикратным. Из-за  Т.Г. Смелая, 2013 Техн. механика. – 2013. – № 1. 45 исключительной сложности этого уравнения получение его точного решения возможно лишь в некоторых частных случаях. По этой причине при решении практических задач газовой динамики приходится использовать численные методы. Наиболее развитыми численными методами решения уравнения Больц- мана являются методы Монте-Карло [1, 2]. Эти методы базируются на стати- стическом подходе, в котором каждое отдельное событие носит случайный характер, а искомое решение получается путем осреднения большого числа таких событий. Один из методов Монте-Карло – метод пробных частиц (МПЧ). Он явля- ется аналогом известного метода в теории переноса нейтронов и основан на методике В. И. Власова случайных блужданий пробных молекул среди поле- вых [3 – 11]. МПЧ применим для решения фундаментальных и прикладных задач высотной аэродинамики космических аппаратов и дает возможность ответить на целый ряд проблемных вопросов. С его помощью можно решать задачи дозвуковой и сверхзвуковой газовой динамики, причем этот метод по- зволяет охватить как область свободномолекулярного течения, так и пере- ходную область, вплоть до сплошносредной. Как и остальным методам реше- ния кинетических уравнений, МПЧ свойственны определенные трудности, связанные с особенностью вычислений при наличии ярко выраженной неод- нородности полей течений (присутствие больших градиентов газодинамиче- ских параметров вблизи обтекаемых преград, формирующихся при малых числах Кнудсена ударных волн, контактных разрывов, пограничных слоев и других эффектов). При моделировании МПЧ объем физического пространства разбивается на малые ячейки. С границ расчетной области производится розыгрыш траек- торий пробных молекул, т. е. векторов их начальных скоростей. В процессе слежения за блужданиями молекул в рассматриваемом объеме накапливаются суммарные характеристики пребывания молекул в расчетных ячейках. Осо- бенности и некоторые тонкости алгоритма МПЧ более подробно рассмотре- ны в [12 – 13]. Для получения решения МПЧ строится соответствующий итерационный процесс по числам Кнудсена. В качестве начального берется свободномоле- кулярное поле параметров, а далее число Кнудсена уменьшается до достиже- ния требуемого режима обтекания. Фактически такая схема соответствует ме- тоду решения уравнения Больцмана путем разложения его правой части в ряд по числу Кнудсена. В свою очередь, при каждом фиксированном числе Кнудсена решение получается путем проведения нескольких последовательных расчетных ите- раций. На последующей итерации в качестве исходных параметров исполь- зуются результаты предыдущей. Задача решается методом установления с оценкой значений параметров на двух последовательных итерациях. Для накопления необходимой статистики в расчетных ячейках при каж- дом шаге проводится большое количество испытаний (розыгрышей пробных молекул), которое зависит от геометрии расчетной области, размера ячеек ис- пользуемой расчетной сетки (РС) и изменяется в пределах N ~ 105÷107. Спе- цифика МПЧ заключается в том, что процесс блуждания каждой пробной мо- лекулы в ячейках поля носит хаотичный характер. Траекторию движения мо- лекулы после розыгрыша, а также характер событий в расчетных ячейках об- ласти (столкновения с другими молекулами, соударения с поверхностью тела 46 или свободные пролеты ячеек) невозможно заранее предугадать. Поэтому, число ячеек, задействованных в блужданиях молекулы, может быть до- статочно большим и во много раз превышать число ячеек расчетной области. Учитывая вышеизложенные особенности МПЧ, можно сделать вывод, что расчетное время может быть велико даже для одной итерации. Целью на- стоящей работы является выбор оптимальной РС для численного моделиро- вания течений разреженного газа МПЧ на основе анализа различных видов расчетных сеток. Основными требованиями к РС являются минимизация рас- четного времени за счет сокращения количества расчетных ячеек без потери качества результата и максимальная экономия времени расчета для одной ячейки. Это можно осуществить за счет: – специальной организации структуры РС, позволяющей легко и быстро переходить от одной ячейки к другой при движении молекулы в пределах расчетной области; – использования достаточно мелких ячеек в зонах с физическими осо- бенностями, т. е. наличие сгущений РС там, где возможно появление боль- ших градиентов параметров, и укрупнения ячеек в остальных областях. При использовании ячеек переменного размера возникает проблема вы- бора критерия, определяющего размер ячейки. Таким критерием должен стать параметр, который легко получить в процессе счета и можно связать с физическими величинами, имеющими значительные градиенты в пределах расчетной области. Для МПЧ удобнее всего в качестве такого параметра вы- брать длину свободного пробега молекул, однозначно определяющую ло- кальный режим течения. Кроме этого, желательно максимально точно аппро- ксимировать границы расчетной области и сохранить возможность примене- ния эффективных алгоритмов обработки входных и выходных данных, вклю- чая ввод/вывод, визуализацию и т. п. Удовлетворить всем этим требованиям одновременно достаточно сложно, поэтому выбор РС требует некоторого компромисса. Процесс построения дискретизирующей расчетную область РС является одним из ключевых моментов проведения численного эксперимента. Рацио- нальным выбором РС можно значительно упростить решение поставленной задачи. Построение РС тесно связано с остальными этапами численного мо- делирования: подготовкой исходных данных, решением модельных урав- нений, анализом полученных результатов. Эти этапы моделирования часто обладают обратной связью: например, на основе анализа полученных резуль- татов возможно внесение корректировок в модель расчета и/или в процесс построения РС и т. п. Таким образом, процесс моделирования является, в об- щем случае, итерационным. Рассмотрим основные виды сеток. В зависимости от способа организации и доступа к параметрам сетки можно разбить на несколько глобальных типов [14]: структурированные, неструктурированные и гибридные, т. е. сочетаю- щие оба способа организации. Для структурированных (или регулярных) сеток характерно наличие упорядоченной по определенным правилам структуры и возможности выде- ления сеточных направлений. Эти направления можно привязать к какой- либо в общем случае неортогональной криволинейной системе координат, что дает возможность однозначно охарактеризовать геометрическую струк- туру набором индексов в узловых точках. Это важное свойство позволяет существенно экономить компьютерные ресурсы. 47 Такие сетки строятся преимущественно при помощи прямых методов, которые условно можно разбить на две тесно связанные группы: методы на основе шаблонов и методы отображения (изопараметрические) [15]. Методы на основе шаблонов [16 – 20] подразумевают разбиение областей заданного вида (прямоугольник, треугольник, параллелепипед, шар, цилиндр, и т.д.) с использованием определенного шаблона, задающего принцип разме- щения узлов и устанавливающего связи между ними. Сетка при этом строит- ся практически «мгновенно», при минимальной затрате ресурсов и с мини- мальным риском возможной ошибки. Методы шаблонов применимы только для областей определенной гео- метрической конфигурации, позволяющей осуществить качественную дис- кретизацию расчетной области, поэтому ни о какой универсальности здесь не может быть и речи. Для этого класса сеток может наблюдаться снижение точности расчетов на границе с телом и в областях с большими градиентами расчетных параметров. Методы отображения [16, 21 – 23] применяются в тех случаях, когда воз- можно построение взаимооднозначного отображения между заданной обла- стью произвольной формы и какой-либо областью простой геометрической формы. При этом должны удовлетворяться следующие требования: соблюде- ние однозначности отображения и гладкости линий сетки для обеспечения непрерывности производных, достаточной густоты сетки в областях с ожи- даемыми большими градиентами параметров, а также ограничение на ско- шенность ячеек во избежание чрезмерной ошибки аппроксимации [24]. Для упрощения задачи чаще всего используют вычислительные области пря- моугольного вида. Зачастую наибольшую трудность может представлять по- иск преобразования координат, отображающего декартову ортогональную систему координат на неортогональную (или ортогональную) систему коор- динат общего вида. Такое отображение должно преобразовывать прямоуголь- ную область с равномерным размещением узлов в вычислительном пространстве в расчетную об- ласть физического пространства, имеющую сложную геометрическую форму и РС со сгуще- ниями узлов в областях с большими градиентами параметров набегающего потока. На рис. 1 [24] приведен пример такой криволинейной физичес- кой области между ударной волной и телом сфе- рической формы с наложенной на неё криволи- нейной неортогональной сеткой. В этом примере поверхность тела выбрана в качестве одной из границ расчетной области, что облегчает поста- новку граничных условий на поверхности тела. Труднее всего найти подходящее отображение для трехмерного случая. В этом случае в основном применяются алгебраические или дифференциальные методы. С точки зрения вычислительной эффективности наиболее предпоч- тительными из них являются алгебраические методы [24 – 34]. Они позволя- ют обеспечить условие локальной ортогональности сетки в заданных облас- тях. Кроме того, перестройка сетки алгебраическими методами осуществля- ется быстрее, и их нередко используют для построения начальной сетки. Ос- новная идея построения вычислительной сетки алгебраическими методами состоит в интерполяции координат границы области для определения внут- Рис. 1 48 ренних узлов сетки. При отображении области с криволинейной границей, заданной набором точек, на расчетную область прямоугольного вида, предва- рительно граница исходной области должна быть аппроксимирована подхо- дящей кривой. Для этой цели лучше всего подходят напряженные сплайны, которые посредством параметра натяжения позволяют управлять формой кривой [35]. Контроль над размещением узлов сетки можно осуществлять с помощью уже известных функций преобразования. Соответствующие преоб- разования позволяют адаптировать РС к требованиям задачи: изменять форму этой области, угол наклона сеточных линий (поверхностей), добиваться их локальной ортогональности или сгущения в наперед заданных областях. Несомненное преимущество алгебраических методов состоит в том, что они являются прямыми и метрические коэффициенты можно вычислять ана- литически. В то же время, требуется проявить изобретательность, чтобы по- лучить сетку с адекватным размещением узлов [24]. Дифференциальные методы используют свойства решений уравнений, в качестве которых часто применяют эллиптические уравнения с частными производными Лапласа или Пуассона. Эти уравнения замечательны тем, что позволяют получать однозначные преобразования с гладкими и непрерыв- ными линиями сетки. К тому же, границы сложной формы легко обраба- тываются. Конечно, эти методы имеют свои недостатки. Несмотря на то, что существуют уже готовые методики выбора параметров для обеспечения при- ближенного контроля размещения узлов [36 – 38], задание параметров, управляющих размещением узлов сетки во внутренней части, является непро- стой задачей, да и границы области могут изменяться со временем. В послед- нем случае сетка должна перестраиваться после каждого шага по времени, что может повлечь значительное увеличение затрат машинного времени. Для построения расчетных сеток дифференциальными методами можно предложить неограниченное число схем их построения. Приемлема любая система уравнений, решение которой дает подходящую сетку. Например, в [39] для построения сетки вокруг некоторого тела приводиться схема, ис- пользующая уравнения в частных производных гиперболического типа. Внешняя граница физической расчетной области при этом заранее не указы- вается, поскольку сетка строится в направлении от внутренней границы, сов- падающей с поверхностью обтекаемого тела. Неплохие результаты в этом случае дает применение методов дуг и объ- емов, с помощью которых строятся ор- тогональные сетки [39]. В качестве па- раметра, контролирующего сетку в фи- зической области, можно использовать площадь её ячейки. Гладкую сетку уда- ется построить только при удачно по- добранном параметре. И наоборот, его неудачный выбор может привести к из- ломам или распространению по сетке искаженной информации о положении граничных узлов. К тому же, на такой сетке отрицательно отражаются имею- щиеся на границе разрывы данных. С другой стороны, при этом сетка строится быстро и является ортогональной. В ка-Рис. 2 49 честве примера приведен рис. 2 из [24], на котором показана РС, построенная вокруг типичного профиля. Здесь сгущение сетки вблизи тела позволяет раз- решить вязкий пристенный слой. Рассмотренные методы характерны тем, что процедура построения сеток предшествует численному решению уравнений в частных производных. В результате сетка может не учитывать особенности конкретной задачи. Мини- мизировать погрешности решения, достигнув высокого разрешения в облас- тях, имеющих особенности решения, помогают адаптивные сетки [40]. Они строятся в процессе решения задачи. В качестве параметров, определяющих форму таких сеток, могут выступать скорость «движения» узлов сетки и рас- стояние между ними в физическом пространстве. В соответствии с учетом особенностей задачи какой-либо из этих двух параметров выбирается опре- дел одолжительность расчета и необходимый объём оперативной пам тодов сквозного счета, чего яющим, а другой вычисляется в процессе решения [24]. Таким образом, главными преимуществами прямых методов являются их надежность и скорость работы. Благодаря специфике организации геометри- ческих данных ячеек и наличию системы индексов, соответствующих сеточ- ным направлениям, регулярные сетки позволяют быстро и просто находить адрес соседней ячейки в заданном направлении и за счет этого позволяют уменьшить пр яти ЭВМ. По той же причине структурированные сетки позволяют векторизировать программы вдоль сеточных направлений и использовать вдоль каждой из ко- ординатных осей независимо друг от друга любые одномерные алгоритмы. Это обстоятельство немаловажно, так как оно позволяет распараллелить ал- горитмы по сеточным направлениям. Кроме того, регулярным сеткам свойст- венен также высокий порядок аппроксимации для ме трудно достичь на неструктурированных сетках. В то же время, сетки, построенные по шаблонам, не позволяют получить достаточно мелкие ячейки в областях с физическими особенностями. Кроме этого, для явных схем, использующих регулярные РС, существует проблема малых ячеек на границах с телом, накладывающая ограничения на шаг интег- рирования и требующая для разрешения устойчивые, консервативные разно- стные схемы. Некоторые проблемы можно было бы решить, применяя методы отобра- жения и используя криволинейные сетки. Однако эти методы также имеют ряд существенных недостатков: применение для расчетной области сложной геометрической формы процедуры построения криволинейной регулярной сетки приведет к существенному увеличению затрат труда и ресурсов ЭВМ, к искажениям сетки, а возможно, и к возникновению особенностей вплоть до появления вырожденных ячеек при отображении. Это может существенно снизить качество результатов и привести к неустойчивости или отсутствию сходимости при неадекватном выборе размещения узлов расчетной сетки. Кроме этого, для методов отображения характерно снижение точности схемы на границах с телом в случае сложной геометрии, т. к. задача построения дан- ного типа РС в общем случае не является тривиальной. Проблема построения более мелких ячеек в областях с физическими осо- бенностями легко разрешается в случае применения неструктурированных сеток [41 – 49]. Характерной особенностью таких сеток является произ- вольное расположение узлов в физической области. Произвольность следует понимать в том смысле, что отсутствуют сеточные направления и невозмож- 50 но упорядочить узлы сетки, привязав её к какой-либо системе координат. Уз- лы сетки объединяются в общем случае в многогранники (3-х мерный слу- чай) или в многоугольники (плоский случай) произвольной формы. Как пра- вило, на плоскости используют треугольные ячейки, реже – четырех- угол инения зада правило, существенно меньше времени, затрачива- емо гранич- ной , включающих в себя ограничения вида внутренних пов ь эти проблемы при Дел ьные, в пространстве – тетраэдры и призмы. В отличие от структурированных, неструктурированные сетки требуют хранения и переработки информации о каждой ячейке: её ребрах, гранях (ориентация, длина и т. п.), а также о её соседних ячейках. Эту функцию вы- полняет список связных графов, который устанавливает способ объед нного множества узлов в отдельные элементы и их организацию. Поскольку перед построением нерегулярной сетки нельзя предвидеть ее будущую структуру, то нельзя гарантировать и ее качества. Часто для его улучшения необходимо прибегать к помощи методов оптимизации [50 – 52]. Этой возможностью обычно не пренебрегают, поскольку затрачиваемое на оптимизацию время, как го на построение. Для создания сеток нерегулярного типа популярно использование итера- ционных методов [53]. В зависимости от особенностей задачи (способа зада- ния начальных и граничных условий, формы расчетной области и предъяв- ляемых требований к организации РС) можно выбрать один из них: коррекции, на основе критерия Делоне, метод исчерпывания. Самыми быстрыми из итерационных методов являются методы гранич- ной коррекции [17 , 54 – 59], и это, за исключением сравнительной простоты реализации, практически их единственное достоинство. Этим методам при- сущ ряд существенных недостатков: повышенные требования к входным данным; невозможность использования для дискретизации областей с грани- цей, заданной при помощи триангуляции; ненадежность (полученные сетки необходимо проверять на правильность структуры); априори низкое качество элементов сеток вблизи границы (необходим этап оптимизации); низкая «чувствительность» алгоритма (при недостаточно малом шаге триангуляции некоторые особенности области могут быть потеряны). Тем не менее, алго- ритм граничной коррекции может быть успешно применен для дискретиза- ции сложных областей ерхностей и ребер. Исходными данными для алгоритмов на основе критерия Делоне [56, 60, 61] должен быть некий набор точек, которые станут узлами будущей триангуляции. Очевидным достоинством такого подхода является точный контроль над размерами элементов сетки, которые определяются плотностью размещения узлов. Увеличение плотности в зонах с особенностями автомати- чески приводит к локальному сгущению сетки. При этом в определенном смысле триангуляция Делоне для заданного набора точек является оптималь- ной. Основным недостатком этого метода являются трудности, возникающие при переходе к трехмерным задачам, и крайне высокая чувствительность ал- горитма к точности машинных вычислений. Попытки решит водят к существенному увеличению расчетного времени. Еще один хорошо известный метод – метод исчерпывания [52, 62 – 65]. Сетки, построенные с его помощью, как правило, обладают неплохим каче- ством, а последующая оптимизация положения узлов дополнительно его улучшает. Методы исчерпывания, в отличие от методов на основе критерия оне, наиболее эффективны в случае изначальной триангуляции границы. 51 Кроме итерационных алгоритмов, при формировании неструктурирован- ной сетки могут использоваться и другие алгоритмы, например рекурсивные (последовательного разбиения, деления и включения и т.п.). Идея метода со- стоит в разделении области на части меньшей величины, построении сетки в каждой из частей и объединении полученных ячеек или блоков. При этом в конечном итоге можно получить сетку однородной структуры либо со струк- турой в виде блоков [66]. В зависимости от числа применяемых рекурсий ре- зультатом может быть многоблочная или же иерархически блочная органи- зация сетки. При этом организация как самих блоков, так и ячеек сетки внут- ри них, может быть и структурированной. Тем не менее, даже если вся сетка локально структурирована, она все равно не может считаться структу- рированной в глобальном масштабе расчетной области. Такой вид сеток при- меним для случая геометрически сложных расчетных областей, а также для задач с разрывными решениями, в которых расчетная область характеризует- ся н у а- ющ ляют области пересечения и интерполи- рую рани- а строится оп- аличием разномасштабных элементов сложной неоднородной структуры. Сетки из разных блоков могут стыковаться точно по поверхностям раз- дела физической области на зоны или пересекаться между собой [67]. В слу- чае точного совпадения блоков при переходе от одной зоны к другой со- храняется консервативность разностной схемы решения уравнений и не тре- буется интерполяция между соседними блоками. При этом требование точ- ного совпадения границ блоков может накладывать дополнительные условия при построении сеток (например, границы зон должны быть фикси- рованы и не могут изменяться произвольным образом). Для бло- ков, имеющих пересечения, эти условия могут нарушаться, но при переходе от одного блока к другом консервативность схемы не гарантируется, а в пересек ихся областях требуется ин- терполяция искомых функций (па- раметров). При любом из двух подходов необходимы: анализ сгенерированной сет- ки на отсутствие самопересечений сеточных линий (в каждом блоке), а также выделение областей пересечения (для пересекающихся зон) или контроль над их отсутствием (в случае точного совпадения границ блоков). Существуют готовые алгоритмы, которые опреде Рис. 3 т значения расчетных параметров в данных областях. Пример применения многоблочной структуры регулярных сеток при точ- ном совпадении границ блоков для сложной области приведен на рис. 3 [68]. Изображенная на рисунке полная сетка строится из отдельных четырехуголь- ных сеток-подобластей с применением метода механической аналогии. Г цы п тим одобластей представляют собой отрезки прямых и дуг окружностей. Построение сетки, состоящей из блоков, фактически осуществляется в два этапа [66]. Сначала физическая область разбивается на несколько зон или блоков. При этом границы блоков могут не соответствовать границам фи- зической области. На следующем этапе для каждого блок альная сетка в соответствии с его граничными условиями. Многоблочные сеточные структуры в общем случае могут быть гибрид- 52 ными [69], что позволяет сочетать достоинства и снижать влияние недостат- ков, присущих каждому типу сеток. Например, гибридная сетка для обтека- ния набора профилей может быть построена следующим способом: область в окрестности каждого профиля покрывается ортогональной регулярной сет- кой, а области между профилями и дальнее поле – неструктурированной [24]. Вычислительный алгоритм должен при этом содержать процедуру переклю- чения расчетных схем для различных типов сеток и, если необходимо, проце- дур ет простое и эф- фек и алгоритмов для реализации этих стру (из- за к для заци е лишены структу- рир у переноса вычислительной информации с одного типа сетки на другой. При использовании иерархических блочных структур необходимо, чтобы на каждом этапе разбиения полученные подобласти (блоки) не были разъеди- нены и в то же время не включали одна другую полностью или частично [70]. Систематический рекурсивный процесс разбивки обеспечива тивное накопление, восстановление и обработку данных. Примером классической иерархической блочной структуры данных яв- ляются древовидные структуры, например квадро- и октодеревья [71 , 72]. Благодаря естественной иерархической структуре и способу её организации все древовидные структуры сочетают в себе значительную экономию объе- мов памяти с эффективностью доступа к нужной информации в ячейках сет- ки. Идеология квадродеревьев успешно применяется для компактной и удоб- ной организации больших баз любых пространственных данных [73 – 76]. Немаловажным достоинством квадро- и октодеревьев является также наличие доступных исходных текстов программ ктур данных и работы с ними [67]. Одним из главных недостатков всех видов деревьев является достаточно сложный алгоритм обхода [77]. Кроме того, области сложной конфигурации требуют большого количества вложений. При этом почти невозможно срав- нить два изображения, которые отличаются, например, лишь поворотом ардинального различия организации структуры его сетки). Несмотря на это, разновидности древовидных структур хорошо подходят для моделирования непрерывных сред и полей значений. Так, для стаци- онарных процессов можно применять воксельные модели сеток [78 – 80], хранящие значения данных для каждого единичного объёма пространства, а нестационарных процессов – их четырехмерную разновидность – доксел. Основное преимущество использования любых нерегулярных сеток по сравнению с регулярнымими заключается в большей гибкости при дискрети- зации области течения сложной формы. Процесс их построения для таких об- ластей зачастую происходит в несколько раз быстрее, однако время решения конкретных задач на нерегулярных сетках (в связи с особенностями органи- и хранения данных) может быть значительно больше, чем на регулярных. Вышесказанное характерно для численного решения задач газовой дина- мики с помощью МПЧ. Процесс слежения за траекториями пробных частиц требует определения номеров и параметров ячеек, в которые последовательно попадает пробная молекула при своём движении. Для нерегулярной сетки поиск ячейки, граничащей с рабочей в заданном направлении, займет гораздо больше времени, чем для регулярной, что делает её применение в МПЧ не- эффективным. Этот же вывод относится и к гибридным сеткам (нере- гулярным, например, в окрестности области уплотнения и регулярным в ос- тальной расчетной области), поскольку такие сетки такж ованности, а значит, и свойственных ей преимуществ. Следует отметить, что на выбор тех или иных способов построения сеток 53 существенное влияние оказывают ограничения, накладываемые использу- емыми методами. Так, во многих методах визуализации для отображения по- верхностей необходимо разбивать их на треугольники, а разноcтные cхемы часто оcнованы на ортогональных четырехугольных cетках. В конечно-эле- ментном анализе при использовании симплициальных сеток, как правило, требуется соблюдать ограничения на форму и размеры элементов, а при ре- шеии некоторых задач дополнительно могут возникать ограничения на топо- логию РС, касающиеся, например, количества элементов, инцидентных одно- му и ельный источник погр дрического сегмента с малым углом полураствора (осе но путем ис- пол тому же узлу, или конфигурации РС вблизи границ и угловых точек. При расчетах МПЧ главной задачей является максимальная минимизация расчетного времени. Её может дать РС, максимально сохраняющая свойство структурированности во всей области. В случае построения криволинейных регулярных сеток в физической области задачи с помощью метода отображе- ния можно одновременно добиться решения сразу двух основных проблем – хорошей адаптации сетки к внешней и внутренней границам области и сгу- щения сетки в местах с большими градиентами параметров (например, рис. 1, 2). При этом сохраняются основные преимущества структурированных сеток – простота и компактность организации данных. Однако существенным не- достатком криволинейных сеток является то, что необходимость отображе- ния области физического пространства (с криволинейными координатами) на вычислительную область (с декартовыми прямоугольными координатами) в процессе решения задачи может существенно усложнять расчеты и увеличи- вать временные затраты. Кроме того, появляется дополнит ешности счета при преобразованиях систем координат. Расчет газодинамических параметров МПЧ в окрестности преграды про- ще всего выполнять на ортогональных четырехугольных cетках. Такие сетки позволяют легко определять координаты центра и размер ячейки, в которую попадет молекула после перемещения. Поскольку форма внешней границы физической области для задач обтекания преград не принципиальна, для трехмерной задачи её имеет смысл выбрать в виде прямоугольного паралле- лепипеда, для двумерной – в виде тонкого прямоугольного параллелепипеда (плоская задача) или цилин симметричная задача). Самой простой прямоугольной структурированной сеткой является сетка с равномерными шагами разбиения по координатным осям. Такая сетка не имеет локального сгущения, поэтому получить на ней решение приемлемой точности зачастую невозможно (уменьшение размеров расчетных ячеек для достижения необходимой точности приводит к существенному увеличению их общего количества и, как следствие, к катастрофическому росту расчёт- ного времени). Применение более высокоскоростной вычислительной техни- ки решает возникшую проблему лишь частично. Добиться локального сгуще- ния сетки в областях с большими градиентами параметров мож ьзования процедуры динамической адаптации [36, 81 – 83]. Существует несколько стратегий адаптации: перемещение узлов сетки, локальное дробление – слияние ячеек и полная регенерация РС [40]. При этом могут варьироваться только координаты узлов, сохраняя топологию сетки. В cлучае изменения топологии возможно разбиение или укрупнение некоторых элементов, изменение конфигурации cвязей между узлами, введение допол- нительных узлов на границах и внутри элементов. Полная регенерация РС заключается в построении новой сетки с использованием информации, по- 54 лученной на старой сетке, и переинтерполяцией решения. Каждый из пере- чиcленных методов поcтроения cеток раccчитан на определенную модель пред комбинации с остальными стра повысить точ- ност д т е в щ дробления– слияния фактически приво- дит к блочным структурам. cтавления раcчетной облаcти [84]. Рассмотрим вышеперечисленные стратегии адаптации применительно к обтеканию преграды в прямоугольной расчетной области. Стратегия полной регенерации применяется при выборе шагов разбиения начальной равномер- ной сетки. Она может успешно применяться в тегиями для повышения их эффективности. При использовании регулируемых шагов РС в зонах с большими гради- ентами параметров (стратегия перемещения узлов сетки) для уменьшения временных затрат зафиксируем число расчетных ячеек в каждом из направ- лений разбиения. Новая РС получается из равномерной с помощью переме- щения узлов. Таким образом повышается густота РС в областях локализации особенностей решения за счет её разрежения в остальных областях. Такой подход был применен в работе [85], когда строилась регулярная прямоу- гольная сетка с неравномерными шагами по осям (рис. 4). Фактически, вдоль каждого сеточного направления использовались несколько размеров шагов: меньшие – для зон c большими градиентами параметров, большие – для ос- тальных областей. Этот простой метод позволяет значительно ь расчетов, не допуская увеличения числа ячеек. Стратегия локального дробления – слияния ячеек РС сводится к включе- нию в сетку дополнительных узлов в зонах с большими градиентами пара- метров при одновременном удалении (или без него) лишних узлов в областях без особенностей. Эта проце- дура может быть применена к «нулевой» РС с равномерным разбиением. На ней могут быть вычислены градиенты, используемые для построе- ния а аптивной РС. Приме- нение такого подхода позво- ляе еще больш повысить точность вычисления пара- метро без су ественного увеличения расчетного вре- мени. Стратегия V∞ Рис. 4 55 Рассмотрим структуру из регулярных сеток, регулярно разбитую на точ- но стыкующиеся по границам блоки. Достоинством такого подхода является простота получения требуемого разбиения ячеек РС в проблемных областях. Недостатком могут быть трудности, связанные с определением границ бло- ков. Кроме того, может усложняться поиск соседней ячейки в требуемом на- правлении, так как в глобальном масштабе могут теряться сеточные направ- ления, что неизбежно приведет к увеличению расчетного времени. V∞ Рис. 5 Частным случаем блочных структур можно считать иерархические блоч- ные структуры («деревья» с несколькими вложениями), когда мелкие сетки находятся внутри более грубых. Основная идея такой РС – локальное измене- ние размера ячеек в отдельных областях – полностью соответствует основ- ным требованиям, предъявляемым к РС в МПЧ (рис. 5). Одно из главных дос- тоинств «деревьев» состоит в компактной организации элементов сетки, что позволяет обеспечить высокоэффективный доступ к данным и их быструю обработку. При этом можно воспользоваться множеством уже готовых алго- ритмов обхода ячеек и манипулирования деревьями различных форм. К не- достаткам относится усложнение алгоритма по сравнению с регулярной сет- кой. Кроме этого, максимальную степень вложенности блоков может ограни- чивать привязка к языку программирования и тем самым делать неэффектив- ными квадро- и октодеревья. Выходом может стать использование их анало- гов, для которых регулируют величину ячейки не степенью вложенности, а кратностью разбиения корневых ячеек, поставив её в зависимость от местных V∞ Рис. 6 56 градиентов параметров или от местных длин свободного пробега молекул на «нулевой» сетке. Полученная таким образом сетка будет локально- равномерной с различной плотностью разбиения корневых ячеек и един- ственным уровнем вложения (рис. 6). Иерархическую блочную структуру с единичным уровнем иерархической глубины можно рассматривать как разновидность организованной специаль- ным образом многоблочной структуры. Она сочетает в себе достоинства этих двух подходов, нивелируя некоторые алгоритмические недостатки. В частно- сти, поскольку границы блоков совпадают с границами корневых ячеек, ав- томатизируется определение границ блоков и отпадает необходимость про- верки их точного совпадения. Поскольку уровень иерархической глубины РС минимален, такая сетка строится достаточно быстро и, кроме того, алгоритм обхода остается достаточно простым. При этом благодаря наличию системы двойной индексации ячеек сохраняется высокоэффективный доступ к сосед- ним ячейкам, а также реализуется основная идея – возможность использова- ния более мелких ячеек только в проблемных зонах расчетной области. При использовании блочной организации сетки в газодинамических за- дачах обтекания преграды появляется проблема одновременного сохранения структуры сетки и выполнения условия непроницаемости поверхности пре- грады. Эта проблема преодолима при аналитическом задании геометрии об- текаемого тела. В этом случае вопрос о столкновении движущейся молекулы с поверхностью тела можно решить, вводя условие непроницаемости и схему отражения от поверхности преграды. Тогда нет необходимости задавать адаптированную к поверхности обтекаемого тела внутреннюю границу физи- ческой области, а полученная сетка полностью сохраняет свою структуру. Таким образом, для решения задач газовой динамики с помощью стати- стического МПЧ наиболее экономными по затратам машинного времени яв- ляются декартовы прямоугольные регулярные сетки с иерархически-блочной организацией. Величина расчетной ячейки при этом регулируется кратностью разбиения корневых ячеек начальной равномерной РС в зависимости от оп- ределяющих локальный режим течения местных длин свободного пробега. 1. Верификация моделей и методов в динамике разреженных газов / В. Н. Гусев, И. В. Егоров, А. И. Ерофеев, В. П. Провоторов // Изв. РАН. – 1999. – № 2. – С. 129 – 134. 2. Егоров И. В. Сопоставление моделирования гиперзвукового обтекания плоской пластины на основе метода Монте-Карло и уравнений Навье – Стокса / И. В. Егоров, А. И. Ерофеев // Изв. РАН. МЖГ. – 1997. – № 1. – С. 133 – 145. 3. Haviland I. K. Application of the Monte-Carlo method to heat transfer in a rarefied gas / I. K. Haviland, M. L. Lavin // Phys. Fluids. – 1962. – V. 5, № 11. – P. 1399 – 1405. 4. Хэвиленд Дж. К. Решение двух задач о молекулярном течении методом Монте-Карло / Дж. К. Хэвиленд // Вычислительные методы в динамике разреженных газов. – М. : Мир, 1969. – С. 7 – 115. 5. Григорьев Ю. Н. Численные методы механики сплошной среды / Ю. Н. Григорьев, М. С. Иванов, Н. М. Харитонова // ВЦ СО АН СССР. – 1971. – Т. 2, № 4. – С. 101 – 107. 6. Власов В. И. Консервативный вариант метода пробных молекул (Монте-Карло) / В. И. Власов // Числен- ные и аналитические методы в динамике разреженных газов : VIII Всесоюзная конф. по динамике разр. газов : труды. – М., 1986. – С. 81 – 85. 7. Власов В. И. Улучшение метода статистических испытаний (Монте-Карло) для расчета течений разре- женных газов / В. И. Власов // Докл. АН СССР. – 1966. – Т. 167, № 5. – С. 1016 – 1018. 8. Власов В. И. Расчет методом Монте-Карло потока тепла между параллельными пластинами в разрежен- ном газе / В. И. Власов // Ученые записки ЦАГИ. – 1970. – Т. 1, № 4. – С. 46 – 51. 9. Власов В. И. Расчет аэродинамических характеристик плоской пластины бесконечного размаха в гипер- звуковом потоке разреженного газа / В. И. Власов // Ученые записки ЦАГИ. – 1971. – Т. II, № 6. – С. 116 – 120. 10. Власов В. И. Расчет обтекания пластины под углом атаки потоком разреженного газа / В. И. Власов // Ученые записки ЦАГИ. – 1973. – Т. IV, № 1. – С. 17 – 24. 11. Власов В. И. Расчет течения разреженного газа около пластины под углом атаки / В. И. Власов // Уче- ные записки ЦАГИ. – 1975. – Т. VI, № 2. – С. 48 – 56. 57 12. Басс В. П. Молекулярная газовая динамика и ее приложения в ракетно-космической технике / В. П. Басс. – Киев : Наук. думка, 2008. – 272 с. 13. Басс В. П. Об одном алгоритме реализации метода Монте-Карло для решения задач динамики разре- женного газа / В. П. Басс, Л. Л. Печерица // Техническая механика. – 2006. – № 1. – С. 67 – 79. 14. Дудникова Г. И. О моделях частиц на неструктурированных сетках / Г. И. Дудникова, Д. В. Романов, М. П. Федорук // Вычислительные технологии. – Новосибирск : Учреждение Российской академии наук Институт вычислительных технологий Сибирского отделения РАН, 1998. – Т. 3, № 6. – С. 30 – 46. 15. Галанин М. П. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространствен- ных областей: прямые методы / М. П. Галанин, И. А. Щеглов. – М., 2006. – 32 с. (Препринт / ИПМ им. М. В. Келдыша РАН, № 10) 16. Aldroubi A. Wavelets on Irregular Grids with Arbitrary Dilation Matrices, and Frames Atoms for L2 (M.d) / A. Aldroubi, С. Cabrelli, U. Molter // Appl. Comput. Harmonic Anal. – 2004. – V. 17. – P. 119 – 140. 17. Borouchaki H. Fast Delaunay Triangulation In Three Dimensions / H. Borouchaki, S. Lo // Computer Methods In Applied Mechanics And Engineering. – 1995. – V. 128. – P. 153 – 167. 18. Joe B. Construction Of Three-Dimensional Delaunay Triangulations Using Local Transformations / B. Joe // Computer Aided Geometric Design. – 1991. – V. 8. – P. 123 – 142. 19. Rivara C. M. Cost analysis of the longest-side refinement algorithm for triangulations / C. M. Rivara, M. Vemere // Engineering with Computers. – 1996. – № 3 – 4. – P. 224 – 234. 20. Skopina M. Multiresolution Analysis of Periodic Functions / M. Skopina // East Journal on Approximations. – 1997. – V. 3, № 2. – P. 203 – 224. 21. Азаренок Б. Н. О построении структурированных сеток в двумерных невыпуклых областях с помощью отображений / Б. Н. Азаренок // Ж. вычисл. матем. и матем. физ. – 2009. – Т. 49, № 5. – С. 826 – 839. 22. Вагер Б. Г. Сплайны при решении прикладных задач метеорологии и гидрологии / Б. Г. Вагер, Н. К. Серков. – Л. : Гидрометеоиздат, 1987. – 160 с. 23. Демьянович Ю. Локальный базис всплесков на неравномерной сетке / Ю. Демьянович // Зап. научн. сем. ПОМИ. – 2006. – Т. 334. – С. 84 – 110. 24. Андерсон Д. Вычислительная гидромеханика и теплообмен : в 2-х т. / Д. Андерсон, Дж. Таннехил, Р. Плетчер. – М. : Мир, 1990. – 728 с. 25. Thompson J. F. Numerical grid generation. Foundations and applications / J. F. Thompson, Z. U. A. Warsi, C. W. Mastin. – North Holland, 1985. – 483 p. 26. Bramkamp F. Development of a flow solver employing local adaptation bazed on multiscale analysis on B- spline grids / F. Bramkamp, J. Ballmann, S. Muller // 8th Annual Conf. of the CFD Society, 11 to 13, June, 2000, Montreal, Canada : proceedings. 27. Флетчер К. Вычислительные методы в динамике жидкостей : в 2 т. / К. Флетчер. – М. : Мир, 1991. – 1056 с. 28. Smith R. E. Algebraic Grid Generation / R. E. Smith // Applied Mathematics and Computation – Elsevier Science Publishing Company, 1982. – V. 10 – 11. – P. 137 – 170. 29. Eiseman P. R. A multi-surface method of coordinate generation / P. R. Eiseman // J. of Comp. Phys. – 1979. – V. 33, № 1. – P. 118 – 150. 30. Eiseman P. R. Coordinate generation with precise controls over mesh properties / P. R. Eiseman // J. of Comp. Phys. – 1982. – V. 47, № 3. – P. 331 – 351. 31. Eriksson L. E. Generation of boundary-conforming grids around wing-body configurations using transfinite interpolation / L. E. Eriksson // AIAA J.– 1982. – V. 20, № 10. – P. 1313 – 1320. 32. Fedosenko N. Application of exact solutions of some elliptic equations for generation of two- and multidimentional analytical grids / N. Fedosenko, E. Sokolov // ALGORITMY 2002 : Conference of Scientific Computing : proceedings. – P. 253 – 259. 33. Соколов Е. И. Об одном методе построения эллиптических сеток, задаваемых явными аналитическими выражениями / Е. И. Соколов, Н. Б. Федосенко // Матем. моделирование. – 2003. – Т. 15, № 6. – С. 101 – 106. 34. Smith R. E. Analytic and Approximate Boundary Fitted Coordinate Systems for Fluid Flow Simulation / R. E. Smith, B. L. Weigel // 18-th Aerospace Sciences Meeting, 14-16 Jan., 1980, Pasadena, California. – 1980. 35. Eiseman P. К. Mesh Generation Using Algebraic Techniques / P. К. Eiseman, R. E. Smith // Numerical Grid Generation Techniques. – NASA Conference Publication, 1980. – P. 73 – 120. 36. Middlecoff J. F. Direct Control of the Grid Point Distribution in Meshes Generated by Elliptic Equations / J. F. Middlecoff, P. D. Thomas // AIAA Paper. – 1980. – V. 18, № 6. – P. 652 – 656. 37. Thompson J. F. Use of Numerically Generated Body-Fitted Coordinate Systems for Solution of the Navier- Stokes Equations / J. F. Thompson, F. C. Thames, С. W. Mastin, S. P. Shanks // AIAA 2nd Computational Fluid Dynamics Conference, Hartford, Connecticut : proceedings. – 1975. – P. 68 – 80. 38. Thompson J. F. Numerical Solution of Flow Problems Using Body-Fitted Coordinate Systems / J. F. Thompson // Computational Fluid Dynamics. – Washington : Hemisphere Publishing Corp., 1980. – 98 p. 39. Steger J. L. Use of Hyperbolic Partial Differential Equations to Generate Body Fitted Coordinates / J. L. Steger, R. L. Sorenson // Numerical Grid Generation Techniques. –1980. – P. 463 – 478. 40. Неструктурированные адаптивные сетки для задач математической физики (обзор) / Л. В. Круглякова, А. В. Неледова, В. Ф. Тишкин, А. Ю. Филатов // Матем. моделирование. – 1998. – Т. 10, № 3. – С. 93 – 116. 41. Barth T. J. Aspects of unstructured grids and finite-volume solvers for the Euler and Navier – Stokes equations / T. J. Barth // Computational Fluid Dynamics. – 1994. – № 4. 42. Войнович П. А. Моделирование разрывных течений газа на неструктурированных сетках. 1. Построение квазимонотонной схемы повышенного порядка аппроксимации / П. А. Войнович, Д. М. Шаров // Мат. моделир. – 1993. – Т. 5, № 7. – С. 86 – 100. 58 http://www.sciencedirect.com/science/journal/00963003 43. Разностные схемы на нерегулярных сетках / А. А. Самарский, А. В. Колдоба, Ю. А. Повещенко, В. Ф. Тишкин, А. П. Фаворский. – Минск, 1996. – 273 с. 44. Thompson J. F. A survey of dynamically adaptive grids in the numerical solution of partial differential equations / J. F. Thompson / Appl. Numer. Math. – 1985. – № 1. – P. 3 – 28. 45. Томпсон Дж. Ф. Методы расчета сеток в вычислительной аэродинамике / Дж. Ф. Томпсон // Аэрокос- мическая техника.– 1985. – Т. З, № 8. – С. 141 – 171. 46. Venkatakrishnan V. Perspective on unstructured grid flow solvers / V. Venkatakrishnan // AIAA J. – 1996. – V. 34, № 3. – P. 553 – 547. 47. Powell K. G. Adaptive-mesh algorithms for computational fluid dynamics / K. G. Powell, P. L Roe // Algorithmic Trends in Computational Fluid Dynamics. – Springer-Verlag, 1993. – P. 303 – 337. 48. Pironneau O. Advances for the simulation of compressible viscous flows on unstructured meshes / O. Pironneau // Algorithmic Trends in Computational Fluid Dynamics. – Springer-Verlag, 1993. – P. 33 – 57. 49. Thompson J. F. A reflection on grid generation in the 90s: trends, needs, and influences / J. F. Thompson // Numerical Grid Generation in Computational Fluid Simulations. – Mississippi, 1996 – P. 1029 – 1110. 50. Freitag L. A. A Comparison of Tetrahedral Mesh Improvement Techniques / L. A. Freitag, C. Ollivier-Gooch // Meshing Roundtable : 5th International Conference, October, 1996, Sandia National Laboratories : proceedings. – 1996. – P. 87 – 106. 51. George P. L. Tet Meshing : Construction, Optimization and Adaptation / P. L. George // 8th International Meshing Roundtable : proceedings. – 1999. – P. 133 – 141. 52. Rassineux A. Generation and Optimization of Tetrahedral Meshes by Advancing Front Technique / A. Rassi- neux // International Journal for Numerical Methods in Engineering. – Wiley, 1998. – V. 41. – P. 651 – 674. 53. Галанин М. П. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространствен- ных областей : итерационные методы / М. П. Галанин, И. А. Щеглов. – М., 2006. – 32 с. (Препринт / ИПМ им. М. В. Келдыша РАН, № 9) 54. Корнеев В. Г. Схемы метода конечных элементов высоких порядков точности / В. Г. Корнеев. – Л. : Изд. Ленингр. ун-та, 1977. – 206 c. 55. Shimada K. Bubble Mesh: Automated Triangular Meshing of Non-manifold Geometry by Sphere Packing / K. Shimada, D. C. Gossard // 3rd ACM Symposium on Solid Modeling and Applications, 17-19 May, 1995, Salt Lake City, UT, USA : proceedings. – New York : ACM Press, 1995. – P. 409 – 419. 56. Baker T. J. Automatic Mesh Generation for Complex Three-Dimensional Regions Using a Constrained Delaunay Triangulation / T. J. Baker // Engineering With Computers. – 1989. – № 5. – P. 161 – 175. 57. Buratynski E. K. A Three-Dimensional Unstructured Mesh Generator for Arbitrary Internal Boundaries / E. K. Buratynski // Numerical Grid Generation in Computational Fluid Mechanics. – Swansea : Pineridge Press, 1988. – P. 621 – 631. 58. Rebay S. Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm / S. Rebay // Journal Of Computational Physics. – 1993. – V. 106. – P. 125 – 138. 59. Shimada K. Anisotropic Triangular Meshing of Parametric Surfaces via Close Packing of Ellipsoidal Bubbles / K. Shimada, A. Yamada, T. Itoh // 6th International Meshing Roundtable : proceedings. – USA : Sandia Corporation, 1997. – P. 75 – 390. 60. Скворцов А. В. Обзор алгоритмов построения триангуляции Делоне / А. В. Скворцов // Вычислительные методы и программирование. – 2002. – № 3. – С. 14 – 39. 61. Weatherill N. P. Efficient three-dimensional Delaunay triangulation with automatic point creation and imposed boundary constrains / N. P Weatherill, О. Hassan // Int. J. Numer. – Meth. Eng. – 1994. – V. 37, № 12. – P. 2005 – 2039. 62. Lohner R. Generation Of Three-Dimensional Unstructured Grids By The Advancing Front Method / R. Lohner, P. Parikh // International Journal of Numerical Methods in Fluids. – 1988. – Vol. 8. – P. 1135 – 1149. 63. Lo S. H. Volume Discretization into Tetrahedra-I. Verification and Orientation of Boundary Surfaces / S. H. Lo // Computers and Structures. – 1991. – V. 39, № 5. – P. 493 – 500. 64. Lo S. H. Volume Discretization into Tetrahedra-II. 3D Triangulation by Advancing Front Approach / S. H. Lo // Computers and Structures. – 1991. – V. 39, № 5. – P. 501 – 511. 65. Owen S. A Survey of Unstructured Mesh Generation Technology : proceedings / S. Owen // Meshing Roundtable : 7th International, Oct, 1998, Dearborn : proceedings. – Dearborn, 1998. – P. 239 – 269. 66. Rubbert P. E. Patched coordinate systems / P. E. Rubbert, K. D. Lee // Numerical Grid Generation / ed. by J. F. Thompson. – 1982. – P. 235 – 252. 67. Лабусов А. Н. Генерация сетки [Электронный ресурс] / А. Н. Лабусов. – Режим доступа к документу : http://www.spbcas.ru/cfd/techn/Grids.htm. 68. Игнатьев А. А. Построение регулярных сеток с помощью механической аналогии / А. А Игнатьев // Математическое моделирование. – 2000. – Т. 12, № 2. – С. 101 – 105. 69. Noak R. W. A three-dimensional hybrid grid generation technique / R. W. Noak, J. P. Steinbrenner // Computational Fluid Dynamics : 12-th AIAA Conference : materials. – San-Diego, 1995. – P. 413 – 423. 70. Benek J. A. Extended chimera grid embedding scheme with application to viscous flows / J. A. Benek, T. L. Donegan // Computational Fluid Dynamics : 8th AIAA Conference, 9-11 June, 1987, Honolulu : materials. – New York : AIAA, 1987. – P. 272 – 282. 71. Samet H. Implementing Ray Tracing with Octrees and Neighbor Finding. / H. Samet // Computer and Graphics. – 1989. – V. 13, № 4. – P. 445 – 460. 72. Samet H. The Quadtree and Related Hierarhical Data Structures / H. Samet // ACM Comput. Surveys. – 1984. – V. 16, № 2. – P. 187 – 260. 59 73. Samet H. Computing Geometric Properties of Images Represented by Linear Quadtrees / H. Samet, M. Tam- minen // IEEE Transaction on Patter Analysis and Machine Intelligenc. – 1985. – V. 7, № 2. – P. 229 – 240. 74. Samet H. Neighbor Finding Techniques for Images Represented Quadtrees / H. Samet // Computer Graphics and Image processing. – 1982. – V. 17, № 1. – P. 37 – 57. 75. Burroughs P. A. Principles of Geographical Information Systems for Land Resources Assessment / P. A. Burroughs. – Oxford : Clarendon Press, 1994. – 193 p. 76. Samet H. The Design and Analysis of Spatial Data Structures / H. Samet. – 1990. – 499 p. 77. Carlbom I. A Hierarchical Data Structure for Representing the Spatial Decomposition of 3D Objects / I. Carlbom, I. Chakravarty and D. Vanderschel // Frontiers in Computer Graphics. – New York : Springer-Verlag, 1985. – P. 2 – 12. 78. Kaufman A. E. Volume Graphics. Sidebar : Fundamentals of Voxelization / Arie E. Kaufman, Daniel Cohen- Or, Roni Yagel // IEEE Computer. – 1993. – V. 26, № 7. – P. 51 – 64. 79. Игнатенко А. Методы представления дискретных трехмерных данных [Электронный ресурс] / А. Игнатенко // Компьютерная графика и мультимедиа. – 2003. – Вып. 1. – Режим доступа к документу : http://cgm.computergraphics.ru/content/view/22. 80. 3D Pixel / Voxel [Электронный ресурс]. – Режим доступа к информации : http://www.bilderzucht.de/blog/3d-pixel-voxel/. 81. Лисейкин В. Д. Обзор методов построения структурных адаптивных сеток / В. Д. Лисейкин // ЖВМиМФ. – 1996. – Т. 36, № 1. – С. 3 – 41. 82. Feedback, Adaptivity and A-Posterior Estimates in Finite Elements: Aims, Theory and Experience / E. R. Arantes, E. Oliveira, I. Babuska, O. C. Zienkiewicz, J. P. Gado, eds. // International Conference on Accuracy Estimates and Adaptive Refinement in Finite Element Computation, June, 1984, Lisbon, Portugal : proceedings. – Lisbon, 1984. 83. Rivara M. A 3D refinement algorithm suitable for adaptive and multi-grid techniques / M. Rivara, C. Levin // J. Comp. and Appl. Math. – 1992. – № 8. – P. 281 – 290. 84. Field D. A. The legacy of automatic mesh generation from solid modeling / D. A. Field // Computer-Aided Geometric Design. – 1995. – V. 12, № 7. – P. 651 – 673. 85. Басс В. П. Гиперзвуковое обтекание теплоизолированного цилиндра разреженным газом / В. П. Басс, Л. Л. Печерица // Вісник Дніпропетровського університету. Механіка. – 2006. – Т. 1, вип. 10. – С. 50 – 60. Институт технической механики Получено 23.02.2013, НАН Украины и ГКА Украины, в окончательном варианте 11.03.2013 Днепропетровск 60 http://loi.sscc.ru/gis/QuadTree/QuadTree.html#references http://loi.sscc.ru/gis/QuadTree/QuadTree.html#references

Similar Items