Аппроксимационные свойства триангуляций поверхностей тема диссертации и автореферата по ВАК РФ 01.01.01, кандидат физико-математических наук Широкий, Александр Александрович

• Широкий, Александр Александрович
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Широкий, Александр Александрович

Оглавление

Введение

1 Априорные оценки погрешности аппроксимации градиента

1.1 Основные понятия и вспомогательные утверждения

1.2 Оценка погрешности аппроксимации градиента функции градиентом кусочно-линейной функции для симплекса

2 Аппроксимационные свойства триангуляции:

2.1 Триангуляции Делоне плоских областей

2.2 Остроугольные триангуляции в пространстве

2.3 Триангуляции с углами, отделёнными от нуля

2.4 Оценка погрешности аппроксимации градиента для решений эллиптических уравнений

2.5 Триангуляции поверхностей

3 Обобщения условия Делоне

3.1 Триангуляция Делоне относительно семейства выпуклых множеств

3.2 Триангуляция Делоне относительно метрики

3.3 Триангуляция Делоне п-мерных гиперповерхностей в Жп+1

3.4 Триангуляция Делоне с коэффициентом сжатия сфер

Работа выполнена при финансовой поддержке грантов РФФИ (проект 11-01-97021-р_поволжье_а) и факультета математики и информационных технологий ВолГУ.

Введение диссертации (часть автореферата) на тему «Аппроксимационные свойства триангуляций поверхностей»

Введение

По своей тематике данная диссертационная работа выполнена на стыке нескольких разделов анализа. Главным вопросом исследования является вопрос об оценках степени аппроксимации производных гладких функций, заданных на поверхности, производными кусочно-линейных функций. Данная тематика тесно связана как с теорией расчётных сеток, так и с вопросами анализа, берущими своё начало от классического примера Карла Шварца (1890, [12]). Основным объектом исследования являются триангуляции поверхностей.

Различные разбиения и, в частности, триангуляции часто используются в задачах численного моделирования для построения расчётных сеток. Во многих случаях расчётные сетки применяются для построения аппроксимации некоторой известной функции. В этом случае встаёт вопрос о точности построенной оценки, а также об устойчивости используемой разностной схемы. Например, в работах С. К. Годунова и Г. П. Прокопова ([14], [15]) нерегулярные сетки используются для аппроксимации первых производных в составе эллиптических дифференциальных уравнений Лапласа, а также формулируются условия, которым должна удовлетворять сетка для обеспечения устойчивости результата численного моделирования. В более поздней работе С. К. Годунова, В. Т. Жукова, О. Б. Феодоритовой [16] нерегулярные сетки применяются для расчёта инвариантных подпространств для симметрических гиперболических систем.

Однако первым заметным результатом, характеризующим зависимость качества приближения от способа построения разбиения стоит признать классический пример Карла Шварца (1890, [12]), известный также как "сапог Шварца". Он представляет собой семейство приближений кругового

з

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

На самом деле геометрические параметры нерегулярной сетки оказывают непосредственное влияние на качество аппроксимации, вплоть до наличия/отсутствия сходимости. Геометрические свойства элементов нерегулярных сеток рассмаривались, например, в работах таких математиков, как S. Korotov (работа [5]), V. A. Garanzha (работа [3]), V. Т. Rajan (работа [7]) — в последней сформулирован ряд результатов, касающихся триангуляции Делоне в n-мерном евклидовом пространстве. В работе [6] авторами (Н. Pottmann, R. Krasauskas, В. Hamann, К. Joy, W. Seibold) исследуются кусочно-аффинные аппроксимации квадратичных функций в Шп и в том числе рассматривается вопрос об оптимальном приближении (с максимальными линейными участками, но при этом с приемлемой точностью) в R2 и отчасти в13. J. R. Shewchuk в работе [8] поднимает вопрос о хорошем конечном линейном элементе в I2 и в I3 с точки зрения аппроксимации градиента функции. В работе Е. А. Пабат и В. А. Клячина ([22]) исследуются свойства кусочно-линейных интерполяций поверхностей уровня функций, заданных на триангуляциях. Было показано, что для обеспечения приближения значений подойдёт любая триангуляция, однако сходимость первых производных наблюдается только для триангуляций, удовлетворяющих условию (2.5), приведённому в настоящей работе на странице 49.

При решении ряда практических задач возникает необходимость в построении триангуляций различных поверхностей. В частности, В. М. Миклюко-вым в работе [34] исследовалась проблема триангуляции локально липшице-вой поверхности. Учитывая "популярность" триангуляции Делоне естественным, казалось бы, образом возникает желание построить соответствующее обобщение на случай поверхностей. Однако, несмотря на то, что алгоритм построения триангуляций Делоне в евклидовых пространствах произвольной конечной размерности был предложен ещё в 1934 году самим Б. Н. Делоне (работа [1]), известные алгоритмы построения триангуляции поверхно-

сти предполагают построение обычной плоской триангуляции с последующим проецированием её на поверхность (см., например, работы А. В. Сквор-цова и Н. С. Мирзы ([39], [40]). Ясно, что проекция плоской триангуляции Делоне на поверхность в общем случае не будет проявлять никаких замечательных свойств, характерных для триангуляции Делоне. Таким образом, возникает задача построения триангуляции Делоне на поверхности с сохранением свойств, присущих её классическому варианту.

Основным объектом исследования данной диссертационной работы являются триангуляции поверхностей.

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

Методика исследования основана на построении верхних оценок модуля разности градиентов кусочно-аффинной аппроксимации и исследуемых с её помощью функций класса С1, С2 или С2'а-решений эллиптических уравнений.

Все результаты, полученые в работе, являются новыми. Выделим основные из них.

1. Априорные оценки разности градиентов в треугольнике и тетраэдре для непрерывно дифференцируемых функций в евклидовой метрике и в метрике поверхности, содержащей их вершины.

2. Оценки погрешности аппроксимации градиентов в евклидовой метрике для триангуляции Делоне плоской области и остроугольной триангуляции в пространстве.

3. Оценки погрешности аппроксимации градиентов для остроугольной триангуляции в метрике поверхности.

4. Теоремы о сходимости градиентов кусочно-аффинной аппроксимации, построенной над триангуляциями £-сетей в М™, к градиентам С2-гладкой функции.

5. Обобщение условия пустого шара на случай п-мерных гиперповерхностей в (п + 1)-мерном пространстве. Оценка погрешности вычисления градиентов для триангуляций Делоне двумерных поверхностей.

Диссертация носит теоретический характер. Результаты диссертации могут найти применение в задачах, связанных с моделированием поверхностей, в частности, в геодезии и картографии, в задачах компьютерной графики (построение полигональных моделей и связанные вопросы), различных пространственных задачах, а также могут быть использованы специалистами при построении расчётных нерегулярных сеток для решения различных вычислительных задач. Материал диссертации может служить основой спецкурсов, написания курсовых, дипломных и других научных работ в высших учебных заведениях, где проводятся исследования по данной тематике.

Апробация работы. Основные результаты работы докладывались на международных и российских конференциях: Девятой международной школе-конференции "Теория функций, её приложения и смежные вопросы" (Казань, 01 - 07 июля 2009 г.), 15-й Саратовской зимней школе "Современные проблемы теории функций и их приложения" (Саратов, 27 января -3 февраля 2010 г.), семинаре механико-математического факультета Томского государственного университета под руководством проф. А. В. Скворцо-ва, семинаре-совещании "Сети в анизотропных пространствах" (Волгоград, 21 -23 апреля 2011 г.), десятой международной школе-конференции "Теория функций, её приложения и смежные вопросы" (Казань, 30 июня - Об июля 2011 г.), 16-й Саратовской зимней школе "Современные проблемы теории функций и их приложения" (Саратов, 27 января - 3 февраля 2012 г.), а также на конференциях и семинарах Волгоградского государственного университета.

Публикации. Основные результаты диссертации опубликованы в работах [23] - [30], [43], [44].

Структура и объём диссертации. Диссертация изложена на 92 страницах и состоит из введения, трёх глав и списка литературы. В работе используется подчинённая нумерация. При этом нумерация параграфов и формул подчинена нумерации глав, нумерация определений, лемм, теорем, следствий, утверждений — нумерации параграфов. Библиография диссертации содержит 44 наименования, включая работы автора.

Пусть I) С Г - некоторая область в Для функций класса С1 (Б) через обозначим вектор градиента в точке х е Б, а производную

по направлению произвольного вектора £ — через скалярное произведение векторов У/(сс) и

|=о-

Если в К71 имеется набор точекро, р\, ..., рь, где 1 < к < п, то обозначим через ¿'(ро, • • •» ¿/-мерный симплекс с вершинами в этих точках. Будем предполагать, что векторы р\ — ри, р2 — ро, ■ Рк — Ро линейно независимы. Если из этого набора точек убрать точку р{, где г = 0, ..., к, то можно построить (к — 1)-мерный симплекс, который обозначим через Этот симплекс является (к — 1)-мерной гранью симплекса 3(ро, ..., рк). Обозначим через П^ (к — 1)-мерную гиперплоскость, содержащую а через щ единичный вектор внешней нормали к П^, лежащий в плоскости симплекса ¿>(Ро, • • •, Рк)-

По отношению к плоскости симплекса 5 произвольный вектор у £ Мп может быть разложен в сумму

где ут — ортогональная проекция вектора у на плоскость симплекса 5, а Vм — ортогональное дополнение проекции у.

Зафиксируем произвольный симплекс 5 С И. Для функции / £ С1 (Б) построим аффинную функцию х) вида

Ь^х) = (а, х) + 6, а е Мп, Ъ е М

такую, что

/(р») = Ь1(рг), при г = 0, ..., к и ам = 0. Пусть вектор-функция Б: Б —> непрерывна. Тогда функцию £) = зир{|^(х1) - : ^ь С D, и \хг - х2\ <

назовём модулем непрерывности функции .Р. Величину

назовём погрешностью вычисления У/(ро) посредством функции Lf(x).

7

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

Обозначим

т

/(т)=Л I+ т).

о

Теорема 1.2.1. Пусть Б С И — некоторый треугольник с заданной в нём аффинной функцией Ь${х), построенной для некоторой непрерывно дифференцируемой в области Б функции /(х). Тогда, если (рз и 4 обозначают значение угла при вершине ро и длину максимальной стороны треугольника Б соответственно, то справедлива оценка:

3/(4) - 4)

<

вт (рз

Теорема 1.2.2. Пусть к — 2 и вершины треугольника 5 лежат на двумерной гладкой поверхности И С В С Предположим, что угол между плоскостью этого треугольника и касательной плоскостью к поверхности

7Г

в точке ро равен а, 0 < а < —. Если функция / £ С1 (И), то выполнено:

мы - VL/ыI < з/№):^/,4)+81па8ир |у/(а:)1 _

эт <рв х&п

Здесь V обозначает градиент дифференцируемой функции в метрике поверхности .Р.

Теорема 1.2.3. Пусть Б С -О — некоторый тетраэдр с заданной в нём аффинной функцией построенной для некоторой непрерывно диффе-

ренцируемой в области Б функции /(х). Обозначим через 6з величину угла между вектором Р2~Ро и двумерной гранью, лежащей напротив вершины Р2, через величину угла при вершине р\ треугольника рърхръ и через 4 длину максимального ребра тетраэдра Б. Тогда имеет место оценка:

8/(4)

(у/ы - УЬ/(р0))Т

<

вт (рз вт 9з

Теорема 1.2.4. Пусть вершины тетраэдра в лежат на трехмерной гладкой поверхности Б С В С Кп. Предположим, что угол между плоско-

стью тетраэдра и касательной плоскостью к поверхности в точке ро pair

вен а, 0 < а < —. Если функция / 6 Cl(D), то выполнено:

IV/Ы - VL,(po)| < . ü + sin a sup |V/(ar)| .

smipssmds 1

Пусть в области Del" задана последовательность конечных наборов точек. Для каждого такого набора рассмотрим его триангуляцию.

Определение 2.0.1. Триангуляцией конечного набора точек назовём набор не имеющих общих внутренних точек симплексов с вершинами из этого набора, образующих покрытие участка пространства, ограниченного выпуклой оболочкой рассматриваемого набора точек.

Определение 2.0.2. Триангуляцию будем называть остроугольной, если для каждого симплекса углы между двумя любыми смежными его гранями острые.

Определение 2.0.3. Триангуляция набора точек называется триангуляцией Делоне, если описанная сфера всякого симплекса триангуляции не содержит внутри себя каких-либо точек из этого набора.

Для всякого симплекса S длину максимальной его стороны обозначим . Для некоторой триангуляции Т положим

d+(T) = max dt.

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

d+(Tm) —> 0 при т —» оо и (2.1)

\/е > ОЗт0 eN : Mm > т0 и Vx G D 3 a G Рт : \а - х\ < е. (2.2)

Условие (2.2) означает, что Рт является е-сетью при всех достаточно больших т.

Рассмотрим некоторую функцию f(x) класса Cl(D) и для каждого т построим кусочно-аффинную функцию fm(x) такую, что fm(a) = f(a) для любой точки а £ Рт.

Заметим, что при выполнении условий (2.1) и (2.2) последовательность fm(x) равномерно сходится к функции fix) на каждом компактном подмножестве К С D. Это, например, следует из работы [8]. Но эти условия

не обеспечивают сходимости производных функций fm(x) к производным функции f(x) даже почти всюду или по норме в пространствах Соболева W^P(D). Это подтверждается хорошо известным примером Шварца ([12], п. 7 гл. 11).

Далее будем предполагать, что функция / : D —> Ш является С2-гладкой в области D Cln, причём будем считать, что все вторые производные ограничены в D. Тогда найдётся постоянная М > О такая, что модуль непрерывности градиента u>(V/, t) < М -t.

Оценка погрешности аппроксимации градиента для классической триангуляции Делоне плоской е-сети может быть получена как следствие теоремы 1.2.1.

Теорема 2.1.1. Пусть задана триангуляция Делоне Т конечного набора точек, являющегося е-сетью в плоской области D С I2. Пусть точка р является вершиной триангуляции Т такой, что для некоторого треугольника из Т, имеющего вершиной эту точку, описанный круг полностью лежит в области D. Тогда справедливо следующее неравенство:

|V/(P)~ VL/(p)| < 14Ме.

Пусть Gm — множество точек, составляющее вершины и рёбра симплексов триангуляции Тт.

Следствие 2.1.1. Пусть f(x) — С2-гладкая в области D С R2 и над последовательностью Тт триангуляций Делоне области D, удовлетворяющих условиям (2.1) и (2.2) построена её кусочно-аффинная аппроксимация fm{x). Тогда справедливо равенство:

lim Vfm(x) = V/M, ж G D \ N Gm. (2.3)

m—> оо ^^

т

В трёхмерном евклидовом пространстве выполнение условия Делоне не гарантирует сходимости градиентов аппроксимации к градиентам исследуемой функции. Однако существует класс триангуляций (остроугольные триангуляции), для которого можно получить конечную оценку соответствующей разности градиентов как следствие теоремы 1.2.3. Если мы будем рассматривать остроугольные триангуляции е-сетей с узлами в некоторой

области D С К3, то при s —0 оценка также устремится к нулю.

ю

Теорема 2.2.1. Пусть задана остроугольная триангуляция Т конечного набора точек, являющегося е-сетью в области I) С К3. Пусть точка р является вершиной триангуляции Т. Тогда

Следствие 2.2.2. Пусть /(х) — С2-гладкая в области Б С М3 и над последовательностью Тт остроугольных триангуляций области Б, удовлетворяющих условиям (2.1) и (2.2) построена её кусочно-аффинная аппроксимация /т(х). Тогда справедливо равенство:

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

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

Пусть Б — некоторая область в Мп. Зафиксируем некоторую маленькую величину д > 0. Будем говорить, что триангуляция Т является триангуляцией с углами, отделёнными от нуля, если для всякого невырожденного симплекса Б е Т ни один из его двугранных углов не будет меньше 5. Рассмотрим последовательность Тт таких триангуляций области Б. Положим также

где £¿5 — длина самого короткого ребра симплекса 5.

Справедлива следующая теорема.

Теорема 2.3.1. Предположим, что для области Б с!п, последовательности наборов точек Рт и их триангуляции Тт с углами, отделёнными от

(2.4)

т

й (Тт) = тт & £етт '

нуля, выполнены условия (2.1) и (2.2). Тогда для любой функции / £ С2 (Б) и любой компактно вложенной подобласти II <Ш Б имеет место неравенство

Следствие 2.3.1. Пусть /(х) — С2-гладкая в области Б С Мп и над последовательностью Тт триангуляций с углами, отделёнными от нуля, области Б, удовлетворяющих условиям (2.1) и (2.2) построена её кусочно-аффинная аппроксимация /т(х). Тогда справедливо равенство:

Отметим, что приведённая ранее оценка (2.8) погрешности аппроксимации градиента включает в себя величину, зависящую от максимума вторых производных исследуемой функции. Однако такие сведения об исследуемой функции доступны не всегда. Тем не менее, для некоторых классов функций существуют априорные оценки второй производной, выражающиеся через значения самой функции. Один такой класс рассматривается в этом параграфе.

Для функций, являющихся решениями эллиптических уравнений вида

где = ау'(ж), Ь% = Ъ\ с = с(х) — функции со значениями из К, / е Са(Г2), а !!7 — любое открытое подмножество в можно получить оценку разности градиентов, не зависящую от максимума второй производной и.

Зафиксируем некоторый п-мерный симплекс 5 С Мп и свяжем с ним ортонормированный базис {е?} как результат процесса ортогонализации Грамма-Шмидта векторов {рг — ро}, г = 1, ..., п. Пусть щ обозначает угол между вектором Рк — Ро и плоскостью, натянутой на векторы

7Г

ех, ..., к = 2, ..., п; (р\ = —, а обозначает угол между гранью

__¿л

5к и плоскостью Щ.

Пусть ит(х) — кусочно-аффинная аппроксимация и такая, что в узлах триангуляции её значения совпадают со значениями и. Тогда справедлива следующая теорема.

(2.9)

771

Ьи = а13 Б ци + ЫБ^и + си = /,

Теорема 2.4.2. Предположим, что для области С W1, последовательности наборов точек Рт и их триангуляции, Тт выполнены условия (2.1) и (2.2). Тогда для любой ограниченной функции и Е C2,a{Q), являющейся решением эллиптического уравнения Lu = f в Q с правой частью / Е Ca(Q), и любой компактно вложенной подобласти U (ё Г2 имеет место неравенство

max max I Vu(x) — Viim(a;)| <

SeTm,ScU xeS

<d+(Tm)r (l + max V--n-— V (2.11)

где

t — C\ (sup \u\ + sup d2x\f{x)\+ sup ) , C\ = const.

Рассмотрим некоторую n-мерную гиперповерхность F в пространстве Rn+1, заданную графиком С2-гладкой функции xn+i — и(хi, ..., хп), х Е Del™. Определим отображение проекции

7т: F D, 7г(жь ..., icn+i) = (хь ..., жп).

Пусть Р — некоторый конечный набор точек в Rn+1, лежащих на поверхности F и таких, что любой симплекс с вершинами из Р является невырожденным. Обозначим через р' = 7г (р) проекцию точки р в область D. Будем рассматривать триангуляцию поверхности F n-мерными симплексами, построенными на множестве Р. Триангуляцией поверхности назовём такой набор Т n-мерных симплексов, что

1. каждая точка р заданного набора является вершиной одного из симплексов S Е Т\

2. каждая вершина любого симплекса S Е Т является одной из точек набора Р;

3. внутренность пересечения любых двух симплексов пуста;

4. проекция системы симплексов Sj Е Т, j = 1, ..., m является обычной триангуляцией набора точек Р' в Еп. Здесь Р' = {р' \ р' = ir(p); р Е Р}.

Будем рассматривать последовательность таких наборов точек Рт, т = 1, 2, ..., расположенных на поверхности И, и соответствующих им триангуляции: Тто, удовлетворяющих условиям (2.1) и (2.2). Для каждого т построим кусочно-аффинную функцию /т(х) такую, что /т(а) = /(а) для любой точки а <Е Рт.

Теорема 2.5.1. Пусть Б — область, расположенная на некоторой трёхмерной поверхности И. Рассмотрим остроугольную триангуляцию Т конечного набора точек Р, являющегося е-сетью в области Б. Пусть точка р является вершиной триангуляции Т, а а — угол между плоскостью тетраэдра 5 и касательной плоскостью к поверхности Р в точке р. Тогда

Отсюда непосредственно вытекает утверждение о сходимости градиентов.

Следствие 2.5.1. Для построенной выше последовательности функций /т(х), х £ Б над остроугольными триангуляциями Тт трёхмерной поверхности Р, удовлетворяющими условиям (2.1) и (2.2), выполнено равенство:

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

В данной работе рассматриваются обобщения триангуляции Делоне на случаи:

1. другого семейства описанных выпуклых множеств (не шаров);

(2.12)

771

2. п-мерных поверхностей в (п + 1)-мерном пространстве;

3. метрического пространства (классическое определение получается в евклидовой метрике);

4. шаров с коэффициентом сжатия г/ (при rj = 1 получится обыкновенная триангуляция Делоне).

Рассмотрим в Жп семейство выпуклых множеств F(x, г), х Е W1, г Е М и конечное множество точек Р, расположенных в некоторой области D С Шп.

Пусть S — произвольный невырожденный симплекс в Мп. Определим описанное множество (если оно существует) F(S) из семейства F(x, г) как множество, чья граница содержит вершины симплекса (а значит, F(S) содержит весь симплекс в силу выпуклости F(x, г)).

Рассмотрим произвольную триангуляцию множества точек Р.

Определение 3.1.1. Будем говорить, что триангуляция равномерна относительно семейства F(x, г), если для любого симплекса S этой триангуляции внутренность множества F(S) не содержит вершин других симплексов.

Определение 3.1.2. Будем говорить, что триангуляция локально равномерна относительно семейства F(x, г), если для любого симплекса S этой триангуляции внутренность множества F(S) не содержит вершин других симплексов, имеющих общую (п — 1)-мерную грань.

Следующая теорема была доказана в работе [21].

Теорема 3.1.1. Для того, чтобы для семейства выпуклых множеств F(x, г) из локальной равномерности следовала глобальная равномерность, достаточно, чтобы указанное семейство обладало свойством: для любого симплекса S существует и единственно описанное множество F(S).

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

Теорема 3.1.2. Пусть Ф(ж) — строго выпуклая вниз функция, х £ Мп. Тогда семейство выпуклых множеств

F(x, г) = {у : Ф(у) = (УФ(ж), у - х) + г}

удовлетворяет условию теоремы 3.1.1.

Замечание. Классическая триангуляция Делоне получается в случае

су

Ф(х) = \х\ .

Рассмотрим произвольный конечный набор точек Р в некоторой области П Е Мп с метрикой и обозначим квадрат элемента длины

Здесь д^ Е С (О,) и в каждой точке х Е Г2 образуют положительно определённую матрицу

Определение 3.2.1. Для произвольного симплекса Б = (р\} ..., рь) описанным шаром В (в) в метрике назовём такой шар В{х о, г), где хо — центр шара, а г — его радиус, что Рг Е дВ{хо, г) и лежит в плоскости симплекса 5(ро? • • • > Рк)-

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

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

Определение 3.2.3. Будем говорить, что для двух соседних симплексов с вершинами из Р выполнено условие пустоты шара, если описанный шар одного симплекса не содержит внутри себя вершин другого симплекса.

Справедлива следующая теорема.

Теорема 3.2.1. Если для любой пары соседних симплексов триангуляции Т выполнено условие пустоты шара, тоТ — триангуляция Делоне в метрике.

Для триангуляций £-сетей в метрике можно построить оценку разности градиентов. Будем использовать обозначения, принятые во второй главе. Сформулируем условия, аналогичные (2.1) и (2.2):

При т —> оо (1+{Тт) = тахтах(¿(рь р{) —> 0, где рь, р1 Е 5, к ^ I; (3.1)

Б^Тт I

Ме > 0 Зт0 е N : Ут > т0 и Ух е Б 3 а е Рт : д(а, х) < е. (3.2)

Далее будем рассматривать триангуляции в метрике, удовлетворяющие данным условиям. Справедлива следующая

Теорема 3.2.4. Предположим, что для области Б С Мп с некоторой метрикой для последовательностей наборов точек Рт и соответствующих им триангуляций Тт выполнены условия (3.1) и (3.2). Пусть и (ё Б — некоторая подобласть такая, что для некоторого натурального ко

ип[ 5 I (И Б при всех т > ко.

\SeTm /

Тогда при т > ко выполнено следующее неравенство:

тах тах IV/(ж) — V<

5еТт,5сС/ ' -1 К ' ¿ГПК ;\д -

< Ас/+(ТГО)

(

1 + п

V

А

Ма тах V ( V

э .чет . яг-тт —' i —'

1

Бет^Бси ' \ ^—^ ЭШЮ; I сое 6п I 3=1 \г=1 111 1

/

где Мд — максимальное собственное значение матрицы \\дц\\.

Для триангуляций Делоне в метрике также справедливо утверждение, касающееся сходимости градиентов.

Теорема 3.2.5. Для построенной выше последовательности функций /т{х), х е Б над двумерными триангуляциями Делоне в Тт в метрике, удовлетворяющими условиям (3.1) и (3.2), выполнено равенство:

Иш Ч/т(х) = У/(х-), хеБ\ МСШ.

те—>оо ^^

(3.7)

т

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

Пусть 5 — некоторый п-мерный симплекс в Мп+1.

Определение 3.3.1. Описанным шаром В(3) для Б назовём (п+1)-мерный шар, содержащий на своей границе все вершины симплекса и имеющий наименьшее возможное значение радиуса.

Определение 3.3.2. Будем говорить, что триангуляция поверхности Б удовлетворяет условию Делоне, если для любого симплекса триангуляции описанный шар в смысле определения 3.3.1 не содержит внутри себя ни одной вершины триангуляции.

Определение 3.3.3. Будем говорить, что для двух п-мерных симплексов, пересекающихся по общей (п—1) -мерной грани выполнено условие пустоты шара, если (п + 1)-мерный описанный шар одного симплекса не содержит внутри себя вершин другого симплекса.

С точки зрения построения оптимальных алгоритмов триангуляции поверхностей, а также задачи аппроксимации градиента в метрике поверхности, важным свойством триангуляции Делоне является свойство утверждающее, что выполнение условия Делоне локально непременно влечет выполнение его глобально (см. [1], [21], [3], [2]). Следующая теорема обобщает это свойство на случай триангуляции гладких гиперповерхностей, заданных графиком функции. Но в отличие от плоского случая необходимо выполнение дополнительного условия.

Условие а). Рассмотрим произвольный п-мерный симплекс Б триангуляции и построим пересечение [/5 всех полупространств, содержащих Б, и которые определяются гиперплоскостями (п + 1)-мерных сфер, являющихся пересечениями описанной сферы симплекса ¿> и его соседнего. Таких полупространств будет не более п + 1 для каждого симплекса Б. Мы предполагаем, что никакая вершина триангуляции не принадлежит внутренности [/5 для всякого Б.

Заметим, что в плоском случае, когда вершины триангуляции лежат в одной гиперплоскости, условие а) очевидно выполняется.

Теорема 3.3.1. Пусть п-мерная гиперповерхность Б задана над выпуклой областью Б С М.п. Триангуляция гиперповерхности Г, для которой любая пара симплексов, пересекающихся по общей (п — 1 )-мерной грани, удовлетворяет условию пустоты шара, является триангуляцией Делоне.

Пусть теперь ^ 6 ; = 1, ..., М - некоторый конечный набор точек и Т<2 — классическая триангуляция Делоне этого набора точек.

Определение 3.3.4. Будем называть п-мерную грань симплекса Б Е Тд гранью, приближающей гиперповерхность Б, если все её вершины лежат

18

на гиперповерхности F.

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

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

Рассмотрим последовательность наборов точек Рт, m — 1, 2, ..расположенных на поверхности F, и соответствующих им триангуляций Тт, удовлетворяющих условиям (2.1) и (2.2). Для каждого m построим кусочно-аффинную функцию fm(x) такую, что fm(a) = fia) для любой точки a G Рт.

Теорема 3.3.4. Пусть задана триангуляция Делоне Т конечного набора точек, являющегося е-сетью области D, расположенной на двумерной гиперповерхности F G R3. Пусть точка р является вершиной триангуляции Т такой, что для некоторого треугольника S из Т, имеющего вершиной эту точку, пересечение его описанной окружности с гиперповерхностью F полностью лежит в области D. Пусть а — угол между плоскостью треугольника S и касательной плоскостью к поверхности F в точке р. Тогда справедливо следующее неравенство:

|V/(p) - VL/(p)| < ЫМе + sin a sup | V/(x) |.

x&D

Следствием этой теоремы будет утверждение о сходимости градиентов кусочно-аффинной функции fm(x) к градиентам исследуемой с помощью неё функции f(x).

Следствие 3.3.1. Для построенной выше последовательности функций fm(x), х 6 D над триангуляциями Делоне двумерной поверхности F, удовлетворяющими условиям (2.1) и (2.2), выполнено равенство:

lim Vfm(x) = V/M, xeD\{\Gm. (3.8)

m

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

19

построить полиэдральную поверхность, точно приближающую боковую поверхность цилиндра.

Рассмотрим произвольный конечный набор Р точек некоторой области ЙСГ.

Зафиксируем число 0 < ту < 1. Пусть 5 — произвольный симплекс в Кп.

Определение 3.4.1. Шар Вд с центром, совпадающим с центром описанного около Б шара радиуса и радиусом г]Яз будем называть ч]-шаром симплекса Б. В случае М2 будем называть г}-кругом.

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

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

С этой стороны ^-триангуляция Делоне может быть охарактеризована, как триангуляция Делоне построенная с некоторой точностью, отражаемой значением параметра 77.

Для триангуляции с коэффициентом сжатия описанной окружности можно построить оценку аппроксимации градиента функции f(x), х £ Б, С2-гладкой в области Б. Здесь и далее мы будем использовать обозначения, принятые в п. 2.

Теорема 3.4.1. Пусть задана г]-триангуляция Делоне Т конечного набора точек, являющегося е-сетью в плоской области Б С М2. Пусть точка р является вершиной триангуляции Т такой, что для некоторого треугольника из Т, имеющего вершиной эту точку, его г]-круг полностью лежит в области Б. Тогда

Следствие 3.4.1. Пусть f(x) — С2-гладкая в области 0с12и над последовательностью Тт 77-триангуляций Делоне области D, удовлетворяющих условиям (2.1) и (2.2) построена её кусочно-аффинная аппроксимация fm(x). Тогда справедливо равенство:

lim Vfm(x) = V/(x), х 6 D \ M Gn,

m->oo

m

Пользуясь случаем, автор выражает глубокую благодарность за полезные обсуждения и замечания своему научному руководителю, д. ф.-м. н. В. А. Клячину, а также к. ф.-м. н., доценту В. В. Попову, к. ф.-м. н. Н. М. Полу бояровой и всем участникам научного семинара "Сверхмедленные процессы" под руководством д. ф.-м. н., профессора В. М. Миклюкова. Хотелось бы отдельно выразить свою искреннюю признательность декану факультета математики и информационных технологий ВолГУ, д. ф.-м. н., профессору А. Г. Лосеву за внимательное отношение и энергичную поддержку.

Список литературы диссертационного исследования кандидат физико-математических наук Широкий, Александр Александрович, 2012 год

Литература

[1] Delaunay В. N. Sur la sphère vide. A la mémoire de Georges Voronoï // Известия АН СССР. - 1934. № 6. - С. 793 - 800 / Перевод с фр. А. Ю. Игумнов в сб. Записки семинара "Сверхмедленные процессы". Вып. 1. - Волгоград: Изд-во ВолГУ, 2008. - С. 147 - 153.

[2] Edelsbrunner H. An Acyclicity Theorem for Cell Complexes in d Dimension. // Combinatorica. Vol. 10 (3). — Heidelberg, Germany: Springer-Verlag Berlin, 1990. - C. 251 - 260.

[3] Garanzha V. A. Discrete Extrinsic Curvatures and Approximation of Surfaces by Polar Polyhedra // Computational Mathematics and Mathematical Physic. Vol. 50. №1,- Dover, DE, USA: Pleiades Publishing, Ltd., 2010.-C. 65 - 92.

[4] Gruber P. M. Error of Asymptotic Formulae for Volume Approximation of Convex Bodies in E3 // Дискретная геометрия и геометрия чисел. Тр. МИАН, том 239. - М.: Наука, 2002. - С. 106 - 117.

[5] Korotov S. Some geometric results for tetrahedral finite elements. // Proceedings of the International Conference NUMGRID-2010. — M.: Фо-лиум, 2010. - С. 41 - 46.

[6] Pottmann H., Krasauskas R., Hamann В., Joy К., Seibold W. On Piecewise Linear Approximation of Quadratic Functions. // Journal for Geometry and Graphics. Vol. 4. № 1. — Lemgo, Germany: Heldermann Verlag, 2000. — С. 31-53.

[7] Rajan V. T. Optimality of the Delaunay triangulation in Discrete Computational Geometry. Vol. 12. — New York, USA: Springer-Verlag New York, Inc., 1994. - C. 189 - 202.

[8] Shewchuk J. R. What is a Good Linear Element? Interpolation, Conditioning, and Quality Measures //In Proceedings, 11th International Meshing Roundtable (September 2002). — Ithaca, New York, USA: Sandia National Laboratories, 2002. - C. 115 - 126.

[9] Waldron S. The Error in Linear Interpolation at the Vertices of a Simplex. // SIAM Journal on Numerical Analysis. Vol. 35, № 3. — Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1998. — C. 1191 -1200.

[10] Винберг Э. Б., Шварцман О. В. Дискретные группы движений пространств постоянной кривизны // Итоги науки и техн. Сер. Соврем, про-бл. мат. Фундам. направления. Т. 29. - М.: ВИНИТИ, 1988. - С. 147 -259.

[11] Гантмахер Ф. Р. Теория матриц. - 5-е изд. - М.: ФИЗМАТЛИТ, 2004. - 559 с.

[12] Гелбаум В., Олмстед Дж. Контрпримеры в анализе. — Волгоград: Платон, 1997. - 251 с.

[13] Гилбарг Д., Трудингер Н. Эллиптические дифференциальные уравнения с частными произвоными второго порядка / Пер. с англ. Л. П. Купцова. Под ред. А. К. Гущина. Изд. 2-е. — М.: Наука, Гл. ред. физ.-мат. лит., 1989. - 464 с.

[14] Годунов С. К., Прокопов Г. П. О расчетах конформных отображений и построений разностных сеток // Журнал вычислительной математики и математической физики, № 7 (5). — М.: Наука, 1967. — С. 1031 - 1059.

[15] Годунов С. К., Прокопов Г. П. О решении дифференциальных уравнений с использованием криволинейных разностных сеток / / Журнал вычислительной математики и математической физики, № 8 (1). — М.: Наука, 1968. - С. 28 - 46.

[16] Годунов С. К., Жуков В. Т., Феодоритова О. Б. Метод расчета инвариантных подпространств для симметрических гиперболических уравнений // Журнал вычислительной математики и математической физики, № 46 (6). - М.: Наука, 1968. - С. 1019 - 1031.

[17] Грачёва Е. А., Клячин В. А. Кусочно-линейное интерполирование поверхностей уровня функций, заданных на нерегулярных сетках // Записки семинара "Сверхмедленные процессы". Вып. 3. — Волгоград: Изд-во ВолГУ, 2008. - С. 157 - 167.

[18] Долбилин Н. П. Разбиение пространства на многогранники // Труды II Всероссийской научной школы "Математические исследования в кристаллографии, минералогии и петрографии". — Апатиты: Изд-во "К &; М", 2006. - С. 7 - 18.

[19] Дубровин Б. А., Новиков С. П., Фоменко А. Т. Современная геометрия: Методы и приложения. - 2-е изд., перераб. — М.: Наука, Гл. ред. физ.-мат. лит., 1986. — 760 с.

[20] Люстерник Л. А., Соболев В. И. Элементы функционального анализа.

— М.: Наука, Гл. ред. физ.-мат. лит, 1965. — 520 с.

[21] Клячин В. А. Об одном обобщении условия Делоне // Вестник Томского государственного университета, Математика и механика, № 1 (2). — Томск: Изд-во Томского ун-та, 2008. — С. 48 - 50.

[22] Клячин В. А., Пабат Е. А. С^-аппрроксимация поверхностей уровня функций, заданных на нерегулярных сетках // Сиб. журн. индустр. ма-тем., № 13 (2). — Новосибирск: Изд-во Института математики им. С. Л. Соболева СО РАН, 2010. - С. 69 - 78.

[23] Клячин В. А., Широкий А. А. Аппроксимационные свойства остроугольных триангуляций // Материалы научной сессии, г. Волгоград, 26 -30 апр. 2010 г. Вып. 6. Математика и информационные технологии. — Волгоград: Изд-во ВолГУ, 2010. - С. 40 - 44.

[24] Клячин В. А., Широкий А. А. Аппроксимационные свойства триангуляции Делоне // Записки семинара "Сверхмедленные процессы". Вып. 5.

- Волгоград: Изд-во ВолГУ, 2010. - С. 8 - 14.

[25] Клячин В. А., Широкий А. А. Триангуляция Делоне многомерных поверхностей // Вестник Самарского государственного университета. Естественно-научная серия. № 2010 / 4 (78). — Самара: Изд-во СамГУ, 2010. - С. 51 -55.

[26] Клячин В. А., Широкий А. А. Триангуляция Делоне многомерных поверхностей // Материалы 15-й Саратовской зимней школы "Современные проблемы теории функций и их приложения". — Саратов: Изд-во СГУ, 2010. - С. 89.

[27] Клячин В. А., Широкий А. А. Триангуляция Делоне многомерных поверхностей и её аппроксимационные свойства // Вестник Волгоградского государственного университета. Серия 1: Математика, физика. № 12.

- Волгоград: Изд-во ВолГУ, 2009. - С. 39 - 44.

[28] Клячин В. А., Широкий А. А. Триангуляция Делоне многомерных поверхностей и её аппроксимационные свойства // Известия вузов. Математика. № 1. - Казань: Изд-во КФУ, 2012. - С. 31 - 39.

[29] Клячин В. А., Широкий А. А. Триангуляция Делоне многомерных поверхностей и её аппроксимационные свойства // Материалы Девятой международной научной школы-конференции "Теория функций, её приложения и смежные вопросы". — Казань: Казан, мат. об-во, 2009. — С. 155 - 157.

[30] Клячин В. А., Широкий А. А. Триангуляция Делоне с коэффициентом сжатия сфер / / XV региональная конференция молодых исследователей Волгоградской области, 9-12 нояб. 2010. Вып. 4. Физика и математика.

- Волгоград: Изд-во ВолГУ, 2011. - С. 71 - 74.

[31] Кобаяси Ш., Номидзу К. Основы дифференциальной геометрии. Том 2. / Пер. с англ. Л. В. Сабинина. — М.: Наука, Гл. ред. физ.-мат. лит., 1981.

- 416 с.

[32] Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. - 7-е изд. — М.: ФИЗМАТЛИТ, 2006. — 572 с.

[33] Медведев Н. Н. Метод Вороного-Делоне в исследовании структуры некристаллических систем. — Новосибирск: Изд-во СО РАН, 2000. — 214 с.

[34] Миклюков В. М. Введение в негладкий анализ. Изд. 3, перераб. — Волгоград: изд-во ВолГУ, 2011. 480 с.

[35] Никольский С. М. Курс математического анализа. Том 1. - 3-е изд. — М.: Наука, Гл. ред. физ.-мат. лит., 1983. — 464 с.

91

Половинкин Е. С., Балашов М. В. Элементы выпуклого и сильно выпуклого анализа. - М.: ФИЗМАТЛИТ, 2004. - 416 с.

Понтрягин Л. С. Основы комбинаторной топологии. - 3-е изд. — М.: Наука, Гл. ред. физ.-мат. лит., 1986. — 120 с.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. - М.: Мир, 1989. - 478 с.

Скворцов А. В., Мирза Н. С. Алгоритмы построения и анализа триангуляции. — Томск: Изд-во Томского ун-та, 2006. — 168 с.

Скворцов А. В. Триангуляция Делоне и её применение. — Томск: Изд-во Томского ун-та, 2002. - 128 с.

Харари Ф. Теория графов. / Пер. с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. — 296 с.

Шикин Е. В., Боресков А. В. Компьютерная графика. Полигональные модели. — М.: Изд-во Диалог-МИФИ, 2000. — 461 с.

Широкий А. А. Условие почти пустого шара. // Материалы Десятой международной научной школы-конференции "Теория функций, её приложения и смежные вопросы". — Казань: Казан, мат. об-во, 2011. — С. 387 - 389.

[44] Широкий А. А. Применение триангуляции Делоне двумерной поверхности к примеру Шварца // Материалы 16-й Саратовской зимней школы "Современные проблемы теории функций и их приложения". — Саратов: Изд-во СГУ, 2012. - С. 200.