Диссертация (1149786), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Однако, для быстро меняющихся потоков равномерные сетки представляются недостаточными, но перейтик неравномерной сетке в рамках кратно-масштабного анализа и предыдущейтехники весьма затруднительно. В дальнейшем был разработан другой подходк построению вейвлетных разложений (см. [2, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18,21, 22, 23, 25, 26, 27, 28, 29, 30, 37, 38, 55]).

В предлагаемой работе этот подходприменяется к сплайн-всплесковому разложению числовых информационныхпотоков, ассоциированных с областями трехмерного пространства:ue(ξ) =Xcj ωj (ξ),jздесь ωj — функции, получаемые из аппроксимационных соотношений и связанные с симплициальным подразделением, допускающим локальное укрупнение. В качестве функций ωj рассмотрены функции Р. Куранта и М. Зламала.С упомянутым подразделением и с подходящим его укрупнением связываются два пространства: исходное пространство и лежащее в нем так называемое7основное пространство; проектирование первого из них на второе порождаетвсплесковое разложение.Привлекательными свойствами этой модели являются локальность, устойчивость, простота алгоритмов декомпозиции и реконструкции поступающихпотоков, асимптотическая оптимальность по N -поперечнику стандартных компактов [12].

Локальность, в свою очередь, позволяет обеспечить параллельностьпроизводимых вычислений (см. [24, 37]).Обращаясь к истории вопроса, заметим, что появлению вейвлетов рассматриваемого типа предшествовали работы, проводимые многими ученымив трех различных направлениях; дадим их краткое описание.Исследования в области обработки больших числовых массивов информации восходят к трем источникам, возникшим независимо друг от друга: к классической теории сплайнов, к методу конечных элементов и к теории вейвлетов. В соответствии с этим можно выделить по крайней мере три направленияразвития теории обработки упомянутых массивов.

Первое направление беретсвое начало от работ Шонберга [84]; здесь исходным моментом является решение какой-либо задачи интерполяции (задачи Лагранжа, Эрмита или ЭрмитаБиркгофа) в классе функций с «кусочными» свойствами и с определенной гладкостью в узлах рассматриваемой сетки (см. [50, 78, 85]). Заметим, что если исходный массив числовой информации задан как сеточная функция на мелкойсетке, то замена этой сеточной функции на результат решения интерполяционной задачи для крупной сетки (являющейся подмножеством мелкой сетки)может рассматриваться как сжатие исходного массива числовой информации.Аппроксимационные свойства и вычислительная простота получаемых сплайнов всякий раз исследуются дополнительно.

Сюда относятся современные исследования по обобщенным сплайнам, так называемым ECT -B-сплайнам (см.,например, [50, 78]); в этих работах для построения сплайнов на сеточных промежутках используются различные ECT -системы, которые при определенныхусловиях удается гладко «склеить» в узлах.Второе направление опирается на аппроксимационные свойства рассматриваемых функций, где определение базисных функций связано с решением аппроксимационных соотношений, рассматриваемых как система уравнений (этиисследования появились в связи с теорией метода конечных элементов, см. [40,58, 90]); при таком подходе интерполяционные свойства и алгоритмы минимиза-8ции вычислительной сложности (вложенность пространств и вейвлетное представление цепочки вложенных пространств) приходится устанавливать дополнительно.

Выбор порождающей m + 1-компонентной вектор-функции ϕ(t), заданной на интервале (α, β), определяет семейства конечномерных пространствна элементарных сеточных интервалах рассматриваемой (конечной или бесконечной) сетки X = {xj }, X ⊂ (α, β), а выбор цепочки A векторов со свойствомполноты приводит к пространству (X, A, ϕ)-сплайнов. Условия гладкости эквивалентны определенным алгебраическим соотношениям между значениями ϕ(t)(и ее производных) в узлах сетки и векторами цепочки A. Требование максимальной гладкости сплайнов (при выбранной вектор-функции ϕ(t) с отличнымот нуля вронскианом из ее компонент) однозначно (с точностью до постоянныхотличных от нуля множителей) определяет цепочку A; при этом однозначноопределяется также пространство (X, A, ϕ)-сплайнов, которое в этом случаеназывается пространством Bϕ -сплайнов (см.

[15, 20]).Третье направление — теория вейвлетов — в основу кладет вычислительную простоту, отражением чего является кратно-масштабное уравнение(см. [31, 39, 53, 75, 87]); исследование последнего приводит в первую очередь ковложенности получаемых пространств и к вейвлетному представлению соответствующей цепочки вложенных пространств (это ведет к минимизации вычислительной сложности численных методов); остальные из перечисленных вышесвойств с бóльшим или мéньшим успехом исследуются дополнительно (см., например, [39]).В настоящее время стало ясно, что эти три направления представляютсобой разные подходы к исследованию и классификации потоков числовой информации. Каждый из этих подходов позволяет учесть разные свойства такихпотоков, так что определенное их объединение позволяет получить эффективный результат.Иллюстрация схемы построений (одномерный случай)В этом пункте дадим иллюстрацию применяемых методов в одномерном случае.Другие примеры могут быть найдены в работах [13, 18, 21, 38] и др.Пусть L — линейное пространство вещественных функций, заданных на9интервале (α, β) ∈ R1 .

Рассмотрим сеткуX : . . . < x−2 < x−1 < x0 < x1 < x2 < . . . ,lim xj = α,j→−∞lim xj = β,j→+∞defи вектор-функцию ϕ(t) = (ϕ0 (t), ϕ1 (t), . . . , ϕm (t))T , t ∈ (α, β) с компонентами изпространства L: ϕi ∈ L, i ∈ {0, 1, . . . , m}.В дальнейшем наряду с интервалом (α, β) рассматривается также отрезок [a, b], содержащийся в этом интервале: [a, b] ⊂ (α, β). След рассматриваемыхздесь функций на этом отрезке позволяет рассматриваемые дальше бесконечные суммы заменить конечными, от бесконечномерных пространств перейтик конечномерным, а бесконечные потоки числовой информации заменить конечными, не нарушая схемы рассуждений и сохраняя правильность получаемых результатов.defРассмотрим множество G линейных функционалов g (s) ∈ L∗ , G = {g (s) }s∈Z ,со свойствомsuppg (s) ⊂ (xs , xs+1 )∀s ∈ Z.(1)Действие функционала g (s) на функцию u ∈ L обозначается острымискобками hg (s) , ui, а действие этого функционала на вектор-функцию ϕ(t) даетвектор-столбец с числовыми компонентами по формулеhg (s) , ϕi = (hg (s) , ϕ0 i, hg (s) , ϕ1 i, .

. . , hg (s) , ϕm i)T .defПусть выполнено условиеdet(hg (s) , ϕi, hg (s+1) , ϕi, . . . , hg (s+m) , ϕi) 6= 0∀s ∈ Z.(2)Положимas = hg (s) , ϕi.def(3)Из (2) следует, что система векторов as , as+1 , . . . , as+m+1 линейно независимаяпри каждом s ∈ Z. Рассмотрим аппроксимационные соотношенияkXi=k−mai ωi (t) = ϕ(t)∀t ∈ (xk , xk+1 )∀k ∈ Z,(4)10suppωs ⊂ [xs , xs+m+1 ]∀s ∈ Z.(5)Благодаря условию (2) из соотношений (4) – (5) функции ωi (t) определяютсяdef Sоднозначно на множестве M = s∈Z (xs , xs+1 ).Предположим, что ωs ∈ L.Учитывая свойство (1) и обозначение (3), видим, что система функционалов {g (s) }s∈Z биортогональна системе функций {ωs }s∈Z :hg (j) , ωs i = δj,s∀j, s ∈ Z.(6)Рассмотрим линейное пространствоdefS = S(X, ϕ) = L{ωs }s∈Z ,(7)где L означает линейную оболочку функций, находящихся в фигурных скобках.e сетки X видаЕсли рассмотреть подмножество Xe : ... < xXe−2 < xe−1 < xe0 < xe1 < xe2 < .

. . ,lim xej = α,j→−∞lim xej = β,j→+∞e ⊂ X,Xто аналогично предыдущему с этой сеткой можно связать функции ωei и натяe ϕ), которое при определенныхнутое на них линейное пространство eS = S(X,условиях (например, в случае сплайнов максимальной гладкости) содержитсяв пространстве S(X, ϕ).Рассмотрим проектирование P пространства S в пространство eS, задаваемое формулойXdefPu =heg (s) , uiωs∀u ∈ S(X, ϕ),(8)s∈Zгде {eg (s) }s∈Z — система функционалов, биортогональная системе координатныхфункций {eωi }i∈Z .Заметим, что при каждом фиксированном t ∈ (exk , xek+1 ) сумма в правойчасти формулы (8) содержит не более, чем m + 1 слагаемых:defP u(t) =kXheg (s) , uiωs (t)s=k−m∀t ∈ (exk , xek+1 ).(9)11Проектирование P определяет вейвлетное разложение.S=eS + W.(10)Если для исходного потока c = (.

. . , c−2 , c−1 , c0 , c1 , c2 , . . .) числовой информацииdef Pdefрассмотреть функцию u(t) = j cj ωj (t), то ее проекция ue = P u на пространствоeS имеет видXue=ai ωeiidefи таким образом, определяет поток a = (. . . , a−2 , a−1 , a0 , a1 , a2 , . . .), соответствуdefющий укрупненной сетке, а также определяется вейвлетный поток b = (. . . , b−2 ,Pdefb−1 , b0 , b1 , b2 , . . .) из разложения w = u−eu по базису пространства S: w = s bs ωs .Переход от потока c к потокам a и b называется декомпозицией, а обратныйпереход — реконструкцией.e = {xk+1 }, формулыВ частном случае m = 1, ϕ(t) = (1, t)T при X\Xдекомпозиции имеют видai = ci при i 6 k − 1,bj = 0 при j 6= k,bk = −ai = ci+1 при i > k,xk+1 − xkxk+2 − xk+1· ck−1 + ck −· ck+1 .xk+2 − xkxk+2 − xkФормулы реконструкции можно записать в видеcj = aj + bjck =при j 6 k − 1,xk+2 − xk+1xk+1 − xk· ak−1 +· ak + bk ,xk+2 − xkxk+2 − xkcj = aj−1 + bjпри j > k + 1.Как было отмечено выше, сужение всех рассматриваемых функций наотрезок [a, b] приводит к конечным потокам, не нарушая логики рассужденийи получаемых результатов.Из предыдущего видно, что в основе предлагаемого подхода к построению вейвлетного разложения лежат аппроксимационные соотношения; поэтому порядок аппроксимации такого разложения асимптотически оптимален поN -поперечнику стандартных компактов.12О симплициальном подразделении специального видаКак видно из вышеизложенного примера, одним из ключевых моментов в схеме построения сплайн-всплескового разложения является наличие укрупняемой(желательно — локально укрупняемой) сетки.

Характеристики

Список файлов диссертации