ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 10, с. 1647-1660
УДК 519.626
АСИМПТОТИЧЕСКИЕ СВОЙСТВА МЕТОДА УТОЧНЕНИЯ ОЦЕНОК ПРИ АППРОКСИМАЦИИ МНОГОМЕРНЫХ ШАРОВ МНОГОГРАННИКАМИ^
© 2015 г. Г. К. Каменев
(119991 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: gkk@ccas.ru Поступила в редакцию 18.12.2014 г.
Переработанный вариант 27.01.2015 г.
В работе рассматривается метод "уточнения оценок" полиэдральной аппроксимации выпуклых компактных тел. Известно, что при аппроксимации выпуклых тел с гладкой границей этот метод порождает многогранники с оптимальным порядком роста числа вершин и гиперграней в зависимости от точности аппроксимации. Рассматриваются свойства метода при полиэдральной аппроксимации многомерного шара. Показано, что в этом случае рассматриваемый метод в качестве вершин аппроксимирующих многогранников порождает на поверхности шара так называемую последовательность глубоких ям. Это позволяет перенести на такие многогранники полученные ранее комбинаторные свойства выпуклых оболочек указанных последовательностей: скорости сходимости по числу граней всех размерностей, оптимальность роста мощности гранной структуры (нормы /-вектора). В работе проведено сравнение комбинаторных свойств аппроксимирующих многогранников метода "уточнения оценок" со свойствами многогранников, обладающих экстремальными мощностями гранной структуры. Показано, что многогранники, получаемые в методе, близки к так называемым многогранникам пирамидальной надстройки, на которых достигается минимум граней всех размерностей при заданном числе вершин. Библ. 32. Фиг. 1.
Ключевые слова: выпуклые тела, многомерный шар, аппроксимация многогранниками, метод уточнения оценок, вершины, гиперграни, грани, гранная структура, /-вектор, скорость сходимости.
DOI: 10.7868/S0044466915100129
1. ВВЕДЕНИЕ
В работе рассматривается классическая проблема аппроксимации многомерных выпуклых тел многогранниками. Эта задача, помимо самостоятельного интереса (см., например, обзоры в [1], [2]), актуальна для таких прикладных исследований, как задачи построения множеств достижимости динамических систем (см. [3], [4]) и задачи многокритериальной оптимизации (см. [5], [6]). В этих приложениях стоит важная задача разработки реализуемых на практике методов полиэдральной аппроксимации выпуклых компактных тел, оптимальных или близких к оптимальным. В рамках этих практических исследований был предложен в [7] и разработан (см. подробности в [6, с. 186]) итерационный адаптивный метод "уточнения оценок" (УО) (the Estimate Refinement (ER) method), который показал себя практически пригодным для аппроксимации выпуклых тел достаточно большой размерности. В [8] этот метод был переформулирован в виде, используемом в исследованиях, в том числе — в настоящей работе.
В [9]—[13] метод УО подробно теоретически исследован. Получены скорости сходимости по числу вершин и итераций в гладком и негладком случаях, а также на начальном этапе аппроксимации. В гладком случае показана оптимальность метода по порядку (по скорости) роста числа вершин и гиперграней аппроксимирующих многогранников в зависимости от точности аппроксимации. Проведено исследование его эффективности (сравнение с многогранниками наилучшей аппроксимации). Показано, что при аппроксимации гладких тел этот метод порождает мно-
1) Работа выполнена при частичной финансовой поддержке РФФИ (коды проектов 13-01-00235 и 12-01-00916), ПФИ Президиума РАН П-15 и П-18, ПФИ ОМН № 3.
1647
гогранники, отклонение которых в метрике Хаусдорфа асимптотически не более чем в четыре раза превышает минимально возможное при том же числе вершин. Следствием этих свойств является оптимальность метода в гладком случае по порядку числа задач вычисления опорной функции аппроксимируемого гладкого тела, необходимых для достижения заданной точности. Сводка большинства результатов теоретического исследования метода УО представлена в [14].
В [15], [16] метод УО исследован в численных экспериментах, в том числе при аппроксимации многомерных эллипсоидов, которые показали, что асимптотические оценки скорости сходимости метода УО, полученные в [9], [11], могут быть значительно улучшены, по крайней мере, в этом классе аппроксимируемых тел.
Особое внимание в теории аппроксимации выпуклых компактных тел многогранниками уделялось проблеме минимизации сложности описания аппроксимирующих многогранников в виде числа основных элементов гранной структуры, таких как вершины или гиперграни. Были получены асимптотические оценки минимального числа вершин или гиперграней, необходимого для получения заданной точности аппроксимации (см., например, обзоры в [1], [2]). Вместе с тем, о полной мощности гранной структуры аппроксимирующих многогранников известно в общем случае значительно меньше (см. [17], [18]). Однако для получения представления об общей сложности задачи полиэдральной аппроксимации недостаточно оценок на скорость роста числа вершин и гиперграней, так как во многих методах имеется необходимость выполнять построение выпуклых оболочек вершин и другие операции, по времени и объему занимаемой методом памяти, зависящие от сложности всей гранной структуры.
Для выпуклых тел, имеющих гладкую границу, задача полиэдральной аппроксимации оказывается связанной с построением метрических сетей на их поверхности. Выпуклая оболочка такой сети дает аппроксимирующий многогранник. Оказывается, что выпуклая оболочка центров системы шаров, дающих оптимальное покрытие поверхности в метрике второй квадратичной формы, асимптотически приводит к отклонению в метрике Хаусдорфа, совпадающему с отклонением многогранников наилучшей аппроксимации (см. [1], [2]). В [19] предложен метод "Глубоких Ям" (ГЯ) (the Deep Holes (DH) method) — универсальный адаптивный итерационный метод аппроксимации вполне ограниченных множеств в произвольных метрических пространствах, основанный на построении близких к оптимальным s-сетей (построения эффективных покрытий и упаковок метрических шаров). Метод ГЯ состоит в построении в аппроксимируемом множестве последовательности точек — так называемой последовательности ГЯ: в последовательном пополнении аппроксимирующей базы (совокупности центров построенной сети) глубокими метрическими ямами аппроксимируемого множества (его точками, наиболее удаленными от базы). Как показано в [14], последовательности многогранников, являющихся выпуклыми оболочками конечных частей последовательностей ГЯ на поверхности гладких выпуклых тел, являются оптимальными по порядку числа вершин. В [13] исследован рост числа гиперграней в классе методов, порождающих на поверхности гладких выпуклых тел последовательности, близкие к последовательностям ГЯ. Показано, что порядок роста числа гиперграней в выпуклых оболочках точек (вершин) из конечных частей этих последовательностей тот же, что и порядок роста числа вершин, что является оптимальным. Так как практически реализуемые способы построения ГЯ на поверхности выпуклых тел в общем случае неизвестны, метод ГЯ является теоретическим подходом, применяемым, в основном, для построения оценок скорости сходимости. В настоящей работе будет использована техника построения последовательностей ГЯ на поверхности гиперсфер для исследования скорости сходимости метода УО при аппроксимации многомерных шаров. Будет показано, что в этом случае при определенных условиях имеет место совпадение результатов применения метода ГЯ и метода УО.
В рамках проблемы аппроксимации выпуклых компактных тел большое значение имеет задача аппроксимации шара. Прежде всего, среди всех изопериметричных (с равным поверхностным объемом) компактных выпуклых тел шар является наиболее сложным объектом для аппроксимации многогранниками (см., например, [1] или [2]). Кроме того, эта задача важна особенно тем, что на полиэдральной аппроксимации шара основаны некоторые неадаптивные методы полиэдральной аппроксимации и методы построения сеток и кодов на поверхности сферы (см. [20], [21]). В работах [22], [23] для метода ГЯ рассматривалась задача полиэдральной аппроксимации шара, была исследована мощность гранной структуры выпуклых оболочек конечных частей последовательностей ГЯ на поверхности сферы, порождаемых методом. Было показано, что норма /-вектора аппроксимирующих многогранников растет в этом случае от отклонения в метрике Хаусдорфа с оптимальной по порядку скоростью. Показано также, что, асимптотически, число граней всех размерностей аппроксимирующих многогранников, получаемых в методе ГЯ, пропор-
ционально числу их вершин. В [23] были также рассчитаны верхние оценки скорости роста числа граней всех размерностей для малых размерностей.
Основной целью настоящей работы является перенесение результатов исследования гранной структуры выпуклых оболочек точек, получаемых в методе ГЯ на поверхности сферы, на многогранники, порождаемые методом УО при аппроксимации многомерного шара.
Работа имеет следующую структуру. Прежде всего рассматривается постановка задачи оптимальной аппроксимации выпуклого компактного тела многогранниками с точки зрения элементов гранной структуры. Приводятся известные результаты по этому вопросу, в частности, для многомерных шаров. Далее излагается метод УО, исследуются применительно к задаче аппроксимации шара его свойства (теоремы 1 и 2) и приводятся с учетом этих свойств полученные ранее результаты исследования скорости его сходимости по числу вершин и гиперграней. Далее излагается метод ГЯ и показывается, что при определенных условиях на многогранник начального приближения метод УО порождает на поверхности сферы последовательность ГЯ (теорема 4). Далее исследуется мощность компонентов гранной структуры в методе УО: результаты теоремы 4 из [23] для метода ГЯ используются для доказательства асимптотической пропорциональности числа граней многогранников, порождаемых методом УО, числу их вершин (теорема 5), а также получаются различные оценки этой зависимости, в том числе для малых (следствие 4) и больших (следствие 3) размерностей. Далее исследуется скорость сходимости метода УО по мощности компонентов гранной структуры: выв
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.