Макеты страниц
А.3. Метрика Хаусдорфа IIМы продолжим обсуждение расстояния Хаусдорфа между двумя множествами в начатое в п. 3.5. Через К. обозначим совокупность всех непустых компактных подмножеств Несмотря на то, что в качестве основной метрики на мы принимаем евклидову метрику, определения и теоремы настоящего раздела применимы и к произвольной полной метрике, включая и -метрики на Иначе говоря, каждой полной метрике соответствует некоторая метрика Хаусдорфа на К.. Упражнения содержат примеры использования так называемой манхэттенской метрики. Рис. А.1. Определим расстояние между точкой и множеством следующим образом (рис. А.1): Предостережение: расстояние здесь и далее в этом приложении не должно автоматически интерпретироваться как метрика в соответствии с определением из п. 3.2. Некоторые расстояния, которые мы рассмотрим, не удовлетворяют аксиомам метрики. Строго говоря, следует использовать вместо в определении . Однако, так как множество Е предполагается компактным, то фактически означает то же самое, что и (упр. 5 в конце параграфа). Обобщим понятие расстояния от точки до компактного множества Е. Определим расстояние между двумя компактными множествами Е и F следующим образом (рис. А.2): Рис. А.2. Строго говоря, следует использовать вместо но вследствие того, что оба множества компактны, корректно и использование Более того, всегда существуют такие точки что (упр. 6 в конце параграфа). Естественно задать вопрос: является ли расстояние метрикой? Очевидно, нет. В частности, если , причем , то (упр. 8 в конце параграфа), что нарушает одно из свойств метрики. Так что же, поиск метрики для К. обречен на неудачу? К счастью, нет. Фактически, мы остановились слишком рано. Нам потребуется еще несколько новых понятий. Для вещественных чисел а и b введем: Рис. А.3. Метрика Хаусдорфа Н(Е, F) Определение метрики Хаусдорфа на К. таково (рис. А.3): Мы докажем, что Н(Е, F) является метрикой, в несколько этапов. Некоторые из них оставлены в качестве упражнений, включая: 1. Если , то (упр. 9 в конце параграфа). 2. Если , то или (упр. 10 в конце параграфа). 3. Если , то (упр. 11 в конце параграфа). Теорема А.3.7. Если задано формулой (А.6), то является метрикой на пространстве К. всех непустых компактных подмножеств . Доказательство. 1. . Это немедленно следует из определения (А.6), так как величины неотрицательны. 2. тогда и только тогда, когда . Если , то, очевидно, . С другой стороны, если , то В соответствии с пунктом 2, предшествовавшим теореме, мы должны получить . 3. . Это утверждение следует непосредственно из определения . 4. для любых , (неравенство треугольника). Во-первых, покажем, что для любых : и Для этого нам потребуется следующая элементарная формула (упр. 7 в конце параграфа): Тогда Докажем неравенство . Неравенство доказывается аналогично. Пусть . Тогда Для каждого Так как это неравенство верно при любом , то Рассмотрим, как можно использовать метрику Хаусдорфа. Пусть (X, d) — метрическое пространство. Напомним, что последовательность из X сходится к точке в -метрике, если Если «точки» — непустые компактные множества и Е, причем используется метрика Хаусдорфа, то утверждение о сходимости принимает вид: На практике определить расстояние Хаусдорфа между двумя множествами бывает непросто. К счастью, имеется альтернативный подход, позволяющий глубже понять метрику Хаусдорфа. Он связан с понятием расширения (дилатации), введенным в п. 3.5. Для заданного множества Е в и радиуса расширение Е радиуса обозначаемое как , определяется как векторная сумма где — замкнутый шар радиуса с центром в начале координат (рис. 3.2). Это можно записать и в следующем эквивалентном виде: Предостережение: в некоторых книгах расширения определяются с помощью открытых шаров, в то время как мы используем замкнутые шары. Наше предпочтение связано с незначительным упрощением доказательства следующей теоремы. Теорема . Пусть Е и F — компактные подмножества Расстояние Хаусдорфа удовлетворяет соотношению: Доказательство. Мы покажем, что в том и только в том случае, если . Из соображений симметрии такое же рассуждение приводит к тому, что в том и только в том случае, если . Предположим, что . Тогда для любой точки имеем откуда следует, что . Поэтому . Обратно, если , тогда для каждой точки существует точка такая, что Из этого следует, что для всех и поэтому Следствие А.3.3. Пусть — компактные множества. Тогда в метрике Хаусдорфа в том и только в том случае, если для каждого существует такой номер N, что из следует Следствие . Пусть — непустые компактные множества, упорядоченные по убыванию: Пусть Тогда Е непусто и компактно, и существует предел в метрике Хаусдорфа. Доказательство. Множество Е непусто и компактно вследствие стандартной теоремы о компактных множествах [42]. В соответствии со следствием надо показать, что для любого существует целое N такое, что из следует Так как множества упорядочены по убыванию, то а значит нам необходимо рассмотреть только первый случай. Множество будучи объединением шаров, открыто и содержится в . В соответствии с упр. 12 в конце параграфа, если пересечение последовательности упорядоченных по убыванию компактных множеств содержится в открытом множестве, то компактные множества сами содержатся в открытом множестве. Таким образом, компактные множества содержатся в . Данное следствие имеет непосредственное отношение к фракталам, которые образуются последовательным устранением открытых множеств. Например, это классическое множество Кантора, получаемое последовательным выбрасыванием открытых срединных третей интервалов. Используя это следствие, получаем, что аппроксиманты (рис. 2.20) сходятся к множеству Кантора в метрике Хаусдорфа. В качестве другого примера можно привести построение ковра Серпинского (рис. 2.5). Теорема А.3.9. Пусть К. есть совокупность всех непустых компактных подмножеств , а Н — метрика Хаусдорфа. Тогда метрическое пространство полное. Доказательство. Пусть — последовательность множеств в которая удовлетворяет критерию Коши для метрики Хаусдорфа. По упр. 3 из прил. А.1, существует такая константа М, что при и поэтому Зададим Тогда являются замкнутыми и ограниченными, а следовательно, компактными подмножествами . Пусть Так как множества упорядочены по убыванию, то из следствия А.3.4 вытекает, что в метрике Хаусдорфа при Мы покажем, что Е также является пределом исходной последовательности в метрике Хаусдорфа, то есть Пусть Существует целое такое, что из следует В частности, из второго условия при следует то есть . Так как удовлетворяет критерию Коши в метрике Хаусдорфа, то существует такое целое что из следует Зафиксируем При любом получим Таким образом, если то и формула (А.9) доказана. Теорема А.3.10. Если А — компактное подмножество — совокупность всех непустых компактных подмножеств А, то метрическое пространство где Н — метрика Хаусдорфа, компактно. Упражнения 1.3.1. Пусть 5 — периметр квадрата с вершинами (0,1), (1,0), (1,1) и (0,1). Нарисуйте расширение используя манхэттенскую метрику на Сравните результат с ответом к упр. 3.5.1. 2. Найдите расстояние Хаусдорфа Н(А,В) в пространстве, оснащенном манхэттенской метрикой: Сравните результат с ответом к упр. 3.5.2. 3. Пусть — манхэттенская метрика на Вычислите , где — точка (1,1), 4. Рассмотрим диск Положим, что решетка с размером ячеек накрывает D, а начало координат решетки совпадает с центром диска. Пусть есть наименьшее множество, представляющее собой объединение квадратов решетки, накрывающих а) Покажите, что расстояние Хаусдорфа Н, использующее евклидову метрику, обладает свойством: б) Покажите, что периметр множества удовлетворяет неравенству Как это связано с длиной окружности D в махэттенской метрике? 5. Покажите, что если Е компактно в то 6. Покажите, что если компактны в то всегда существуют такие точки , что 7. Покажите, что (а ) 8. Покажите, что если , то Более того, если 9. Покажите, что если и 10. Покажите, что если , то или . 11. Предположим, что E, F и G суть компактные множества в с евклидовой метрикой. Покажите, что 12. Убедитесь в верности следствия Если множество Е является пересечением компактных множеств и содержится в открытом множестве G, то при всех достаточно больших . 13. Покажите, что для
|
Оглавление
|