Бабенко - Основы численного анализа (947491), страница 58
Текст из файла (страница 58)
Таблица произвольного элемента ф и Х будет состоять из двух частей: слова Ту в алфавите Ао и расшифрооыоающего алгоритлга В. Предполагается, что имеется еще алфавит А~ и расшифровывающий алгоритм 1) является алгоритмом в нем. В частности, в качестве алфавита Аг мы можем взять алфавит какого-либо языка программирования 275 З 2. е-ентрекил кемпакглее высокого уровня. Длина слова Т? называется длиной таблицы и обозпачается через 1(Т?). Отметим, что содержание таблицы.
т. е. слова Т?. для ралли шых элементов компакта разное, а расшифровывающий алгоритм один. 11редполагается, что рас>пифровывающий алгоритм потенциально определяет по слову Т? некоторый элемопт д? е В. Так, в рассмотренном выше примере расшифровывающий алгоритм сводился к алгоритму вычисления значений некоторого мпогочлеиа пятой степени„и поэтому элемент д? это сам мяогочлеп. Так может быть пе всегда. Но расшифровывающий алгоритм должен позволить восстановить график элемента д?, для чего его нужно заставить проработать на некотором счетном всюду плотном множестве из области значений аргумента. После этого полученное множество следует замкнуть.
Это и будет график элемента д?. Точностью таблицы Т? называется величина и? =, ?' — дТ . Рассмотрим множество таблиц (Т>н 1 ~ Х., 1(Т?) < й>) элементов компакта Х, длина которых це превосходит некоторой величины?>>. Расшифровыва>ощи>й алгоритм 11 позволяет построить отооражепие й,: (Ту:,? й Х, 1(Т,) < Л ) -- В. (3) Введем величину, характеризующую точность метода табулировапия элемеятов компакта с помощью таблиц длины, не большей Ж: >> = — эир е?.
Множество таблиц конечное множество, поскольку табли?ех ца — это двои >нос слово. Следовательно, отображение (3) определяет в В конечное множество ем-сеть для компакта Х. Поэтому сразу же возникает ряд вощ>осов. Как построить наиболее оптимальную таблицу, чтобы при заданной ее длине была минимальна величина е»? Не будет ли для оптимальной таблицы и к>>-сеть минимальной длины'? Как связаны между собой величины е>е и >х'? Чтобы ответить яа эти вопросы, рассмотрим теорию е-энтропии. 3 2.
к-энтропия коьтпактов 1. Метрический порядок компакта. В 3 1 мы рассмотрели задачу о длине минимальной "-сети. Исследование минимальных е-покрытий компакта Х провели в 1932 г. Л.С. Понтрягин и Л. 11Шпирельмап 190). Оии рассмотрели е-покрытия замкнутыми множествами и ввели минимельндн> мощность таких покрытий. обозначив ее через >х'(е: Х). Эта функция принимает целые положительные значения и при е — 0 неограниченно возрастает.
Ясно, что?у>(е; Х) метрическая характеристика компакта Х. В работе 190) введен метрический порядок компакта Х; 1ой Ж(е; Х) Й= 1цп -е 1оя(1/е) Ясно, что 0 < й < со; метрический порядок, зависит от метрики, введенной па компакте, и ие является топологяческим инвариаптом. В работе 190) показано, как в Рк' вложить простую дугу, для которой й = 1. В то 276 Глава 4. Творил табулироваиия и -эатпроаия же время простая дуга как гомеоморфный образ отрезка является одномерным компактом.
Если па компакте Х вводить различные метрики, то его метрический порядок будет меняться. Теорема 1 (Понтрягина — Ш1ннрельмана. Нижнлл грань метрических порядков длл всевозможных метрик, компакта Х равна его размерности: 1п1 Й вЂ” "- г11тпХ. Ниже через т«т(в; Х) обозначим минимальную мощность 2е-покрытия компакта Х замкнутыми множествами. Назовем е-.энтропией компакта Х величину Н(сч Х) .—..
1оиХт(г: Х) (см. [от91). Здесь и в дальнейшем логарифмы берутся по основанию 2. В работе 159) введены еще две характеристики компактов. Согласно теореме 3 ~1 гл. 2, если компакт Х С В, где  — метрическое пространство, то в В для любого е > 0 сутцествует конечная -сеть для Х. Следовательно, при любом е будет существовать г-сеть лоишмальной мощности тэт(е; Х, В). Назовем в-энтропией компактаа Х отттосительно В величину Н(е; Х, В) =!одетт'(щ Х, В). Множество 971 С В называется е-различимым, если любые две его точки лежат на расстоянии, большем е. Обозначим через ЛХ(=-, Х) .мощность максимального е-различимого подмножества множества Х. Назовем е-емлтостью компакта Л величину С(: Х) =" 1ои т11(е; Х). Заьтетим, что поскольку множество Х непусто, то тт'(е) > 1.
Лт(г; Л, В) > 1, ЛХ(в; Л) > 1, и поэтому три введенные функции неотрицательны. Докажем несколько простых теорем о свойствах этих функций. Теорема 2. Длл произвольного колтая;тпа Х, лежащего в лтетарическом прошпронстве В, именэт местпо неравенотва С(2е «) < Н(в Х) < Н(. «В) < С(е «) Доказаткльство. Очевидно, достаточно устаповитгь что ЛХ(2гц Х) < Хчт(е; Х) < Х(в: Х, В) < ЛХ(е: Л).
(1) Пусть (хт, ...,,т,„), где р = М(е: Х) максимальное е-различттмое множество. Тогда оно является е-сетьто для Х, ибо в противном случае в Х нашлась бы точка у, расстояние от которой до точек хт, ..., х„было бы больше г. Но это противоречит максимальности множества (хт, ..., х„).
Поэтому 1ч'(е: Х, В) < М(е; Х). Пусть (ум ..., у„) е-сеть в В для множества Л. Рассмотрим ша- ры Т, = (этй В: р(от у,) < ) (э =1,2, ...,9). Множествами,=Т,ОЛ (т' = 1, 2, ..., 9) образуют 2г-покрытие компакта Х. Следовательно, т«т(е; Х) < о; в частности. тч'(е; Л) < тч'(е: Х, В). Если имеется 2е-покрытие компакта Х и 2е-различиьтое множество, то число точек во втором не болыпе, чем число элементов 2е-покрытття, 277 З2. с-знтропия коллпактов ибо в противном случае в одном из множеств 2»-покрытия лежало бы не менее двух точек 2»-различимого множества, что противоречиво.
Таким образом, 31(2в, Х) < Х(в, Х). П Заметим, что если Лн Хх компакты и Х1 с Хз а Г(е: Х) какая-либо из введенных функций, то Г(е; Х1) < Г(»; Ла). Следующее свойство носит несколько более тонкий характер. Теорема 3. Все введенные длункции как функции от в являются невозрастающими при возрасгпании в. Функции Н(в: Х) и С(в; Х) непрерывны справа. Доказатвльство. Ясно, что первая часть теоремы непосредственно следует из определений. Вторую часть теоремы докажем для функции .'И(в; Х). Пусть 31(в; Л) = п и (хн ..., х„) соответствующее во-различимое множество. Пусть»1 = пппр(хп х,) > ев, если»в < е < вп !' то Лд(;-; Х) > и.
Но в силу монотонности И(е; Л) = и. Доказательство непрерывности справа функции Н(в: Х) см, в [60[. П Будем говорить., что пространство В ценшрируемо, если для ли~бого множества Т диаметра д существует точка то с В такая, что для любой точки х с Т имеем р(х, хв) < д12- Предложение 1. Если В центрируе,мо, шо для любого компакта Х с В Н(»; Х) = Н(в: Х. В). (2) ДОКАЗЛГВЛЬСТВО. В СаМОМ ЛЕЛЕ, Пуетв [»ЛМ ..., »зв) ЫИНИМаЛЬ- ное 2в-покрытие компакта Х. В каждом множестве ш „найдется такая точка з:, что р(х, х,) < в для любой точки множества ш .
Поэтому точки (хм ..., х„) образуют в-сеть для Х. Отек~да 1я'(в; Л, В) < Ж(е; Х) и поэтому по теореме 3 имеет место соотношение (2). П Это предложение можно уто.шить в том смысле, что потребовать цептрируемость только от компакта Х. Это означает, что для любого множества Т с Л диаметра д в В найдется точка хо, от которой любая точка х й Т находится на расстоянии, не большем д1'2.
Ясно, что для таких компактов предложение 1 остается в силе. Если  — компакт, В =- С[В), Х с В компакт, то, согласно лемме Ерохина, компакт Х центрируем. Поэтому в С[11) Н(в; Х) = Н(ш Х С[В)). (3) 2. Оценка энтропии некоторых множеств. Рассмотрим несколько простых примеров оценки энтропии некоторых множеств. Если Х конечное множество, Х = (хм,,,, х„), то знтропивй этого множества называется величина Н(Х) = 1ой и.
Если (хн,,,, хо) трактовать как записи, но отвлечься от их содержания. то для идентификации отдельных элементов нам потребуется и различных ключей. Если ключом будет двоичное слово, то очевидно, 278 Глава 4. Теория табулирооаииа и е-отправил что минимальная длина таких слов Й будет определяться из условия Й = = (Н(Х)) -, '1, если Н(Х) - нецелое число, и Й = Н(Х) .
в противном случае. В самом деле, 2а 2!и!лЕт1 > эн!х) и если Н(Х) .- нецелое, то очевидно, что 2" а < и. Таким образом, слова длины Й могут ш|ужить ключами для файла (та, ..., х„). Если Х вЂ” замкнутое ограничешюе множество 1-мерного пространства (т. е. компакт), содержащее бесконечно много различных точек, то очевидно, что Н(е: Х) о сс при е — О. Легко получить оценку сверху для в-энтропии. В самом деле, мы можем заключить компакт Х в куб с ребром а. Если мы построим покрытие этого куба малыми кубами с ребром 2 /чг1, то получим требуемое покрытие компакта Х. Мощность покрытия не превосходит величины Таким образом, п(е; Х) (~ ( ) е (!+0(1)), и, следовательно, Н(в; Х) < 1!п(1/ ) -'- С. С другой стороны., если компакт Х имеет внутренние точки, то в этот компакт можно вписать некоторый куб, Построив в этом кубе 2в-различимую сеть, получим, что ее мощность = (1/ ), и поэтому по теореме 2 Н(е; Х) < !!п(1~в) — Сы где Сз > О некоторая константа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
