Библиотека по интерполяции высоких порядков на неструктурированных треугольных и тетраэдральных сетках

Размещено на http://www.allbest.ru/

Библиотека по интерполяции высоких порядков на неструктурированных треугольных и тетраэдральных сетках

И.Б. Петров, доктор физ.-мат. наук, проф., зав. каф., А.В. Фаворская, студентка, Московский физико-технический институт (государственный университет), e-mail: petrov@mipt.ru

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

Ключевые слова: интерполяция высоких порядков, треугольные сетки, тетраэдральные сетки, неструктурированные сетки.

High-order interpolation on unstructured triangular and tetrahedral grids library. Petrov I.B., Favorskaya A.V.

We developed methods of high-order interpolation on unstructured triangular and tetrahedral grids: polynomial interpolation from the first to the fifth degree inclusive, interpolation with the help of a limiter based on polynomial interpolation from the second to the fifth degree inclusive, straight-line interpolation. The library that implements all these methods was written and we carried out its numerical testing.

Keywords: high-order interpolation, triangular grids, tetrahedral grids, unstructured grids. интерполяция полином тетраэдральный

В ряде задач механики деформируемого тела, к примеру, в задачах сейсмической разведки, используется сеточно-характеристический метод [1] на неструктурированных треугольных для двумерных задач и тетраэдральных для трехмерных задач сетках. Как правило, при выборе таких типов сеток ограничиваются методами первого порядка аппроксимации, так как вычисляются только значения в вершинах, а для определения функции, более сложной, чем линейная, требуются значения в большем числе точек.

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

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

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

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

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

Когда речь идет о треугольных сетках, под векторами будем понимать двумерные векторы вида , когда речь идет о тетраэдральных сетках - трехмерные. Обозначим векторы вершин треугольника за , , . А векторы вершин тетраэдра - за , , , .

Для каждого заданного по соответствующим формулам вычисляются веса опорных точек и . Значение полинома в искомой точке определяется по формулам

, (1)

(2)

для треугольников и тетраэдров соответственно.

В формулах (1), (2) ? значение интерполируемой функции в опорной точке .

Кусочно-линейная интерполяция

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

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

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

Кусочно-линейный интерполянт не может иметь строгих экстремумов ни в каких точках, кроме опорных.

Интерполяция с ограничителем. Приведем алгоритм построения интерполянта с ограничителем на треугольных (тетраэдральных) сетках на основе интерполяции полиномом порядка .

1) Определяем значение пробной функции заданной точке с помощью полиномиальной интерполяции порядка , пусть оно равно .

2) Определяем, в каком из малых треугольников (тетраэдров) лежит точка (В случае попадания в восьмигранник, как и при кусочно-линейной интерполяции, вводим вспомогательную ось).

3) Сравниваем с минимумом значений в вершинах и максимумом значений в вершинах этого треугольника (тетраэдра).

3.1) Если , то значение интерполянта в точке : .

3.2) Если , то значение интерполянта в точке : .

3.3) Если , то значение интерполянта в точке : .

Использование интерполяции с ограничителем позволяет устранять осцилляции полиномов, возникающие при наличии разрывов в интерполируемых функциях.

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

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

Список использованной литературы

1. Магомедов К. М., Холодов А. С. Сеточно-характеристические численные методы. -- М.: Наука, 1988.

2. Петров И. Б., Лобанов А. И. Лекции по вычислительной математике. -- М.: Интернет-Университет Информационных Технологий, 2006.

3. Челноков Ф. Б. Численное моделирование деформационных динамических процессов в средах со сложной структурой // Диссертация на соискание ученой степени кандидата физико-математических наук.

Иллюстрации

Рис. 1 Опорные точки в тетраэдре для кубической интерполяции

Рис. 2 Восьмигранник для опорных точек квадратичной интерполяции

Рис. 3 Полиномиальные интерполянты

Рис. 4. Интерполянты с ограничителем

Размещено на Allbest.ru