Квазирешетки в прикладных задачах обработки цифровой информации
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
ечетных m [8].
Собственное разбиение Фибоначчи единичного полуинтервала I уровня m получается, если подействовать несколько раз сдвигом S на полуинтервалы до их первого возвращения в полуинтервал 1т.Разбиение содержит Fm+1 и Fm+2 полуинтервалов длины и и ,если уровень m четный, и соответственно Fm+1 и Fm+2 полуинтервалов, если m нечетный. Тогда инвариантность разбиений относительно действия сдвига S:
(1.32)
где разбиение получается перекладыванием двух крайних правых полуинтервалов из разбиения .
.3 Алгоритмы построения квазирешетки и оценка их свойств
При переходе от неоднородной квазирешетки к отвечающей ей однородной квазирешетке необходимо знать вектор сдвига ?. Для этого требуется уметь находить частное решение (x10,x20) из O2 неоднородного уравнения
(1.32)
Кольцо Фибоначчи O является евклидовым относительно деления с остатком по норме, следовательно, частные решения уравнения (1.32) можно найти с помощью алгоритма Евклида. Отметим, что указанный алгоритм весьма трудоемкий [9].
С другой стороны, использование одномерной квазирешетки F (1, 3) позволяет в кольце Фибоначчи O определить деление с остатком полностью аналогично тому, как это делается в кольце целых рациональных чисел Z, и тем самым получить быстрый алгоритм деления в кольце O. Возникающий таким образом алгоритм Евклида является 2-ступенчатым и, что необходимо отметить, по своей сути является одномерным. В теореме 1.1 доказана верхняя оценка для количества шагов в алгоритме [5].
Для построения данного алгоритма (F1-алгоритм) мы воспользуемся модифицированной квазирешеткой полученной ?-инфляцией квазирешетки Фибоначчи , где для . Имеем
где .
Необходимость замены основной квазирешетки F сжатой квазирешеткой F1 обусловлена тем, что разностная функция
или ? (1.34)
принимает положительные значения, не превосходящие 1 Данное обстоятельство позволяет в алгоритме деления с остатком формально использовать квазирешетку F1 вместо кольца целых рациональных чисел Z.
Таблица 1.2 - Замены основной квазирешетки F сжатой квазирешеткой F1
N12345?1(N)11 + ?2 + ?3 + ?3 + 2 ???1(N)11 - 2 - 3 - 3 -
Пусть , где . Из (1.34) следует существование единственного , удовлетворяющего условиям
, где (1.35)
Используя (1.35), получаем представление
, где и .(1.36)
1-алгоритм - это рекуррентное повторение действия (1.36):
(1.37)
где для i = 0,1, 2,...
Докажем конечность F1 - алгоритма (1.37), т.е. покажем, что для некоторого . Пусть ,тогда имеем
.(1.38)
Если Ni ? 4, то получаем неравенства
,(1.39)
так как из включения следует .
Аналогично имеем
для ;
для ;(1.40)
для .
Итак, в (1.39) для мы видим препятствие, не позволяющее доказать конечность F1 - алгоритма. Это означает, что (1.37) не является обычным алгоритмом Евклида. И действительно, далее мы убедимся в том, что (1.37) - это 2-ступенчатый алгоритм по терминологии Кука [5]. Для доказательства потребуется дополнительная информации нам потребуется дополнительная информация о величине на следующем шаге .
Если , то ввиду (1.40) получаем неравенство
,(1.41)
так как , иначе в силу (1.38) выполнялось бы неравенство
или . Откуда следует , что противоречит предположению . Поэтому для имеем (таблица 1.2)
.(1.42)
Пусть , тогда, снова используя (1.40), приходим к неравенству
,
из которого и (1.40) для получаем
.(1.43)
Аналогично в остальных случаях имеем
и, следовательно,
.(1.44)
Поскольку , то можем переписать F1 - алгоритм (1.37) в более привычном виде
(1.45)
Оценим сверху величину . Применяя несколько раз равенство , получаем для любого i ?0 связь
(1.46)
между остатками ri+i и r0. Удобно указанную связь (1.46) перевести в матричную форму. Так как , то отсюда приходим к следующему матричному соотношению
,(1.47)
где Mi = Qo…Qi и матрицы Qj имеют вид . Пусть обозначает длину вектора . Тогда, очевидно,
(1.48)
и правая часть, ввиду соотношения (1.47), может быть оценена как
(1.49)
.(1.50)
Пусть ? - вектор из R2, с коэффициентом r ? 0, (, ) - скалярное произведение в R2. Воспользуемся неравенством
,(1.51)
вытекающим из следующей цепочки преобразований , где ? - максимальное собственное значение матрицы RRt. Поскольку R = Rt - симметрическая матрица, то
, где (1.52)
максимальное собственное значение матрицы R. Теперь из (1.51), (1.52) получаем нужное нам неравенство
.
Применим его к правой части (1.49). Имеем
(1.53)
(1.54)
собственное значение матрицы Rj (1.50). Отсюда и (1.48) получаем неравенство , из которого и (1.46) вытекает неравенство для нормы остатков ri+1 в .F1-алгоритме (1.45)
.(1.55)
Согласно (1.39), (1.40) и (1.54), получаем следующие неравенства для произведений ?i ?i:
для
для (1.56)
для .
Отсюда, используя (1.39) и (1.40), оцениваем сверху попарные произведения , предварительно перегруппировывая их к виду :
для , ;
для , ;
для , .(1,57)
Разобьем произведение в правой части неравенства (1.55) на 1) сдвоенные пары для ; и 2) одиночные пары для Nk ? 2 и не входящих в 1). Оценим их с помощью неравенств (1.56), (1.57) и применим к (1.55). Получаем
, если i четное,(1.58)
если i нечетное.
Теперь отметим, чт?/p>