авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 |

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ На правах рукописи Усевич Константин Дмитриевич АНАЛИЗ ...»

-- [ Страница 3 ] --

Найдем линейные соотношения для h1. Из (3.4.4) получаем h1 = c1 +b1 = d d+1 d+1 d+ 2h1 c1 + c1, а значит h1 2h1 = 2 · 4d1. Таким образом, hd удовлетворяет d d d+1 d+1 d линейному рекуррентному соотношению h1 6h1 + 8h1 = 0, то есть d+2 d+1 d+ имеет параметрический вид h1 = a1 4d + a2 2d. Вычислим первые члены этой d последовательности c1 = 1, b1 = 0. По формуле (3.4.4), b1 = 1, c1 = 3. Таким 1 1 2 образом, h1 = 4.

Из предложений 3.4.3 и 3.4.5 следует результат о количестве ганкелевых матриц.

Теорема 3.4.1.

LK r /3, r min(L, K), LK,1 L(K+1) = r /3, r = K L, r LK r min(L, K) или r = L K.

, r Замечание 3.4.3. Заметим, что известен более простой способ нахождения hN [56], основанный на свойствах однородных идеалов. Возможно, похожим d способом можно найти и hN,1.

d Глава Результаты для двумерного случая 4.1. Траекторное пространство и ранг массива Для двумерного метода АСС важным является описание зависимости ран га блочно-ганкелевой траекторной матрицы массива от размеров окна. Для общего случая теории таких матриц, аналогичной [74], не существует. В этом разделе мы рассматриваем массивы, являющиеся подмассивами бесконечных массивов, для которых такое описание становится возможным.

4.1.1. Траекторное пространство и основные свойства ранга Определение 4.1.1. Линейное пространство, порожденное m n подматри цами массива F, def (M,N ) Nx M,Ny N L(M,N ) (F) = span({Fk,l }k,l=0 ), будем называть (M, N )-траекторным пространством массива F.

Так как собственные и факторные векторы образуют ортонормированные ба зисы соответственно пространств столбцов и строк матрицыW, системы{i }d i= и {i }d являются ортонормированными базисами (Lx, Ly )-траекторного про i= странства L(Lx,Ly ) (F) и (Kx, Ky )-траекторного пространства L(Kx,Ky ) (F) (см. (1.7.2) и (1.7.3)).

Определение 4.1.2. Размерность (Lx, Ly )-траекторного пространства назы вается (Lx, Ly )рангом массива rank(Lx,Ly ) (F) = dim L(Lx,Ly ) (F) = rank W(Lx,Ly ).

Выделим базовые свойства ранга.

Замечание 4.1.1. Так как W(Lx,Ly ) = (W(Kx,Ky ) )T, то rank(Lx,Ly ) (F) = rank(Kx,Ky ) (F).

Иными словами, функция rank(Lx,Ly ) (F) центрально симметрична относи тельно точки (Nx /2, Ny /2).

4.1.2. Тензорное произведение рядов Рассмотрим базовый пример двумерного массива, являющегося тензор ным произведением рядов: fm,n = pm qn. Покажем, что двумерное АСС-разло Nx 1,Ny жение массива F = fm,n может быть выражено через АСС разло i,j= Ny Nx жения рядов (pm )m=0 и (qn )n=0.

В матричных обозначениях произведением двух рядов P = (p0,..., pNx 1 ) и Q = (q0,..., qNy 1 ) является F = PT Q. Зафиксируем размеры окна (Lx, Ly ) и обозначим X(p) и X(q) ганкелевы матрицы, порожденные P and Q соответ ственно:

p0 p1... pKx 1 q0 q1... qKy p1 p2... p Kx q1 q2... qK y X(p) X(q) =, =.

......

......

......

......

pLx 1 pLx... pNx 1 qLy 1 qLy... qNy Тогда блочно-ганкелева траекторная матрица W, порожденная массивом F, является кронекеровским произведением W = W(q) W(p).

В этом случае имеет место следующая теорема.

Теорема 4.1.1 ([87, Th. 13.10]) Пусть X(p) и X(q) имеют сингулярные раз ложения dp dq (p) (p) (p) (q) (q) (q) j Uj (Vj ), l Ul (Vl ).

(p) (q) (4.1.1) = = X X j=1 l= Тогда разложение dp dq T (p) (q) (q) (p) (q) (p) (4.1.2) Uj Vj W= j l Ul Vl j=1 l= является сингулярным разложением матрицы W после перегруппировки (p) (q) слагаемых (по невозрастанию m n ).

Следствие 4.1.1. Ранг произведения рядов равен произведению рангов:

rank(Lx,Ly ) (PT Q) = rankLx P rankLy Q.

4.1.3. (Lx, Ly )-траекторное пространство бесконечного массива Рассмотрим бесконечный массив F. По аналогии с траекторным простран ством массива F введем (Lx, Ly )-траекторное пространство F и (Lx, Ly )-ранг следующим образом:

def def (L,Ly ) + L(Lx,Ly ) (F) = span{Fk,lx rank(Lx,Ly ) F = dim L(Lx,Ly ) (F), }k,l=0, (L,Ly ) def L 1,L где Fk,lx подматрицы бесконечного массива (ср.

x y = (fm+k,n+l )m=0,n= (1.7.1)).

Лемма 4.1.1. Пусть r(F) и A(1),..., A(r) порождают L(F). Тогда (Lx, Ly )-подмассивы A(1),(Lx,Ly ),..., A(r),(Lx,Ly ) порождают L(Lx,Ly ).

Важно также следующее утверждение.

Лемма 4.1.2.

L 1,Ly x rank(Lx,Ly ) (F) = dim span{Fk,l }k,l=0.

Доказательство.

(L,Ly ) + Набор подматриц {Fk,lx является столбцами следующей бесконечной }k,l= матрицы:

def (L,Ly ) W = [vec F0,0x :

(L,Ly ) (L,Ly ) vec F1,0x : vec F0,1x :

(L,Ly ) (L,Ly ) (L,Ly ) vec F2,0x : vec F1,1x : vec F0,2x :

...].

Строками этой матрицы являются развертки (с перечислением элементов в L 1,Ly том же порядке) бесконечных массивов {Fk,l }k,l=0. Утверждение леммы x следует из равенства столбцового и строчного рангов.

Из леммы 4.1.2 очевиден результат о соответствии r(F) и rank(Lx,Ly ) F.

Предложение 4.1.1. Равносильны следующие условия.

линейный рекуррентный массив, т.е. r(F) = dim L(F) +.

1. F 2. Существуют Lx0 и Ly0, такие что rank(Lx,Ly ) F = d + для Lx Lx0 и Ly Ly0.

3. rank(Lx,Ly ) (F) C для всех (Lx, Ly ), где C + некоторая кон станта.

Замечание 4.1.2. Пусть F линейный рекуррентный массив (см. раздел 2.2) его Nx Ny подмассив. Тогда L(Lx,Ly ) (F) линейной сложности d, и F L(Lx,Ly ) (F) для любых (Lx, Ly ) и rank(Lx,Ly ) (F) d. В разделе 4.2 мы найдем область значений (Lx, Ly ), для которых rank(Lx,Ly ) (F) равен d.

Замечание 4.1.3. Существуют массивы, для которых I(F) = {0}, но в то же время r(F) = +.

Пример 4.1.1. Массив fm,n = sin m · ln(n + 1), для любых размеров окна (Lx, Ly ), Lx 2 имеет ранг rank(Lx,Ly ) (F) = 2Ly. При этом массив удовлетво ряет линейному рекуррентному соотношению fm+2,n = 2 cos(1)fm+1,n fm,n.

Легко показать, что конечный подмассив F размера Nx Ny будет иметь (Lx, Ly )-ранг равный 2 · min(Ly, Ky ) для любых размеров окна (Lx, Ly ), таких что 2 min(Lx, Kx ) Nx /2, 1 min(Ly, Ky ) Ny /2.

Линейные рекуррентные массивы, для единообразия с терминологией ме тода АСС [66], будем называть массивами конечного ранга, а линейную слож ность рангом массива. Массивы, для которых выполняются условия заме чания 4.1.3 будем называть массивами неполного ранга [19].

4.1.4. Полиномиальное представление массивов и оценка линейной сложности В этом разделе мы для массива конечного ранга (ЛРМ) с биномиальным представлением с одним корнем (2.2.7) покажем, что по полиномиальному представлению массива (2.2.5) можно не только оценить линейную сложность из замечания 2.2.8, но и способом, похожим на предложение (2.2.3), найти линейную сложность.

Лемма 4.1.3. Пусть F массив и заданы Lx, Ly. Пусть также существу ет набор линейно независимых Lx Ly матриц A(1),..., A(m), линейно неза висимый набор бесконечных массивов B (1),..., B (m) и задана m m матрица m m (L,L ) (wst )m, wst (B (t) )k,l A(s).

Fk,lx y W= = s,t= s=1 t= Тогда rank(Lx,Ly ) (F) = rank W.

Доказательство.

(Lx, Ly )-ранг F равен рангу бесконечной матрицы W, построенной в доказа тельстве леммы 4.1.2. По условию леммыы, W = AWC, где A = [vec A(1) :

... : vec A(m) ] m m, а C бесконечная матрица с m строками, t-й строкой Ct которой является развертка массива B (t) Ct,· = (B (t) )0,0, (B (t) )1,0, (B (t) )0,1, (B (t) )2,0, (B (t) )1,1, (B (t) )0,2,....

Так как по условию A и C имеют линейную сложность m, лемма доказана.

Предложение 4.1.2. Пусть q многочлен с коэффициентами ak,l, причем M, N N таковы, что ak,l = 0, если k M или l N.

M 1 N ak,l mk nl. (4.1.3) q(m, n) = k=0 l= Рассмотрим двумерный массив F, определенный как f (m, n) = q(m, n)m µn. (4.1.4) Тогда, если Lx 2M и Ly 2N, то rank(Lx,Ly ) (F) = r(F) = rank(M,N ) (G), где c0,0... c0,2N..

C=,.. ck,l = ak,l k! l!.

..

c2M 2,0... c2M 2,2N Доказательство.

Применяя формулу Тейлора, мы получаем (Fk,l )m,n = q(m + k, n + l)m+k µn+l = M N s+t q(m, n) m+k n+l st = µ mn (k, l) = (4.1.5) ms nt s! t!

s=0 t= s n t M s N t M N m m µ n k k u µl lv = au+s,v+t (u + s)!(v + t)!.

s! t! u! v!

s=0 t=0 u=0 v= Разложение (4.1.5) можно записать в виде MN MN (L,L ) wst (A(s) )(B (t) )k,l, (Fk,lx y ) = s=1 t= где 1 T A(u+M v+1) = 0u,..., (Lx 1)u 0v,..., (Ly 1)v u! v!

1 Tv B (u+M v+1) 0u,..., k u,... 0,..., lv,...

= u! v!

для 0 u M 1, 0 v N 1, и wst элементы блочно-ганкелевой матрицы W(M,N ) (C) (см. (1.7.4)).

Системы {Aj }j=0 1 и {Bj }j=0 1 являются линейно независимыми. По лем MN MN ме 4.1.3 предложение доказано.

Следствие 4.1.2. Линейная сложность массива, определенного в (4.1.4), равна линейной сложности массива коэффициентов C с элементами ck,l = ak,l k! l!.

4.1.5. Оценки линейной сложности по диаграмме Ферре биномиального представления В этом разделе мы покажем, как можно улучшить оценки линейной слож ности из раздела 2.2.

Пусть F имеет представление (2.2.7) с корнем (, µ) и массивом коэф фициентов B. Обозначим deg F = max(,)Supp B ( + ), т.е. deg F является степенью многочлена при корне (, µ) в представлении (2.2.5). Заметим, что deg F = max(,)F(Supp(B)) ( + ).

Тогда имеет место следующая оценка.

Предложение 4.1.3. Пусть F имеет представление (2.2.7) и r = deg F.

Тогда r + 1 r(F).

Доказательство.

Легко показать, что существует множество мощности r +1, которое F(Supp B) может съесть. Действительно, существует элемент (0, 0 ) c(A), такой что 0 + 0 = r. Пусть (1, 1 ),..., (r, r ) последовательность индексов, та кая что (j, j ) (j+1, j+1 ) {(0, 1), (1, 0)} для 0 j r 1. Можно def видеть, что последовательность множеств 0 =, j+1 = j (j, j ) об разует последовательность множеств из определения 2.2.14, если положить (kj+1, lj+1 ) = (j, j )(0, 0 ). Таким образом, F(Supp B) всегда может съесть множество {(0, 0 ),..., (r, r )} мощности m + 1.

Легко видеть, что в общем случае построенное множество может иметь больше элементов, чем любая рука диаграммы Ферре.

Теорема 4.1.2. Пусть F имеет представление (2.2.7) и r = deg F. Тогда (r/2 + 1)2, для четных r, (4.1.6) r(F) ((r + 1)/2 + 1) (r + 1)/2, для нечетных r.

Доказательство.

Пусть B массив коэффициентов биномиального представления. Тогда r(F) = r(B) = dim span {Bk,l }k+lr.

Обозначим Tk следующее пространство вырожденных массивов def Tj = {C = (cmn )+ : cmn = 0 for m + n j}.

m,n= Тогда Bk,l принадлежит Tj для j r(k+l)+2 и не обязательно принадлежит Tj для меньших j. Введем пространства def Cj = span {Bk,l }k+l=mj+2 Tj, def Sj = span(C0,..., Cj ) = span(Sj1, Cj ) Tj.

Тогда L(B) = Sr.

Заметим также, что dim Sj min(dim Sj1 + dim Cj, dim Tj ).

j+ Так как dim Cj r + 1 j and dim Tj = s, можно показать, что s= r dim Sr min(j + 1, r j + 1) = j= (r/2 + 1)2, для четных r, = ((r + 1)/2 + 1) (r + 1)/2, для нечетных r.

Замечание 4.1.4. Пусть Supp(B) = {(, ) : + r} и r, для опреде ленности, четно. Тогда оценка из предложения 2.2.6 равна (r + 1)(r + 2)/2, а оценка из теоремы 4.1.2 равна (r/2 + 1)2, что меньше примерно вдвое.

4.2. Оценки множества допустимых размеров окна 4.2.1. Оценка множества для бесконечного массива Определение 4.2.1. Пусть бесконечный массив F имеет линейную слож ность d. Размеры окна (Lx, Ly ) будем называть допустимыми, если для этих размеров окна rank(Lx,Ly ) (F) = d.

Также введем обозначение для множества допустимых размеров окна def M(F) = {(Lx, Ly ) N2 : rank(Lx,Ly ) (F) = r(F)}.

Пример множества допустимых размеров окна для бесконечного массива изображен на рис. 4.1.

Рис. 4.1. Множество допустимых размеров окна В этом разделе мы будем исследовать вопрос о нахождении множества M(F) допустимых размеров окна.

Замечание 4.2.1. Очевидно, что множество M = M(F) обладает следую щими равносильными свойствами:

1. Если (, ) M, то для любых (k, l) N2 индекс ( + k, + l) M.

2. Дополнение N2 \ M является (бесконечной) диаграммой Ферре.

3. Существует набор C = {(1, 1 ),..., (m, m )} N2, такой что для лю бых i j i j и i j, и def M = N2 + C = ((1, 1 ) + N2 )... ((m, m ) + N2 ).

Отметим также, что любая пара (, ) M(F) может служить в качестве размеров окна (Lx0, Ly0 ), участвующих в формулировке предложения 4.1.1.

Далее мы покажем, как найти верхние оценки для множества M, т.е. как найти достаточно большое подмножество M.

определяющее множество для F.

Лемма 4.2.1. Пусть A Тогда (Bx (A), By (A)) M(F), где def Bx (A) = 1 + min{ : (A (, 0)) N2 = }, def By (A) = 1 + min{ : (A (0, )) N2 = }.

Пользуясь утверждениями из раздела 2.2, можно оценить множество раз меров окна по биномиальному представлению.

Следствие 4.2.1. Если F имеет биномиальное представление и A = Supp B (1) +... + Supp B (r), то (Bx (A), By (A)) M(F).

Так как по замечанию 2.2.11 всегда существует базисная диаграмма Ферре, имеет место следующая грубая оценка.

Следствие 4.2.2. Если r(F) = d, то (d, d) M(F).

С помощью базисов Гребнера можно довольно точно оценить множество M(F), с точностью до конечного числа элементов.

Теорема 4.2.1. Пусть Gx и Gy диаграммы Ферре под старшими членами базисов Гребнера (множества (2.2.11) из предложения 2.2.9) для лексикогра фических упорядочений y x и x y соответственно. Тогда для любого (Lx, Ly ) M выполняются Ly By (Gx ), Lx Bx (Gy ), Доказательство.

Докажем, например, Ly By (Gx ). Пусть, напротив, (Lx, Ly ) M и Ly By (Gx ). Не умаляя общности, мы можем считать Lx Bx (Gx ) (в против ном случае положим (Bx (Gx ) + 1, Ly ) M). Рассмотрим множество A = {0,..., Lx 1} {0,..., Ly 1}, которое является определяющим. Далее мы покажем, что B = A Gx также является определяющим.

Пусть f1,..., fr C[x, y] элементы граничного базиса Гребнера (см.

предложение 2.2.12), расположенные в порядке возрастания степени старшего члена по x. Пусть rb = max{k : LT(fk ) = x y Ly 1 }. Пусть LT(frb ) = x0 y Ly 1.

Пусть g1,..., g0 элементы граничного предбазиса для множества A, соответствующие элементам из следующего подмножества (A):

{(0, Ly ),..., (0 1, Ly )}.

Пусть h1,..., h0 остатки от деления g1,..., g0 на систему f1,..., fr, кото рые имеют следующий вид:

(k) hk = xk1 y Ly c(,) x y.

(,)B Следовательно, система {g1,..., g0, f1,..., fr } является граничным предбази сом и значит, по лемме 2.2.5, r(F) #B #Gx = r(F). Таким образом, мы получаем противоречие.

Предложение 4.2.1. Пусть 1,..., r различные числа. Пусть также m1,..., mr N, m1... mr, и заданы множества {µ1,1,..., µ1,m1 } C,.

.

.

{µ1,1,..., µ1,mr } C, dk r ck,l i µj.

fi,j = k k,l k=1 l= Тогда Gx (F) = { (0, 0),..., (0, m1 1), (1, 0),..., (1, m2 1),.

.

.

(r 1, 0),..., (r 1, mr 1)}.

Доказательство.

Нетрудно видеть, что идеал порождается следующими многочленами:

(x 1 )... (x r ) (x 1 )... (x r1 )(y µr,1 )... (y µr,mr ) (x 1 )... (x r2 )(y µr1,1 )... (y µr1,mr1 ).

.

.

(x 1 )(y µ1,1 )... (y µ1,m1 ).

Этот набор многочленов является базисом Гребнера идеала I[F] по отноше нию к лексикографическому упорядочению с y x.

Следствие 4.2.3. Пусть fi,j = c1 i µj +... + c1 i µj.

11 mm Обозначим dx и dy количество различных значений среди чисел 1,..., m и µ1,..., µm соответственно. Обозначим my и mx максимальную кратность одинакового значения среди 1,..., m и µ1,..., µm. Тогда (Bx (Gx ), By (Gx )) = (dx, my ) и (Bx (Gy ), By (Gy )) = (mx, dy ), что позволяет оценить множество допустимых размеров окна по dx, dy, my, mx.

Замечание 4.2.2. Результат предложения 4.2.3 был уже получен с помощью матричных методов в работе [127]. Теорема 4.2.1 это обобщение данного результата на случай произвольных массивов.

Также можно поставить вопрос: можно ли найти все множество M(F), с помощью нахождения размеров Bx (A), By (A) для некоторой системы мно жеств? Например, можно перечислить все базисные диаграммы Ферре [125].

Однако базисные диаграммы Ферре не являются минимальными по включе нию определяющими множествами, в противном случае перечисление всех ба зисных диаграмм Ферре давало бы множество M.

Замечание 4.2.3. Если A определяющее множество, то не обязательно су ществует нормальное множество B, являющееся подмножеством A. Рассмот рим массив fm,n = ij,0 + 1 + (1)i+j. Массив имеет линейную сложность 3.

Пусть массивы A, B заданы как am,n = 1 + (1)m+n и bm,n = 1 (1)m+n.

Легко видеть, что F, (k, l) = (0, 0), Fk,l = A, сумма k + l четна и положительна, B, сумма k + l нечетна.

Легко видеть, что A = {0, 1} {0, 1} является определяющим множеством.

С другой стороны, все базисные диаграммы Ферре это {0} {0, 1, 2} и {0, 1, 2} {0}. Таким образом, A не содержит ни одной минимальной диа граммы Ферре.

4.2.2. Переход от бесконечного массива к конечному Рассмотрим бесконечный массив F, подматрицей которого является ко нечный массив F размера Nx Ny.

Очевидно, что L(Lx,Ly ) (F) L(Lx,Ly ) (F). Далее мы покажем, что при неко торых условиях L(Lx,Ly ) (F) = L(Lx,Ly ) (F).

Предложение 4.2.2. Пусть F массив конечного ранга d, заданы Nx, Ny, Lx, Ly и числа Kx, Ky допустимы. Тогда выполняется L(Lx,Ly ) (F) = L(Lx,Ly ) (F), rank(Lx,Ly ) (F(Nx,Ny ) ) = rank(Lx,Ly ) (F).

Доказательство.

Имеем (4.2.1) rank(Lx,Ly ) (F) rank(Lx,Ly ) (F) = r d.

Так как размеры окна (Kx, Ky ) допустимы, для любых m Kx и n Ky сдвиг K 1,Ky Fm,n линейно выражается в виде линейной комбинации системы {Fk,l }k,l=0, x (L,Ly ) и следовательно Fm,n линейно выражается через элементы системы x (L,Ly ) Kx 1,Ky {Fk,lx }k,l=0.

Пусть A {0,..., Lx 1} {0,..., Ly 1} такое множество индексов, что мощность его равна r и множество сдвигов {Fk,l }(k,l)A линейно независи (K,Ky ) мо. Докажем, что соответствующий набор подматриц {Fk,l x }(k,l)A линейно независим.

Пусть это не так, т.е. существуют нетривиальные коэффициенты {ak,l }(k,l)A C, (K,Ky ) (L,Ly ) такие что = 0. Таким образом, мы имеем Fk,lx x am,n Fm,n,A = M (m,n)A L 1,Ly для всех 0 k Kx 1, 0 l Ky 1, где A = (ak,l )k,l=0 и ak,l x (L,Ly ) полагается равным нулю, если (k, l) A. Так как Fm,n линейно выражается x / (L,Ly ) Kx 1,Ky 1 (L,Ly ) через элементы системы {Fk,lx, соотношение Fm,n x }k,l=0,A = M (m, n) N2 и значит выполняется для всех ak,l Fk,l = 0. Таким образом, (k,l)A получаем противоречие.

Следствие 4.2.4. Множество всех размеров окна (Lx, Ly ), на которых для конечного массива F достигается максимальный ранг d (будем его также называть множеством допустимых размеров окна для F) можно найти как {(Lx, Ly ) N2 : rank(Lx,Ly ) (F) = d} = M(F) ((Nx + 1, Ny + 1) M(F)).

Пример множества допустимых размеров окна для конечного массива изображен на рис. 4.2.

Рис. 4.2. Множество допустимых размеров окна 4.3. Двумерная разделимость Определение 4.3.1. Два массива F(1) и F(2) называются слабо (Lx, Ly )-по луразделимыми, если L(Lx,Ly ) (F(1) ) L(Lx,Ly ) (F(2) ).

Массивы называются слабо (Lx, Ly )-разделимыми, если они (Lx, Ly )-по луразделимы и (Kx, Ky )-полуразделимы.

Как и в разделе 3.2, мы в основном будем изучать полуразделимость, так как условие разделимости будет объединением условий полуразделимости.

4.3.1. Разделимость произведений рядов Базовым примером разделимости является разделимость произведения рядов. Рассмотрим две пары одномерных рядов (1) (1) (1) (1) P(1) = (p0,..., pNx 1 ), Q(1) = (q0,..., qNy 1 ), (2) (2) (2) (2) P(2) = (p0,..., pNx 1 ), Q(2) = (q0,..., qNy 1 ).

Предложение 4.3.1. Произведения рядов F(1) = (P (1) )T (Q(1) ) и F(2) = (P (2) )T (Q(2) ) полуразделимы тогда и только тогда, когда или ряды P (1) и P (2) Lx -полуразделимы или ряды Q(1) и Q(2) Ly -полуразделимы.

Доказательство.

(1) (1) (2) (2) Пусть A1,..., Ad11, A1,..., Ad12 базиcы Lx -траекторных пространств ря (1) (1) (2) (2) дов P (1) и P (2), а B1,..., Bd21, B1,..., Bd22 базисы Ly -траекторных про странств Q(1) и Q(2). Тогда траекторные пространства массивов F(1) и F(2) (1) (1) (1) (2) (2) (2) порождаются матрицами Ck,l = Ak (Bl )T и Ck,l = Ak (Bl )T.

По свойству скалярного произведения Фробениуса (2) (2) (2) C(1), Ck,l = A(1), Ak (1) (4.3.1) Bn, Bl.

m,n m M 2 Следовательно, если L(Lx ) P (1) L(Lx ) P (2), то L(Lx,Ly ) F(1) L(Lx,Ly ) F(2).

Если обе пары рядов не полуразделимы, то существуют индексы m, n, k, l, (1) (2) (1) (2) такие что Am, Ak не ортогональны и Bn, Bl не ортогональны, т.е.

(2) (2) (2) C(1), Ck,l = A(1), Ak (1) Bn, Bl = 0, m,n m M 2 Следовательно F(1) и F(2) не полуразделимы.

Пример 4.3.1. [Полуразделимость двух комплексных экспонент] Рассмотрим (1) (2) две комплексные экспоненты fm,n = c1 m µn, fm,n = c2 m µn. Пусть также 11 min(Lx, Kx ) 2 и min(Ly, Ky ) 2. По предложению 4.3.1 массивы (Lx, Ly )-по луразделимы тогда и только тогда, когда выполняется одно из условий:

• ряды m и m Lx -полуразделимы.

1 • ряды µn и µn Ly -полуразделимы.

1 Следствием из предложения 4.3.1 является достаточное условие двусто ронней разделимости, которое, однако, не является необходимым.

Следствие 4.3.1. Если одна из пар рядов, P (1), P (2) или Q(1), Q(2) Lx или Ly разделима, то (Lx, Ly )-разделимой является и пара (F(1), F(2) ).

Пример 4.3.2. [Двусторонняя разделимость двух комплексных экспонент] Так как (Lx, Ly )-полуразделимость эквивалентна Lx - или Ly -полуразделимости пар одномерных экспонент, массивы (Lx, Ly )-разделимы при выполнении од ного из условий:

1. m и m Lx -разделимы.

1 2. µn и µn Ly -разделимы.

1 3. m и m Lx -полуразделимы, µn и µn Ky -полуразделимы.

1 2 1 4. m и m Kx -полуразделимы, µn и µn Ly -полуразделимы.

1 2 1 Пункты 1, 2 предъявляют большие требования к аргументу экспонент и связи с размерами окна: например для п. 1 по теореме 3.2.3 1, 2 должны k m иметь представление k = (1) exp 2i. С другой стороны + gcd(Lx,Kx ) на вторую пару экспонент не накладывается никаких ограничений.

Пункты 3 и 4 предъявляют меньшие требования к аргументу экспонент никакие из пар рядов не обязаны быть полностью разделимыми. Однако в этом случае требуется полуразделимость по обоим переменным.

Пример 4.3.3. [Разделимость массивов неполного ранга] По предложению 4.3.1 и следствию 4.3.1 полуразделимыми (разделимыми) могут быть и массивы неполного ранга. Действительно, пусть P (1) и P (2) Lx -полуразделимы (Lx -разделимы) а Q(1), Q(2) имеют полный ранг. Тогда массивы F(1) = (P (1) )T (Q(1) ) и F(2) = (P (2) )T (Q(2) ) (Lx, Ly )-полуразделимы ((Lx, Ly )-разделимы).

Пусть, например, (1) fn,m = cos (21 n + 1 ) ln(m + 1), (2) fn,m = cos (22 n + 2 ) ln(n + 1).

и 1 = 2, 0 1, 2 1/2 и Lx 1, Lx 2 являются целыми числами. Массивы F(1) и F(2) (Lx, Ly )-полуразделимы, при этом rank(Lx,Ly ) F(1) = 2 min(Ly, Ky ), rank(Lx,Ly ) F(2) = 2 min(Ly, Ky ).

4.3.2. Разделимость бесконечных массивов конечного ранга Далее мы будет рассматривать полуразделимость подмассивов бесконеч ных массивов конечного ранга.

Определение 4.3.2. Два массива F (1) и F (2) называются (Lx, Ly )-полураз делимыми, если L(Lx,Ly ) (F (1) ) L(Lx,Ly ) (F (2) ).

Замечание 4.3.1. Если F(1) = F(1),(Nx,Ny ) и F(2) = F(2),(Nx,Ny ) конечные подмассивы бесконечных массивов F (1) и F (2) конечного ранга. Пусть также заданы размеры окна (Lx, Ly ), причем (Lx, Ly ) и (Kx, Ky ) допустимы для F (1) и F (2).

Тогда, по предложению 4.2.2, (Lx, Ly )-полуразделимость F (1) и F (2) рав носильна (Lx, Ly )-полуразделимости F(1) и F(2).

Замечание 4.3.2. По леммам 4.1.1, 2.2.3 два бесконечных массива вида (2.2.4) (Lx, Ly )-полуразделимы тогда и только тогда, когда (Lx, Ly )-полуразделимы все пары их слагаемых вида (2.2.7).

Таким образом, достаточно найти все массивы F (2) вида (2.2.7), полуот делимые от массива (1) (4.3.2) fm,n = Q1 (m, n)m µn.

Для начала будем рассматривать случай, когда F (2) имеют вид fm,n = m µn.

(2) Нам потребуются некоторые утверждения о произведении бесконечных рядов.

(1) (2) Определение 4.3.3. Пусть F = (f0,..., fn,...) и F = (f0,..., fn,...) бесконечные ряды конечных рекуррентных рангов d1 и d2. Два ряда на (1) (1) зываются L-разделимыми, если пространство L(L) F = F2d1 +1 ортогонально (2) (2) пространству L(L) F = F2d2 +1.

Замечание 4.3.3. Два бесконечных ряда конечного ранга L-разделимы то гда и только тогда, когда они удовлетворяют условиям теоремы 3.2.3.

Аналогично доказательству предложения 4.3.1 можно доказать следую щее утверждение.

(1) (1) (1) Лемма 4.3.1. Произведения рядов конечного ранга F = (P )T (Q ) и (2) (2) F(2) = (P )T (Q ) полуразделимы тогда и только тогда, когда или ряды (1) (2) (1) (2) P и P Lx -полуразделимы или ряды Q и Q Ly -полуразделимы.

Пример 4.3.4. [Отделимость от многочлена от одной переменной] Пусть Q1 (m, n) = G(n) многочлен от одной переменной степени r 1.

По лемме 4.3.1 массив G(n)m µn (Lx, Ly )-полуотделим от массива m µn 11 тогда и только тогда, когда массив m Lx -полуотделим от массива m.

1 Для рассмотрения отделимости многочленов от обеих переменных, нам потребуется следующее утверждение.

Замечание 4.3.4. Очевидно, что траекторное пространство L(Lx,Ly ) (F) по (L,L ) рождено конечными (Lx, Ly )-подмассивами DF,(k,l) массивов DF,(k,l). Если раз xy меры окна(Lx, Ly ) являются допустимыми, то размерность траекторного про странства L(Lx,Ly ) (F) равна размерности пространства подмассивов DF,(k,l).

Пример 4.3.5. [Отделимость от линейной функции] Пусть Q1 (m, n) = a/1 m + b/µ1 n + c, где a = 0, b = 0. Тогда (1,0) (1,0) (0,0) F (1) = a(1,µ1 ) + b(1,µ1 ) + c(1,µ1 ) и по лемме 2.2.1 траекторное пространство порождено массивами def A0 = 0 x (1 )(0 y (µ1 ))T, L L def B1 = aA(1,0) + bA(0,1), где def def A(1,0) = 1 x (1 ))T 0 y (µ1 ), A(0,1) = 0 x (1 ))T 1 y (µ1 ), L L L L 0 () = (1,,..., L1 )T, 1 () = (0, 1, 2,..., (L 1)L2 )T, определяются в L L (3.1.5).

Для (Lx, Ly )-полуразделимости необходимо и достаточно, чтобы A0, F(Lx,Ly ) = 0 или B1, F(Lx,Ly ) = 0. Из первого равенства получаем, что 2 0 x (1 ), 0 x (2 ) 0 y (µ1 ), 0 y (µ2 ) = 0 или = 0.

L L L L 2 Пусть выполняется первое равенство, т.е. ряд m Lx -полуотделим от ряда m.

1 Тогда B1, F(Lx,Ly ) = 0 = a A(1,0), F(Lx,Ly ) + b A(0,1), F(Lx,Ly ) = 2 2 a 1 x (1 ), 0 x (2 ) 0 y (µ1 ), 0 y (µ2 ) + L L L L 2 b 0 x (1 ), 0 x (2 ) 1 y (µ1 ), 0 y (µ2 ) = L L L L 2 = a 1 x (1 ), 0 x (2 ) 0 y (µ1 ), 0 y (µ2 ).

L L L L 2 Левый множитель последнего произведения равняться нулю не может по при меру 3.2.4, поэтому правый множитель равен.

Таким образом, массивы разделимы тогда и только тогда, когда Lx -раз делимы ряды m и m и Ly -разделимы ряды µn и µn.

1 2 1 Пример 4.3.6. [Отделимость от суммы одномерных многочленов] Пусть Q1 (m, n) = G(m) + H(n), многочлены, причем хотя бы у одного из многочленов степень G(m), H(m) больше 1. Пусть d1 = deg G 1, d2 = deg H 1. Тогда пространство L(F) содержит массив am,n = G (m)m µn, A = DF (1),(1,0), и, следовательно, A и F (2) должны быть (Lx, Ly )-полуразделимы. По приме ру 4.3.4 ряды µn и µn Ly -полуразделимы. Кроме этого, пространство L(F) 1 содержит массив C = DF (1),(0,d2 1), который имеет вид cm,n = (G1 (m) + an + c))m µn. (4.3.3) В силу 0 = C(Lx, Ly ), 0 x (2 )(0 y (µ2 ))T = L L M Lx 1 Ly (G(m) + an + c)(1 2 )m (µ1 µ2 )n = = m=0 n= Lx G(m)(1 2 )m ) 0 y (µ1 ), 0 y (µ2 ) =( + L L m= Ly (an + c)(µ1 µ2 )n ) 0 x (1 ), 0 x (2 ) +( = L L n= Ly an(µ1 µ2 )n ) 0 x (1 ), 0 x (2 ) =( L L n= получаем по примеру 3.2.4, что m и m должны быть Lx -разделимы. В этом 1 случае по примеру 4.3.4 каждый массив G(m)m µn и H(n)m µn (Lx, Ly )-по 11 луотделим от F (2), а значит их сумма F (1) тоже полуотделима от F (2).

Таким образом, два массива отделимы тогда и только тогда, когда Lx -раз делимы ряды m и m и Ly -разделимы ряды µn и µn.

1 2 1 Пример 4.3.7. [Отделимость от смешанной степени] Пусть Q1 (m, n) содер жит смешанную степень m n,, 0. Пусть эта степень максимальна по сумме + среди всех таких степеней. Следовательно, коэффициент b(,) (,) при массиве 1,µ1 не равен нулю. Тогда либо 1. Коэффициент b(k,l) = 0 если k или l.

2. Существуют k, l, такие что или k или l, при этом b(k,l) = 0.

Рассмотрим сдвиги DF (1),(,0) и DF (1),(0,). В случае 1 оба сдвига имеют вид G(m)m µn и H(n)m µn. В случае 2 один из сдвигов имеет вид 11 (G(m) + H(n))m µn.

Следовательно, по предыдущим примерам Lx -разделимы ряды m и m и 1 Ly -разделимы ряды µn и µn. Теперь рассмотрим сдвиг DF (1),(1,1). Ввиду 1 максимальности, сдвиг имеет вид (am2 + bmn + cn2 + dm + en + f )m µn, b = 0. Тогда DF (1),(1,1), 0 x (2 )(0 y (µ2 ))T = L L M Lx 1 Ly (am2 + cn2 + dm + en + f )(1 2 )m (µ1 µ2 )n + = m=0 n= Lx 1 Ly (bmn)(1 2 )m (µ1 µ2 )n = m=0 n= Ly Lx m n(µ1 µ2 )n ), = b( m(1 2 ) )( m=0 n= и каждый из множителей не равен нулю по примеру 3.2.4.

Массив, имеющий смешанную степень многочлена, не отделим ни от ка кого массива конечного ранга.

Следствием примеров является следующая теорема.

Теорема 4.3.1. Массив вида (4.3.2), где Q1 = const, (Lx, Ly )-полуотделим от массива m µn тогда и только тогда, когда выполняются все следующие условия:

1. Многочлен Q1 (m, n) имеет вид G(m) + H(n), где G, H многочлены.

2. Если H(n) = const, то ряды m и m Lx -полуразделимы.

1 3. Если G(m) = const, то ряды µn и µn Ly -полуразделимы.

1 Теперь мы можем перейти к общему случаю полуразделимости массивов вида (2.2.7) Пример 4.3.8. [Полуразделимость двух многочленов] Пусть массивы F (1) и (1) (2) F (2) заданы как fm,n = Q1 (n)m µn и fm,n = Q2 (n)m µn.

11 По лемме 2.2.1 для (Lx, Ly )-разделимости массивов необходимо, чтобы массивы F (1) и m µn были полуразделимы. Это происходит тогда и только тогда, когда ряды µn и µn Ly -полуразделимы. Легко видеть, что в этом случае 1 и исходные массивы полуразделимы.

Таким образом, массивы F (1) и F (2) (Lx, Ly )-полуразделимы тогда и толь ко тогда, когда µn и µn Ly -полуразделимы.

1 Пример 4.3.9. [Полуразделимость двух линейных функций] Пусть (1) fm,n = (am + bn + c)m µn, (4.3.4) (2) fm,n = (dm + en + f )m µn.

и как минимум три из коэффициентов a, b, d, e не равны нулю. Пусть, для (2) определеннности, a, b = 0. Так как L(Fm ) порождено двумя массивами F (2) и (0,0) (0,0) (2,µ2 ), то разделимость массивов включает в себя отделимость F (1) от (2,µ2 ).

Таким образом, пары m и m и пары µn и µn Lx - и Ly -полуразделимы соот 1 2 1 ветственно. Базисами траекторных пространств являются:

{0 x (1 )(0 y (µ1 ))T, F1,(Lx,Ly ) } и {0 x (2 )(0 y (µ2 ))T, F2,(Lx,Ly ) }.

L L L L Ортогональность всех пар кроме F1,(Lx,Ly ) и F2,(Lx,Ly ) следует из полуразде лимости одномерных рядов. Запишем условие ортогональности оставшихся массивов 0 = F1,(Lx,Ly ), F2,(Lx,Ly ) M Lx 1 Ly m (am + bn + c)(dm + en + f )m µn 2 µ2 n = m=0 n= Ly Lx (adm2 + (af + cd)m + cf )(1 2 )m (µ1 µ2 )n + = m=0 n= Ly 1 Lx + n (1 2 )m (bem + bf + cem)(µ1 µ2 ) + n=0 m= Ly Lx m(1 2 )m n(µ1 µ2 )n, +(bd + ae) m=0 n= где первые два слагаемых равны нулю из одномерной полуразделимости, а в последнем слагаемом суммы не равны нулю по примеру 3.2.4 и, следовательно, (bd + ae) = 0.

Таким образом, два массива вида (4.3.4) (Lx, Ly )-полуразделимы тогда и только тогда, когда пары рядов m, m и µn, µn Lx - и Ly -полуразделимы, а 1 2 1 также коэффициенты связаны соотношением (4.3.5) r C.

(a, b) = r(d, e), Теорема 4.3.2. Пусть массив F (1) задан (4.3.2), а массив F (2) задан fm,n = Q2 (m, n)m µn, (2) (4.3.6) причем оба многочлена Q1 (m, n) и Q2 (m, n) отличны от константы, и в совокупности содержат хотя бы по одной степени и m и n.

Массивы F (1) и F (2) разделимы тогда и только тогда, когда 1. Ряды m и m Lx -полуразделимы.

1 2. Ряды µn и µn Ly -полуразделимы.

1 3. Масссивы имеют вид (4.3.4) и выполняется условие (4.3.5).

Доказательство.

Каждый из массивов F (1) и F (2) должен быть отделим от m и m, поэтому по 1 теореме 4.3.1, выполняются условия 1, 2, (так как Q1 и Q2 содержат степени как m, так и n) и массивы имеют вид (1) fm,n = (G1 (m) + H1 (n))m µn, (2) fm,n = (G2 (m) + H2 (n))m µn.

Пусть, например, deg G1 0.

• Если deg H2 = 1, то должны быть полуразделимы mm µn и F (2), т.е.

Lx 1 Ly m (m)(G2 (m) + an)m µn 2 µ2 n = 0= m=0 n= Lx 1 Ly m a(m)nm µn 2 µ2 n, = m=0 n= что невозможно по примеру 4.3.7.

• Если deg H2 = 1, то должны быть полуразделимы массивы mm µn и nm µn, что также невозможно.

• Если же deg H2 = 0, то deg H1 0 и deg G2 0, т.е. должны быть полуразделимы mm µn и F (1), что аналогично предыдущему случаю.

Таким образом, Q1 и Q2 могут быть только линейными функциями и поэтому удовлетворяют условию (4.3.5).

Результаты теорем 4.3.1 и 4.3.2 можно оформить в следующем виде.

(1) Теорема 4.3.3. Для (Lx,Ly ) M(F (1) )M(F (2) ) массивы fm,n = P1 (m, n)m µn (2) и fm,n = P2 (m, n)m µn (Lx,Ly )-полуразделимы только в следующих случаях:

1. P1 = P1 (m), P2 = P2 (m), ряды µn и µn Ly -полуразделимы;

1 2. P1 = P1 (n), P2 = P2 (n), ряды m и m Lx -полуразделимы;

1 3. P1 = const, P2 = Q21 (n) + Q22 (m), ряды m и m Lx -полуразделимы, 1 ряды µn и µn Ly -полуразделимы;

1 4. P1 = a1 m+b1 n+c1, P2 = a2 m+b2 n+c2, ряды m и m Lx -полуразделимы, 1 ряды µn и µn Ly -полуразделимы и a1 b2 + b1 a2 = 0.

1 4.4. Непрерывный вариант и системы в частных производных В этом разделе рассматривается непрерывный вещественный вариант ме тода АСС, который был рассмотрен в работе [35] для одномерных функций, и обобщен в работе [19] для двумерных функций. Предметом исследования является общий вид функций, имеющих конечное АСС разложение. Будет по казано, что общий вид таких функций соответствует виду массивов конечного ранга (ЛРМ) (2.2.6).

4.4.1. Разложение функций. Ранг функций Пусть D = [0;

tx ] [0;

ty ] и задана функция f : D R. Определим разложение функции f для непрерывного варианта метода 2D-SSA [19].

Зафикcируем параметры метода (размеры окна) (x, y ) : 0 x tx, 0 y ty. Обозначим D1 = [0;

x ] [0;

y ], D2 = [0;

tx x ] [0;

ty y ]. Пусть def функция g : D1 D2 R, определенная как g ((u, v), (s, t)) = f (u + s, v + t), принадлежит классу L2 (D1 D2 ). Тогда существует разложение Шмидта (см.

[10]) + (4.4.1) f (u + s, v + t) = g (u, v), (s, t) = k k (u, v) k (s, t), k= где {k }+ и {k }+ ортонормированные системы в L2 (D1 ) и L2 (D2 ) соот k=1 k= ветственно, а также 1 2... k... 0. Разложение (4.4.1) является разложением функции f в непрерывном варианте метода 2D-SSA.

Определение 4.4.1. Количество ненулевых слагаемых в разложении (4.4.1) будем называть (x, y )-рангом def rank(x,y ) (f ) = max{k 1 : k 0}.

В этом случае также будем говорить, что функция f имеет конечный конечного ранга). Положим rank(x,y ) (f ) = + (f (x, y )-ранг (или f бесконечного ранга), если все k 0.

Если некоторая функция допускает конечное разложение, разделяющее переменные в сумме, то она является функцией конечного ранга, что показы вает следующая лемма.

Лемма 4.4.1 ([19, лемма 6]) 1) Если существуют pi L2 (D1 ) и qi L2 (D2 ), такие что r (4.4.2) f (u + s, v + t) = pj (u, v) qj (s, t), j= где (u, v) D1, (s, t) D2, и равенство (4.4.2) выполняется почти везде, то (x, y )-ранг f не превосходит r. Более того, каждая функция k из (4.4.1) яв ляется линейной комбинацией функций pi, а каждая функция k – линейной комбинацией qi.

2) Если обе системы {pi }r и {qi }r к тому же линейно независимы i=1 i= в L2 (D1 ) и L2 (D2 ), то функция f имеет в точности (x, y )-ранг r.

Замечание 4.4.1. Если (x, y )-ранг равен d, то не существует представле ния (4.4.2) c r d.

Нас интересует общий вид непрерывных функций, имеющих разложение вида (4.4.2). В случае одной переменной задача имеет сравнительно простое решение [35]. Пусть r f (u + s) = pk (u) qk (s), k= где pk и qk достаточно гладкие. Это равенство можно продифференцировать по u:

r i d (i) f (u + s) = pk (u) qk (s) du k= и получить, что m + 1 производных f выражаются как линейные комбинации m функций:

r (i) (i) f (s) = pk (0) qk (s).

k= Следовательно, производные линейно зависимы и f является решением неко торого линейного обыкновенного дифференциального уравнения (ОДУ) выс шего порядка b0 f + b1 f (1) +... + br f (r) = с постоянными коэффициентами. Таким образом, f имеет представление в виде линейной комбинации произведений полиномов, экспонент и косинусов.

В настоящем разделе мы докажем аналогичный результат для случая двух переменных. Мы покажем, что непрерывная функция, допускающая пред ставление (4.4.2), является решением некоторой линейной системы уравнений высшего порядка в частных производных, для которой известен общий вид решения: линейная комбинация произведений полиномов, экспонент и косину сов.

4.4.2. Линейные системы уравнений в частных производных Теория многомерных (в частных производных) аналогов линейных ОДУ изложена, например, в [72]. Приведем здесь основные определения и утвер ждения из [72] для случая двух переменных.

Определение 4.4.2. Множество A N2 называется связным к нулю, если для любого (, ) A выполняется одно из условий: либо ( 1, ) A, либо (, 1) A, либо (, ) = (0, 0).

Пусть A связное к нулю множество. Система уравнений g (,) = a(,),(, ) g (, ), (4.4.3) (, ) (A), (, )A где g : R, G CA(A) () достаточно гладкая, а коэффициенты a(,),(, ) вещественные, называется системой уравнений высшего порядка.

Наряду с системой уравнений (4.4.3) рассмотрим систему алгебраических уравнений def P(,) = x y a(,),(, ) x y = 0, (4.4.4) (, ) (A).

(, )A Известны следующие утверждения.

Предложение 4.4.1. Число линейно независимых решений системы (4.4.3) равно размерности факторалгебры идеала, порожденного многочленами P(,), т.е. количеству решений (с учетом кратности) системы (4.4.4).

Теорема 4.4.1 ([72, теорема 7.1]) Решения комплексной системы (4.4.3) име ет вид d (4.4.5) g(x, y) = pk (x, y) exp(k x + µk y), k= где (k, µk ) C, а pk (x, y) комплексные многочлены.

Предложение 4.4.2. Функция f (x, y) = q(x, y) exp(k x + µk y) является ре шением системы (4.4.3) тогда и только тогда, когда 1. (, µ) C2 является корнем системы (4.4.4);

2. для любого (, ) (A) выполняется q, (P(,) (x, y)) = 0, x y (x,y)=(,µ) bk,l xk y l дифференциальный оператор где для многочлена q(x, y) = k,lN определяется как def q, = bk,l.

xk y l x y k,lN При этом для любых (, ) N2 функция q (,) (x, y) exp(x + µk y) так def же является решением системы, где q (,) = q.

x y Предложение 4.4.3. Любое вещественное решение системы (4.4.3) с веще ственными коэффициентами можно выразить как h (4.4.6) g(x, y) = Pi (x, y) exp(i x + µi y) cos(i x + i ) cos(i y + i ), i= где i, µi, i, i, i, i R, а Pi вещественные многочлены.

Доказательство.

По теореме 4.4.1 функция g представима в виде (4.4.5). Кроме того, она веще ственная, следовательно, d Re Ci · Re (pi (x, y) exp(i x + µi y)) + g(x, y) = i= Im Ci · Im (pi (x, y) exp(i x + µi y)), т. е. функция g имеет представление (4.4.6).

4.4.3. Общий вид функций конечного ранга Здесь мы представим способ построения системы высокого порядка для функции f, имеющей разложение (4.4.2), что позволит найти общий вид функ ций конечного ранга.

Определение 4.4.3. Систему {k }d функций G R будем назвать ли k= нейно независимой на G R2, если не существует таких коэффициентов d k R, k {1,..., d}, что k k 0 на G.

k= ограниченная область в R2 и система {k }d состоит Заметим, что если G k= из непрерывных функций на G (замыкании G), то их линейная независимость на G эквивалентна линейной независимости в L2 (G). Если же система состоит из одной функции 1, то линейная независимость означает 1 0.

Введем обозначение для систем частных производных функции. Для h :

G R обозначим def {h() }A = {h(, ) }(, )A, где A N2.

односвязная область в R2, A Пусть связное к нулю множество и задана функция g : R, у которой существуют непрерывные на произ водные g (,) для (, ) A (A).

Лемма 4.4.2. Если система {g () }A линейно независима, и она перестает быть линейно независимой, если добавить любую из производных g (,) для (, ) (A), то g на может быть представлена в виде (4.4.5) или (4.4.6).

Доказательство.

Так как для любого (, ) (A) система {g }A{(,)} линейно зависима, а система {g () }A линейно независима, то g удовлетворяет некоторой системе (4.4.3) с вещественными коэффициентами. По предложению 4.4.3 функция g имеет вид (4.4.6) (или (4.4.5)) на.

Далее будем обозначать h Ck (G), если у функции h : G R существу ют все производные h(,) порядка вплоть до k (т. е. таких (, ) N2, что + k) на G0 (внутренность G), вместе с непрерывностью функции и ее производных на G.

Пусть, как и в п. 4.4.1, D = [0;

tx ] [0;

ty ] и задана функция f : D R.

Кроме того, заданы размеры окна (x, y ) : 0 x tx, 0 y ty. Как и раньше, D1 = [0;

x ] [0;

y ], D2 = [0;

tx x ] [0;

ty y ].

Теорема 4.4.2. Пусть ненулевая функция f Cm+1 (D) имеет разложение (4.4.2) с r = m, причем pk и qk из (4.4.2) принадлежат Cm+1 (D1 ) и C(D2 ) соответственно, для любого k {1,..., m}. Тогда f является суммой про изведений экспонент, многочленов, косинусов.

Доказательство.

Для непрерывных функций равенство почти везде (4.4.2) является равенством всюду на D1 D2. Значит, для всех (, ) N2 : + m, таких что m d+ (,) f (u + s, v + t) = pk (u, v) qk (s, t), du dv k= (,) где (u, v) D1 и (s, t) D2. Полагая u = u0, v = v0 и обозначая pk,0 = (,) (u0, v0 ), приходим к равенству pk m (,) (,) (4.4.7) f (x, y) = pk,0 qk (x, y), k= def которое выполняется при (x, y) 0 = (u0, v0 ) = (u0 ;

u0 + tx x ) (v0 ;

v0 + ty y ). Покажем, что существует такое множество A, для которого выпол няются условия леммы 4.4.2 с = 0. Будем строить последовательность связных к нулю множеств Ai таким образом, что #Ai = i и система {f () }Ai линейно независима. Положим A1 = {(0, 0)}. Пусть уже построено множество Ai. Если для любого (, ) (Ai ) система {f () }Ai {(,)} линейно зависима, то мы нашли необходимое множество A = Ai. Если это не так, обозначим (i, i ) тот элемент (Ai ), для которого система {f () }Ai {(i,i )} линейно неза висима, положим Ai+1 = Ai {(i, i )} и продолжим построение последова тельности множеств. Заметим, что этот процесс закончится либо при i m, либо при i = m, так как для любого (, ) (Am ) система {f () }Am {(,)} бу дет состоять из (m + 1) функций, которые по равенствам (4.4.7) выражаются через m функций. Следовательно, любая система {f () }Am {(,)} линейно за висима. Таким образом, по лемме 4.4.2 функция f на 0 (и по непрерывности на замыкании 0 ) имеет представление (4.4.5).

Выберем точки {(u1, v1 ),..., (ur, vr )}, чтобы замыкания областей k = (uk, vk ) покрывали прямоугольник D и пересекались на множествах нену левой меры. Например, для x tx /2, y ty /2 достаточно взять точки {(0, 0), (x, 0), (0, y ), (x, y )}. Как уже ранее доказано, функция f на каждой области k имеет представление вида (4.4.5), т. е.

hk (4.4.8) f (x, y) = Ck,i pk,i (x, y) exp(k,i x + µk,i y) i= на k, причем можно считать, что пары (k,i, µk,i ) C2 различны для i {1,..., hk }. Так как области k пересекаются, количества слагаемых, пара метры функций и константы для представлений (4.4.8) совпадают. Таким об разом, f на D имеет представление вида (4.4.5), а значит и вида (4.4.6), что и требовалось доказать.

Теорема 4.4.3 (об общем виде функций конечного ранга) Если выполняется f Cm+1 (D) и для некоторых размеров окна f имеет (x, y )-ранг m, то она имеет представление (4.4.6) на D.

Доказательство.

Достаточно доказать, что в равенстве (4.4.1) k Cm+1 (D1 ) и k C(D2 ) для любого k {1,..., m}. Функции k являются собственными функциями интегрального оператора S : L2 (D1 ) L2 (D1 ) (Sh)(u, v) = S(u, v, x, y)h(x, y)dxdy, D где S(u, v, x, y) = f (u + s, v + t)f (x + s, y + t)dsdt.

D Легко убедиться, что ядро S(u, v, x, y) Cm+1 (D1 D1 ). Известно (см. [10, гл.

VI]), что собственные функции k интегрального оператора с непрерывным ядром непрерывны на D1. Покажем, что они являются достаточно гладкими.

Так как собственные числа k не равны нулю для 1 k m, выполняется 1 (4.4.9) k (u, v) = Sk = S(u, v, x, y)k (x, y)dxdy.

k k D Правую часть (4.4.9) можно продифференцировать под знаком интеграла до m + 1 раз по u или по v, следовательно, k Cm+1 (D1 ). Аналогично, k Cm+1 (D2 ), и мы получаем условия теоремы 4.4.2.

Важным следствием является независимость ранга от размеров окна.

Теорема 4.4.4. Если f Cm+1 (D) и для некоторых размеров окна (x0, y0 ) f имеет конечный ранг, т. е. rank(x0,y0 ) (f ) = m, то для любых (x, y ), та ких что 0 x tx, 0 y ty, (x, y )-ранг функции f равен m.

Доказательство.

По теореме 4.4.3 функция f имеет вид (4.4.6). Очевидно, что существует пред ставление r (4.4.10) f (u + s, v + t) = pk (u, v)qk (s, t), k= def def где m r, (u, v) D1,0 = [0;

x,0 ][0;

y,0 ], (s, t) D2,0 = [0;

tx,0 x,0 ][0;

ty, y,0 ], a pk, qk суммы произведений полиномов экспонент и косинусов, т. е.

слева и справа в равенстве (4.4.10) стоят функции вида (4.4.6). Следовательно, можно продолжить функции f, pk и qk на всю плоскость R2 и считать, что равенство (4.4.10) имеет место для любых (u, v, s, t) R4.

По лемме 4.4.1 функции k и k в разложении m (4.4.11) f (u + s, v + t) = k k (u, v) k (s, t) k= являются линейными комбинациями функций pk и qk, а значит, k и k суммы произведений экспонент, многочленов и косинусов и их тоже можно формально продолжить на всю плоскость R2, с сохранением равенства (4.4.11) для всех (u, v, s, t) R4. Таким образом, для любых размеров окна (x, y ) имеет место разложение (4.4.11), причем k и k линейно независимы на D1 и D2 (так как k и k линейно независимы на D1,0 и D2,0 ). По лемме 4.4. (x, y )-ранг равен m.

Далее для достаточно гладких функций (x, y )-ранг будем называть ран гом функции.

4.4.4. Свойства системы высшего порядка Покажем связь между рангом функции и свойствами системы уравнений в частных производных, которой она удовлетворяет. Ранг функции оказыва ется равным минимальному порядку систем уравнений, для которых данная функция является решением.

Лемма 4.4.3. Если на = D0 f является решением некоторой системы (4.4.3), то f допускает разложение вида (4.4.2) с r #A (иными словами, ранг функции f не превосходит #A).

Доказательство.

По формуле Тейлора m f (u + s, v + t) = pj (u + s, v + t) exp(j (u + s)) + µj (v + t)) = j= (4.4.12) m MM s+t µj t) k!1l!

kl = s t exp(j s + exp(u + µv) ms nt pj (u, v), j=1 k=0 l= где M некоторое достаточно большое натуральное число. Так как функции s+t (u, v) являются решениями уравнения (4.4.3), то они могут быть ms nt pj выражены через линейно независимые решения {gk }r системы (4.4.3) и раз k= ложение (4.4.12) может быть записано в виде r (4.4.13) f (u + s, v + t) = hk (s, t)gk (u, v).

k= При этом, по предложению 4.4.1 r #A.

Предложение 4.4.4. Если выполняются условия теоремы 4.4.2, и количе ство слагаемых в разложении (4.4.2) минимально (т. е. ранг функции f ра вен m), то 1) существует связное к нулю множество Am мощности m, такое что f удовлетворяет некоторой системе (4.4.3) с A = Am ;

2) для любого связного к нулю множества A, для которого f удовле творяет некоторой системе (4.4.3), мощность A не может быть меньше m.

Доказательство.

1) Положим (s0, t0 ) = (0, 0) и проведем для этой точки этап построения мно жества индексов, как в теореме 4.4.2. Пусть он завершился на множестве Aj, где j m. Положим A = Aj, = D2. По лемме 4.4.2 набор функций {f () }Aj является линейно независимой на системой решений некоторого уравнения f (,) = a(,),(, ) f (, ), (4.4.14) (, ) (A).

(, )A Так как по теореме 4.4.2 функция f представляется в виде (4.4.6), получаем, что на всем D функция f удовлетворяет системе (4.4.14), и по лемме 4.4.3 f имеет представление вида (4.4.2) с r #A = j. По условию предложения, так как ранг f равен m, получаем, что j = m, и мы построили искомое Am = Aj.

2) Предположим противное, т. е. что существует A : #A = r m и f удовлетворяет системе (4.4.3). Тогда повторив рассуждения леммы 4.4.3, можно представить f в виде (4.4.13), где {gk }r являются решениями системы k= (4.4.3), что противоречит условию о минимальности m.

Глава Численные эксперименты 5.1. Отделимость массивов конечного ранга от шума В данном разделе проводится сравнительный анализ качества очистки двумерных массивов от шума двумерным методом АСС (сокращенно 2D-SSA) с различными параметрами, а также альтернативными способами, основанны ми на сингулярном разложении матриц. В качестве основной альтернативы рассматривается SVD всего изображения, так как такой метод очистки от шума применяется в различных практических задачах [50, 80]. Также рас сматривается метод MSSA, в рамках которого массив интерпретируется как многомерный ряд. Как было показано в разделе 1.7.2, SVD и MSSA можно рассматривать как частные случаи 2D-SSA при особых размерах окна.


5.1.1. Описание методов очистки от шума N 1,Ny Пусть имеется массив F = (fmn )m,n=0 и мы наблюдаем зашумленный x Nx 1,N массив F = F +, где = (mn )m,n=0 y По заданным размерам окна (Lx, Ly ) и числу r производится АСС-разло жение и в качестве оценки F массива выбирается массив, восстановленный по первым r компонентам:

FR = F{1,...,r}, где массив F{1,...,r} задается (1.7.10), т.е. группировкой {1,..., L} = {1,..., r} {r + 1,..., L}. Для измерения отклонения зашумленных и восстановленных массивов от исходного используется нормированное квадратичное расстояние (1.1.3), т.е.

def distms 2 F(1), F(2) = distM (F(1), F(2) ) = ||F(1) F(2) ||2.

M Nx N y Сравнение производится методом статистического моделирования. В ка честве модели шума используется модель белого гауссовского шума, т.е. i,j N (0, 2 ). Зашумленность массива измеряется характеристикой SNR (Signal to Noise Ratio):

distms 2 (F, 0) ||F|| M SNR = =.

2 ) Edistms (F, F Моделируется выборка F = F (1),..., F (s) зашумленных массивов. При заданных параметрах (размеры окна Lx, Ly, количество компонент r) в резуль тате восстановления получается выборка FR = FR,(1),..., FR,(s) восстанов ленных массивов.

В качестве оценки качества восстановления массива можно выбрать сред няя квадратичная ошибка (mean squared error, MSE ):

s distms 2 FR,(k), F, MSE = s k= которая является оценкой Edistms 2 (FR, F).

Сравнивалась очистка от шума при следующих размерах окна:

“SVD”, сингулярное разложение всего массива (1.7.11);

• (Lx, Ly ) = (Nx, 1) “MSSA-X”, многомерный ряд по x (1.7.12);

• (Lx, Ly ) = (Nx /2, 1) “MSSA-Y”, многомерный ряд по y (1.7.13);

• (Lx, Ly ) = (1, Ny /2) “2D-SSA_M”, 2D-SSA при максимальном зна • (Lx, Ly ) = (Nx /2, Ny /2) чении произведения Lx Ly ;

• (Lx, Ly ) = (L0, L0 ), где L0 = “2D-SSA_L”, 2D-SSA, min(Nx, Ny ) сравнимый по трудоемкости c SVD.

5.1.2. Массивы конечного ранга, сравнение методов Пусть массив F имеет конечный ранг, rank F = d min(Nx /2, Ny /2).

Тогда для рассматриваемых размеров окна rank(Lx,Ly ) F Lx Ly, т.е. траек торная матрица имеет неполный ранг и можно ожидать (Lx, Ly )-отделимости массива F от шума. При достаточно большом соотношении сигнал/шум, когда собственные числа сигнала и шума разделены, наилучшее восстановление до стигается для r = rank(Lx,Ly ) F, что было установлено на основе экспериментов для различных массивов конечного ранга (см. [19]). Заметим, что для времен ных рядов при любом ненулевом соотношении сигнал/шум наблюдается асимп тотическая разделимость ряда конечного ранга от белого шума при N и L N, 0 1, что отмечалось в недавней работе [64]. Это свойство m n также наблюдается и для массивов. Для массива sin + 0.5 sin + 0. 6 на рис. 5.1 изображена зависимость ошибки восстановления при SNR = 0.1, (Lx, Ly ) = (Nx /2, Ny /2) и Nx = Ny (порядок сходимости имеет вид O(1/(Nx Ny ))).

0. MSE 0. 0. 50 100 150 N_x = N_y m n Рис. 5.1. MSE восстановления для массива sin + 0.3 и SNR = 0. + 0.5 sin 6 Далее в этом разделе на примерах различных массивов конечного ранга демонстрируются свойства методов при восстановлении по количеству компо нент, равном (Lx, Ly )-рангу r = rank(Lx,Ly ) F. Формулы массивов приведены в таблице 5.1. Все массивы имеют размеры 24 24, уровень шума выбирался не слишком большим (SNR 3). Часть массивов является произведениями одномерных рядов конечного ранга, а часть поворотами на /4 этих про изведений рядов. Для примера также приведен массив, состоящий из суммы произведений рядов (sin_prod_sum).

Таблица 5.1. Массивы конечного ранга, формулы массив fm,n m n sin12_sin6 sin + 0.5 sin + 0. 6 (mn) (m+n) sin12_sin6_rot sin + 0.5 sin + 0. 62 n (0.1m 1.14) sin lin_sin (m+n) 0.1 mn 1.14 sin lin_sin_rot 2 m n m n + 0.5 · sin sin_prod_sum sin sin sin 6 6 3 exp exp (0.04m + 0.03n) (0.1m 1.14) (0.1n 1.13) lin_lin (0.05(m + n) 0.84) (m n) · 0. lin_lin_rot m sin_exp sin + 0.5 exp (0.05n) (m+n) 0.05(mn) sin_exp_rot sin + 0.5 exp 62 (0.1m 1.14) exp (0.05n) lin_exp Отметим, что для методов SVD, MSSA-X и MSSA-Y ранг может быть меньше ранга массива, так как размеры окна могут не попадать в область допустимых размеров окна (см. раздел 4.2). В таблицах 5.2–5.4 приводятся ре зультаты восстановления для 50 реализаций. В большинстве случаев результа ты приводятся только для MSSA-X, так как если ранги для MSSA-X и MSSA-Y совпадают, то результаты восстановления практически не различаются.

Результаты экспериментов таковы.

1. Для всех тестовых примеров наилучшее восстановление достигается для “2D-SSA_M” (таблицы 5.2–5.4). Также для всех тестовых примеров име ет место следующая упорядоченность по убыванию качества восстанов ления: 2D-SSA_M, 2D-SSA_L, MSSA.

2. Для массивов, у которых ранг для SVD существенно меньше, чем ранг для 2D-SSA, SVD оказывается лучше, чем 2D-SSA_L и MSSA (табли ца 5.2).

Таблица 5.2. MSE (ранг) для массивов с небольшим SVD-рангом массив SVD MSSA-Y 2D-SSA_L 2D-SSA_M 0.0150 (2) 0.0269 (4) 0.0208 (8) 0.0069 (8) sum_prod_sin 0.0075 (1) 0.0127 (2) 0.0093 (4) 0.0034 (4) sin12_sin 0.0071 (1) 0.0128 (2) 0.0094 (4) 0.0034 (4) lin_sin 0.0060 (1) 0.0112 (2) 0.0076 (4) 0.0028 (4) lin_lin В то же время, для массивов с одинаковым рангом во всех методах SVD оказывается хуже остальных методов, причем эти массивы в основ ном, массивы из первой группы, повернутые на /4. Это показывает устойчивость 2D-SSA к повороту, в отличие от SVD (см. таблицу 5.3).

Таблица 5.3. MSE (ранг) для массивов с одинаковым рангом массив SVD MSSA-Y 2D-SSA_L 2D-SSA_M sin12_sin6_rot 0.0290 (4) 0.0242 (4) 0.0091 (4) 0.0035 (4) 0.0074 (4) 0.0073 (4) 0.0024 (4) 0.0009 (4) lin_sin_rot 0.1600 (2) 0.1411 (2) 0.0504 (2) 0.0206 (2) sin_exp_rot 0.1872 (1) 0.1601 (1) 0.0505 (1) 0.0224 (1) exp 3. В примерах, где ранг массивов не сильно различается для разных ме тодов, SVD также оказывается хуже, чем аналогичный ему по трудо емкости 2D-SSA_L, но SVD остается немного лучше, чем MSSA-X (см.

таблицу 5.4).

Таблица 5.4. MSE (ранг) для массивов с близкими рангами массив SVD MSSA-X MSSA-Y 2D-SSA_L 2D-SSA_M 0.0529 (1) 0.0921 (2) 0.0471 (1) 0.0346 (2) 0.0145 (2) sin_exp 0.0569 (1) 0.1056 (2) 0.0481 (1) 0.0339 (2) 0.0136 (2) lin_exp 0.0106 (2) - 0.0151 (3) 0.0071 (4) 0.0027 (4) lin_lin_rot 5.1.3. Зависимость ошибки восстановления от размеров окна и структура ошибки Основной целью данного раздела является исследование вопроса выбо ра оптимальных размеров окна для восстановления массива (в смысле MSE).

Рассмотрим тестовый массив sin12_sin6 и найдем размеры окна, при кото рых достигается оптимальное восстановление. На рис. 5.2 изображены графи ки RMSE (корни из MSE) для размеров окна (Lx, Ly ) {2,..., Nx 2} {2,..., Ny 2} для различных размеров массива.

Рис. 5.2. Зависимость RMSE от (Lx, Ly ) для (Nx, Ny ) = (12, 12), (18, 18), (24, 24), (48, 48).

На графиках можно увидеть, что (Lx, Ly ) = (Nx /2, Ny /2) не являются оп тимальными размерами окна для восстановления массива, а таковыми явля ются размеры окна (Lx, Ly ) (Nx /3, 2Ny /3) или эквивалентные им (Lx, Ly ) (2Nx /3, Ny /3). Данный эффект имеет место и для одномерных рядов [64], где половина длины ряда L = N/2 не является оптимальной длиной окна. Одна ко в случае массивов выигрыш при выборе оптимальных размеров окна, по сравнению с (Nx /2, Ny /2), измеряемый как (MSEopt /MSEhalf 1)100% [69], составляет примерно 7% (см. подробнее в таблице 5.5).

Для одномерного случая также известно, что различны оптимальные дли ны окна для восстановления различных частей ряда: краев, середины, и т. д.

При этом для середины ряда оптимальной является L = N/2, а для краев L 0.4N, при этом выигрыш по сравнению с L = N/2 составляет около 9%, что аналитически доказано для константного ряда в [69]. Для того, что бы исследовать зависимость ошибки от интересующей области, введем меру качества восстановления области I {0,..., Nx 1} {0,..., Ny 1} как s 1 R,(k) fm,n fm,n MSEI =.

s|I| (m,n)I k= Рис. 5.3. Области массива Далее рассмотрим 24 24 массив sin12_sin6 и разобъем его на три об ласти: центральную область (center, (m, n) Ic ), среднюю полосу (middle, (m, n) Im ) и крайнюю область (edges, (m, n) Ie ), в соответствии с рис. 5.3.

Ic = {Nx /3,... 2Nx /3} {Ny /3,..., 2Ny /3}, Im = {Nx /6,..., 5Nx /6} {Ny /6,..., 5Ny /6} \ Ic, Ie = {0,..., Nx 1} {0,..., Ny 1} \ (Ic Im ).

На рис. 5.4 приведены зависимости восстановления от размеров окна мас сива sin12_sin6 для различных областей (400 реализаций).

Рис. 5.4. MSEIc, MSEIm, MSEIe для (Lx, Ly ) {2,..., Nx 2} {2,..., Ny 2}.

Можно увидеть, что для центральной области оптимальные размеры ок на равны (Nx /2, Ny /2), в то же время оптимальные размеры окна для средней полосы и краев совпадают и примерно равны (Nx /3, 2Ny /3). Оба эти наблюде ния согласуются с известными результатами для некоторых одномерных рядов конечного ранга [69]. Результаты для оптимальных размеров окна продемон стрированы в таблице 5.5 (MSEL, MSEH границы доверительных интерва лов для MSE).

Таблица 5.5. Оптимальное восстановление для различных областей Lx Ly MSE MSEL MSEH MSEJc MSEJm MSEJe 16 9 0.0031 0.0030 0.0032 0.0018 0.0026 0. 12 12 0.0034 0.0033 0.0035 0.0015 0.0027 0. Отметим, что оптимальные размеры окна совпадают и для краев массива, и для средней полосы, и для всего массива. Этот факт можно объяснить тем, что доли Je, Jm, Jc составляют 5/9, 1/3 и 1/9 соответственно, поэтому несмот ря на то, что ухудшение восстановления для середины больше чем улучшение для краев, на качество восстановления массива в среднем это не влияет. Заме тим также, что на краях качество восстановления массива улучшается более чем на 10%.

5.1.4. Массивы неполного ранга Также было проведено сравнение методов восстановления для массивов неполного ранга, определенных в разделе 4.1.

Сравнивались те же методы. Рассматривалось два тестовых примера: про изведение ряда бесконечного ранга (1,..., 1, 1,..., 1) на ряд из синусов, и этот же массив, повернутый на /4, оба массива 24 24, формулы приведены в таблице 5.6.


Таблица 5.6. Массивы неполного ранга, формулы массив fm,n n sign (m 12 + 0.5) sin inf_sin (m n + 3) sign (m + n 24 + 0.5) sin inf_sin_rot Для массива inf_sin (Lx, Ly )-ранг равен min(Lx, Kx ) · min(2, Ly, Ky ), т.е.

увеличивается только при изменении Lx. Можно показать, что для массива inf_sin_rot (Lx, Ly )-ранг равен 2·(min(Lx +Ly, Kx +Ky )2) (для Kx, Ky, Lx, Ly больших 2).

Массивы восстанавливались для каждого из методов по оптимальному количеству компонент. Результаты содержатся в таблице 5.7. Заметим, что оптимальное количество компонент не равно, вообще говоря, истинному рангу.

Таблица 5.7. Массивы неполного ранга, MSE (ранг, оптимальный кол-во компонент) массив SVD MSSA-X MSSA-Y 2D-SSA_L 2D-SSA_M 0.0131 0.0729 0.0228 0.0315 0. inf_sin (1,1) (12,3) (2,2) (10,5) (24,13) 0.1243 0.0814 - 0.0406 0. inf_sin_rot (24,8) (12,5) (16,6) (44,13) Для массива inf_sin, как и ожидалось, лучшие результаты дает SVD (так как SVD хорошо отделяет массивы ранга 1, т.е. представляемые в виде pm ·qn ).

Следующий по качеству MSSA-Y (в случае, когда массив рассматривается как многомерный ряд по y). Это тоже объяснимо, так как ряды fm,· являются рядами конечного ранга одинаковой структуры (синусами с одинаковой часто той и различными фазами). Из этого можно сделать вывод, что для массивов, у которых неравноправны координаты (по одной координате ряды имеют ко нечный ранг, а по другой бесконечный), лучше применять MSSA, т.е. рас сматривать массив как набор рядов конечного ранга. В случае inf_sin_rot, напротив, массив нельзя представить в виде pm · qn, и здесь SVD дает худшее качество, а случаи MSSA-X и MSSA-Y не различаются и тоже дают плохое качество.

Причем SVD оказывается хуже 2D-SSA, даже если восстанавливать не по оптимальному количеству компонент, а по рангу незашумленного массива. За метим также, что 2D-SSA с размерами окна (5, 5) дает лучшее восстановление, чем с размерами (12, 12).

5.2. Задачи анализа изображений В этом разделе будут рассматриваться различные приложения метода АСС для анализа изображений. Будут рассматриваться задачи сглаживания цифровых моделей рельефа и задачи классификации текстур.

5.2.1. Фильтрация цифровых моделей рельефа Так же как и для временных рядов, метод АСС может быть применен для сглаживания изображений, т.е. выделения низкочастотной составляющей.

Нами будет рассмотрено сглаживание изображений на примере цифровых мо делей высот (ЦМВ), для которых данная задача возникает при вычислении морфометрических характеристик, таких как горизонтальная и вертикальная кривизны [60]. Применению метода АСС для сглаживания ЦМВ посвящены работы [65] и [20].

Рассмотрим следующий способ сглаживания. Пусть F изображение. По размерам окна (Lx, Ly ) и количеству выбранных компонент d строится F{1,...,d} восстановленное по первым d компонентам изображение.

Рассматриваются данные из работы [20], где анализируются ЦМВ для территории Москвы и прилегающих районов, выделенные из архива SRTM (Shuttle Radar Topographic Mission) [114]. ЦМВ в архиве STRM имеют раз решение 3, что на широте Москвы составляет приблизительно 52 93 м.

Приведенная здесь ЦМВ имеет размеры 624 456 и изображена на рис. 5.5.

Отметим, что здесь и далее на рисунках для цифровых изображений (в том числе и ЦМВ) ось x направлена вправо, а ось y вниз, т.е. массив транспони рован перед изображением.

С помощью окна размером 10 10 и выбора различного числа компонент, d = 1, 5, 12 мы получаем фильтрацию с различным разрешения. Исходная ЦМВ и результаты фильтрации изображены на рис. 5.5.

Горизонтальные и вертикальные кривизны функции f (x, y) определяются как [59] p2 r+2pqs+q 2 t kv =, (q 2 +r2 ) (1+p2 +q 2 ) (5.2.1) 2 2q r2pqs+p2 t 2, kh = (q +r2 ) 1+p +q 2f 2f 2f f f x2, xy, иq= y.

r= t= s= p= y 2 x Дискретизацию равенств 5.2.1 не имеет смысла применять к исходному изображению, так как оно содержит высокочастотную составляющую (см. [65] и [20]). На рис. 5.6 и рис. 5.7 изображены карты горизонтальных и вертикаль ных кривизн для отфильтрованных изображений.

Как было показано в [20], полученные карты кривизн хорошо отража ют геоморфологические признаки разной степени детализации и могут быть полезны для инженерно-геологического районирования территории Москвы.

Отметим, что при выборе одной компоненты наблюдаются разрывы кривизн на расстоянии размера окна, что можно объяснить разрывом производной ве совой функции (1.7.9), на которую происходит деление при ганкелизации.

Рис. 5.5. Исходная ЦМВ территории Москвы и результаты фильтрации по первым 1, 5 и 12 компонентам Рис. 5.6. Горизонтальная кривизна для результатов фильтрации по первым 1, 5, 12 компо нентам Частотные свойства фильтрации с помощью АСС Здесь мы рассмотрим частотные свойства фильтрации, которые позво ляют осуществлять фильтрацию разной степени детализации. Для массива Рис. 5.7. Вертикальная кривизна для результатов фильтрации по первым 1, 5, 12 компо нентам N 1,N F = (fm,n )m,n=0 y определим его двумерное дискретное преобразование Фу x Nx 1,N рье F = (fm,n )m,n=0 y как Nx 1,Ny fm,n e2imk/Nx e2inl/Ny. (5.2.2) fm,n = k,l= Преобразование Фурье является линейным преобразованием (подробнее см. в разделе 5.3), поэтому для G = F(1) +F(2) верно G = F(1) +F(2). Рассмотрим группировку {1,..., 100} = J1 J2 J3 J4 = {1} {2,..., 5} {6,..., 12} {13,..., 100}, восстановленные массивы FJ1, FJ2, FJ3, FJ4, и их преобразования Фурье FJ1, FJ2, FJ3, FJ4. Преобразованиями Фурье восстановленных по первым d компо нентам массивов для d = 1, 5, 12, 100 являются (FJ1 ), (FJ1 + FJ2 ), (FJ1 + FJ2 + FJ3 ) и (FJ1 + FJ2 + FJ3 + FJ4 ). На рис. 5.8 изображены модули элементов преоб разований Фурье. Можно увидеть, что фильтрация по первым компонентам представляет собой частотную фильтрацию “по слоям” спектра. Отметим при роду асимметрии слоев. Элементы исходного массива F являются измерения ми высоты поверхности на прямоугольной сетке, fm,n = f (x m, y n), причем x /y 52/93 = 0.559. Для того, чтобы изобразить в масштабе исходной функ Рис. 5.8. Модули преобразований Фурье FJ2,FJ3, FJ4.

ции, изображения DF T необходимо растянуть по x. На рис. 5.9 изображены растянутые преобразования Фурье.

Рис. 5.9. Растянутые модули преобразований Фурье FJ2,FJ3, FJ4.

Видно, что фильтрация АСС соответствует выбору частот спектра в неко тором круге |(x, y )| d, что вполне объяснимо, так как поверхность земли в районе Москвы должна быть изотропна относительно характеристик кривизн по направлениям. Таким образом, фильтрация АСС является адаптивной для формы спектра Фурье конкретного изображения, что может быть полезным, так как мы заранее можем не знать характер распределения частот.

5.2.2. Задачи анализа текстур Основным недостатком существующих методов анализа текстур, основан ных на собственных фильтрах, является высокая размерность пространства откликов, что требует отдельной процедуры классификации в многомерном пространстве откликов, зачастую, нелинейной. Кроме того, в силу вычисли тельных сложностей, в предыдущих работах рассматривались лишь неболь шие размеры окна (не более 10 10). В данном разделе будет показано, как в рамках методологии АСС можно обойтись без классификации в многомерном пространстве. Кроме того, будет показано, что при увеличении размеров окна точность классификации может улучшаться, что безусловно делает актуаль ным разработку быстрых методов АСС-разложения.

Расстояния близости между изображениями Для двух изображений F(1) и F(2) мы будем вводить расстояние (F(1),F(2) ) на основе существующих в рамках методологии АСС принципов. Основная идея заключается в том, чтобы ввести некоторую меру близости между траек торными пространствами L(Lx,Ly ) (F(1) ) и L(Lx,Ly ) (F(2) ) или их конечномерными аппроксимациями.

Естественным расширением идеи собственной фильтрации является рас смотрение вместо одномерных проекций на собственные массивы (см. раздел 1.7.3), проекций на некоторое подпространство, порожденное набором соб ственных массивов. Пусть есть два массива F(1) и F(2) и выбрано подпростран ство Ld = span{j1,..., jd }, порожденное собственными массивами массива F(1). Тогда введем следующее расстояние Kx 1,Ky (2),(Lx,Ly ), Ld ) distM (Fk,l k,l= CH (F(2), F(1) ) =, Kx 1,Ky (2),(Lx,Ly ) Fk,l M k,l= (2),(Lx,Ly ) где Fk,l есть скользящие Lx Ly окна массива F. Расстояние, анало гичное CH, используется при обнаружении разладки в структуре временных рядов [66] и в алгоритмах subspace tracking в обработке одномерных сигна лов. Заметим, что расстояние CH, вообще говоря, несимметрично и зависит от выбора набора J = {j1,..., jd } собственных троек. Для простоты далее мы будем считать, что {j1,..., jd } = {1,..., d}, т.е. нам необходимо задать лишь количество компонент d.

Другое расстояние близости между подпространствами было предложено в [109]. Пусть F(1), F(2) два изображения и W(1), W(2) их траекторные матрицы. Введем нормализованные траекторные матрицы X1 = W(1) / tr(W(1) (W(1) )T ),, X2 = W(2) / tr(W(2) (W(2) )T ) для которых их нормы Фробениуса, т.е. и совместную траекторную матрицу (аналогично алгоритму MSSA) X3 =.

X1 X def (k) (k) Пусть также для k = 1..3, 1,..., dk собственные числа матриц Sk = Xk XT (квадраты сингулярных чисел), причем S(3) = S(1) + S(2). Так как мат k рицы нормализованы, суммы собственных чисел для S(1) и S(2) равны 1 и для k = 1, 2 собственные числа можно рассматривать как вероятности исхо дов дискретных распределений в точках {1,..., dk }. Предлагаемое расстояние основано на сравнении данных распределений. Обозначим t (k) Fk (t) = j, k = 1... 3, j= функции распределения собственных чисел и введем функцию G(t) = F1 (t) + F2 (t) 2F3 (t).

Если два изображения совпадают, то G(t) = 0. Если два изображения (Lx, Ly )-разделимы, то G(t) 0 для любого t, 1 t rank(Lx,Ly ) (F(1) ) + rank(Lx,Ly ) (F(2) ), к тому же G(t) 0 для любых пар изображений (подробнее см. в [109]).

Расстояния между изображениями вводятся как (F(1), F(2) ) = max G(t) AZ 0tr 1 (F(1), F(2) ) = G(t).

AZ 0tr Применение расстояний в задачах классификации Для начала отметим некоторые свойства расстояний. Предложенные рас стояния не требуют масштабирования изображений, так как масштабирование в них присутствует. Центрирование изображений для их сравнения, как и в других методах текстурного анализа [124] необходимо, однако здесь мы бу дем рассматривать модификации расстояний, которые уже содержат в себе центрирование, основанное на методе АСС с центрированием [66]. Вместо тра екторных матриц W в расстояниях CH, AZ используются центрированные T траекторные матрицы (W WEK EK ). С такой модификацией введенные рас стояния вообще не требуют стандартизации.

Покажем применимость и некоторые свойства расстояний на примере за дачи сегментации. Пусть имеется исходное изображение G размера Tx Ty, заданы размеры Nx Ny, 1 Nx Tx, 1 Ny Ty и базовое Nx Ny изоб ражение F(1). Требуется построить карту принадлежности скользящих изоб T N,Ty Ny (N,Ny ) ражений Gk,l x к базовому классу, C = (ck,l )k,l=0 x, ck,l {0, 1}.

x Данная задача будет решаться следующим образом: выбираются размеры окна (Lx, Ly ), 1 Lx Nx, 1 Ly Ny, расстояние и параметр расстояния T N,Ty Ny (r для AZ и d для CH ). Затем строится карта расстояний D = (dk,l )k,l=0 x, x (N,Ny ), F(1) ), из которой карта C строится выбором некоторого поро dk,l = (Gk,l x га.

В качестве тестового изображения было выбрано стандартное тестовое изображение “barbara”, Nx = Ny = 512. Размер базового изображения и сколь зящих изображений равен Nx Ny = 20 20. Примеры тестового и базового изображения изображены на рис. 5.10. В данном разделе в качестве базового изображения взято скользящее изображение с координатами (k, l) = (96, 257) (выделено красной рамкой на рис. 5.10).

Рис. 5.10. Barbara: тестовое и базовое изображения Размеры окна были выбраны равными 10 10 и строилась карта расстоя ний для различных параметров r, d. Качество сегментации оценивалось визу ально. Общие результаты таковы: оба расстояния при некоторых параметрах позволяют идентифицировать область, текстурированную так же, как и базо вое изображение (угол скатерти на рис. 5.10). Карты расстояний для CH для различных d изображены на рис. 5.11. Видно, что для расстояния CH важен выбор размерности подпространства: при увеличении ранга расстояние CH начинает давать ложные срабатывания.

d=2 d=4 d=8 d = Рис. 5.11. Barbara: карта расстояния CH Расстояние AZ, напротив, при увеличении количества рассматриваемых компонент стабилизируется. Таким образом, не требуется хорошая оценка ран га, что является преимуществом метода, поскольку не требуется оценивать по рядок модели. Заметим также, что в данном примере требуется лишь неболь шое число компонент. На рис. 5.12 изображены карты расстояний для 1.

AZ r=2 r=4 r=8 r = Рис. 5.12. Barbara: карта расстояния AZ Columbia-Utrecht texture database В этом разделе также демонстрируется применимость введенных рассто яний для задачи классификации сложных природных текстур. Рассматрива ется база данных CUReT [52, 54]. База данных содержит 61 классов поверх ностей материалов, сфотографированных при различных условиях. В работе [124] для каждого класса выбраны 92 представительных текстуры размера 200 200.

В данном эксперименте нами выбраны Nc = 40 классов текстур из 61.

Набор из 3680 текстур делится на базовый FB,(k),(l), k {1,..., Nc }, l {1,..., Nt } и тестовый FT,(k),(l), k {1,..., Nc }, l {1,..., Nt }, причем в каждом из наборов каждому классу соответствует Nt = 46 текстур.

Классификация осуществляется следующим образом: каждой текстуре FT,(k),(l) из тестового набора ставится в соответствие jk,l класс ближайшей текстуры. Тогда процент правильно классифицированных текстур определя ется как Nc #{jk,l = k} k= 100% ·, Nc Nt т.е. количество тех текстур, для которых класс jk,l, определенный с помощью процедуры классификации, совпадает с истинным классом. Сравнивались рас стояния и 1 для размеров окна (10, 10) (r = 15). Процент правильно AZ AZ классифицированных текстур составляет 82.32% и 86.51% соответственно, что демонстрирует применимость расстояний для данных задач, а также некото рое превосходство расстояния 1.

AZ Покажем, что при увеличении размеров окна качество классификации мо жет быть улучшено. Для ускорения вычислений изображения были масшта бированы до размеров 100 100 и был выбран набор из 10 классов текстур {40, 42, 43, 45, 46, 47, 50, 51, 52, 53}.

Таким образом, на 920 изображениях сравнивались расстояния 1 для разме AZ ров окна (5, 5) и (20, 20) (что соответствует размерам окна (10, 10) и (40, 40) для исходных изображений). Результаты классификации составляют 86.54% и 90.86%. Причину улучшения классификации можно увидеть и на матрице попарных расстояний между базовыми FB,(k),(l) изображениями и тестовыми изображениями FT,(k),(l), изображенной на рис. 5.13 для окон (5, 5) и (20, 20).

На рис. 5.13 видно, что классификация с окном (5, 5) хуже различает пары тек Рис. 5.13. Матрица расстояний между тестовыми (столбцы) и базовыми (строки) изобра жениями. Слева: окно (5, 5), справа: окно (20, 20).

стур {43, 45}, {47, 50} и {52, 53}. На рис. 5.14 изображены образцы текстур из пары {43, 45}. Видно, что расстояния между пиками второй текстуры заметно больше 5. Возможно поэтому классификация с окном (5, 5) плохо различает эти текстуры известно [66], что для хорошей разделимости синусоидальных сигналов требуется, чтобы длина окна была не менее половины периода.

Рис. 5.14. Примеры текстур из базы данных CURET. Слева: класс 43 (id: 081);

справа:

класс 45 (id: 044).

5.3. Комплекс программ для АСС-разложения и обработки данных Данный раздел посвящен описанию алгоритмов и методов, лежащих в основе разработанного в рамках диссертации комплекса программ, который позволяет осуществлять АСС-разложение для вещественнозначных массивов.

В рамках комплекса также реализованы алгоритмы обработки изображений, описанные в разделе 5.2.

Наиболее существенные затраты, как машинного времени, так и памяти, относятся к этапу разложения как наиболее трудоемкому этапу метода АСС.

Для массива FNx,Ny и размеров окна (Lx, Ly ) блочно-ганкелева траекторная матрица, получаемая на шаге вложения, имеет размер L K, где L = Lx Ly и K = (Nx Lx + 1) (Ny Ly + 1). Даже для небольшого изображения 219 219 и небольших размеров окна 20 20 траекторная матрица имеет размер 400 40000 = 1.6 · 107, что при попытке представления элементов мат рицы в виде 8-байтовых чисел с плавающей запятой требует 1.28 · 108 байт (около 100 мегабайт) оперативной памяти. В худшем случае, при выборе окна Lx = Nx /2 и Ly = Ny /2 матрица имеет размер 1000010000 и для ее хранения требуется около 800 мегабайт. Даже для небольших размеров окна хранение траекторной матрицы представляется нецелесообразным. Сингулярное разло жение такой матрицы также представляет вычислительные трудности: стан дартные методы сингулярного разложения [15, 63], например, требуют около O(L2 K + LK 2 + K 3 ) умножений.

Для уменьшения объема памяти и вычислительной сложности предлага ется два метода:

• вычисление сингулярного разложения блочно-ганкелевой матрицы W с помощью вычисления собственных чисел и собственных векторов кова риационной матрицы S = WWT ;

• вычисление лишь первых нескольких векторов сингулярного разложе ния с помощью итераций Ланцоша. Данный метод является расширени ем на двумерный случай метода, предложенного в [81].

В обоих случаях не требуется хранения всей траекторной матрицы. В пер вом случае можно вычислять лишь необходимое количество факторных век торов. Во втором случае требуется лишь реализация умножения траекторной матрицы на вектор, которая может быть эффективно осуществлена с помо щью дискретного преобразования Фурье [81, 104].

5.3.1. АСС-разложение на основе вычисления ковариационной матрицы Пусть F двумерный массив, заданы размеры окна (Lx, Ly ). Рассмотрим алгоритм метода АСС при использовании лишь ковариационной матрицы, т.е.

без шага вложения.

Этап разложения. Сингулярное разложение траекторной матрицы d j Uj VjT, W= j= можно найти следующим образом. Пусть S = (sij )L,L = WWT. Тогда {j }d j= i,j= j, {Uj }d собственные числа матрицы S, j = ее собственные векторы.

j= Элементы ковариационной матрицы S являются скалярными произведениями всевозможных пар различных Kx Ky подматриц массива F (K,Ky ) su+vLx +1,s+tLx +1 = Fu,vx,Ky ), Fs,t x (K M, где 0 u, s Lx, 0 v, t Ly. Таким образом, ковариационную матрицу можно вычислить без построения траекторной матрицы W.

j WT Uj. Так как j = Факторные векторы можно найти как Vj = 1/ j F j (см. раздел 1.7.3), построения траекторной матрицы также не тре 1/ буется. К тому же обычно требуются лишь первые d компонент сингулярного разложения, поэтому можно вычислять лишь первые d факторных векторов, что позволяет сократить объем используемой памяти.

Этап восстановления. При восстановлении также не требуется постро ения сгруппированных элементарных матриц. Пусть I некоторая группа индексов, и нам нужно найти восстановленный массив FI (см. (1.7.10)), кото рый получается из H MLx,Kx (ELy Ky H C Z)(WI ) H MLx,Kx (1Ly Ky H C )(WI ) = j Uj VjT = H MLx,Kx (1Ly Ky H C ) = jI j Uj VjT ).

H MLx,Kx (1Ly Ky H C )( = jI Таким образом, нам достаточно уметь вычислять j Uj VjT ).

H MLx,Kx (1Ly Ky H C )( Покажем, как коэффициенты результирующего элементарного массива Fj = L 1,L можно выразить через соответствующие собственный массив {fmn }m,n=0 y x j и факторный массив j.



Pages:     | 1 | 2 || 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.