Бабенко - Основы численного анализа (947491), страница 62
Текст из файла (страница 62)
- ("') е,г(2Лс) Учитывая неравенство (4) н предложение 5 3 3 гл, 3, имеем оценку 3 ,3„< г+ — 1оиг — , 'С., где С некоторая константа, .значение которой нетрудно определить. Из сказанного вытекает следующий способ табулировання функпин конечной гладкости. В узлах хе...., хг л запоминаем величины У(хе),, Х(х„~), а в остальных узлах х,, х„лишь младлпие раз- РЯДЫ ЧНСЕЛ ф(Х„), ..., Т"(Хп) И ИХ ЗНаКИ. ЕСЛИ !Г"!, < Ж, тО НаэаПОМИНание этой информации потребуется слово длины, не большей 2ХЛ, г 1ои ' 4 (н, — г + 1)~3г 4 1. 'сем самым расшифровывающнй алгоритм таблицы будет состоять из двух частей. В первой из ннх вычисляется значение р(хь ,) = = зип р(хь.~.,) (... + гсб2 1 +...), а затем разряды, отвечающие у ) гп Итак, чтобы определить Т(хьк,) с точностью еД2Л,), нам на основании неравенства (5) достаточно задать младшие разряды числа ,((хь~.,-): нл2 "л —, гол л2 ' ~ -...
+ и, р2'' о, где и, двоичные цифры., в. р определяются из условий 2 ' < о„е < 2 ' ~, 2 ' " < е~(2Л,) < < 2 — л — РЛ-1 Если окажется, что !р(хек,) ~ < о,е, то кроме разрядов осси ..., ос,л „ нужно задать еще зяак числа 1(хьо,). Чтобы запомнить всю эту информацию, достаточно использовать двоичное слово длины, не большей 296 Глава 4. Теория тобулирооаиия п е-литроп я ~(Л1) 0~ 2з~" (г —.
1) ~ и поэтому длина таблицы 1(ТХ) не будет превосходить величины ЛХ 'Хл 2ХЛ, 1(ТХ) < о( — ) )1(3, ' г1ой (7) где а = епр2~~"(г — 1) ~(г!)~Х' константа, не зависящая от г. ~ >2 Пусть рг'" (ЛХ., М: 1) = И'" (ЛХ: 1),'~ (Х 6 С(Х): ~Х < гХ). Из неравенства (7) следует, что ЛХ 1Д. 2ЛХЛ„ Н(е: 11'".(ЛХ, Х: 1)) < о,1„( — ) !1 — г1о8 ". (8) Рассмотрим, какие изменения нужно внести в данный способ табулирования в случае функций многих перомопных.
Теперь мы будем пользоваться многомерным сплайном 1(х; Х) и неравенством (3.6.8), в котором шаги сетки Лм ..., Лл выберем так же, как и при оценке поперечников в з 7 гл. 3. Запишем более грубое неравенство, чем (3.6.8): ~Х(х) — 1(х; Х) ~ < А, ~ ЛХ„Ь"' —, Л„... Лп швх Х(х") - Х(х~) ~, где Аг — константа, зависящая только от т. Если е ) О -- точность таблицы, то округленные значения функции в узлах нужно выбирать так, чтобы для любого узла х~ выполнялось неравенство ~~Х(х~) — Х(х~) ~ < < е Х(2Лт... Л,,). Если п = (6о - а„)/Ь„то мы возьмем минимальное п, для которого ЛХ16,"' < еХ(21А,), Х вЂ” -- 1, 2,..., й (9) Поэтому ~Х(х) — Х(х: Х) < е, Как и в одномерном случае, запоминать все приближенные значения функции Х пе надо, а надо запомнить лишь затравочныс величины Х(хь), где и = (Йм ..., )и) (О < (гу " .г; — 1, Х = 1, 2, ....,1).
Первая часть расшифровывающего алгоритма будет восстанавливать значения Х(х~) во всех узлах. Это можно делать последоватольно, начиная с двумерной плоскости (х: а~ < хт < 6ы ав < хз < 6х хз = аз, .), где где з определено выше, будут заменяться соответствуюп1ими разрядами из таблицы и будет уточняться знак результата. Сделав цикл по Л от О до и — г, мы восстановим значения Д(хо) во всех узлах, а затем вторая часть алгоритма выстроит сплайн Х(х, Х). Из неравенства (1) следует,что з4.
Табрлирооо!«ис» и г-энтропия фу««кц«»и конечной гладкости 297 ситуация сводится к уже рассмотренной одномерной, затем можно перейти к трехмерным плоскостям и т.д. Знание младших разрядов во всех узлах х~ поможет полностью восстановить значения у(х~). Очевидно,. чго для запоминания младших разрядов достаточно иметь слова длиной (1ой(2Л„,, Л,,аги + 2 = »д„, где а аналог константы а,, Подсчитаем длину таблицы. Из неравенств (9) вытекают равенства и ((2УА )«Ук»((» о )(»И — !)«Ук» ~ и поэтому число узлов сетки будет равно р «ул .=П(,- ) =(2УА,)"Я(-') "( -О(" -)), у=! где «„=.- п«ахг,, 1,«р .= 2 1«»г, и у«~Ус = П Л1 "'. Предположим, что »=! >=! ф < 1«'., тогда У(ТТ) <.у,( — ) /1/+«!...гу!ой "' "., (10) р «Уе 2ЛУЛ„,...Л„ где ус некоторая константа, зависящая только от т.
Можно показать, что "у, < г! +... -, 'г! + о(г! +... + ц ). Из (10) вытекает неравенство Н(е: И'" (М» Л»:, 1)) < 'у 1 ~ — ) + ««... г! 1ок "' "', (11) р «Уе 2ХЛ„,... Л„, Найдем для е-энтропии оценку снизу и покажем, что предложенный способ табулирования даст оптимальные таблипы. Пусть 1" (и т 1)-мерный куб со стороной д, пестр«»енный при доказательстве предложения 2 з7 гл. 3. Этот куб изометрично вложен в компакт И'" (М, »««, 1), н его размерность и и длина ребра Б связаны соотношением д > Сес1'оу«п е. Вершины куба определяют в нашем компакте О-различимую сеть мощности 2кт .
Взяв д = йе, отсюда получим кт! р» «у С(2, Ы'(М Л'1)) > (Сс)'Уо,У ( —" — 1, (12) По теореме 2 з 2 отсюда получаем оценку снизу для е-энтропии. Неравенства (П), (12) остаются в силе и в общем случае р ф оо. Пусть Х = Ы» ' (М, Ж; 1), где 1 < р < со» рр > 1. Имеет место 'Теорема 1.
Нри сделанных с«редиолохсенилх при " < ее имеют место оценки Св(т, р)!Е!( — ) < Н(е, Х) < С«(г, р),1,:( — ) — '«.!... г! Уо — +11(г, р), у««уе «уе у«« е Е где СоСт', р), С«(г» р), Р(г, р) — коистинть«, зивисл«цие только от ъ, р. 298 Глава 4. Теория табулирооаяил п о-онтровттл Мы привели доказательство этой теоремы при р = ж; при р ~ сю она доказана в [18[. Иными хлетодами эта теорема была доказана в [33[. Случай гт =...
=- гт, р =- со рассмотрен в [60], а случай гт... гп 1 < р < <оо вЩ. 3 а д а ч н. Задача о главном члене аснмнтотики е-энтропии для иэотропного класса И" выдвигалась Л.Н.Колмогоровым. Задача о главном члене асимптотики а-энтропии класса И" (ЛХ; Х) имеет большое значение для численного анализа, поскольку через о-энтроттию выражаются основные характеристики многих алгоритмов.
Такого рода примеры мы приведем в следующей главе. Поэтому мы также выдвигаем эту важнуто задачу. 1*. Выясните вопрос о существовании предела 11 О(е: Л)[Х -'Я о и (13) и вычислите этот предел, если он существует. Здесь Х .—. И'" (ЛХ, Лт; Х). В о 7 гл. 3 мы сформулировали аналогичные задачи об асимптотике функции пс(=-, И" (М; 1), С[Х)), где б =- о, д. Мы выдвинули гипотезу, что суще- ствует и и. (=; И " (М; Х), С[Х)) [Х-'Я". Обозначим его через о(о, г, р). Предел (13) обозначим через т(г, р) (естественно, предполагая, что он существует), 2*.
Вычислите отношение т(г, р) то(ст, .т., р) =- д(ст, г, р) (14) при условии, что 1 < р < ж. Это отношение — исключительно важный параметр. Поскольку при сделанных предположениях В(о, т', р) = ' — , 'о(1), О(е; Ит" (М, М;1)) (:, р) (; И7(М, Х), С,Х)) то Д(о, г, р) равно среднему числу битов на один параметр при оптимальном их выборе, которые необходимы для описания элементов компакта Ит,", (ЛХ, Л1; 1) с точностью -. В то время как для аналитических функции эта характеристика давалась формулой (3,24) и стремилась к "о при о О, для классов гладких функций . с(о, г, р) — величина конечная. Таким образом, при переходе от нефтшитного способа приближенного задания элементов компакта с помощью набора парамет1юв к финитному способу приближенного задания Зймкчйнив.
Если рр < 1, то сохраняются оценки -энтропии класса 1Ф ' (М; Х). рассматриваемого как подмножество пространства Хо(Х), где т4 < р(1 — рр) т. Способ табулирования, приведенный в [18[, пригоден и здесь, но только нужно запоминать не приближенные значения функции Х' в узлах (эти значения могут быть не определены), а значение некоторого среднего от Х.
Принцип экономии старших разрядов действует и здесь. Полученные результаты переносятся и на случай нецелых тЗ (у=1,2,...,1). 24. Табулирооонио и г-шевронил 4ункции коночной гладкоогви 299 (с той же точностью) в случае оптимального их выбора нужно израсходовать конечное число битов на один параметр, какова бы ни была точность приближенного задания. Зе. Покажите, что 3(о, г, р) й(г~-'...— г~) при г, оо 0 =- 1, 2, ..., 1). где у --некоторая константа. Рассмотрим класс И'" (М; 1) в случае нецелых гз (1 = 1, 2, ..., 1). Очевидно, как нужно распространить определение класса на нецелые г,.
В самом деле, будем считать, что функция У е и'" (лх; 1) как функпия х (з = = 1, 2, ..., 1) при фиксированных переменных тм ..., ло м кг ь, ..., г~ непрерывно дифференцируема (г,) раз па отрезке (аэ, Ьг . Если гэ -- целое чис ю, то в этом определении под г,) нужно понимать г, — 1. 4*. Докажите, что теорема 1 остается в силе для класса И (ЛХ; 1) при нецелых г, (з = 1, 2,..., 1). Первые три задачи до сих пор не нашли своего решения.
2. Проклятие размерности. В связи с затронутыми вопросами остановимся на роли размерности пространства независимых переменных. Функция л,.( ) и в-энтропия определяются в основном величиной (у/г) ь1о. Величина р, которую целесообразно именовать гладкостью, существенным образом влияет на объем таблицы либо па число параметров, необходимых для приближенного представления функции. В изотропном случае г~ =... = г~ = г мы имеем р = г((, и, таким образом, Н(г; Х) — (д1г)Н', Стало быть, при прочих равных условиях объем таблицы гладкой функпии растет зкспоненциально с ростом й В этом состоит феномен, именуемый прокллтислз ролмерности.
Желая иметь реалистические алгоритмы, мы вынуждены с увеличением 1 работать со все большими значениями г. Во многих задачах это возможно, так как решение потенциально бесконечно дифференцируемо, и надо только уметь этим воспользоваться. Даже в трехмерных задачах газовой динамики, где решение имеет разрывы (ударные волны) или локальные особенности (пентрированные волны разрежения), решеяие ме.иду разрывами организовано просто и гладко. Поэтому, выделяя разрывы, можно создать эффективные алгоритмы решония трехмерных задач газовой динамики. Данные соображения о роли числа независимых переменных интересно сопоставить с теоремой Колмогорова о суперпозипии функций [164, 165].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
