научная статья по теме МЕТОД ПОЛИЭДРАЛЬНОЙ АППРОКСИМАЦИИ ШАРА С ОПТИМАЛЬНЫМ ПОРЯДКОМ РОСТА МОЩНОСТИ ГРАННОЙ СТРУКТУРЫ Математика

Текст научной статьи на тему «МЕТОД ПОЛИЭДРАЛЬНОЙ АППРОКСИМАЦИИ ШАРА С ОПТИМАЛЬНЫМ ПОРЯДКОМ РОСТА МОЩНОСТИ ГРАННОЙ СТРУКТУРЫ»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2014, том 54, № 8, с. 1235-1248

УДК 519.651

МЕТОД ПОЛИЭДРАЛЬНОЙ АППРОКСИМАЦИИ ШАРА С ОПТИМАЛЬНЫМ ПОРЯДКОМ РОСТА МОЩНОСТИ ГРАННОЙ СТРУКТУРЫ1)

© 2014 г. Г. К. Каменев

(119991 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: gkk@ccas.ru Поступила в редакцию 26.12.2013 г.

Переработанный вариант 12.03.2014 г.

Рассматривается задача полиэдральной аппроксимации многомерного шара. Известно, что норма /-вектора (максимальное число граней различных размерностей) аппроксимирующего многогранника растет не медленнее, чем 0(S(1 - d)/2), где 8 — отклонение в метрике Хаусдорфа и d — размерность пространства. Рассматривается итерационный метод построения метрических сетей — метод "Глубоких Ям", состоящий в данной задаче в последовательном пополнении множества вершин многогранника его глубокими ямами в метрике на поверхности шара (т.е. точками поверхности, наиболее удаленными от вершин многогранника). Показано, что мощность гранной структуры построенного многогранника будет иметь оптимальную скорость роста. Показано, что асимптотически, число граней всех размерностей аппроксимирующих многогранников, получаемых в методе, пропорционально числу их вершин. Получены явные выражения для констант, зависящие только от размерности пространства, в том числе при больших размерностях. Получены верхние оценки скорости роста числа граней всех размерностей в зависимости от точности аппроксимации для малых размерностей (d от 3 до 5). Библ. 30.

Ключевые слова: выпуклые тела, многомерный шар, аппроксимация многогранниками, покрытия и упаковки на сфере, упаковка шаров в шар, сферические коды, методы полиэдральной аппроксимации, вершины, гиперграни, грани, гранная структура, /-вектор.

Б01: 10.7868/80044466914080067

1. ВВЕДЕНИЕ

Рассматривается задача полиэдральной аппроксимации выпуклых тел (см. [1], [2]) для случая, когда аппроксимируемое тело является многомерным шаром. Эта задача, помимо самостоятельного интереса, актуальна при разработке методов построения сферических покрытий, сеток и упаковок, а также методов полиэдральной аппроксимации гладких и негладких выпуклых тел. В качестве примеров использования теории полиэдральной аппроксимации многомерных выпуклых тел в прикладных исследованиях можно назвать задачи построения множеств достижимости динамических систем (см. [3], [4]) и множества достижимых критериальных векторов в задачах многокритериальной оптимизации (см. [4]).

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

1) Работа выполнена при частичной финансовой поддержке РФФИ (коды проектов 13-01-00235 и 12-01-00916), ПФИ Президиума РАН П-15 и П-18, ПФИ ОМН № 3.

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

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

Наряду с задачей оценки минимального числа граней, вершин и иных компонентов гранной структуры, необходимых для достижения заданной точности, стоит важная задача разработки реализуемых на практике методов полиэдральной аппроксимации выпуклых компактных тел, оптимальных или близких к оптимальным. Такая задача возникает во многих приложениях: в теории оптимального управления (см. [3]), математическом моделировании [4] и т.п. В рамках этих практических исследований был предложен в [7] и разработан (см. подробности в [4]) адаптивный метод "уточнения оценок", который показал себя практически пригодным для аппроксимации выпуклых тел достаточно большой размерности.

В [8] предложен метод "глубоких ям" (ГЯ) — универсальный адаптивный итерационный метод аппроксимации вполне ограниченных множеств в произвольных метрических пространствах, основанный на построении близких к оптимальным е-сетей (построения эффективных покрытий и упаковок метрических шаров). Метод ГЯ состоит в последовательном пополнении аппроксимирующей базы (совокупности центров построенной сети) глубокими метрическими ямами аппроксимируемого множества (его точками, наиболее удаленными от базы) — построения так называемой последовательности ГЯ. В [8] показано, что при заданной мощности метрической сети метод ГЯ позволяет строить аппроксимацию с радиусом покрывающих шаров, не более чем вдвое большим минимально возможного. В [9] показано, что при аппроксимации гладких тел метод "уточнения оценок" (УО) порождает на поверхности тела последовательность вершин, асимптотически близкую к последовательности ГЯ в метрике второй квадратичной формы. Как показано в [9], последовательности многогранников, соответствующие последовательностям ГЯ, являются оптимальными по порядку числа вершин аппроксимирующих многогранников. В [10], [11] исследован рост числа гиперграней в классе методов, порождающих последовательности, близкие к последовательностям ГЯ. В этих работах показано, что порядок роста числа гиперграней в выпуклых оболочках точек (вершин) из этих последовательностей тот же, что и порядок роста числа вершин, и является оптимальным.

В настоящей работе рассматривается задача полиэдральной аппроксимации шара. Известно (см. [1], [2], [5]), что норма /-вектора аппроксимирующего многогранника (максимум из числа вершин, гиперграней и граней произвольной размерности) растет от отклонения в метрике Хаусдорфа не медленнее, чем 0(8(1 - ^/2), где 8 — отклонение многогранника от тела в метрике Хаусдорфа и d — размерность пространства. В [12] изложены результаты применения метода ГЯ для построения полиэдральной аппроксимации шара с оптимальным порядком роста гранной структуры и были получены некоторые оценки, улучшенные в настоящей статье.

Основной целью настоящей работы является изучение метода ГЯ и основанной на нем полиэдральной аппроксимации многомерных шаров с параметрами гранной структуры, близкими к оптимальным. Заметим, что такой подход может также быть непосредственно использован для построения субоптимальных покрытий и упаковок сферы (см., в частности, [13], [14]).

В начале работы даются основные определения, и излагается итеративный метод построения метрических сетей — метод ГЯ. Далее исследуются внутренне-геометрические свойства, в частности, скорость сходимости во внутренней метрике сферы. В следующей части исследуются внешне-геометрические свойства выпуклых оболочек сетей, порождаемых рассматриваемым методом, в частности, их скорость сходимости к аппроксимируемому шару в метрике Хаусдорфа. Далее исследуется мощность гранной структуры этих выпуклых оболочек. Показано, что норма /-вектора аппроксимирующих многогранников растет от отклонения в метрике Хаусдорфа не быстрее, чем 0(8(1- ^/2), т.е. с оптимальной скоростью. Показано также, что, асимптотически, число граней всех размерностей аппроксимирующих многогранников, получаемых в методе ГЯ, пропорционально числу их вершин. В этом отношении эти многогранники ближе по комбинаторным свойствам к многогранникам, двойственным к так называемым многогранникам усечения из [15], на которых достигаются минимальные оценки числа граней при заданном числе вер-

шин. В конце работы вычислены верхние оценки роста числа граней всех размерностей для d от 3 до 5.

2. МЕТОД ГЯ

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

Пусть T — конечное подмножество A (база покрытия) и card(T) — его мощность, т.е. число элементов. Для x e A пусть р(х, T) := min{p(x, t): t e T} и p(A, T) := sup{p(x, T): x e A}. Для е, 0 < е, пусть [T]E := {x e К: p(x, T) < е}, и (T)£ := {x e К: p(x, T) < е}. Для заданного у , 0 < у < 1, положим

DHy(T) := {x e A: р(х, T) > yp(A, T)}.

В дальнейшем в данной работе будем считать A компактным. В силу конечности T имеем p(A, T) = = max {p(x, T): x e A}, поэтому DHj(T) не пусто. Точки x e DHj(T) называются глубокими ямами (deep holes) — см., например, [21, с. 5]. Множество DHj(T) назовем множеством ГЯ базы T и обозначим его через DH(T), а множество DHY(T) назовем множеством ГЯ уровня у.

Опишем метод ГЯ из [8] — класс итерационных алгоритмов построения е-сетей для вполне ограниченных множеств.

Метод глубоких ям: пусть t1 e A и T1 := {t1}. Пусть множество Tn построено и p(A, Tn) > 0. Тогда

Tn + 1 := Tn U {tn + lb где tn + 1 e DHy(Tn).

Метод ГЯ может быть переформулирован для некоторой начальной базы покрытия, состоящей более, чем из одной точки:

пусть T1 с A. Пусть множество Tn построено и p(A, Tn) > 0. Тогда имеем Tn +1 := Tn u {tn +1}, где tn + 1 e DHy(Tn).

Если не оговорено спец

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком