Журнал “Информационные технологии”, 2010г. (в печати) icon

Журнал “Информационные технологии”, 2010г. (в печати)



НазваниеЖурнал “Информационные технологии”, 2010г. (в печати)
Дата17.10.2016
Размер
ТипУроки, сочинения

Журнал “Информационные технологии”, 2010г. (в печати)

УДК 519.63

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

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

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

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

Введение

В ряде задач механики деформируемого тела, к примеру, в задачах сейсмической разведки, используется сеточно-характеристический метод [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. Челноков Ф. Б. Численное моделирование деформационных динамических процессов в средах со сложной структурой // Диссертация на соискание ученой степени кандидата физико-математических наук.

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

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 Полиномиальные интерполянты.

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

Иллюстрации:



Рис. 1




Рис. 2




Рис. 3




Рис. 4

- -



Похожие:

Журнал “Информационные технологии”, 2010г. (в печати) iconПрограмма курса оптические информационные технологии курс «Оптические информационные технологии»
Курс «Оптические информационные технологии» реализуется в рамках направления подготовки бакалавров 552800 «Информатика и вычислительная...
Журнал “Информационные технологии”, 2010г. (в печати) iconМетодические указания и задания по выполнению практических работ для студентов специальности 1-25 01 13 Экономика и управление туристической индустрией, Мультимедийная презентация
Разработка модели традиционного обучения в высшей школе. Лекция по курсу: «Информационные технологии в туризме» на тему: «Информационные...
Журнал “Информационные технологии”, 2010г. (в печати) iconУрок обобщения знаний по теме. Тема : «Преобразование рациональных выражений». Класс : Технологии : Технология уровневой дифференциации обучения, компьютерные (новые информационные) технологии обучения
Технологии: Технология уровневой дифференциации обучения, компьютерные (новые информационные) технологии обучения
Журнал “Информационные технологии”, 2010г. (в печати) iconТесты по информатике. Полезные программы. В частности, Конспекты школьника
Информатика в школе Информатика, информационные технологии, интернет-технологии, web-дизайн, основы теории баз данных, программирование,...
Журнал “Информационные технологии”, 2010г. (в печати) icon«информационные технологии как средство повышения эффективности преподавания математики» Автор: преподаватель математики гоу спо «Борисовский агромеханический техникум»
«информационные технологии как средство повышения эффективности преподавания математики»
Журнал “Информационные технологии”, 2010г. (в печати) iconИспользование кейс-технологии на уроках географии
Учебник. Учебник «Начальный курс географии» под редакцией Герасимова Т. П., Неклюкова Н. П. (М.: Дрофа, 2010г.)
Журнал “Информационные технологии”, 2010г. (в печати) iconКонспект интегрированного урока в 1 классе Тема урока : «Вежливые слова» Риторика Тема: «Вежливые слова» Внеклассное чтение Тема: В. Осеева «Волшебное слово»
Образовательные технологии: игровые технологии (Б. П. Никитин), технология интегрированного обучения, информационные технологии
Журнал “Информационные технологии”, 2010г. (в печати) iconПубликации 2007-2008: Аксенова А. А. «Преподавание элективного курса «Делопроизводство и офисные технологии»
Аксенова А. А. «Преподавание элективного курса «Делопроизводство и офисные технологии» в классах социально-гуманитарного профиля»...
Журнал “Информационные технологии”, 2010г. (в печати) iconИнформационные системы и федеральные образовательные порталы
Федеральный образовательный портал "Информационно-коммуникационные технологии в образовании"
Журнал “Информационные технологии”, 2010г. (в печати) iconУкраинская ассоциация цифровой и трафаретной печати профиль Ассоциации
Трафаретной Печати – это объединение печатных компаний и компаний-поставщиков материалов из Украины, созданное с целью организации...
Разместите ссылку на наш сайт:
Уроки, сочинения


База данных защищена авторским правом ©izlov.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
связаться с нами