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

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

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


Pages:     | 1 || 3 | 4 |

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

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

Определение 2.1.2. Пусть ряд имеет ранг d. Если 1 d N/2, то вектор Q, удовлетворяющий условиям предложения 2.1.3, будем называть вторым характеристическим вектором. Для d = 1 вторым характеристическим век N тором называется любой Q KN +1, такой что Q span{I0 +1 P,..., IN +1 P }.

/ N Для d = 0 второй характеристический вектор не определен. Для краткости, характеристическим вектором будем называть первый характеристический вектор, если не указано иное.

Для ряда полного ранга, т.е. для d = (N + 1)/2, пару векторов P и Q, удо влетворяющих условиям предложения 2.1.2, будем называть парой характери стических векторов (не различая первый и второй), так как они определены с точностью до замены базиса в двумерном пространстве.

Замечание 2.1.4. Для ряда ранга d = 1 пункт 2 предложения 2.1.3 также выполняется для пары характеристических векторов.

Предложение 2.1.4 ([74, Prop. 5.2]) Характеристические векторы P и Q любого ряда удовлетворяют соотношению p0 0... 0 q0 0.............

.....

.....

..

pd q..

det (2.1.8). = 0.

....

.

0 p0 qN d+..

............

.

...

0... 0 pd 0 0 qN d+ Также верно утверждение, обратное предложению 2.1.4.

Предложение 2.1.5 ([74, Th. 5.2, Rem. 5.2]) Пусть даны N, 1 d (N + 1)/2. Тогда любой паре векторов P Kd+1 и Q KN d+2, удовлетворяющим свойству (2.1.8), соответствует единственный (с точностью до умноже ния на константу) ряд FN, для которого они являются характеристически ми.

Для случая pd = 0 замечание 2.1.4 и предложение 2.1.5 можно записать на языке многочленов.

Предложение 2.1.6. Существует взаимнооднозначное соответствие меж ду ранга d N/2 с pd = 1 и парами взаимно простых многочленов P (z) и Q(z) (т.е. таких, что gcd(P, Q) = 1), deg P = d, deg Q d, pd = 1. При этом векторы P = (p0,..., pd )T и Q = (q0,..., qd1, 0,..., 0)T KN d+2 явля ются характеристическими для соответствующего ряда.

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

Пусть FN ряд ранга d N/2, и существует характеристический вектор P с pd = 1. Пусть Q некоторый второй характеристический вектор. Существу ет единственный многочлен вида Q(z), такой что Q (z) = H(z)P (z) + Q(z).

По предложению 2.1.3, этот вектор можно выбрать характеристическим, и ха рактеристический вектор такого вида существует ровно один с точностью до умножения на константу. Матрица из (2.1.8) является матрицей результанта [9, Гл. 5, §34] пары многочленов P (z) и Q(z), поэтому эти многочлены взаимно просты.

С другой стороны, если P, Q два таких взаимно простых многочлена, pd = 1, deg Q d, то определитель результанта (2.1.8) не равен нулю, и тогда, по предложению 2.1.5, существует единственный с точностью до умножения на константу ряд FN, для которого векторы P и Q являются характеристиче скими.

Таким образом, мы установили соответствие между следующими множе ствами классов эквивалентности (a) рядов по отношению умножения на кон станту и (b) пар P, Q, обладающих описанным свойством, по отношению умно жения Q на константу. Чтобы установить искомое соответствие, достаточно выбрать общую константу.

2.1.4. Поведение ранга при расширении ряда В теории ганкелевых матриц [74] изучается вопрос более широкий, чем во прос о продолжимости ряда (ср. определение 1.5.1), а именно: “как изменяется ранг и структура ганкелевой матрицы при добавлении к ней одного столбца с сохранением ганкелевости?” Сохранение ганкелевости матрицы X(L) означает, что добавляемый столбец имеет вид (L,) def XN L = (fN L+1,..., fN 1, )T, (2.1.9) () а расширенная матрица X(L) (FN +1 ) является L-траекторной матрицей ряда () () FN +1 = (f0,..., fN 1, ). Матрицу X(L) (FN +1 ) будем называть -расширением () матрицы X(L), а ряд FN +1 будем называть -расширением ряда FN.

Определение 2.1.3. [74, Def. 5.9] -расширение матрицы X(L) называется особым (singular extension [74]), если ее ранг при расширении сохраняется, () т.е. rankL (FN +1 ) = rankL (FN ).

Замечание 2.1.5. Ряд L-продолжим в смысле определения 1.5.1, если для него существует единственное особое -расширение.

Оказывается, что охарактеризовать все особые продолжения и, в частности, случаи L-продолжимости, можно лишь проследив, как меняется ранг всего ряда (а не только матрицы) при его -расширении.

Лемма 2.1.3. Пусть rank FN = d. Тогда для -расширения ряда выполняет ся неравенство () d rank FN +1 d + 1.

() Доказательство. Матрица X(L) (FN +1 ) получается из X(L) добавлением од ного столбца, поэтому () (2.1.10) 0 rankL FN +1 rankL FN для 1 L N. Неравенство (2.1.10) можно продолжить и для L = N + 1, если формально положить rankN +1 FN = 0. Отсюда получаем, что () () rank FN rank FN +1 = max rankL FN + 1LN + max rankL FN + 1 = rank FN + 1, 1LN + что и требовалось доказать.

Таким образом, при расширении возможны два варианта изменения ран га, изображенные на рис. 2.1.

Рис. 2.1. Поведение ранга Следствие 2.1.2. Пусть rank FN = d. Тогда -расширение матрицы X(L) • при 1 L d является особым для любого, • при N d + 1 L N не является особым ни для какого, • для любого d L N d + 1:

() – не является особым для тех, для которых rank FN = rank FN +1, () – является особым для тех, для которых rank FN = rank FN +1.

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

Предложение 2.1.7. Пусть rank FN = d, 0 d (N + 1)/2.

1. Если d = (N + 1)/2 (ряд полного ранга), то любое -расширение ряда имеет ранг d;

2. если d N/2, P = (p0,..., pd )T характеристический вектор ряда, то • при pd = 0 любое -расширение ряда имеет ранг d + 1, • при pd = 0 ранг расширения выражается как rank FN, = () rank FN +1 = rank F + 1 =, N где d (2.1.11) 0 = (pd ) pj fN d+j.

j= При этом, если ранг при расширении • сохраняется (pd = 0 и = 0 ), то сохраняется и характеристический () вектор P (FN +1 ) = P, () • увеличивается (pd = 0 или = 0 ), то ряд FN +1 имеет характеристи ческий вектор I0 P = (p0,..., pd, 0)T, d+ (заметим, что он не определен однозначно при d = N/2).

Полезно также и следующее следствие предложения 2.1.7 о свойствах ря да при его сокращении.

Следствие 2.1.3. Пусть дан ряд FN = (f0,..., fN 1 ) ранга 0 d N/ с характеристическим вектором P = (p0,..., pd )T. Его сокращение FN 1 = (f0,..., fN 2 ) обладает следующими свойствами:

1. Если pd = 0, то ранг FN 1 равен d, причем первый характеристический вектор P = P (FN 1 ) сокращенного ряда • равен P, если d N/2, • определен не однозначно, если d = N/2 (так как FN 1 имеет пол ный ранг).

2. Если pd = 0, то FN 1 имеет ранг d1 с характеристическим вектором P = (p0,..., pd1 )T.

2.1.5. Библиографические ссылки В [74] содержится первое полное описание структуры ядра для ганкеле вых матриц общего вида. В отечественной литературе эта теория представлена лишь в книге [33], в которой рассматривается структура лишь квадратных и почти квадратных(N N + 1) матриц. Задача о поведении ранга при расши рении впервые рассматривалась в работе Иохвидова [23]. Существуют также и работы по исследованию структуры блочно-ганкелевых матриц [57] при рас ширении.

В работе [74] активно используется язык многочленов, например, вводит ся понятие характеристических многочленов, а не векторов. Рассматриваются многочлены с корнями из P1 [26], т.е., по сути, однородные многочлены [26, Гл. 7]. Существуют также работы, в которых неявно рассматриваются ганке левы матрицы и, даже по сути, пересечение ядер нескольких матриц [41, 56].

В них рассматриваются конечные последовательности, удовлетворяющие ли нейным рекуррентным соотношениям (см. раздел 1.4). В [41] рассматриваются однородные формы особого типа и показывается, что множества линейных ре куррентных соотношений соответствуют однородным идеалам с пустым мно гообразием. Характеристические векторы P и Q, возникающие в теории ганке левых матриц, в точности соответствуют базисам Грёбнера (см. раздел 2.2.7) этих идеалов, подробнее см. в [41].

2.2. Бесконечные массивы В этом разделе мы будем рассматривать бесконечные комплекснозначные массивы F = (fm,n )+ и множества линейных рекуррентных соотношений, m,n= которыми связаны их элементы. Мы будем пользоваться, в основном, теорией полилинейных рекуррентных последовательностей [27–29]. k-Последователь ностью над полем K называется отображение Nk K. Таким образом, беско нечный двумерный массив является 2-последовательностью. Все утверждения и определения для простоты мы будем приводить для k = 2.

2.2.1. Бесконечные массивы и линейная сложность Определение 2.2.1. Для массива F его (k, l)-сдвигом Fk,l называется беско нечный массив с элементами (Fk,l )m,n = (F)m+k,n+l. Пространством сдвигов def называется L(F) = span{Fk,l }+.

k,l= Размерность пространства сдвигов называется линейной сложностью [28] def r(F) = dim L(F).

Определение 2.2.2. Будем называть F линейным рекуррентным массивом, (1) (1) ЛРМ 1, если существуют числа r1, r2 N0 и коэффициенты c0,..., cr1 1 C, в [28] k-линейной рекуррентной последовательностью, k-ЛРП (2) (2) c0,..., cr2 1 C, такие что для любых m, n N0 выполняются равенства r1 1 r2 (1) (2) fm+r1,n = ck fm+k,n, fm,n+r2 = cl fm,n+l, k=0 l= (1) (1) т.е. каждый столбец F удовлетворяет ЛРФ с коэффициентами c0,..., cr1 1 и (2) (2) каждая строка удовлетворяет ЛРФ с коэффициентами c0,..., cr2 1.

Предложение 2.2.1 ([27, Предл. 1.6]) L(F) конечномерно тогда и только тогда, когда F является линейным рекуррентным массивом.

Рассмотрим подробнее множество линейных рекуррентных соотношений для произвольного массива. Пусть C[x, y] кольцо многочленов двух пере менных над C. Для бесконечного массива F введем операцию умножения на + a(,) x y C[x, y] как многочлен p(x, y) =,= + (2.2.1) a(,) F,.

pF =,= Замечание 2.2.1. Относительно этой операции пространство бесконечных массивов становится (левым) C[x, y]-модулем [9]. L(F) является подмодулем, т.е. для любых q(x, y) C[x, y], G L(F) верно qG L(F).

Определение 2.2.3. Будем говорить, что многочлен p(x, y) аннулирует F, если pF = 0.

+ a(,) x y аннулирует F тогда Иными словами, многочлен p(x, y) =,= и только тогда, когда + a(,) fk+,l+ = 0 для любых k, l N0. (2.2.2),= Замечание 2.2.2. По предложению 2.2.1 r(F) + тогда и только тогда, когда существуют многочлены одной переменной r1 1 r2 (1) (2) r ck xk, r cl y l, p1 (x) = x p2 (y) = y k=0 l= которые аннулируют F, т.е. p1 F = p2 F = 0.

Определение 2.2.4. Для любого множества массивов S def I(S) = {p C[x, y] : pG = 0 G S} будем называть аннулятором S.

def Аннулятор I(F) = I({F}) будем называть аннулятором массива F.

Замечание 2.2.3. Для любого множества S его аннулятор I(S) является идеалом в C[x, y]. Напомним, I C[x, y] называется идеалом, если p + sq I для любых p, q I, s C[x, y].

Определение 2.2.5. Идеал I называется нульмерным, если его многообра def зие Z(I) = z C2 : f (z) = 0 f I конечно.

Известно следующее утверждение.

Предложение 2.2.2 ([26, Гл. 5, § 3, Т. 6]) I нульмерен тогда и только то гда, когда I содержит многочлены от одной переменной по x и по y.

Следствие 2.2.1. Массив F является линейным рекуррентным тогда и только тогда, когда его аннулятор I(F) нульмерен.

Также иногда может быть полезно следующее утверждение.

Предложение 2.2.3. r(F) = d тогда и только тогда, когда существу ют массивы A(1),..., A(d) и B (1),..., B (d), такие что d (j) (j) (2.2.3) fm+k,n+l = am,n bk,l, j= при этом наборы {A(1),..., A(d) } и {B (1),..., B (d) } являются базисами L(F).

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

Достаточно заметить, что равенство (2.2.3) можно записать в виде d d (j) A(j) bk,l am,n B (j).

(j) и Fm,n = Fk,l = j=1 j= 2.2.2. Биномиальное представление и базисы пространства сдвигов Определение 2.2.6. Для C и N0 определим элементарный беско нечный ряд = (g0,..., gn,...):

n n ( )n = gn =, где ( n ) биномиальный коэффициент k n(n 1)... (n k + 1), k 0, n def k!

= 1, k k = 0.

Замечание 2.2.4. Для = 0 элементарные ряды имеют вид def = e = (0,..., 0, 1, 0,...).

Определение 2.2.7. Для (, µ) C и (, ) N2 элементарный массив опре (,) def делим как (,µ) = ( )T ( ), т.е.

µ def (,) ((,µ) )m,n = ( )m ( )n.

µ Предложение 2.2.4 ([29, Теорема 13]) Линейный рекуррентный массив F имеет представление r + (k) (,) (2.2.4) F= b, ((k,µk ) ), k=1,= (k) где Z(I(F)) = {(1, µ1 ),..., (r, µr )} и b, некоторые комплексные коэф фициенты, ненулевых среди которых конечное число.

Замечание 2.2.5. Представление (2.2.4) называется биномиальным представ лением;

оно единственно в силу линейной независимости элементарных мас (,) сивов (,µ) для различных (, µ) C и (, ) N2.

Следствие 2.2.2. Бесконечный ЛРМ F имеет представление r qk (m, n)m µn, (2.2.5) fm,n = kk k= где Z(I(F)) = {(1, µ1 ),..., (r, µr )} и qk некоторые комплексные много члены.

Представление (2.2.5) также является единственным.

Замечание 2.2.6. Вещественнозначные ЛРМ имеют вид r qk (m, n)m µn fm,n = Re = kk (2.2.6) k= r pk (m, n)m µn cos(k m = + k ) cos(k n + k ), kk k= где k, k, k, k, k, µk R и pk являются вещественными многочленами.

2.2.3. Биномиальное представление с одним корнем Определение 2.2.8. Носителем массива F будем называть def Supp F = {(, ) N2 : f, = 0}.

Будем называть массив вырожденным, если его носитель конечен, т.е. когда # Supp F +.

Замечание 2.2.7. По предложению 2.2.4 массив F вырожден тогда и только тогда, когда Z(I(F)) = {(0, 0)}.

Важным примером являются массивы, обладающие биномиальным пред ставлением (2.2.4) с одним корнем (, µ):

(,) (, µ) C2, (2.2.7) F= b(,) (,µ), (,)N где B = (b, )+ (вырожденный) массив коэффициентов представления.

,= Лемма 2.2.1 ([29, Следствие 2]) Пусть (, µ) C2. Тогда для k, l N 0, k или l, l (,) k (x ) (x µ) (,µ) = (k,l), k и l.

(,µ) Предложение 2.2.5. 1. Для массива вида (2.2.7) массивы def DF,(k,l) = (x )k (y µ)l F имеют вид (,) (2.2.8) DF,(k,l) = b(+k,+l) (,µ).

(,)N Иными словами, DF,(k,l) обладает биномиальным представлением с одним корнем (, µ), массивом коэффициентов для которого является соответ ствующий сдвиг исходного массива коэффициентов Bk,l.

2. L(F) = {span DF,(k,l) }+.

k,l= Доказательство.

1. Следует из леммы 2.2.1.

2. Для любых u, v C, любой моном x y является линейной комбинацией многочленов (x u)k (y v)l. Полагая (u, v) = (, µ) или (u, v) = (, µ), получаем, что любой сдвиг F, линейно выражается через массивы DF,(k,l), и наоборот.

Следствие предложения 2.2.5 позволяет найти линейную сложность ЛРМ по массиву коэффициентов его биномиальному представлению.

Следствие 2.2.3 ([29, Предл. 23, (б)]) Пусть массив F имеет представле ние (2.2.7) и B есть массив коэффициентов. Тогда 1. I(F) = {p(x, y µ) : p(x, y) I(B)}.

2. r(F) = r(B).

2.2.4. Определяющие множества и оценки сверху линейной сложности по биномиальному представлению В этом разделе будет показано, что при переходе к массиву коэффици ентов биномиального представления сохраняется не только размерность, но и другие свойства пространства сдвигов.

Определение 2.2.9. Будем называть множество индексов A N2 определя def ющим для массива F, если dim span{F }A = r(F), где {F }A = {F(,) }(,)A.

Множество называется базисным, если оно определяющее и #A = r F, т.е.

{F }A является базисом L(F).

Очевидно, что если A определяющее множество, то r(F) #A, т.е. линей ную сложность ЛРМ можно оценить сверху.

Определение 2.2.10. Множество F N2 называется диаграммой Ферре 2, если для любого (, ) F оно содержит все меньшие индексы, т.е. для любого (k, l) N2, если k, l, то и (k, l) F.

Определение 2.2.11. Для множества индексов A обозначим F(A) наимень шую диаграмму Ферре, которая содержит множество A. Иными словами def F(A) = {(, ) N2 : (k, l) N2, (k +, l + ) A}.

0 На рис. 2.2 продемонстрирован пример множества и наименьшей диаграм мы Ферре, содержащей его. Множества индексов изображаются в виде набора клеток, ориентация осей соответствует расположению элементов массива в матричной записи.

По массиву коэффициентов биномиального представления массива с од ним корнем можно найти все его определяющие диаграммы Ферре.

Лемма 2.2.2. Пусть массив F имеет представление (2.2.7) с массивом ко эффициентов B. Диаграмма Ферре F является определяющей для F тогда и только тогда, когда F является определяющей для B.

В диссертации допускаются бесконечные диаграммы Ферре.

Рис. 2.2. Множество и его наименьшая диаграмма Ферре Доказательство.

Используя доказательство п.2 предложения 2.2.5, каждую степень xk y l можно выразить в виде линейной комбинации {(x ) (y µ) }k,l.

Так как Bk,l = 0 для любого (k, l) F(Supp B), то очевиден следующий / результат.

Предложение 2.2.6 ([29, Предложение 23, (а)]) Пусть F имеет представ ление (2.2.7). Тогда F(Supp B) является определяющим множеством для F и rank F #F(Supp B).

В разделе 4.1 будет показано, как можно найти в некоторых случаях более точ ную оценку линейной сложности, основываясь лишь на свойствах F(Supp B).

Линейную сложность можно оценить и по набору коэффициентов поли номиального представления (2.2.5).

Замечание 2.2.8. Если массив имеет вид c, m n m µn, fm,n = (,)N то коэффициенты массива C = (c, )+ линейно выражаются через млад,= шие коэффициенты массива B соответствующего биномиального представле ния (2.2.7):

(k) (,) c, = a, b,.

, Следовательно, F(Supp(B)) = F(Supp(C)) и вместо биномиального пред ставления в оценке предложения 2.2.6 можно использовать полиномиальное представление (2.2.5).

2.2.5. Нижняя оценка линейной сложности По носителю массива коэффициентов также можно получить нижнюю оценку для линейной сложности.

Определение 2.2.12. Для множества B Z2, обозначим def B + (k, l) = {(, ) Z2 : ( k, l) B}.

Определение 2.2.13. Для диаграммы Ферре F множеством углов называет ся c(F) F, такое что (, ) c(F) {( + 1, ), (, + 1)} F =.

Определение 2.2.14. ([29]) Диаграмма Ферре F может съесть множество, если существует цепочка множеств = 0 1... m =, где |j \ j1 | = 1 для 1 j m, и для каждого j существует индекс (kj, lj ) N2, такой что пересечение (F + (kj, lj )) j состоит из одного элемента (j lj, j lj ), где (j, j ) принадлежит c(F).

Пример “съедения” множества изображен на рис. 2.3.

Рис. 2.3. Углы диаграммы Ферре (слева) и процесс “съедения” множества (справа) Пусть E(F) обозначает максимальную мощность множества, которое мо жет съесть F.

Предложение 2.2.7 ([29, Теорема 31]) Пусть массив F имеет представле ние (2.2.7) и B есть его массив коэффициентов. Тогда E(F(Supp B)) r(F).

Пример 2.2.1. Если A = F(Supp B) = {0,..., M 1} {0,..., N 1}, то A может съесть любое свое подмножество. Следовательно, r(F) = #A = E(A) = M N и в этом случае A будет базисным множеством для F.

Пример 2.2.2. Диаграмма Ферре A всегда может съесть свою руку в направ лении x (в направлении y), т.е. максимальное множество вида {(0, 0), (1, 0),..., (k, 0)} (или {(0, 0), (0, 1),..., (0, l)} соответственно), которое содержится в A.

В [29] не приводится, что легко можно найти большее множество, чем ру ка, которую может съесть диаграмма Ферре, что будет показано в разделе 4.1.

2.2.6. Оценки линейной сложности по биномиальному представлению общего вида Лемма 2.2.3 ([29, Лемма 28]) Пусть F имеет биномиальное представление (2.2.4) и массивы F (1),..., F (r) определены как (k) (,) F (k) = (2.2.9) b(,) (k,µk ), (,)N т.е. F = F (1) +... + F (r). Тогда I(F) = I(F (1) )... I(F (n) ), L(F) = L(F (1) )... L(F (n) ), в частности, r(F) = r(F (1) ) +... + r(F (n) ).

Следствием из леммы 2.2.3, предложений 2.2.7 и 2.2.6 является следующее утверждение.

Следствие 2.2.4. Если массив имеет представление (2.2.4), B (k) масси вы коэффициентов компонент этого представления и Fk = F(Supp B (k) ), то выполняются неравенства E(F1 ) +... + E(Fr ) r(F) #F1 +... + #Fr.

Верхнюю оценку можно уточнить, предъявив определяющее множество, которое можно построить по Supp(B (k) ).

Определение 2.2.15. Определим для множеств A, B N2 сумму по Мин ковскому как def A + B = {( +, + ) : (, ) A, (, ) B}.

Также определим A+B = N2 \ (N2 \ A + N2 \ B).

0 0 Замечание 2.2.9. Легко видеть, то введенные операции являются коммута тивными и ассоциативными.

Предложение 2.2.8 ([29, Следствие 27]) Множество A = F(Supp(B (1) ))+... +F(Supp(B (r) )) является определяющим для F. В частности, rank F #A.

2.2.7. Граничные базисы и базисы Гребнера В этом разделе мы установим связь между определяющими множествами и свойствами идеала.

Определение 2.2.16. Факторалгеброй R(I) = C[x, y]/I идеала I называет ся множество классов эквивалентности def R(I) = {[p]I : p C[x, y]}, def где [p]I = {q C[x, y] : q p I}, с определенными в нем операциями сло def жения [p]I + [q]I = [p + q]I и умножения [p]I · [q]I = [p · q]I.

Из определения легко следует следующая лемма.

a(,) x y принадлежит I тогда и Лемма 2.2.4. Многочлен p(x, y) =,N a(,) [x y ]I = [0]I.

только тогда, когда,N Из леммы можно вывести следствие об изоморфизме факторалгебры и про странства сдвигов.

Следствие 2.2.5 ([27, Следствие 1.1]) Пусть F является ЛРМ. Множество A является определяющим (базисным) для F тогда и только тогда, ко гда {[x y ]}(,)A порождает факторалгебру R(I) (является базисом для R(I)).

def Определение 2.2.17. Границей множества индексов B N2 назовем (B) = ((B + (1, 0)) (B + (0, 1))) \ B.

Лемма 2.2.5. Пусть F является ЛРМ, A некоторое конечное множе ство индексов, содержащее 1 и (A) = {(1, 1 ),..., (r, r )} его граница.

1. Множество A является определяющим для F тогда и только тогда, когда существует набор многочленов pk I(F), 1 k r, вида def (k) pk (x, y) = xk y k a(, ) x y, (2.2.10) (, )A 2. Если множество A является базисным, то набор многочленов в п. определен единственным образом.

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

1. Необходимость очевидна, так как в этом случае любой класс эквива лентности [xk y k ]I должен линейно выражаться через элементы набора {[x y ]I }(, )A.

Теперь покажем достаточность. По [100, Лемма 2.3] для любого (, ) / A моном x y может быть представлен в виде r xy = pk (x, y)qk (x, y) + h(x, y), k= h(, ) x y. Таким образом, [x y ]I = h(, ) [x y ]I, где h(x, y) = (, )A (, )A и по следствию 2.2.5 A является определяющим.

(k) 2. По лемме 2.2.4 для любого k выполнено [xk y k ]I = a(, ) [x y ]I, и (, )A (k) коэффициенты определены единственным образом в силу единствен a, ности разложения по базису {[x y ]I }(, )A.

Определение 2.2.18. Для определяющего множества A набор многочленов вида (2.2.10) называется граничным предбазисом. Если множество A базис ное, то этот набор многочленов называется граничным базисом [79, 116].

Определение 2.2.19. Будем говорить, что идеал I порожден многочлена ми p1,..., pm, если многочлен q принадлежит I тогда и только тогда, ко гда он является полиномиальной комбинацией многочленов p1,..., pm, т.е.

q = p1 h1 +... + pm hm для некоторых h1,..., hm C[x, y]. Иными словами, иде ал I порожден p1,..., pm, если I = C[x, y]p1 +...+C[x, y]pm. Будем обозначать I = p1,..., pm.

Определение 2.2.20. Отношение, заданное на N0 называется допусти мым упорядочением, если • является линейным упорядочением множества N0, • Если (, ) (, ) и (k, l) N2, то ( + k, + l) ( + k, + l), • Если (, ) = (0, 0), то (0, 0) (, ).

Если задано упорядочение, то для каждого многочлена определен стар ший член LT(p).

Предложение 2.2.9 (О делении с остатком, [26, Гл. 2,§3, Т. 3]) Пусть задан набор p1,..., pm C[x, y], LT (pk ) = xk y k. Тогда для любого p C[x, y] су ществуют такие многочлены h1,..., hm, r C[x, y], что p = p1 h1 +... pm hm + r, a(,) x y, а и r(x, y) = (,)A A = N2 \ ((N2 + (1, 1 ))... (N2 + (m, m ))), (2.2.11) 0 0 т.е. ни один моном r(x, y) не делится ни на один старший член pk.

Многочлен r называется остатком от деления.

Заметим, что остаток от деления определен не однозначно.

Определение 2.2.21. ([26, Гл. 2, §5]) Набор p1,..., pm I называется ба зисом Гребнера идеала I относительно упорядочения, если старший член любого p I делится на какой-то из старших членов pi. При этом I = p1,..., pm.

Замечание 2.2.10. Базис Гребнера не единственен, но для базиса Гребнера множество (2.2.11) определено однозначно.

Предложение 2.2.10 ([36, Теорема 26.2]) Набор p1,..., pm I является ба зисом Гребнера, если для любого многочлена p остаток от деления его на p1,..., pm равен нулю тогда и только тогда, когда p I.

Замечание 2.2.11. ([26, Гл. 5, §3, Предл. 1]) Для любого нульмерного идеала I и любого упорядочения если A есть множество, определенное в (2.2.11), то {x y }(,)A является базисом факторалгебры R(I).

Предложение 2.2.11 ([36, Теорема 26.4]) Остаток от деления любого мно гочлена из C[x, y] на базис Гребнера для фиксированного упорядочения опре делен однозначно.

Предложение 2.2.12 ([116, Th. 8.30]) Для любого нульмерного идеала и лю бого упорядочения существует базис Гребнера, являющийся граничным для множества (2.2.11).

Глава Результаты для одномерного случая 3.1. Систематизация типов рядов конечного ранга В этом разделе на основе теории ганкелевых матриц, изложенной в разде ле 2.1, систематизируются и уточняются известные результаты и соотношения из теории метода АСС [66].

Сначала формально изучается связь L-продолжимых рядов с бесконечны ми рядами (например, в [66] этот вопрос освещен недостаточно). Затем уста навливаются соотношения между продолжимыми рядами и множеством ЛРФ, которым они удовлетворяют. На основе этих результатов характеризуются ре версивные ряды. И наконец, уточняется результат [47] о связи рядов конечного ранга с реверсивными рядами.

3.1.1. Продолжимые ряды и бесконечные ряды Следствие 2.1.2 показывает, что свойство L-продолжимости является свой ством ряда (а не L), и определяется поведением ранга при расширении. В связи с этим разумно ввести следующее определение Определение 3.1.1. Ряд FN ранга d называется • продолжимым (единственным образом), если существует единственное (), такое что d = rank FN = rank FN +1, при этом ряд L-продолжим для любых d L N d + 1;

• непродолжимым (никаким образом), если ни для какого ранг не со храняется, т.е. ряд не допускает L-продолжение ни для какого L.

По предложению 2.1.7, мы получаем однозначную классификацию рядов.

Следствие 3.1.1. Ряд FN либо является рядом полного ранга, либо продол жимым (d N/2, pd = 0), либо непродолжимым (d N/2, pd = 0).

В предложениях 2.1.7 и следствии 2.1.3 показано, как изменяется принадлеж ность ряда к этим классам при расширении и сокращении. Далее мы устано вим взаимнооднозначное соответствие между бесконечными рядами конечно разностной размерности и продолжимыми рядами. Нам потребуется следую щее утверждение о рангах бесконечных ганкелевых матриц, которое можно найти также в Предложение 3.1.1 ([12, Гл. XVI, §10]) Пусть дан ряд F = (f0, f1,...)T.

Рассмотрим бесконечную ганкелеву матрицу f f f2...

0 1 f f......

1 2 X f 2.........

..........

.

.

1. Рекуррентный ранг последовательности равен рангу X rrank F = rank X, определяемому как число линейно независимых строк (столбцов) бес конечной матрицы.

2. Если fdim0 F = d, то det X(d) F2d1 = 0, где FN = (f0,..., fN 1 )T.

Покажем, что любой ряд, удовлетворяющий ЛРФ, продолжим.

Предложение 3.1.2. Пусть rrank(F ) = d + и N 2d.

1. Конечный ряд FN имеет ранг d.

2. Ряд является продолжимым и характеристическим вектором для ря да FN является вектор P = (p0,..., pd )T, составленный из коэффици ентов минимального многочлена P (z) ряда F.

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

Ранг матрицы X(d+1) не меньше d по второму пункту предложения 3.1.1. Сле довательно, ранг ряда равен d, так как строки связаны линейным соотноше нием (1.4.9), которое соответствует минимальному многочлену P (z).

Замечание 3.1.1. Очевидно, что FN удовлетворяет ЛРФ 1.4.1 тогда и только тогда, когда вектор (a0,..., a1, 1) принадлежит левому ядру R(+1).

Лемма 3.1.1. 1. Продолжимый ряд FN с характеристическим вектором P удовлетворяет всем ЛРФ порядка N d (1.4.1), характеристиче ский многочлен (1.4.3) которых имеет вид A(z) = P (z)Q(z).

2. Продолжимый ряд FN ранга d не удовлетворяет ни одной ЛРФ порядка d.

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

1. Пункт 1 следует из замечаний 2.1.3 и 3.1.1.

2. Пусть это не так, тогда по замечанию 3.1.1 левое ядро R(+1) не пусто, что приводит к противоречию, так как + 1 d.

Следствие 3.1.2. Любой продолжимый ряд FN c характеристическим век тором P = (p0,..., pd1, 1)T можно продолжить единственным образом до бесконечного ряда F, минимальным многочленом которого будет P (z).

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

Применяя предложение 2.1.7 последовательно и продолжая ряд с сохранением ранга, можно единственным образом продолжить FN до бесконечного ряда F = (f0, f1,...), причем весь ряд F удовлетворяет ЛРФ (1.4.1). F не может удовлетворять ЛРФ меньшего порядка, так как иначе ей бы удовлетворял ряд FN, что невозможно по лемме 3.1.1.

Заметим, что соответствие между продолжимыми рядами и бесконечны ми рядами также затронуто в [41].

3.1.2. Продолжимость и линейные рекуррентные формулы Для начала дадим более конструктивное условие продолжимости.

Предложение 3.1.3. Пусть ряд FN имеет ранг d. Следующие условия эк вивалентны 1. ряд удовлетворяет некоторой ЛРФ (1.4.1) с N/2, 2. ряд продолжим.

При этом характеристический многочлен A(z) этой ЛРФ обязан делиться на производящий многочлен P (z) характеристического вектора P.

К тому же, продолжение 0 можно получить по той же ЛРФ, т.е fN = f(N )+ можно получить из равенства (1.4.1), положив n = N d0, т.е. 0 = fN.

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

2. 1. Следует из леммы 3.1.1.

1. 2. Так как N/2 и R(+1) не пусто и rank FN N/2. Таким образом, (a0,..., a1, 1)T = P(+1) H для некоторого H = (h0,..., hr )T, а значит 1 = pd · hr и pd = 0. При этом получаем, что A(z) = P (z)H(z) по замечанию 2.1.3.

Так как по предложению 2.1.7 характеристический вектор при продолже ( ) нии сохраняется, по лемме 3.1.1 имеем, что ряд FN +1 удовлетворяет любой ЛРФ с характеристическим многочленом вида B(z) = P (z)Q(z), т.е. ЛРФ (1.4.1) в частности.

Заметим, что из доказательства следует, что d, поэтому продолжи мость ряда эквивалентна L-продолжимости ряда для некоторого L, такого что L N + 1, а это условие на L можно заменить на условие min(L 1, K), где K = N L + 1, что автоматически включает условие N/2.

Таким образом, мы сразу же получаем следствие, которое является уси лением [66, Th. 5.4].

Следствие 3.1.3. Ряд FN L-продолжим тогда и только тогда, когда суще ствует min(L 1, K), такое что ряд удовлетворяет ЛРФ порядка.

Заметим, что это утверждение является конструктивным способом продолже ния в ситуации, когда характеристический вектор P ряда FN не известен.

В дополнение к определению 1.4.2, будем полагать rrank FN = N, если ряд не удовлетворяет никакой ЛРФ. Очевидным следствием 3.1.3 является следующее утверждение.

Следствие 3.1.4. Ряд продолжим тогда и только тогда, когда rrank FN N/2. При этом rrank FN = rank FN.

Отметим, что rrank FN N/2 тогда и только тогда, когда ряд непродол жим или полного ранга. C помощью второго характеристического вектора мы можем точно определить взаимосвязь ранга и рекуррентного ранга. Для этого докажем простую лемму.

Лемма 3.1.2. Пусть P Kd+1 и Q KN d+2 первый и второй характе ристические векторы некоторого ряда FN. Если pd+1 = 0, то qN d+2 = 0, и наоборот. То же верно для p0 и q0.

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

Пусть pd+1 = qN d+2 = 0. Тогда матрица из (2.1.8) имеет последнюю нулевую строку, а значит вырождена, что приводит к противоречию.

Предложение 3.1.4. Если ряд полного ранга или непродолжим, то rrank F = N rank F + 1 N/2.

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

По следствию 3.1.4 имеем rrank F N/2. Если ряд ранга d N/2, то pd = 0 и для d L N d + 1 по предложению 2.1.2 никакой вектор вида (a0,..., aL1, 1)T не принадлежит R(L), а значит, по замечанию 3.1.1 rrank F N d + 1 (что верно и в случае полного ранга).

Для d = 1 утверждение тривиально. Если d 1, то по лемме 3.1. qN d+1 = 0 и из вектора Q по лемме 3.1.1 можно образовать искомую ЛРФ.

Замечание 3.1.2. В случае rrank F N/2, аналогично бесконечным рядам, многочлен P (z) будем называть минимальным многочленом ряда. Его корни будем называть корнями ряда.

3.1.3. Реверсивные ряды. Характеризация В дополнение к определению 1.4.2, будем полагать fdim FN = N, если для ряда не существует реверсивной ЛРФ. Очевидным следствием следствия 3.1. является следующее утверждение.

Следствие 3.1.5. fdim FN N/2 тогда и только тогда, когда ряд про должим и p0 = 0 (или, что то же самое, p0 = 0, pd = 0). При этом fdim FN = rank FN.

В таком случае по следствию 3.1.2 имеется бесконечное особое продолже ние до ряда той же конечно-разностной размерности.

Следствие 3.1.6. Ряд FN конечно-разностной размерности fdim FN N/ имеет единственное представление вида (1.4.10), c d N/2. Это представ ление определяется корнями ряда (корнями его минимального многочлена) Определение 3.1.2. Ряд с fdim FN N/2 будем называть рядом регулярной конечно-разностной размерности.

Дадим дополнительную характеризацию рядам регулярной конечно-раз ностной размерности. Нам потребуется понятие L-продолжения назад.

Определение 3.1.3. РядFN допускаетL-продолжение назад (является L-про должимым назад ), если существует единственный C, такой что L(L) (FN ) = L(L) (, f0,..., fN 1 ).

Очевидно, что L-продолжимость назад эквивалентна L-продолжимости впе def ред перевернутого ряда FN = (fN 1,..., f0 ). Аналогично определению 3.1. можно ввести определения продолжимости и непродолжимости ряда назад.

Лемма 3.1.3. Если P является характеристическим вектором FN, то P = (pd,..., p0 )T.

Предложение 3.1.5. Ряд FN либо является рядом полного ранга, либо про должимым назад (если p0 = 0), либо непродолжимым назад (если p0 = 0).

Очевидна также следующая характеризация рядов регулярной конечно разностной размерности.

Предложение 3.1.6. Ряд FN L-продолжим назад и вперед тогда и только тогда, когда он имеет регулярную конечно-разностную размерность.

В завершение подраздела, мы полностью установим связи между рангом и разностной размерностью аналогично предложению 3.1.4.

Предложение 3.1.7. Если ряд имеет полный ранг, или он непродолжим вперед или назад, то fdim F = N rank F + 1.

Пусть rank F N/2. Аналогично предложению 3.1.4 имеем fdim F r = N d + 1 N/2 по предложению 2.1.2 и замечанию 3.1.1.

Если rank F = 1, то утверждение тривиально. Иначе, как и в предложе нии 3.1.4 покажем, что второй характеристический вектор Q дает искомую ЛРФ. Рассмотрим случай pd = 0. По лемме 3.1.2 qr = 0. Если к тому же p0 = 0, то q0 = 0 и мы берем Q = Q. Если pd = 0, то Q () = Q() + P () тоже является производящим многочленом второго характеристического век тора по предложению 2.1.3. В результате, q0 = 0, qr = 0. Так как Q Lr+1, мы получаем, что коэффициенты qr q (3.1.1) (,..., ) qr qr дают ЛРФ, которая управляет FN и последний коэффициент которой не равен нулю. В случае p0 = 0 и pd = 0 мы имеем q0 = 0 и, следовательно, можно полу rd чить ЛРФ вида (3.1.1), полагая Q = Q+IN d+2 P. Таким образом, fdim F = r.

Пусть d = rank F = (N + 1)/2. Если p0, pd = 0, то P дает ЛРФ d pk fd+n = fk+n.

pd k= Если p0 = pd = 0, то Q дает ЛРФ по лемме 3.1.2. Рассмотрим случай p0 = 0, pd = 0. По лемме 3.1.2 q0 = 0. Мы может выбрать R, такое что pd +qd = 0. Следовательно, Q = P + Q дает необходимую ЛРФ.

Следствие 3.1.7. Любой конечный ряд ранга d 1 удовлетворяет некото рому конечно-разностному уравнению.

3.1.4. Теорема Бухштабера. Базис траекторного пространства Здесь мы покажем, как можно улучшить теорему 1.4.1.

Теорема 3.1.1. Пусть 0 rank FN = d N/2. Существуют неотрица тельные числа,, +, такие что rank F = + + + и fdim(f,..., fN 1+ ) =.

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

Пусть P = (p0,..., pd )T характеристический вектор FN и он имеет вид P = (0,..., 0, v0,..., v, 0,..., 0)T, (3.1.2) + v0, v = 0, иными словами def def def = min{k : pk = 0}, + = min{k : pdk = 0}, = d +, (3.1.3) def где vi = pi.

Пусть G = GM = (f,..., fN 1+ ), где M = N +. Тогда по (3.1.2) мы получаем V = (v0,..., v )T R(+1) (G).

Если = 0, то G = 0 и fdim G = 0. Если 0, достаточно показать, что характеристический вектор G. Пусть это не так, тогда так как M/2, V существует H = (h0,..., h )T, 0, такой что I0 H,..., I H R(+1) (G).

Тогда для H1 = (0,..., 0, h0,..., h, 0,..., 0)T + мы имеем I0 H1,..., I H1 R(d+1) (F ) и получаем противоречие с (3.1.2).

Теорема 3.1.1 говорит о том, что мы можем отрезать не более rank F значений из начала и из конца ряда, чтобы получить ряд регулярной ко нечно-разностной размерности. Отметим, что и + могут быть рассмот рены по отдельности. Число +, например, это такое минимальное l, что ряд FN l = (f0,..., fN l1 )T продолжим вперед.

Далее нам также потребуется представление базиса для траекторного про странства.

Предложение 3.1.8 ([74, Th.8.1]) Пусть FN ряд ранга d N/2, с харак теристическим вектором P, причем, и + определены в (3.1.3). Пусть пары всех ненулевых корней P (z) с кратностями (оче (1, 1 ),..., (m, m ) видно, 1 +... + m = ).

Если размер окна L удовлетворяет d L N d + 1, то базисом пространства R(L) является e 1,..., e, 0 (1 ),..., 1 1 (1 ), L L.

. (3.1.4).

0 (m ),..., m 1 (m ), L L eL+ +1,..., eL, где k k () = (1,, 2,..., L1 )T = L k (3.1.5) (0,..., 0, k!,..., (k+j)! j,..., (Lk1)! Lk1 )T, (L1)!

= j!

k стандартный базисный вектор в CL.

а ek Очевидными следствиями предложения 3.1.8 являются следующие утвер ждения.

Следствие 3.1.8 ([66, §5.3]) Если FN допускает L-продолжение, то eL / L(L) (FN ).

Предложение 3.1.9 ([66, Th. 5.4]) Пусть L N/2. Если eL L(L) (FN ), то / FN является L-продолжимым.

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

Достаточно заметить, что если eL L(L) (FN ), то ряд не является рядом пол / ного ранга, а значит предложение 3.1.8 применимо.

Легко можно построить аналоги следствий 3.1.8 и 3.1.9 для продолжимо сти назад, заменив eL на e1.

3.2. Разделимость Основным результатом этого раздела является необходимое и достаточное условие разделимости рядов регулярной конечно-разностной размерности, ос нованное на характеристических многочленах рядов и их корнях. В частности, это условие позволяет перечислить все возможные случаи слабой разделимо сти и рассмотреть все стандартные примеры (см. [66, §6.1]) c единой точки зрения. Новая теория излагается для односторонней разделимости, результа ты об обычной разделимости являются ее следствиями.

3.2.1. Критерий односторонней разделимости (1) (2) Теорема 3.2.1. Пусть FN ненулевой ряд, а FN ряд регулярной ко нечно-разностной размерности d с минимальным многочленомP (2) (z). Пусть L удовлетворяет d L N d + 1 и {U1,..., Ur } является произвольным (1) базисом L(L) (FN ).

(1) (2) Ряды FN и FN L-полуразделимы тогда и только тогда, когда P (2) (z) является общим делителем многочленов Uj (z), 1 j d (другими словами, (2) все корни ряда FN должны быть общими корнями многочленов Uj (z), по крайней мере, с соответствующими кратностями).

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

(1) (2) (1) Заметим, что L(L) (FN ) L(L) (FN ) тогда и только тогда, когда L(L) (FN ) (L) (2) L (FN ). По замечанию 2.1.1 данное включение подпространств эквивалент (2) (2) но Uj R(L) (FN ) для всех 1 j r. По замечанию 2.1.3, Uj R(L) (FN ) тогда и только тогда, когда Uj (z) = P (2) (z)Qj (z), где P (2) (z) это характе (2) ристический многочлен FN, а Qi (z) ненулевой многочлен. Предложение доказано.

Замечание 3.2.1. Утверждение теоремы 3.2.1 верно даже для 1 L d, и значит верно для важного случая L N/2. Действительно, если L d, то по (L) (2) предложению 2.1.1 dim(L (FN )) = L L = 0 и только нулевой ряд может (2) быть отделим от FN. С другой стороны, для таких L любой многочлен Ui (z) имеет степень меньше d и значит не может делиться на P (2) (z).

Теорема 3.2.1 с замечанием 3.2.1 дают способ нахождения всех рядов конечно (1) (2) разностной размерности FN, которые отделимы от данного ряда FN.

(1) ненулевой ряд и {U1,..., Ur } является бази Теорема 3.2.2. Пусть FN (1) сом его траекторного пространства L(L) (FN ). Пусть также µ1,..., µl все ненулевые общие корни U1 (z),..., Ur (z) и d1,..., dl это их общие крат ности, т.е. dk это минимальная кратность корня µk среди многочленов Ui (z). Тогда все ряды регулярной конечно-разностной размерности не более (1) N L + 1, L-полуотделимые от FN, имеют вид l (2) Qk (n)µn, (3.2.1) fn = k k= где Qk (n) возможно нулевые многочлены степени менее dk.

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

Вдобавок к корням µk, у многочленов Ui (z) может быть общий корень µ0 = кратности d0 N0. Тогда многочлен R(z) = z d0 (z µ1 )d1 1... (z µl )dl является наибольшим общим делителем всех Ui (z). Таким образом, по заме (1) (2) чанию 3.2.1 FN и FN L-полуразделимы тогда и только тогда, когда характе ристический многочлен P (2) (z) является делителем R(z). По следствию 3.1. ряды, имеющие это свойство, являются в точности рядами вида (3.2.1).

(2) Замечание 3.2.2. Для L K условие fdim FN N L + 1 выполняется автоматически и теорема 3.2.2 позволяет найти все ряды регулярной конечно разностной размерности, L-полуотделимые от данного.

Замечание 3.2.3. Утверждение теоремы 3.2.2 не зависит от выбора базиса.

Действительно, если µ является общим корнем для многочленов {U1 (z),..., Ur (z)}, то µ является корнем любой линейной комбинации Uj (z).

(1) Пусть FN ряд регулярной конечно-разностной размерности вида (1.4.10).

(1) Тогда базис L(L) (FN ) состоит из векторов l (k ) из предложения 3.1.8, L k m, 0 l k, и мы можем использовать теорему 3.2.2 для определения ря (1) дов конечно-разностной размерности, отделимых от FN. Более того, условие разделимости может быть проверено по отдельности для каждого слагаемого в представлении (1.4.10).

(1) (2) Замечание 3.2.4. Для ряда FN вида (1.4.10) ряд FN регулярной конечно (1) разностной размерности не более N L + 1 отделим от FN тогда и только тогда, когда он L-полуотделим от каждого слагаемого Pk (n)n в представле k нии (1.4.10).

Действительно, базисом траекторного пространства слагаемого Pk (n)n явля k ется набор векторов i (k ), 0 i k, и, следовательно, условие на корни L (2) (1) ряда FN для отделимости от FN совпадает с одновременным выполнением (1) условий отделимости от каждого слагаемого FN.

3.2.2. Полуотделимость от рядов регулярной конечно-разностной размерности По замечанию 3.2.4, рассмотрение разделимости произвольных рядов ре гулярной конечно-разностной размерности можно свести к нахождению рядов, отделимых от данного ряда вида P1 (n)n, т.е. рядов с единственным, возмож но кратным, корнем ряда. Далее мы рассмотрим этот случай постепенно в отдельных примерах. В этом подразделе мы, как и раньше, предполагаем, что L N/2.

(1) Пример 3.2.1. [Полуотделимость от константы] Пусть FN c = 0. Тогда (1) пространство L(L) (FN ) является линейной оболочкой одного вектора 1L = (1,..., 1)T CL. Рассмотрим его производящий многочлен zL L (3.2.2) W1 (z) = z +... + 1 =.

z Все корни µk многочлена W1 (z) являются простыми;

это корни L-й степени из единицы, исключая 1:

2ik µk = exp, 0 k L.

L На рис. 3.1 корни µk обозначены точками.

Рис. 3.1. Корни ряда, отделимого от константы.

(1) По теореме 3.2.2 все L-полуотделимые от FN ряды имеют вид L1 n 2ik (2) (3.2.3) fn = ck exp.

L k= (2) Отметим, что FN имеет период L и удовлетворяет условию L (2) (3.2.4) fn = n= тогда и только тогда, когда он имеет представление (3.2.3) (см. [66, §6.1]). В вещественнозначном случае от константы L-полуотделимы слева гармоники, имеющие один из периодов L.

(1) Пример 3.2.2. [Полуотделимость от комплексной экспоненты] Пусть fn = (1) n. Тогда базисом L(L) (FN ) является набор из одного вектора (1,,..., L1 )T, (2) и все корни ряда FN должны быть корнями многочлена L1 L W (z) = z +... + z + 1.

Сделав замену переменных z = x/, мы приходим к уравнению W1 (x) = 0, где W1 (x) определен в (3.2.2). Следовательно, все корни W (z) тоже просты и имеют вид exp (2ik/L) 2ik µk = = 2 exp, || L (2) где 0 k L. Следовательно, ряд FN имеет вид L1 L1 n exp (2ik/L) (2) c k µn fn = = ck.

k k=1 k= Это представление становится более иллюстративным, если записать корни µk в показательной форме. Если = exp(2i), 0, [0;

1), то k µk = 1 exp 2i +.

L Корни µk изображены на рис. 3.2.

(1) Выпишем отдельно результаты для случая Im = 0, в котором ряд FN является вещественным экспоненциальным. Если = Re 0 (т.е. = 0), (2) def (1) (3) (3) = n fn, где fn = n L-полуотделим от всех рядов вида fn то fn име ет период L и нулевую сумму (в смысле равенства (3.2.4)). Если 0 (т.е.

Рис. 3.2. Корни ряда, отделимого от комплексной экспоненты.

(1) = 0.5), то fn = ()n является также экспоненциально модулированным косинусом с периодом 2 (экспоненциально модулированным пилообразным ря дом) и множество всех L-полуотделимых рядов может быть описано похожим способом.

Рассмотрим также важный случай суммы экспонент с сопряженными по казателями, которые соответствуют вещественным экспоненциально модули рованным косинусам с периодами, отличными от 2. Этот случай имеет неко торые особенности.

Пример 3.2.3. [Полуотделимость от суммы сопряженных экспонент] Пусть n (1) fn = cn + d, Im = 0. Выберем Im 0, не умаляя общность. Тогда по (2) примеру 3.2.2 и замечанию 3.2.4 любой корень µ ряда FN должен удовлетво рять 2ik 2il µ = exp = exp, L L где 0 k, l L. Таким образом, 2im = exp, L где m Z, т.е. должно обязательно иметь вид m (3.2.5) = exp 2i, 0, 2L (1) (2) чтобы ряд FN мог быть отделим от FN. Так как Im 0, мы можем выбрать (2) m удовлетворяющее 0 m L. Тогда корни ряда FN имеют вид (2k m) µk = 1 exp 2i, 2L где 0 k L, k = m, и ряд имеет представление n (2k m) n (2) fn = ck exp 2i.

2L k{1,...,L1}\{m} Заметим, что в противоположность примеру 3.2.2 возникает естественное (1) ограничение (3.2.5) на возможные корни ряда FN. В вещественнозначном слу чае если два экспоненциально модулированных косинуса L-полуразделимы, то эти косинусы должны иметь целые периоды, кратные 2L. Действительно, ес n (1) ли fn = n cos( + 2n) = cn + d, где R, 0 и (0, 0.5), то (1) должно удовлетворять = m/(2L), 0 m L, чтобы ряд FN был отделим от какого-нибудь ряда. Таким образом, все вещественнозначные временные (2) (1) ряды FN, отделимые от FN, должны иметь представление (2k + ) ck n cos k + (2) fn = n, 2L k{1...,L}\{k0 } m где k0 =, 0, m четно, = 1, m нечетно, c k и k произвольные вещественные константы. Это представление соот ветствует рассуждениям из [66, §6.1], однако приведенное в данной работе обоснование представляется более показательным.

Заметим, что случаи нечетных и четных m различны. Действительно, ряд (2) n fn должен иметь период 2L;

однако, для нечетных m он обязательно имеет период L. Этот эффект также был замечен (для косинусоидального ряда) в [66, §6.1], однако в данной работе его природа более ясна. Примеры располо (2) жения корней ряда FN для этих двух случаев и = || = 1 изображены на рис. 3.3.

Рис. 3.3. Корни ряда (маленькие точки), отделимого от суммы сопряженных экспонент (крупные точки), = 1.

Наконец, покажем, что ряд с кратным корнем не отделим ни от какого ряда.

Пример 3.2.4. [Полуотделимость от экспоненциально модулированного по (1) линома] Пусть fn = P1 (n)n, = 0, где P1 (n) многочлен ненулевой степе (1) ни. По предложению 3.1.8 базис FN включает в себя векторы W = 0 () = (1,,..., L1 )T, L 1 () = (0, 1, 2,..., (L 1)L2 )T.

L Заметим, что в этом базисе мы можем заменить 1 () на L (1) W = 0 () + 1 () = (1, 2, 32,..., LL1 )T.

L L (2) По теореме 3.2.2, все корни ряда FN должны быть по крайней мере общими (1) корнями производящих многочленов W (z) и W (z). Делая замену перемен ных z = x/ как в примере 3.2.2, мы приходим к уравнению (1) W1 (x) = W1 (x) = 0, (1) где W1 (x) определен (3.2.2) и W1 (x) = LxL1 +... + 3x2 + 2x + 1. Все корни многочлен W1 (x) лежат на единичной окружности, в то время как коэффи (1) циенты W1 (x) строго убывают, а значит, по теореме Энестрёма-Какейа [71], (1) корни W1 (x) лежат строго внутри единичного круга и, следовательно, мно (1) гочлены W1 (x) и W1 (x) не имеют общих корней. Таким образом, никакой (1) ряд регулярной конечно-разностной размерности N/2 не отделим от FN.

3.2.3. Перечисление случаев левой отделимости для L K Для начала перечислим явно все случаи левой разделимости между нену левыми рядами регулярной конечно-разностной размерности в случае L K.


По примеру 3.2.4 только ряды с простыми корнями ряда могут быть полураз делимы. Рассмотрим два ряда d (1) ak n, fn = k k= (3.2.6) d (2) b l µn, fn = l j= такие что ak, bl = 0 и k = s, µl = µj для k = s, l = j. Тогда, по заме чанию 3.2.4 эти ряды L-полуразделимы тогда и только тогда, когда каждое слагаемое ak n отделимо от каждого bl µn. Объединяя сказанное выше и ис k l пользуя пример 3.2.2, мы получаем следующую теорему.

(1) Теорема 3.2.3. Два ряда регулярной конечно-разностной размерности FN (2) и FN L-полуразделимы для L N/2 тогда и только тогда, когда они имеют вид (3.2.6) и существуют вещественные числа 0 и [0;

1/L), такие что mk k = exp 2i +, L hl µl = 1 exp 2i +, L где 0 mk, hl L различные натуральные числа.

Как и в примере 3.2.3, теорему 3.2.3 можно специализировать для веществен ных рядов. В этом случае снова появляется ограничение на (либо = 0, либо = 1/2L).

Рассмотрим полуразделимость непродолжимых вперед или назад рядов.

Отметим, что здесь и далее мы не предполагаем L N/2.

(1) (2) Теорема 3.2.4. Пусть FN и FN два ненулевых ряда, 1 L N, и eL (1) L(L) (FN ). Эти ряды полуразделимы тогда и только тогда, когда они явля ются “граничными” рядами, а именно, N d (1) (1) (1) FN =(0,.................., 0, fN d,..., fN 1 ), (3.2.7) (2) (2) (2) FN =(f0,..., fLd1, 0,.................., 0), N (Ld) где 1 d L.

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

(1) (L,2) (2) Пусть eL L(L) (FN ). Тогда столбцы Xi матрицы X(L) (FN ) удовлетво (L,2) (L,2) ряют Xi eL, 1 i K. Таким образом, последняя компонента Xi (2) (2) (2) каждого вектор равна нулю и мы имеем FN = (f0,..., fL2, 0,..., 0).

K (1) (2) (2) Рассмотрим перевернутые ряды FN и FN. Если FN ненулевой, мы (2) имеем eL L(L) (FN ) и, применяя первую часть доказательства, получаем (1) (1) (1) FN = (fN 1,..., fK, 0,..., 0). Доказательство завершается замечанием, что K (2) (1) сумма длин ненулевых частей в начале FN и в конце FN не может превосхо дить L.

Из предложения 3.1.9 и теоремы 3.2.4 мы получаем следующий результат.

(1) (2) два ненулевых ряда, L N/2, причем Следствие 3.2.1. Пусть FN и FN (1) (2) FN непродолжим вперед или FN непродолжим назад. Ряды L-полураздели мы тогда и только тогда, когда они имеют вид (3.2.7).

Замечание 3.2.5. По предложению 3.1.6 полная классификация случаев ле вой L-разделимости для L N/2 предоставляется теоремой 3.2.3 и следстви ем 3.2.1.

3.2.4. Двусторонняя разделимость Завершим этот раздел рассмотрением обычной, двусторонней разделимо сти. Два ряда называются слабо (двустороне) разделимыми, если они L- и K-полуразделимы [66, Ch. 6].

Теорема 3.2.5. Следствие 3.2.1 останется верным, если мы заменим ле вую разделимость на двустороннюю, а L на min(L, K).

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

Не умаляя общности, пусть L N/2. Следствие 3.2.1 говорит, что необходи мость в теореме 3.2.4 имеет место. Достаточность в теореме 3.2.4 также имеет место, так как все ряды вида (3.2.7) с L = L0 имеют такой же вид и для L L0.

Таким образом, нам опять достаточно рассмотреть случаи разделимости (1) (2) рядов регулярной конечно-разностной размерности. Пусть FN и FN два (1) (2) = d(1) и fdim FN = d(2), соответственно. Не умаляя таких ряда fdim FN общности, можно считать, что L K. Эти ряды могут быть разделимыми только если их траекторные матрицы имеют неполный ранг, следовательно, по предложению 3.1.2 длина окна L удовлетворяет неравенству max(d(1), d(2) ) L N max(d(1), d(2) ) + 1. Легко увидеть, что теорема 3.2.2 и замечание 3.2. описывают все ряды, L- и K- полуотделимые от данного.

Теорема 3.2.6. Пусть L = gcd(L, K). Все примеры из раздела 3.2.2, а так же теорема 3.2.3 остаются верными, если мы заменим левую разделимость на двустороннюю и L на L.

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

Достаточно доказать утверждение только для примера 3.2.1, так как осталь ные примеры и теорема 3.2.3 основаны на нем В этом случае все корни µk из примера 3.2.1 должны быть общими корнями W1 (z) (определенного в (3.2.2)) и многочлена z K1 +... + 1 = (z K 1)/(z 1). Очевидно, это равносильно представимости µk в виде 2ik 0 k L, µk = exp, L что и требовалось доказать.

3.3. ЛРФ прогноза и ее побочные корни В данном разделе систематизируются известные результаты о поведении побочных корней ЛРФ, используемой при прогнозировании в методе АСС (см. [66, §5.2]), с помощью теории ортогональных многочленов на единичной окружности. Также используются современные результаты из теории ортого нальных многочленов, которые позволяют найти сильную асимптотику побоч ных корней ЛРФ прогноза в методе АСС.

3.3.1. Характеристический полином ЛРФ прогноза Пусть ряд FN, fdim FN = d, характеристический полиномом P (z). Пусть также длина окна L удовлетворяет d L N d + 1 и = L(L) (FN ), т.е.

рассматривается случай идеальной отделимости. Тогда R = R проектор на левое ядро R = R = R(L) (2.1.1). Рассмотрим вектор B = R eL. По предло жению 1.5.3 A = cB. Как и ранее, будем обозначать производящие полиномы векторов A и B как A(z) и B(z), согласно обозначения в разделе 3.2.1. По замечанию 2.1.3 мы получаем (3.3.1) A(z)/c = B(z) = P (z)Hn (z), (n) (n) (n) где Hn (z) = hn z n +... + h1 z + h0 является многочленом степени n + 1, def n = L d 1. Все n корней многочлена Hn (z) являются в точности побочны ми корнями A(z) с соответствующими кратностями. Далее мы будем изучать свойства многочленов Hn (z).

Предложение 3.3.1. Вектор (n) Hn = (h0,..., h(n) )T (3.3.2) n коэффициентов многочлена Hn (z) можно выразить как Hn = (P P)1 en+1, где матрица P = P(L) определена (2.1.5) и P обозначает эрмитово сопря жение P. Иными словами, Hn является единственным решением уравнения (3.3.3) Tn Hn = en+1, где def Tn = P P C(n+1)(n+1). (3.3.4) Доказательство.

По предложению 1.5.3 и следствию 2.1.1, B = P(L) Hn и Hn минимизирует невязку P(L) V eL среди всех векторов V CLd. Следовательно, Hn мо жет быть выражено как решение P(L) V eL в смысле наименьших квадратов:

Hn = (P P)1 P eL = (P P)1 en+1, (3.3.5) где последнее равенство выполняется, так как pd = 1.

Замечание 3.3.1. Проектор R может быть явно выражен через характери стический многочлен как R = P(P P)1 P.

По построению, матрица Tn, определенная в (3.3.4), является теплицевой эрмитовой матрицей Tn = (tij )n,n i,j= с коэффициентами dk pj pk+j, 0 k d, j= (3.3.6) tk = 0, k d, tk, k 0.

Отметим, что коэффициенты tk не зависят от n. Также отметим, что любая матрица Tn имеет не более 2d + 1 ненулевых диагоналей:

t... td 0...........

. Tn = td... t0... td.

............

... t td Нетрудно видеть, что коэффициенты tk совпадают с ковариационной функ цией процесса скользящего среднего с коэффициентами pk [3, Гл. 5]. Если мы перепишем уравнение (3.3.3) как (3.3.7) TGn = e1, (n) (n) где G = (hn,..., h0 )T, то мы получим в точности уравнение Юла–Уолкера для этого процесса.

3.3.2. Основные свойства ортогональных многочленов В этом подразделе мы применим теорию ортогональных многочленов на окружности и получим короткие доказательства для основных свойств побоч ных корней. Сначала перепишем уравнение (3.3.3) в терминах ортогональных d tk z k, где tk определены в (3.3.6). Легко видеть, многочленов. Пусть t(z) = k=d что t(z) = P (z)P (1/z) и соотношение t(z) = P (z)P (z) = |P (z)|2 0 (3.3.8) выполняется для всех z T1, где Tr = {z C : |z| = r} обозначает окруж ность в комплексной плоскости радиуса r.

Для неотрицательной функции w(z) L1 (T1 ) (т.е. функции, интегриру емой по Лебегу на контуре T1 ) можно определить скалярное произведение в пространстве комплексных многочленов как def (3.3.9) p(z), q(z) = p(z)q(z)w(z)d, w где z = ei. Функция w(z) называется весом. В частности, можно определить скалярное произведение ·, · t для веса t(z) из (3.3.8).

Предложение 3.3.2. Многочлены Hn (z), n 0, определенные в (3.3.1), об разуют систему ортогональных относительно ·, · многочленов.

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

Очевидно, что tkl = 1, z kl = zl, zk для любых k, l Z. Следовательно, t t мы можем переписать равенство (3.3.3) в виде 0, 0 k n, n (n) k Hn (z), z t = hl tkl = 1, k = n.

l= Легко увидеть, что Hn (z), Hm (z) t = 0 при m = n и 2 def Hn (z), Hn (z) t = h(n) = Hn (z) t= n (n) для любого n 0, где коэффициент hn не равен нулю, так как он является старшим коэффициентом многочлена.

Замечание 3.3.2. Пусть n (z), n 0 некоторая система многочленов сте пени n, которые ортогональны относительно некоторого веса w(z) (т.е. выпол няется n (z), m (z) = 0 для m = n и n (z) = 0 для всех n). Тогда мно w w гочлены n определены единственным образом с точностью до константных множителей. Этот факт следует из свойств стандартного процесса ортогона лизации последовательности {1, x, x2,...}, см. например [12, Ch. IX, §6].

Таким образом, предложение 3.3.2 является характеризацией Hn (z).

Замечание 3.3.3. Система n из замечания 3.3.2 является ортогональной и относительно веса w(z) для любого 0.

Наиболее известным свойством побочных корней является следующее: все побочные корни ЛРФ прогноза лежат внутри единичного круга. Этот резуль тат можно найти в [44, 83, 85], однако доказательства, как правило, довольно сложны. На языке ортогональных многочленов, напротив, существует корот кое доказательство (его также можно найти в [113, Ch. 1]).

Теорема 3.3.1. Пусть n (z) последовательность ортогональных много членов степени n относительно ·, · w. Тогда |z0 | 1 если n (z0 ) = 0, т.е.

все корни многочленов n лежат строго внутри единичного круга.

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

Пусть n имеет корень z0, тогда n (z) = Q(z)(z z0 ), где deg Q = n 1, и следовательно n, Q = 0. Тогда мы имеем w 2 Q(z) = zQ(z), zQ(z) = zQ(z) = w w w = |z0 |2 Q(z) 2 = Q(z)z0 + n (z) + n (z) w, w w где последнее равенство следует из ортогональности многочленов n. Перепи сав данное равенство, мы получаем (1 |z0 |2 ) Q(z) 2 0, откуда = n (z) w w следует утверждение теоремы.

Далее мы приводим простое доказательство еще одного известного ре зультата из [44] о соответствии лишних корней ЛРФ прогноза вперед и назад.


Пусть ряд FN продолжим вперед и назад, т.е. d является не только рекур рентным рангом, но и конечно-разностной размерностью ряда. В этом случае под ЛРФ прогноза назад мы подразумеваем ЛРФ прогноза для перевернуто го ряда FN (ср. определение 3.1.3);

ЛРФ прогноза вперед обозначает обычную ЛРФ прогноза.

Очевидно, что rank FN = rank FN. Также из предложения 2.1.2 легко видеть, что FN является рядом конечно-разностной размерности d с характе ристическим многочленом p1 P (z), где многочлен P (z) означает переверну тый многочлен pd + pd1 z +... + p0 z d. Корнями этого многочлена являются 1 с кратностями k (см. (1.4.5)). Для удобства для каждого многочлена k B(z) = br z r +... + b1 z + b0, где br = 0, введем обозначения def b0 z r +... + br1 z + br, (3.3.10) B(z) = def B (z) = B(z) = b0 z r +... + br1 z + br.

Тогда |P (z)|2 = |P (z)|2 = |P (z)|2, (3.3.11) |z| = 1.

Из данного соответствия легко следует следующий факт:

Предложение 3.3.3. Побочные корни ЛРФ прогноза вперед и назад сопря жены.

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

Функция u(z) = |p0 |2 |P (z)|2 является весом системы ортогональных много членов для перевернутого ряда FN. Тогда для любых многочленов Q(z) и S(z) мы имеем = |p0 |2 P (z), Q(z) t, Q(z), S(z) u что следует из (3.3.9). Следовательно, любой из ортогональных относитель но u(z) многочленов n (z) имеет корни, которые являются сопряженными к корням соответствующего многочлена Hn (z), что и требовалось доказать.

Заметим, что в некоторой литературе в определение ЛРФ прогноза на зад входит сопряжение [83], и предложение 3.3.3 формулируется как побочные корни ЛРФ прогноза назад и вперед совпадают.

3.3.3. Асимптотические свойства побочных корней В этом разделе мы приводим обзор новых результатов в теории ортого нальных многочленов и используем их для описания асимптотического пове дения побочных корней. Мы следуем, в основном, [96] and [95] и представляем все результаты в упрощенном виде, специализируя их для веса t(z), опреде ленного в (3.3.8).

Наряду с Tr, введем обозначения def Dr (a) = {z C : |z a| r}, def Dr = Dr (0), def Dc = {z C : |z| r}, r для любого r 0 и a C.

Рассмотрим характеристический многочлен P (z), определенный в (1.4.5) и набор ортогональных многочленов Hn (z), определенных в (3.3.1). Используя преобразование, подобное (3.3.11), мы можем перенести все корни многочле на внутрь замкнутого единичного круга Dc, не изменяя при этом вес t(z).

Рассмотрим следующий многочлен (z 1 )l.

(z k )k (3.3.12) C(z) = l k:|k |1 l:|l | Тогда |P (z)|2 = c|C(z)|2, (3.3.13) где c некоторая положительная константа. Тогда, по замечанию 3.3.3 веса t(z) = |P (z)|2 и u(z) = |C(z)|2 порождают одинаковые системы нормирован ных ортогональных многочленов Hn, причем все корни C(z) лежат внутри замкнутого единичного круга.

Заметим, что в представлении (3.3.12) пары корней P (z), связанные соот ношением k = 1 “склеиваются”. Для удобства будем рассматривать стан l дартное представление многочлена C(z):

C(z) = (z a1 )m1... (z as )ms, (3.3.14) где ak различны для всех 1 k s. Максимальный модуль = max1ks |ak | 1 будем называть критическим радиусом многочлена P (z), а окружность T критической окружностью. Пусть, более того, корни C(z) упорядочены так, что первые u корней лежат на критической окружности, а остальные строго внутри нее, т.е. |a1 | =... = |au | = и |ak | для k u. Будем называть a1,..., au ведущими корнями of C(z). Пусть также первые корней a1,..., a имеют наибольшую кратность M среди a1,..., au, т.е. ms = M для всех 1 s и mj M для j u.

Предложение 3.3.4 ([96, Prop. 1, Th. 3]) Пусть 1.

1. Для любого 0 существует N1 (), такое что все корни Hn (z) лежат в круге D+ для любого n N1.

2. Для любого 0 существует N2 (), такое что замкнутый круг Dc содержит не более 1 корней Hn (z) для каждого n N2.

Предложение 3.3.5 ([95, Cor. 1]) Если = 1, то для любого 0 суще ствует N2 (), такое что для всех n N2 замкнутый круг Dc содержит не более u 1 корней Hn (z).

Эти два предложения предполагают, что большинство корней равномер но стремится к критической окружности T (эти корни называются обычны ми корнями) и только ограниченное число корней остается строго внутри D (называемые ложными корнями). Ложные корни беспорядочно блуждают внутри D (при изменении n), но, грубо говоря, они асимптотически близки к нулям функций Gn, определенных как anM +d+1 C (ak ) k, 1, (z ak )C (M ) (ak ) Gn (z) = k=1 n+d+ u ak (1)k k (C )(k ) (ak ), = 1, (z ak )C (k ) (ak ) k= где f (m) обозначает m-ю производную функции f и C (z) определен в (3.3.11).

В [95, 96, 119] можно найти точные формулировки и более подробные результа ты о ложных корнях;

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

Теперь обратимся к поведению обычных побочных корней. Здесь приве ден лишь неформальный обзор результатов. Точные и математически строгие результаты можно найти в [96, Th. 4] and [95, Th. 5] (для случая 1 и = 1, соответственно).

• Асимптотическое поведение модулей обычных побочных корней имеет вид 1 + M log(n) + O, 1, n n (n) |zi | = 1 + log(n) + O 1, = 1.

n n • Для функции f определим Z (f ) = -окрестность множе a:f (a)=0 D (a) ства ее нулей. Обозначим также l k=1 D (ak ), 1, BC, = u D (a ), = 1.

k=1 k Тогда для достаточно больших n и малых лишних корней нет в области A,,n = {z : ||z| | } \ (BC, Z (Gn )).

(n) (n) связная подобласть A,,n и z1,..., zr(n) корни H n (z) в D, • Пусть D упорядоченные по величине своих аргументов. Тогда для любых k, l, таких что 1 k, (k + l) r(n) для всех достаточно больших n, мы имеем 2l (n) (n) arg(zk+l ) arg(zk ) = +O.

n n Эти результаты в слабом виде можно найти в [119]. Прокомментируем данные результаты.

• Обычные побочные корни асимптотически равноотстоящими по аргумен ту.

• Порядок сходимости обычных побочных корней к единичной окружно сти отличается для = 1 и 1. В последнем случае скорость сходи мости зависит от максимальной кратности M ведущих корней C(z).

• Для 1 только корни a1,..., a (т.е. ведущие корни максимальной кратности M ) сильно влияют на поведение побочных корней: они опре деляют число ложных побочных корней и их окрестности исключаются из A,,n ;

в случае = 1 все ведущие корни C(z) влияют на асимптоти ческое поведение побочных корней.

• В вещественнозначном случае почти каждый корень ряда имеет сопря женную пару (когда ряд является суммой модулированных гармоник).

Поэтому ведущих корней C(z) обычно несколько и велика вероятность появления ложных побочных корней.

Пример 3.3.1. [Обычные и ложные побочные корни] Рассмотрим сумму двух экспоненциально модулированных гармоник. Каждое слагаемое соответствует двум сопряженным корням, поэтому = u = 4 и M = 1. Корни ЛРФ прогноза изображены на рис. 3.4 (напомним, что L = n + d + 1).

L = 20 L = 1. 1. X X X X 0. 0. X X 1. 1. X X 1.0 0.0 1.0 1.0 0.0 1. L = 40 L = 1. 1. X X X X 0. 0. X X 1. 1. X X 1.0 0.0 1.0 1.0 0.0 1. Рис. 3.4. Главные (x) и побочные (o) корни, fn = 0.9n cos n + cos (2 sin(0.25)n) На рис. 3.4 видно, что ложные корни блуждают внутри критической окружности;

для некоторых L ложные корни исчезают. Коэффициент sin(0.25) выбран, чтобы обеспечить рациональную независимость ведущих корней от C(z). Если почти все корни ряда рационально зависимы (т.е. корни ряда в виде линейных комбинаций других корней ряда с рациональными коэффици ентами), то ложные корни перемещаются более регулярно, подробнее см. в [95, 96, 119].

3.3.4. Некоторые приложения и замечания Для начала продемонстрируем связь между асимптотической разделимо стью и поведением побочных корней. Мы покажем, что приближенная [66, Ch.

6] левая отделимость линейного ряда от косинуса неформально может быть объяснена условием точной отделимости, разработанном в разделе 3.2. Пусть def def (1) W (L,0) (z) = W1 (z) и W (L,1) (z) = W1 (z) многочлены из примера 3.2.4.

Корни W (L,0) всегда лежат на единичной окружности и расположены через равноотстоящие промежутки по аргументу (исключая 1). Можно показать [34], что W (L,1) (z) для L = 1, 2,... образуют систему ортогональных много членов относительно веса P (z) = |z 1|2 и по результатам раздела 3.3.3 корни W (L,1) (x) асимптотически распределены так же, как и корни W (L,0) (z). На рис. 3.5 изображены корни W (L,0) (x) и W (L,1) (x) для достаточно большого L.

Можно сказать, что это подтверждает асимптотическую отделимость перио L = 1. ******* ** ** ** * * * * * * * * * * * * 0. * * * * * * * * * * * * * * 0. * * * * * * * * * * * * 0. * * * * * * * * * * * * * * * * * 1. * ** ** ** ******* 1.0 0.5 0.0 0.5 1. Рис. 3.5. Корни W (L,0) (z) и W (L,1) (z).

дического ряда от линейной функции. То же самое может быть показано и для полиномиального ряда. Отметим, что это наблюдение не претендует на строгое утверждение. Современные результаты относительно приближенной разделимости получены в [101].

Рассмотрим, что происходит с кратностью в случае наличия шума. Рас смотрим случай экспоненциального ряда, модулированного квадратным мно гочленом. Корень ряда в этом случае один и имеет тройную кратность.

Как видно из рис. 1.3, при наличии шума кратный корень разделяется на три отдельных корня. Несмотря на это, побочные корни ведут себя как в слу чае кратного корня. Действительно, побочные корни в зашумленном случае близки к истинным. Вдобавок к этому, ложные корни не появляются внутри критической окружности.

3.4. Подсчет числа матриц данного ранга в конечном поле 3.4.1. Сведение задачи подсчета количества ганкелевых матриц к задаче подсчета рядов Пусть K = Fq. Рассмотрим задачу, вкоторой требуется найти число ган келевых матриц данного размера и данного ранга над Fq LK = #{X KLK : H ганкелева, r rank X = r}.

LK = KL.

В этом разделе мы будем рассматривать случай L K, так как r r Введем следующее обозначение для количества рядов длины N и ранга d.

hN = #{FN KN : rank(FN ) = d}.

d По предложению 2.1.1 hN = 0 только для d {0,..., (N + 1)/2}. К тому d же, так как общее число рядов длины N равно q N, верно соотношение (N +1)/ hN = q N. (3.4.1) d d= Предложение 3.4.1. Число ганкелевых L K матриц ранга r выражает сяследующим образом 0, L r, = hN, LK L r, r r N L1 N q hd, L = r, d= где N = L + K 1.

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

Для случая L r утверждение очевидно. Пусть L r. По предложению 2.1. ранг r ганкелевой матрицы X может быть меньше L (N + 1)/2 тогда и только тогда, когда он равен рангу порождающего ее ряда FN, т.е. количество таких ганкелевых матриц равно количеству временных рядов ранга r.

В случае L = r число матриц можно найти из соотношения L LK = qN.

r r= 3.4.2. Независимость числа рядов данного ранга от длины ряда Здесь мы покажем, что число рядов hN не зависит от N, что упростит d дальнейшие вычисления. Введем обозначения для количества продолжимых и непродолжимых рядов ранга 0 d N/2.

cN = #{FN KN : rank(FN ) = d, pd = 0}, d bN = #{FN KN : rank(FN ) = d, pd = 0}.

d Очевидно, что hN = cN + bN. Сначала опишем основное свойство cN.

d d d d Лемма 3.4.1. Для всех N 2d числа cN равны некоторой константе cd.

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

Покажем, что если N 2d, то cN +1 = cN. Действительно, из определения про d d должимости каждому продолжимому ряду ранга d и длины N можно сопоста вить один ряд длины N + 1. С другой стороны, по следствию 2.1.3, каждому продолжимому ряду d и длины N + 1 соответствует ровно один ряд длины N + 1.

Замечание 3.4.1. Существует и иное доказательство. По предложению 2.1. существует взаимнооднозначное соответствие между продолжимыми рядами ранга d и длины N и парами многочленов P и Q, не имеющих общих корней.

Заметим, что никаких условий на N в этом соответствии нет, поэтому cN d совпадают для всех допустимых N.

Как мы покажем дальше, аналогичным свойством обладают bN, а значит d и hN. Для этого докажем следующую лемму.

d Лемма 3.4.2. Для N 2d и d 1, выполняется равенство N 1 N bN = qbd1 + (q 1)cd1.

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

Доказательство этой леммы может быть проведено аналогично доказатель ству предыдущей леммы. Достаточно заметить, что по предложению 2.1.7 из продолжимого ряда ранга d получается (q 1) непродолжимых рядов ранга большего на единицу, а из непродолжимого получается q таких рядов.

Лемма 3.4.3. Для N 2d числа bN равны некоторой константе bd, при d этом для d 1 выполняются соотношения:

(3.4.2) bd = qbd1 + (q 1)cd1.

.

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

Достаточно доказать независимость bN от N для d = 0. Для любого N су d ществует ровно один ряд ранга 0: (0,..., 0)T. Он и является продолжимым, т.к. его характеристический вектор равен (1), b0 = 1. Непродолжимых рядов ранга 0 нет. Для d 1 соотношение (3.4.2) следует по индукции и по леммам 3.4.1 и 3.4.2. В частности, b1 = (q 1) · q и c1 = (q 1).

Пример 3.4.1. Проиллюстрируем, что лемма 3.4.3 верна для d = 1 и q = 2.

Существует три ряда ранга 1 в F2 и длины, большей 2:

(1,..., 1), P = (1, 1)T (1, 0,..., 0), P = (0, 1)T (0,..., 0, 1), P = (1, 0)T.

Таким образом, c1 = 2, b1 = 1 для любого N 2 в F2.

Следствие 3.4.1. Число рядов данного ранга равно hd, d N/ N hd = r, d = (N + 1)/2, d где hd некоторая константа, зависящая лишь от d, а rd число невы рожденных ганкелевых матриц размера d d.

3.4.3. Результаты о количестве матриц и рядов Предложение 3.4.2. Выполняется 1, d= hd =, (q 2 1) · q 2d2, d 0, rd = (q 1) · q 2d2, d 0.

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

Проведем оказательство по индукции. База d = 0, 1 см. лемму 3.4.3. h0 = 1, h1 = (q + 1)(q 1) = q 2 1. Нетрудно заметить, что r1 = (q 1).

Пусть известно, что rd = (q 1) · q 2d2. Тогда для N = 2d из соотношений (3.4.1) можно вывести d d (N 1) hj + rd = q N 1.

hj = j=0 j= d d (N ) hj + hd = q N, hj = j=0 j= и значит hd = rd + q 2d2 · (q 2 q) = (q 2 1) · q 2d2. Достаточно доказать, что rd+1 = (q 1) · q 2d. Действительно, для N = 2d d+1 d (N +1) hj + rd+1 = q N +1.

hj = j=0 j= Таким образом, rd+1 = q N +1 q N, что и требовалось доказать.

Заметим, что для доказательства утверждения достаточно знать только h0.

Следствие 3.4.2. Для случая q = 2 имеем:

1, d = 0, hd =, 3 · 4d1, d 0, rd = 4d1, d 0.

Следствие 3.4.3. Выполняется 0, min(L, K) r, 1, min(L, K) r = 0, LK r = (q 2 1) · q 2(r1), min(L, K) r 0, L+K q q 2(L1), min(L, K) = r.

3.4.4. Подсчет рангов матриц с ограничениями Рассмотрим следующую задачу. Пусть q = 2, т.е. K = F2. Требуется найти число LK,1 ганкелевых матриц, которые имеют ранг r, и траекторное r пространство (1.3.1) которых содержит вектор 1L = (1,..., 1)T KL. Для начала сведем эту задачу к задаче определения количества рядов, обладающих определенным свойством, как это сделано в разделе 3.4.1. Отметим, что здесь недостаточно рассматривать случай L K, так как при транспонировании матрица может терять указанное свойство.

Предложение 3.4.3. LK,1 можно найти как r 0, r min(L, K) N, h, r min(L, K) r LK, r = hN,1, r r=KL LK, r=L r где hN,1 это число рядов длины N и ранга r, таких что характеристиче r ский вектор P имеет четное число единиц.

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

Для случая r min(L, K) утверждение очевидно. Для L = r имеем 1L L(L) (FN ) = KL для любой из ганкелевых матриц ранга L, поэтому LK,1 = L LK L.

Для краткости будем говорить, что вектор A ортогонален B (AB), если AT B = 0.

Пусть r min(L, K) и FN ряд, образующий некоторую ганкелеву мат рицу с eL L(L) (FN ). Тогда, по предложению 2.1.1 r = rank FN ;

к тому же очевидно, что r N/2. Тогда принадлежность 1L пространству L(L) (FN ) рав носильна условию 1L R(L), что по предложению 2.1.2 эквивалентно d (3.4.3) P 1r+1 pk = 0, k= т.е. четности количества единиц в векторе P.

Пусть r = K. Тогда по предложению 2.1.1 либо K = r rank FN, либо r = rank FN. Допустим, что выполняется первый случай L N d + 1, и аналогично предыдущему пункту, условие принадлежности 1L пространству L(L) (FN ) равносильно дизъюнкции двух условий:

P 1r+1, Q1N r+2.

Но если такое выполняется, то матрица из (2.1.8) при умножении на 1N + слева дает 0, т.е. она не является матрицей полного ранга, и мы получаем противоречие. Таким образом, имеем r = rank FN. В этом случае, так как K L, ортогональность 1L пространству R(L) опять равносильна (3.4.3).

Далее, аналогично разделу 3.4.2, введем величины cN,1 и bN,1, как количе d d ства рядов данного ранга, характеристический вектор P которых имеет четное число единиц. Заметим, что введенные величины инвариантны относительно размера ряда.

Лемма 3.4.4. Для фиксированного d и всех N 2d:

1. cN,1 равно некоторой константе c1.

d d 2. bN,1 равно некоторой константе b1, при этом для d 1 выполняется d d соотношение, аналогичное (3.4.2):

b1 = 2b1 + c1. (3.4.4) d d1 d 3. hN,1 равно некоторой константе h1.

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

Воспользуемся доказательствами лемм 3.4.1 и 3.4.2. В качестве базы индукции в лемме 3.4.2 достаточо заметить, что c1 = 1, b1 = 0 (см. пример 3.4.1).

1 3.4.5. Нахождение количества рядов данного ранга с ограничениями Для нахождения h1 не подходят рассуждения, аналогичные доказатель d ству предложения 3.4.2, так как мы не знаем общее количество таких рядов.

Заметим, что достаточно уметь вычислять cN,1, и тогда можно воспользовать d ся формулой (3.4.4) для нахождения bN,1 и hN,1. Для этого запишем условие d d (3.4.3) на языке многочленов с помощью следующей леммы.

Лемма 3.4.5. Вектор A Fn ортогонален 1n тогда и только тогда, когда 1 является корнем A(z) т.е. A(z) делится на z + 1 (будем обозначать как z + 1 | A(z)).

Введем также в рассмотрение функцию Эйлера для многочлена A(z) = a0 + a1 z +... + an z n (A) = #{B(z) : deg B deg A, gcd(A(z), B(z)) = 1}.

Лемма 3.4.6. Выполняется (A) = 2n (1 2n1 )... (1 2nm ), где n = deg A, а n1,..., nm степени компонент в разложении A(z) в про изведение неприводимых многочленов [30, c. 157].

Таким образом, нам необходимо перенумеровать все ряды, у которых ха рактеристический многочлен P (z) делится на z + 1. Для этого воспользуемся предложением 2.1.6.

Замечание 3.4.2. Для поля F2 константа существует ровно одна, поэтому последний шаг в доказательстве предложения 2.1.6 тривиален.

Лемма 3.4.7. Число cN,1 выражается как d c1 = (P ).

d deg P =d,z+1|P (z) Доказательство.

По предложению 2.1.6 каждый продолжимый ряд ранга d соответствует паре многочленов P (z) и Q(z), таких что deg Q deg P = d, gcd(P, Q) = 1, а также pd = 0 (последнее условие выполняется для любого многочлена степени d в F2 ). По лемме 3.4.5 мы получаем искомое утверждение.

Теперь мы можем найти рекуррентное соотношение для c1.

d Предложение 3.4.4. Для d 1 выполняется c1 c1 = 2 · 4d1.

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

Многочлен z+1 является неприводимым, поэтому по лемме 3.4.6 выполняются следующие соотношения:

2 (A(z)), gcd(A(z), z + 1) = 1, ((z + 1)A(z)) = (A(z)), иначе.

Таким образом, получаем c1 = (P (z)(z + 1)) = d+ deg P =d = (P (z)(z + 1)) + (P (z)(z + 1)) = deg P =d, deg P =d, z+1|P (z) gcd(z+1,P (z)) 2c1 + c = c1 + cd.

= d d d Достаточно показать, что cd = 2 · 4d1. Из (3.4.2) получаем, что bd+1 = hd + bd и b1 = 1, b2 = 4. Таким образом, bd+1 bd = 3·4d1, и поэтому bd удовлетворяет линейному рекуррентному соотношению bd+2 5bd+1 + 4bd = 0, а значит имеет вид bd = a1 4d + a2 Подстановкой для d = 1, 2 получаем bd = 4d1 и cd = 2 · 4d1.

Предложение 3.4.5. Числа h1 для d 1, выражаются как d h1 = 4d1.

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



Pages:     | 1 || 3 | 4 |
 





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

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