Научная литература
booksshare.net -> Добавить материал -> Физика -> Лидл Р. -> "Конечные поля. Том 1" -> 209

Конечные поля. Том 1 - Лидл Р.

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1 — М.: Мир, 1988. — 430 c.
ISBN 5-03-000065-8
Скачать (прямая ссылка): konechniepolya1988.djvu
Предыдущая << 1 .. 203 204 205 206 207 208 < 209 > 210 211 212 213 214 215 .. 371 >> Следующая

*
I А .
-.<ж
<
ческой последовательностью. Аналогично если через d7V обозна чить п-й
вектор состояния соответствующей импульсной функции, то dr = d0Ar = d0.
Применив теперь теорему 8.16, получаем! утверждение теоремы. ? |
8.20. Пример. Условие mj 'X- па в формулировке теоремы 8.19 необходимо
ввиду того, что существуют однородные линейные рекуррентные
последовательности k-w порядка, не являющиеся чисто периодическими, но
содержащие к линейно независимых векторов состояний. Пусть d0, dlt ... -
рекуррентная последова-* тельность 2-го порядка над полем являющаяся
импульсной/ функцией и задаваемая рекуррентным соотношением dn+,z ==?.! -
л 0, 1, ... . Эта последовательность имеет вид 0, 1, U
1, . Очевидно, что векторы состояний do и dx линейно
незави-

41
§ 2. Импульсная функция. Характеристический многочлен
507
симы над Fg, в то время как сама последовательность d0, ...
не является чисто периодической (в данном случае д0 - 1). Утверждение,
обратное утверждению теоремы 8.19, неверно. Чтобы показать это,
рассмотрим линейную рекуррентную последовательность 3-го порядка sn, su
... над полем определяемую рекуррентным соотношением sn+9 - sn, п = О, 1,
с вектором начального состояния s0 - (1, 1, 0). Тогда как сама
последовательность s", Sj, ..., так и соответствующая импульсная функция
являются периодическими последовательностями с минимальным периодом,
равным 3. В то же время любые три вектора состояния последовательности
s<" slt ... линейно зависимы над полем F2. ?
Пусть s0, s,, ... - линейная однородная рекуррентная последовательность
k-ro порядка над полем FflJ удовлетворяющая линейному рекуррентному
соотношению
Ч .
"~1" ^ft-2^n+fe-2 + ' ' * *f" @0$п> Ц О, 1 , . . ., (8.7)
где aj ? 0 < / < к - 1. Многочлен
} (х) = хк- ah"txk~l - ak_2xk~2 - ¦ ¦ • - aQ ? Fq [х]
называется характеристическим многочленом дайной линейной рекуррентной
последовательности. Ясно, что он зависит только от линейного
рекуррентного соотношения (8.7). Если А - матрица, определенная в (8.3),
то легко заметить, что f (х) совпадает с характеристическим многочленом
матрицы Л, как ои определяется в линейной алгебре, т. е. f (х) = det (xl
- Л), где I - единичная матрица размера к X к над полем F?. С другой
стороны, матрицу Л можно рассматривать как сопровождающую матрицу
нормированного многочлена f (х).
В качестве первого применения понятия характеристического многочлена
рекуррентной последовательности покажем, как в одном важном частном
случае члены линейной рекуррентной последовательности могут быть явно
выражены через коэффициенты многочлена / (*)•
8.21. Теорема. Пусть s0, зг, ... - однородная линейная рекуррентная
последовательность k-го порядка над полем Fg и - ее характеристический
многочлен. Если корни аг, ак
многочлена / (х) все различны, то
k
sn - ? р(а/, п ~ 0, 1, . . ., (8.8)
е^е Рь Ра - различные элементы поля разложения многочлена f (х) над полем
F9, которые однозначно определяются начальными членами рекуррентной
последовательности s0, st, ... ,
508
Гл, 8. Линейные рекуррентные последовательности
Доказательство. Константы р1( можно определить из
системы линейных уравнений
k
S а"р
/=!
'/и
•id.
Ж!
Так как определитель этой системы является on редел ителещ Вандермонда,
который отличен от нуля ввиду условий, наложен ных на ах, ай, то элементы
рь Рй определяются однозначна и, как вытекает нз правила Крамера, лежат в
поле разложения:; iF9 (ах, ...,~ай) многочлена / (х) над полем Fq. Теперь
для того*! чтобы доказать равенство (8.8) для всех п 0, достаточно иро*|
верить, удовлетворяют ли рекуррентному соотношению (8,7).1 элементы из
правых частей формулы (8.8) при рх, ..., рй, опреде ленных, как было
указано выше. Но
к к к
2? а ~ V* й п-ffc-I " V и п^к-2
з Р/a/ ak~j 2j P/а/ ~ ak-z L Р/а/
'Х'Л
4 ч /¦=1,
/=1
f % --А-
/-1
Оо S Р/а"
/-1
к
1". *
? p,f (а,) а? = 0
/-1
для всех rt > 0. Тем самым теорема доказана. U|
8*22. Пример. Рассмотрим линейную рекуррентную последа ? вательиоеть s(),
sy, ... над полем Г2" задаваемую рекуррентными соотношением sn+.2 - sn+1
-+- sn, rt = 0, 1, и начальными з* чеииямн 50 -= Si !. Соответствующий
характеристический мнОЛ| гочлен равняется / (х) - х2 - х - 1 ? f2 [х].
Если |р4 - (a)'$l
то корнями ' многочлена f (х) являются а, = а и а2 = 1 г аЛ
Учитывая начальные значения, получаем соотношения рх 1- р2 =*
- I, pjcc ф- р2 (I + а) = 1 и, следовательно, рх - а, р2 = I +
аф
Из теоремы 8.21 следует, что sn = ап^[ + (!-+- а)^1 для всех|
% $
щ ч-S
п 0. Так как ря - 1 для всех ненулевых р ? jp4, получаем что Sxi+a sn для
всех п 0, что согласуется с тем, что минималь^ ный период этой
последовательности равен 3.
8.23. Замечание. Формула, аналогичная формуле (8.8), спра ведлива и в
случае, когда кратность каждого корня многочлена; [ {х) не превосходит
характеристики р поля Рассмотрим этод^ случай более подробно. Пусть a,,
,..,ат - различные корни многочлена /(а), и пусть каждый корень ait i --
Предыдущая << 1 .. 203 204 205 206 207 208 < 209 > 210 211 212 213 214 215 .. 371 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed