Содержание к диссертации
Введение
Глава 1. Адаптивные методы полиэдральной аппроксимации (АМПА) 46
1.1. Итерационные методы и общие аппроксимационные схемы 46
1.2. Хаусдорфовы (//-) схемы и последовательности 50
1.2.1. //-схемы 50
1.2.2. Базовые методы 52
1.3. Хаусдорфовы АМПА 54
1.3.1. Хаусдорфовы методы 54
1.3.2. Метод «Уточнения Оценок» 57
1.3.3. Методы «Уточнения Внешних Оценок» 64
1.4. Нехаусдорфовы АМПА 68
Глава 2. Теория сходимости АМПА , 73
2.1. Теоретические основы исследования АМПА 73
2.2. Метод изменения объема на итерациях АМПА 74
2.3. Метод упаковок нормалей 84
2.4. Метод «Глубоких Ям» (МГЯ) 93
2.4.1. Описание МГЯ 93
2.4.2. Скорость сходимости МГЯ 96
2.4.3. Эффективность МГЯ 98
2.4.4. АМПА, основанные на МГЯ 102
2.4.5. Исследование хаусдорфовых АМПА методом «Глубоких Ям» 106
2.5. Асимптотические оценки скорости сходимости, оптимальность и эффективность АМПА 116
2.5.1. Аппроксимация произвольных ВКТ 116
2.5.2. Аппроксимация гладких ВКТ 117
2.5.3 Оптимальность по порядку хаусдорфовых АМПА 118
2.5.4. Эффективность хаусдорфовых АМПА при аппроксимации гладких тел 120
2.5.5. Асимптотические оценки скорости сходимости и эффективность асимптотических Я-методов 127
2.6. Асимптотические оценки скорости сходимости, оптимальность и эффективность конкретных АМПА 130
2.6.1 Базовые методы 130
2.6.2. Метод «Уточнения Оценок» 135
2.6.3. Методы «Уточнения Внешних Оценок» 138
2.6.4. Метод «Сближающихся Многогранников» 145
2.7. Оценки скорости сходимости АМПА на начальном этапе 160
2.7.1. Оценки скорости сходимости первых членов Н-последователыюстей 160
2.7.2. Оценки скорости сходимости первых членов Н\-последовательностей 165
2.7.3. Оценки скорости сходимости конкретных АМПА на начальном этапе 167
Глава 3. Теория двойственности оптимальных АМПА 169
3.1. Двойственные классы АМПА 170
3.2. Двойственность хаусдорфовых АМПА восполнения и отсечения . 174
3.3. Методы конструирования оптимальных АМПА на основе теории двойственности 183
3.3 Л. Точные двойственные аналоги 183
3.3.2. Двойственные методы 192
3.3.3. Точные двойственные аналоги для двойственных методов 198
3.3.4. Прямо-двойственные методы 200
3.3.5. Комбинированные (двухфазные) методы решения смешанных задач 201
3.4. Самодвойственные оптимальные АМПА 203
3.4.1. Необходимость разработки самодвойственных методов 203
3.4.2. Описание самодвойственных методов 205
3.4.3. Скорость сходимости самодвойственных методов 207
3.4.4. Оптимальность и эффективность самодвойственных методов216
Глава 4. Приложение теории оптимальных АМПА: аппроксимационные свойства негладких выпуклых дисков 219
4.1. Аппроксимационные свойства выпуклых дисков 220
4.2. Основные определения 223
4.3. Метод «Экстремальных Ям» 224
4.4. Верхняя оценка для скорости сходимости многоугольников наилучшей аппроксимации 230
4.5. Верхняя оценка аппроксимационного числа 233
4.6. Верхняя оценка аппроксимируемости 234
4.7. О свойствах одного класса выпуклых дисков со счетным числом вершин 236
Глава 5. Экспериментальное исследование скорости сходимости и эффективности оптимальных АМПА 248
5.1. Задачи и методика численного исследования эффективности АМПА 248
5.2. Методика исследования в классе многомерных эллипсоидов 253
5.3. Результаты исследования в классе многомерных эллипсоидов 264
5.3.1. Результаты предварительных численных исследований АМПА 264
5.3.2. Простой пример численного исследования АМПА 266
5.3.3.Некоторые общие вопросы реализации численных исследований АМПА в классе эллипсоидов 268
5.3.4. Результаты численных исследований метода «Уточнения Оценок» 273
5.4. Дальнейшие исследования АМПА 277
5.4.1. Дальнейшие исследования метода «Уточнения Оценок» 277
5.4.2. Результаты численных исследований метода «Сближающихся Многогранников» 278
5.4.3. Результаты численных исследований прямо-двойственного метода 280
5.4.4. Результаты численных исследований комбинированного метода 281
5.5. Исследование в классе дисков с бесконечным числом вершин 283
5.6. Основные выводы из экспериментального исследования оптимальных АМПА 286
Глава 6. Практическое применение оптимальных АМПА в задачах принятия решений 287
6.1. Использование АМПА в методе Обобщенных Множеств Достижимости (ОМД) 287
6.1.1. Метод ОМД 287
6.1.2. Принятие решений на основе метода ОМД 290
6.1.3. Использование АМПА в методе ОМД 295
6.1.4. Визуализация полиэдральных аппроксимаций ОМД 299
6.2. Разработка стратегий развития сельскохозяйственной области с учетом экологических факторов 304
6.2.1. Описание проблемы 304
6.2.2. Краткое описание модели 306
6.2.3. Подробное описание модели 308
6.2.4. Исследование проблем распределения водных ресурсов в типичном подрегионе и области в целом 323
6.2.5. Исследование перспектив сохранения экосистемы области в связи с хозяйственным развитием её пяти экономических районов .330
6.3. Другие приложения АМПА в эколого-экономических проблемах 338
6.3.1. Методика многокритериального анализа эколого-экономических проблем методом ОМД 338
6.3.2. Примеры многокритериального анализа эколого-экономических проблем методом ОМД 340
6.4. Визуализация множества Парето в многомерных задачах выбора из конечного числа альтернатив 344
6.5. Использование оптимальных АМПА для исследования динамических моделей 348
6.5.1. Основные понятия 348
6.5.2. Аппроксимация множеств достижимости на основе АМПА .351
6.6. Визуальный метод идентификации параметров 355
6.6.1. Проблема идентификации параметров 355
6.6.2. Идентификация параметров по методологии ОМД 357
6.6.3. Выпуклая задача визуальной идентификации и АМПА 358
6.6.4. Общий случай задачи визуальной идентификации 359
Заключение. Основные результаты диссертации 360
Литература
- Хаусдорфовы АМПА
- Исследование хаусдорфовых АМПА методом «Глубоких Ям»
- Двойственность хаусдорфовых АМПА восполнения и отсечения
- Верхняя оценка для скорости сходимости многоугольников наилучшей аппроксимации
Введение к работе
Актуальность темы. Аппроксимация многогранниками является традиционным средством теории выпуклых множеств. Первые аппроксимаци-онные теоремы восходят к Минковскому. В частности, Минковским было доказано, что для каждого выпуклого компактного тела можно найти сходящуюся последовательность выпуклых полиэдров, аппроксимирующих это тело. Эти утверждения широко использовались для получения результатов, связанных с геометрией выпуклых поверхностей. Однако долгое время интерес к задаче был сугубо теоретическим. На важность практической аппроксимации выпуклых тел многогранниками возможно впервые указал Л.С.Понтрягин в связи с проблемой построения множеств достижимости динамических систем. В настоящее время задача аппроксимации выпуклых компактных тел (ВКТ) многогранниками возникает во многих приложениях: в математическом программировании, кодировании изображений и др.
Важное практическое значение вычислительные алгоритмы полиэдральной аппроксимации выпуклых компактных тел имеют в задачах принятия решений на основе использования математических моделей в методе обобщенных множеств достижимости (ОМД), разрабатываемого в ВЦ РАН начиная с 70-х годов группой исследователей под руководством А.В. Лото-ва. В этом подходе вместо изучения отдельных вариантов решения осуществляется сжатие (агрегирование) информации о всех допустимых вариантах. Агрегирование состоит в построении в явном виде множества всех таких значений показателей качества решения, которые могут быть достигнуты в модели как результат допустимых вариантов решений (управлений). Построенное в явном виде множество достижимых значений показателей - обобщенное множество достижимости - может быть использовано для конструирования различных методов анализа моделей и принятия решений на их основе. В выпуклом случае для построения такого описания необходимо разработать эффективные методы полиэдральной аппроксимации выпуклых тел.
Важным отличием адаптивных методов полиэдральной аппроксимации (АМПА) от методов приближенного описания с помощью отдельно взятых выпуклых тел (таких как симплекс, параллелепипед, эллипсоид, цилиндр) является возможность аппроксимации выпуклых компактных тел с любой степенью точности. За это преимущество, однако, приходится платить высокую цену: как показывают существующие теоретические оценки, а также экспериментальные и прикладные исследования, сложность описания аппроксимирующего многогранника быстро растет с увеличением точности и ростом размерности аппроксимируемого тела. Тем не менее, в задачах при-
. „о. НАЦИОНАЛЬНАЯ | 3 БИБЛИОТЕКА {
нятия решений необходимо использовать методы, обеспечивающие возможность аппроксимации с любой (заранее не известной) степенью точности в связи с тем, что для исследователя важна форма и конкретное расположение паретовой границы аппроксимируемого множества, а не только область, где это множество находится.
В связи со сказанным выше, использование методов полиэдральной аппроксимации (МПА) при исследовании математических моделей приводит к необходимости разработки методов, оптимальных с точки зрения сложности описания аппроксимирующих многогранников (под которой будем понимать число вершин или гиперграней). Кроме того, поскольку каждый запрос информации об аппроксимируемом теле (например, каждое вычисление опорной или дистанционной функции) может требовать большого времени, представляют интерес методы, оптимальные с точки зрения числа таких запросов (в частности, числа вычислений опорной или дистанционной функции).
Цель работы. Целью работы является:
1) Разработка теории оптимальных адаптивных методов полиэдральной
аппроксимации выпуклых компактных тел. В рамках этой теории:
необходимо разработать методы создания новых адаптивных методов аппроксимации, оптимальных как с точки зрения сложности аппроксимирующего многогранника, так и с точки зрения числа решаемых задач выпуклой оптимизации на аппроксимируемом теле;
необходимо разработать методы теоретического исследования скорости сходимости и эффективности методов полиэдральной аппроксимации.
-
Разработка методики проверки в численных экспериментах эффективности адаптивных методов при достижимых на практике точностях аппроксимации.
-
Разработка методики использования адаптивных методов полиэдральной аппроксимации в многокритериальных задачах принятия решений в рамках математического моделирования.
Метод исследования. В работе при разработке и исследовании адаптивных методов полиэдральной аппроксимации используются методы выпуклого анализа, дифференциальной геометрии, теории информации и вычислительной геометрии. При разработке методики использования адаптивных методов полиэдральной аппроксимации в задачах принятия решений в рамках математического моделирования используются принципы и методы теории принятия решений, в том числе метод обобщенных множеств достижимости.
Научная новизна. Результаты диссертации, полученные автором, являются новыми. Основные из этих результатов следующие:
-
Создана теория оптимальных адаптивных методов полиэдральной аппроксимации выпуклых компактных тел. Введены классы адаптивных методов полиэдральной аппроксимации, основанные на адаптивных схемах восполнения и отсечения. Введено понятие Я-методов отсечения и восполнения и исследованы их свойства. Введено понятие более узкого класса Яг методов отсечения и восполнения с более сильными свойствами. [2], [3], [5], [13], [18]
-
Для Я- и Ярметодов получены верхние оценки скорости сходимости, исследована их эффективность. Доказана оптимальность по порядку числа вершин (методы восполнения) и числа гиперграней (методы отсечения) для гладких (Я-методы) и произвольных (Я)-методы) тел. В гладком случае доказана независимость эффективности Ярметодов восполнения от свойств аппроксимируемых тел (совместно с Р.В.Ефремовым). [3], [5], [7], [13], [18], [16], [17], [26]
-
На основе теории оптимальных адаптивных методов полиэдральной аппроксимации изучены существующие алгоритмы и предложены новые. В частности, для существующего и активно используемого в приложениях метода «Уточнения Оценок» доказана принадлежность к классу оптимальных Ярметодов восполнения, изучена его скорость сходимости и эффективность. [2], [5], [8], [13].
-
Предложен метод «Сближающихся Многофанников», использующий одновременно схему восполнения и схему отсечения. Для этого метода получены оценки скорости сходимости и доказана в гладком случае оптимальность по порядку числа вершин внешнего и гиперфаней внутреннего аппроксимирующих многофанников, а также по порядку числа вычислений опорной функции аппроксимируемого тела. [10]
-
Развита теория построения и исследования оптимальных адаптивных методов аппроксимации для тел, заданных своей дистанционной (калибровочной) функцией. Введено понятие двойственных классов адаптивных методов полиэдральной аппроксимации. Доказано, что Я- (Н\-) методы восполнения и отсечения являются двойственными классами. Для известных методов сформулированы двойственные аналоги. [18]
-
Для тел, заданных одновременно опорной и дистанционной функциями, предложены самодвойственные методы. Доказано, что они оптимальны по порядку числа вершин внешних, гиперфаней внутренних аппроксимирующих многофанников, а также по порядку числа вычислений опорной и дистанционной функций аппроксимируемого множества, причем как в гладком, так и в негладком случае. [21 ], [20]
-
Получена новая верхняя оценка аппроксимационного числа негладких выпуклых дисков. [15]
-
Разработаны теоретические основы методики экспериментального ис-
следования эффективности адаптивных методов полиэдральной аппроксимации в классе многомерных эллипсоидов. [2]
-
Осуществлено экспериментальное исследование эффективности методов в классах многомерных эллипсоидов (совместно с СМ. Джолдыбае-вой). [4], [6]
-
Разработана методика использования методов полиэдральной аппроксимации в многокритериальных задачах принятия решений, в частности при анализе эколого-экономических проблем (совместно с А.В.Лотовым, В.А.Бушенковым и О.Л.Черных). [1], [14], [11], [12], [23], [24], [25], [28], [29]
-
С помощью оптимальных адаптивных методов полиэдральной аппроксимации исследована сложная эколого-экономическая модель сельскохозяйственного региона (совместно с А.В.Лотовым и ван Вальсумом). [11], [22]
-
Предложена методика анализа многомерной задачи выбора на основе визуализации паретовой границы выпуклой оболочки критериальных точек (совместно с В.А.Бушенковым, Д.И.Гусевым, А.В.Лотовым, и О.Л.Черных). [9], [14], [28], [29]
Практическая ценность. В работе исследованы существующие и разработаны новые эффективные методы полиэдральной аппроксимации выпуклых тел. Проведено исследование этих методов в численных экспериментах. Разработана методика использования рассматриваемых методов в задачах принятия решений. С применением рассматриваемых методов исследована сложная эколого-экономическая система сельскохозяйственного региона (совместная работа с Международным институтом прикладного системного анализа (ИИСА)). Оптимальные адаптивные методы полиэдральной аппроксимации, рассмотренные в работе, были использованы также в системе поддержки поиска эффективных стратегий улучшения качества воды в крупных реках (в рамках Федеральной целевой программы «Возрождение Волги»).
Результаты, изложенные в настоящей работе, получены при финансовой поддержке РФФИ (коды проектов 95-01-00968, 98-01-00323, 01-01-00530, 04-01-00662), по программе поддержки ведущих научных школ (коды проектов 00-15-96118, НШ-1843.2003.1), при поддержке программы №3 фундаментальных исследований ОМН РАН «Вычислительные и информационные проблемы решения больших задач» и программы фундаментальных исследований РАН «Математическое моделирование и интеллектуальные системы».
Апробация. Результаты, нашедшие отражение в диссертации, докладывались на следующих совещаниях, конференциях и семинарах: на Всесоюзной конференции «Теория, методология и практика системных
исследований» (Москва, 1985), на конференции «Математические методы управления и обработки информации» (Москва, 1985), на семинаре «Многокритериальные задачи математического программирования» Всесоюзного научно-исследовательского института системных исследования (Москва, 1985), на методологическом семинаре «Методы имитационного моделирования экономических объектов» Центрального экономико-математического института АН СССР (Москва, 1985), на заседаниях школы-семинара ИВЕРСИ-85 «Системные и прикладные аспекты диалога на персональных ЭВМ» (Тбилиси, 1985), на IX Всесоюзном симпозиуме «Системы программного обеспечения решения задач оптимального планирования» (Москва, 1986), на конференции молодых ученых Вычислительного центра АН СССР (Москва, 1988), на Советско-финском симпозиуме "Information technology and economic modeling" (Хельсинки, Финляндия 1992), на международной конференции «Konvexgeometrie» (Обервольфах, ФРГ 1997), на 2-й Московской международной конференции по исследованию операций (Москва, 1998), на научной сессии «Проблемы прикладной математики и информатики» Вычислительного центра РАН (Москва, 2000), на 3-й Московской международной конференции по исследованию операций (Москва, 2001), на научной конференции «Математика, Механика и Информатика 2002», поев. 10-летию РФФИ (Москва, 2002), на научной конференции «Математические модели сложных систем и междисциплинарные исследования», поев. 85-летию академика Н.Н.Моисеева (Москва, 2002), на 58-й Конференции Европейской рабочей группы «Поддержка многокритериального принятия решений» (Москва, 2003), на международной конференции «Математическое моделирование социальной и экономической динамики» (Москва, 2004), на 4-й Московской международной конференции по исследованию операций (Москва, 2004) и на ряде семинаров МГУ (Механико-математический факультет: семинарах кафедр математического анализа, теории чисел и дискретной математики; факультет Вычислительной математики и кибернетики: семинар кафедры оптимального управления), института Проблем механики РАН, Московского физико-технического института, Вычислительного центра РАН им. А.А. Дородницына.
Публикации. Основные результаты диссертации опубликованы в 29 работах, из них четыре книги: [11] в соавторстве с А.В. Лотовым, В.А. Бу-шенковым и О.Л. Черных; [14] главы 1-5 в соавторстве с А.В Лотовым и В.А. Бушенковым, гл. 8 - самостоятельно; [28] в соавторстве с А.В. Лотовым и В.А. Бушенковым; [29] главы 1-6 в соавторстве с А.В. Лотовым и В.А. Бушенковым, гл. 8 - самостоятельно.
Структура и объем работы. Диссертация состоит из предисловия, введения, шести глав, заключения, списка литературы из 160 наименова-
ний, 17 таблиц и 71 рисунка. Текст диссертации без списка литературы, таблиц и рисунков составляет 361 страницу машинописного текста, общий объем - 420 страниц.
Хаусдорфовы АМПА
Методы, реализующие //-схемы, будем называть хаусдорфовыми (или Н-) методами. Класс методов, использующих //-схему восполнения или отсечения (т.е. порождающих //-последовательности восполнения или отсечения с константой /для СєЩ, будем обозначать через S {y, С). Если необходимо, будем различать класс Н-методов восполнения $) (/, С) и -отсечения 9f{y, С). Очевидно, что при у\ /2 справедливо Sj(yh QczSXn, С).
Если для некоторой константы у, некоторого класса св сс6п некоторого метода М справедливо MeSj(y, С) для любого Сє Й , то будем писать Мє? (у, Я ). Из теоремы 1.2.1 сразу вытекают Следствие 1.3.1. MEaeSjl(l, сф, МБОєс(1, Щ. Следствие 1.3.2. Класс методов, использующих Ярсхемы восполнения или отсечения (т.е. порождающих Н\-последовательности восполнения или отсечения с константой /для тела Сє 6), будем обозначать через $)\{у, С). Если необходимо, будем различать класс Н\-методов восполнения Sjl](y, С) и - отсечения $f\{y, С). Если для некоторой константы у, некоторого класса Ф а &и некоторого метода М справедливо Mefi\(y, С) для любого СєсЄ , то будем писать MGS
Если величина константы у в некотором утверждении значения не имеет, класс Я- (Яр) методов будем обозначать через #(гб ) (ft іСй )).
Класс методов, использующих асимптотические Я-схемы восполнения или отсечения (т.е. порождающих асимптотические Я-носледовательности восполнения или отсечения с константой у для тела Сєї), будем обозначать через aSj(y, С). Если необходимо, будем различать класс асимптотических Н-методов восполнения aS) (y С) и отсечения aSjc\(y С). Если для некоторой константы у, некоторого класса с ё и некоторого метода М справедливо Мєаіз(/, С) для любого Сє% , то будем писать Мєа$)(у, % ). Совершенно аналогично определим класс асимптотических Н\-методов а$)\{у, С) и обозначение Мєа9)\(у % ). Ясно, что для любых Се &и /справедливо $(у, C)cza (y, С).
Если величина константы у в некотором утверждении значения не имеет, класс асимптотических Я- (Яр) методов будем обозначать через
В настоящем разделе будут рассмотрены конкретные методы, реализующие Н- и Яр схемы восполнения и отсечения.
Заметим, прежде всего, что приведенные выше (раздел 2 настоящей главы) базовые методы допускают и другую формулировку.
БАЗОВЬІЙІ МЕТОД ВОСПОЛНЕНИЯ (БВІ) Пусть для Сє и Pe (Q построен Р"є.У(С). Для построения Р ] выполняются следующие процедуры: ШАГ 1. а). Найти и„ := arg max {g(u, Q-gfaP"): нє S 1}. b). Найтир„єТ(ит С). Шаг 2. Положить Р"+] := conv {р„, Р"}.
Действительно, из (1.2.7) следует, что в этом случае p(pmP") = SlI(P",C). Наоборот, пусть р(рп, Р") = бн(Р",С) и р := proj (рп, Р"). Тогда для ип-=(рп -Р У\\ Рп -р \\ справедливо g(un, С) - g(un, Ґ) = SH(P",C) и, кроме того, рпеТ\ип, С), что доказывает эквивалентность двух формулировок метода БВ. БАЗОВЫЙ] МЕТОД ОТСЕЧЕНИЯ (БОІ) Пусть для Се и Р0є (О построен Р"єУс(С). Для построения Р"+ выполняются следующие процедуры: ШАГ 1. а). ШширпедР": р(рп, С) = S"(P",C). b). Положить ип=(рп - proj (ртС)У\\ря - proj (р„,С)1. Шаг 2. Положить Р ] := P"nL(un, Q. Действительно, если и„ := arg max {g(u, Р") - g{u, С): иє S A} и PnzT{un, P"), то pipn,C) = 6И(Р",С). Наоборот, пусть p(pm С) - S"{P",Q и p := proj (pn,C). Тогда для u„:=(p„ -р У\\ря -р \\ справедливо g(w„, Q - g{un, P") = Sfl(P",C), что доказывает эквивалентность двух формулировок метода БО.
Исследование хаусдорфовых АМПА методом «Глубоких Ям»
Прежде всего, установим связь между хаусдорфовыми МПА и покрытием поверхности гладких ВКТ в метрике в.о.к.ф. методом Глубоких ям. В настоящей работе мы ограничимся рассмотрением Н\-последовательностсй восполнения. Случай Я-последовательностей восполнения рассмотрен в работе [28], а Я-последователыюсти отсечения рассмотрены в работе [26].
Пусть Сег(?+2, и пусть дС снабжена метрикой в.о.к.ф. /J». Как и в предыдущем пункте, это означает следующее. Для любой редС через щір) обозначим единичную нормаль к ВС в точке/?, направленную внутрь С. В K-ndp), С) выберем декартову прямоугольную систему координат. Вместе с -ndp) она образует декартову прямоугольную систему координат всего Ed. Через hp обозначим ортогональную проекцию на 1(-пс{р% С). Пусть U— окрестность р на дС, такая что hp есть гомеоморфизм U на hp{U) и hp(U) есть открытый евклидов шар размерности d \ на l(-ndp), С). Представим U в виде x=(u,J[u)), где u=hp(x) для любого XGU. Тогда/- строго выпуклая функция из класса С2 на hp(U). Для uekp(U) с помощью (2.4.4) введем вто рую основную квадратичную форму (в.о.к.ф.) qPtU(s), где seEd 1 и Ь {и) коэффициенты в.о.к.ф. Длину кривой класса Сх на дС определим с помощью соответствующего разбиения через (2.4.3). Для хуєдС через //ц(лг, у) обозначим геодезическую метрику в.о.к.ф. на дС, т.е. точную нижнюю грань длин (в соответствующей метрике) кривых класса С1 из дС, соединяющих х и у.
Лемма G [113]. Пусть Сєс6+ и к \. Тогда существует такое v.=v (Л, С) 0 {h\ h{X, С) 0), что для любых р.хєдС, xeBv(p) (р(х, hp(x)) h), справедливо
Лемма G содержится в [113] в разбросанном по доказательствам теорем виде, поэтому приведем ее доказательство из явно сформулированных утверждений этой работы, следуя изложению [ИЗ].
Обозначим через Зц(А, В) := inf {//ц(х, у): х є А, у є В} минимальное расстояние между множествами А и В в метрике //][.
Лемма G1 ([113], стр. 287). Пусть СеЪ2 и Я \. Пусть JczM:=dC и J - измеримо. Тогда существуют точки рієдС, соответствующие им карты U{, hi, окрестности її точек pi и числа St 0, 1=ї, ...,т, такие что для u,vehp (//) выполняется а) ap,uis) qPAs) 1 Л1/2 л, б) її с Ui, // - измеримые, її и ... и Im = J, h n Ii = 0 , к Ф І, УЦ(4 дЩ 4
Лемма G2 ([113], стр. 294). Пусть C&V+2 и Л 1. Пусть ре дС и U-ее окрестность, такая, что для любых u,vehp{U) и seE " \{0} определена в.о.к.ф. в виде (2.4.4) и выполняются условия а) леммы G1. Пусть x,yeU, Ци(х,у) д\і(х, дії). Тогда Замечание. Из леммы G2 сразу следует, что для любых соответствующих р и Uи любогохєі/, fiiip, х) д\і(р, dU), выполняется Лемма G3 ([113], стр. 295). Пусть числа Si О, /=1, ..., т, определены, как в лемме G1. Тогда существует h 0, такое, что для любых х,уедС, piy, hx(y)) h, справедливо {i\\{x,y) min{4: /=1, -» tn}. Доказательство леммы G. Докажем сначала существование такого v 0, что для любых р є дС и xeBj(p) выполнено утверждение леммы.
Множество ВС - компактно. Поэтому оно измеримо (по Жордану). Значит, к дС применима лемма G1. В силу леммы G1 найдется такое натуральное т и разбиение дС = I} и ... и 1т, что выполнены свойства а) и б) из утверждения леммы G1. ПустьредС. Тогда/? лежит в одном из множеств 1р 1 j m, скажем, в 1\. В силу б) справедливо b\\(p, dU\) Si. Пусть K=min {S;-. =1, ..., т]. Тогда для любого хедС из метрического шара Ву(р)={хедС: jUn(pjc) v} справедливо рц(р, x) Sn(p, dU{). Кроме того, выполнены свойства а) леммы G1, т.е. для произвольного р выполнены условия леммы G2, и, в силу замечания к лемме G2, утверждение леммы G о существовании v доказано.
Существование И 0, такого, что утверждение леммы G выполнено для любых р є дС и р(х, hp(x)) h, вытекает непосредственно из леммы G3 и только что доказанного утверждения о существовании к Лемма G доказана. Лемма 2.4.1. Пусть для Cef ?+ построена сходящаяся последова телъность многогранников {Р"}п=о,и і3" є . / (С). Тогда для многообразия дС с метрикой fi\\ в.о.к.ф. справедливо \\mdm, (М (Рв)) = 0.
Доказательство. Для начала заметим, что нижнюю грань в определении дисперсии (2.4.1) можно заменить без потери общности на минимум, т.к. отображение К(т):=[}{уєдС:щ{{хру) г} і есть непрерывное и монотонно возрастающее отображение полуинтервала [0,со) на компакт. Пусть теперь у„ є ВС, такая что Пусть р„ :=argmin{//j(у„,р):р є М (Рп)}. Дальше очевидно, что тт{р(р,їіУп(р)):рєМ1(Р")} 5(Р\С). Пусть pn :=argmin{/?(p,A (р)):рєМ (Р")}. Возьмем произвольное Л 1. В силу сходимости последовательности многогранников найдется N, такое что для любого n N, а также дпяу„ и pn , выполнится утверждение леммы G, т.е. м(РЇ,у„) рлР(Рб„,пУіі(рі)). Тогда, в силу двух последних неравенств, получим сітІ{рП)(М1(Рп)) = МР Уп) МРІУп) лІ2ЛЗн(Рп,С). Из последнего неравенства с учетом сходимости о (Р",С)- 0 следует утверждение леммы.
Двойственность хаусдорфовых АМПА восполнения и отсечения
В силу сходимости Я-последовательностей отсечения (теорема 1.2.2), можно выбрать Nтак, чтобы RQ(P") R0(Q/(\-s)m, n N, Тогда из первого утверждения теоремы следует второе.
Теорема 3.2.2 полностью доказана.
Заметим, что по теоремам 3.2.1 и 3.1.2 полярная последовательность для Н(у ( -последовательностей восполнения (отсечения) является Я-последователыюстью отсечения (восполнения) для полярного тела, но теоремы 3.2Л и 3.2.2 дают более слабую оценку на ее константу. Это не дает говорить о двойственности конкретных Я-последовательностей отсечения и восполнения, но позволяет заключить о двойственности классов АМПА, порождающих их.
Следующие теоремы устанавливают, что для классов АМПА, порождающих Н\{% ( -последовательности восполнения и отсечения, справедливы такие же отношения двойственности, как и для классов АМПА, порождающих Н(у ( -последовательности.
Теорема 3.2.3. Пусть {Рп}п,\,... - (асимптотическая) Н\{у, С)-последовательность восполнения для Сє%, Р"є!?о (С), п=0,1,... . Тогда {(-Р") }„=о,і,.„ есть (асимптотическая) Н\(уа, С )-последовательность отсечения, где константа уа определена в утверждении теоремы 3.2. J. Кроме того, {(Р") }n= u,... есть асимптотическая Н{(у (у, С), С )-последователъность отсечения, где константа у (у, С) определена в утверждении теоремы 3.2.1.
Доказательство. Пусть р„ - вершина, присоединяемая к Р" на (и+1)-й итерации схемы восполнения. По определению Н\-последовательности восполнения для некоторого VneSipn, С% справедливо g(vfl,Q-g{v„r) C). Пустьр 7il{vM П) и Рп := 1(у„, О). По (3.1.1)/? = vjgym F1) є d(P") . 179 Pn = vn/g(vn, С) є дС , откуда р = t(pn , (Р") )- Пусть u„ := pj\\pn\\, тогда по (3.1.1) n(p„) = l(uf , С ). Так как vneS(p„, С), TO/?WG/(V№ С), поэтому А = л(/(у„, С))єл(/?„) = /(«„, С ). Но /?„ є5С , поэтому р„ є 7(ил, С ). Далее, по лемме 3.2.2 р(рМрп)) = p{xQ{vn,Pn))MPn)) g(y„,P„) - g(v„,Pn) g(?n,C) - g(y ,P") \\p„\\RQ(P") Н0(С)Я0(Р") откуда по свойству Н\-последовательности восполнения и лемме 3.2.1 получаем р(рМРп)) Г(С)Г(РП) yS((Pnr,C ) r(P"\ yS((Pn) ,C ). д0(С)дь(/»и) 0(с)2 Но Мр„) = 1(и„, С ), поэтому pip, л(рп)) = g{u„, р) - g(un, С ), откуда g(un,p) - g&n, С ) pip, л{рп)). Осталось учесть, что го(Р") го( ). Итак, при любом п мы получили, что для р„ = л{1{у„, С)) є Т(и№ С ), где и„=р„/\\р„\\ є S 1, справедливо фп, ФЛ (Г) )) - g(u„, С ) уЛ(Р")\ С ). Первое утверждение теоремы доказано. Второе утверждение теоремы следует, как и в доказательстве теоремы 3.2.1, из сходимости -последовательностей восполнения.
Теорема 3.2.4. Пусть {Р"}„=ох... (асимптотическая) Н\{у, )-последовательность отсечения для Сє%, Р"є 0с(С), «=0,1,... . Тогда {(Р") }п=о,і,... есть (асимптотическая) Н\{ус, С Упоследовательность восполнения, где константа ус определена в утверждении теоремы 3.2.2. Кроме того, {CP") }«=o,i,... есть асимптотическая Н\(у (у, С), С )-последовательность восполнения, где константа у (у, С) определена в утверждении теоремы 3.2.1.
ISO Доказательство. Пусть и„ - направление, по которому происходит уточнение Р" на (л+1)-й итерации схемы отсечения. По определению Н\-последовательности для некоторогоpn TiUn, С), справедливо g(un, t(p„, Ґ)) - g(u„, О y%P", С). Пустьр := t(pn, Г)ирп = x(l(itn С)). По (3.1.1)р = ujg О є дС . Пусть v„ :=pj\\pn\\ = Р% \\ тогда по (3.1.1) л{р„) = 1(у„, С ) и Мр) = l(v„, (Р") ). Так накритій,» С), тор„є/(ида С), поэтому р = л(/(и„, С))е яЫ - /(v„, С ). Но/7„ є5С , поэтому v„eS(p„ , С ). Далее, по лемме 3.2.2 Р(Рй (р)) = рИ/(ии,С)) (р)) ::g(»B p)-g("B»0 g(«w (pw tf))-g(«w C) №b(C) RQ(P")R0(C) откуда по свойству #i -последовательности отсечения и лемме 3.2.1 получаем РО». ,«(Р)) ЖУ) .с) -р (У) ,с«).
Но я(р) = /(vw, (О ), поэтому / „ , я(р)) - g(v„, р ) - g(v„, (/ ") ), откуда, так как/?„ єаС , то g(v„, С ) - g(v„, (Р") ) /фД я(ря)). Осталось учесть, чтоДоЮ йо(Я).
Итак, при любом я мы получили, что существует опорная гиперплоскость л(рп) = 1(у„, С ) є S{pn , С ), гдер„ = л(1(ип, С)) є 8С , такая, что g(vm С ) - g{u„, (/ ") ) усдЦР") , С ). Первое утверждение теоремы доказано. Второе утверждение теоремы следует, как и в доказательстве теоремы 3.2.2, из сходимости Н\-последовательностей отсечения.
Теорема 3.2.4 полностью доказана.
Итак, в настоящем параграфе установлен факт двойственности классов АМПА, порождающих Н- и //і-последовательности восполнения и от сечения, состоящий в том, что последовательность из многогранников, со-полярных к многогранникам Н- (Н\-) последовательности восполнения, оказывается Н- (Н\-) последовательностью отсечения для полярного тела и наоборот.
Теоремы 3.2.1-3.2.4 позволяют распространять результаты исследования (см. главу 2) скорости сходимости и свойства оптимальности конкретных АМПА, генерирующих Я- (Яр) последовательности восполнения (отсечения), на скорость сходимости и свойства оптимальности двойственных к ним методов, порождающих Я- (Яр) последовательности отсечения (восполнения). В качестве примера, иллюстрирующего достоинства и недостатки такого подхода к исследованию свойств АМПА, исследуем свойства Н\-последовательностей отсечения и методов, генерирующих их, по свойствам -последовательностей восполнения.
Верхняя оценка для скорости сходимости многоугольников наилучшей аппроксимации
Основной результат, касающийся многоугольников наилучшей аппроксимации, сформулируем в виде следующей теоремы:
Теорема 4.4.1. Для CGW при п NQ(C) и у, 0 v 5(,%, С), справед ливо где N0(C) := 1 + o(C+B)N2 и ( f? с {l + j2 Доказательство теоремы 4.4.1. Пусть {T„}„=i&... - последовательность, порождаемая методом ЭЯ для СєҐв, Р" := conv Т„. По теореме 4.3.1 для любых п o(C+B)N2 и и, 0 v д\Р", С), справедливо
Учтем, что при [ є2 справедливо Ш(і,-) иЯ(є2,-). Пусть JVo :== 1 + c(C+B)N2. Величина о\. м С) определена при п 3. В этом случае по свойству 4.3.3 справедливо Р" є Рп{С), откуда
Но NQ(C) 1 + 2л! \г 3. Поэтому для любых п N0, таких что ф"Л, С) О, и ц 0 v 5( „, С), справедливо , + l,J P,Z(extC)]. [ 1 + 2 , Теорема 4.4.1 доказана. Теорема 4.4.1 допускает более простую формулировку, применение которой в численных расчетах, однако, затруднительно. Эта формулировка потребуется далее при получении верхних оценок аппроксимируемости ВКТ. Теорема 4.4.2. Для Се Є при п NQ(C), %i?m С) 0 справедливо " + lsJV",c,(C где ЩС) := 1 + а(С+В)Н2 и Ne(C) := Km supNS_V(C). v- +0 Доказательство. Действительно, при є\ є2 справедливо 9Я(є\,-) 9Я(б2,-)- Поэтому функция NJ C) является невозрастающей. Далее утверждение теоремы непосредственно следует из теоремы 4.4.1. Теорема 4.4.2 доказана. Теорема 4.4.2 позволяет дать верхние оценки числа вершин МНА, необходимых для достижения любой заданной точности аппроксимации.
Следствие 4.4.1. Для С илюбых є и ц 0 v є, справедливо min {п: %&т Q s} max {N0(Q, Ne.,(C)}, где NQ(C) и Nb(C) определены в формулировке теоремы 4,4.1.
Доказательство. По теореме 4.4.1 для любых є, 0 є, п NQ, таких что о\Р", С) є,и ц0 v є, справедливо 1 + л/2 Таким образом, max {«: о\&п, С) є} + 1 max {NQ, Ns-y). Ho max {и: %ifn, C) є} + 1= min {n: o\:fn, С) є}. Следствие 4.4.1 доказано.
Теорема 4.4.1 позволяет дать верхние оценки величины д\іУп, С) для любых значений п NQ. Следствие 4.4.2. Для СеУ и любых n Nu, справедливо д&т С) Sn(C) := min {є 0: NC) n), где NU{C) и NC) определены в формулировке теоремы 4.4.1.
Доказательство. Прежде всего, в силу непрерывности справа функции NC) минимум в определении величины 5„(С) достигается. Предположим теперь, что Ь\іРп, С) 8п(С). Тогда для любого малого v имеем что противоречит утверждению теоремы 4.4.2. Следствие 4.4.2 доказано. Следствие 4,4,3. Существуют С eft и положительное є , такие что для всех є,0 є є , и v, 0 v s, справедливо min {«: b\Vn, С ) є} =N JC% где величина Nb{C) определена в условии теоремы 4.4.1. Доказательство. Действительно, пусть РєіУ\{В), т (Р) = N. Обозначим рР := min {р(р, q): р, q є М (Р)}. Так как р(р, q) p{Z(p\ Z(q)\ то ЯЯО, Z(ext Р)) = N, 0 fi рР. Так как Pe&N(B), то N0 (Р) NQ (В). Поэтому при N N0(B) и єі (1 + л/2) РР справедливо max {No(P), N Р)} =N.C другой стороны, min (и: & т Р) є} = N, є 5(#V./, Р). Итак, при N ЛГ0(Я), С є ;%{), т (С ) = Nu є є := min {р/(1 + л/2)2, 5(j%b С)} справедливо min {л: %?„, С) }= max {N0(P), NUQ} = WQ. Следствие 4.4.3 доказано.
Таким образом, верхние оценки в утверждениях теоремы 4.4.1 и следствия 4.4.2 достижимы. В настоящем разделе будет получена верхняя оценка нижнего и верхнего аппроксимационных чисел произвольного ВКТ. Теорема 4.5.1. Пусть Сєг#. Тогда .(с) яад г(2е! С). Доказательство. Утверждение теоремы достаточно доказать для а(С). Если существует N такое, что 5[% С) = 0, значит, Ceff и а(С)-0. Но в этом случае card (ext С) = card (Z(ext С)) оо. Поэтому dm Z(ext С)) = 0, так что утверждение теоремы выполнено.
