Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 112
Текст из файла (страница 112)
Пример. Условие т! > п„в формулировке теоремы 8.19' необходимо ввиду того, что существуют однородные линейные' рекуррентные последовательности й-го порядка, не являющиеся ' чисто периодическими, но содержащие я линейно независимых, векторов состояний. Пусть де, д,, ... — рекуррентная последова--' тельность 2-го порядка над полем Ке, являющаяся импульсной:", функцией и задаваемая рекуррентным соотношением д„„е = = с1„„, и — О, 1,,... Эта последовательность имеет вид О, 1, 1 1, ....
Очевидно, что векторы состояний д, и д, линейно незави-1 5 2. Импульсная функция, Характеристический иного»лен 507 симы над г», в то время как сама последовательность д, й„.„ не является чисто периодической (в данном случае и, = 1). Утверждение, обратное утверждению теоремы 8.!9, неверно. Чтобы показать это, рассмотрим линейную рекуррентную последовательность 3-го порядка в,, в„... над полем К„определяемую рекуррентным соотношением в„„= в„, и = О, 1, ..., с вектором начального состояния а, = (1, 1, 0). Тогда как сама последовательность з„, в„.„, так и соответствующая импульсная функция являются периодическими последовательностями г минимальным периодом, равным 3.
В то же время любые три вектора состояния последовательности в», в„... линейно зависимы над полем г,. ( ) Пусть ап во ... — линейная однородная рекуррентная последовательность к-го порядка над полем Г», удовлетворяющая линейному рекуррентному соотношению зо,с = а„,в,„, + а„»в„„, »+ .. Ф аов„, и = О, 1,..., (8 7) где аз Е Г», 0.(1~( й — 1. Многочлен 1 (х) = х" — а„,х' — ' — а„,х" — ' — — а, Е г (х) называется характеристическим многочленвм данной л инейной рекуррентной последовательности.
Ясно, что он зависит только от линейного рекуррентного соотношения (8.7). Если А — матрица, определенная в (8.3), то легко заметить, что 7' (х) совпадает с характеристическим многочленом матрицы А, как он определяется в линейной алгебре, т. е. 7' (х) = де1 (хà — А), где 1— единичная матрица размера й х й над полем К . С другой стороны, матрицу А можно рассматривать как сопровождающую матрицу нормированного многочлена ~ (х). В качестве первого применения понятия характеристического многочлена рекуррентной последовательности покажем, как в одном важном частном случае члены линейной рекуррентной последовательности могут быть явно выражены через коэффициенты многочлена 1(х), 8.21.
Теорема. Пусть в„ з» ... — однородная линейная ре"Уррентная последовательность й-го порядка над полем Г» и ! (х) — ее характеристический многочлен. Если корни а„..., иь много»лена 1' (х) все различны, то в" = ~()сиг, п=О, 1, ..., (8.8) /=! ()и ..., рд — различные элементы поля разложения много"»ена 1(х) над полем г», которые однозначно определяются нач"льными членами рекрррентной последовательности в„в,, ....
508 Гл. 8. Линейные ренуррентные последовательности Доказительство. Константы !)т, ..., ()„можно определить из системы линейных уравнений ~„а;"~! =- зн, и = О, 1,..., й — !. !:! Так как определитель этой системы является определителемр Вандермонда, который отличен от нуля ввиду условий, наложен-,, ных на а„..., ал, то элементы ()!, ..., 1)л опРеделЯютсЯ однозначно! и, как вытекает из правила Крамера, лежат в поле разложения":,:, К (а,, ..., аь) многочлена ((х) над полем Е . Теперь для того,'~, чтобы доказать равенство (8.8) для всех и ) О, достаточно прой,' верить, удовлетворяют лн рекуррентному соотношению (8,7) ' элементы из правых частей формулы (8.8) при ()„..., ()л, опреде,' ленных, как было указано выше. Но ~~ р;а," " — ал ! ~~ ();а,"Ч " ' — ае т ~ р!а,' " /=.! !=-! !=-! — с!е Е р!а!' = Е ()!~(а!) а! — — О е !=-! /=! для всех и ~~ О.
Тем самым теорема доказана. Пч 8.22. Пример. Рассмотрим линейную рекуррентную последо-' вательность лв, л, над полем К., задаваемую рекуррентным.' соотношением ь„,, =-- л„„+ л„, и =- О, 1, ..., и начальными зна*х е чеииями к, — — л! =- 1. Соответствующий характеристический мно-',', гочлен равняется ((х) =-- х' — х — 1 Е Ее !х).
Если К, = 1е (а)" то корнями'многочлена ) (х) являются а, — — а и ае — 1+ а.й! Учитывая начальные значения, получаем соотношения (), -г Ов =( == 1, (),а + !)е (! + а) =- 1 и, следовательно, р! =- а, ()е = 1 + а.!' Из теоремы 8.2! следует, что а„=- а"+' + (1+ а)"+' для всех,', и > О. Так как Рв == 1 для всех ненулевых () Р Г4, получаем," что л„„= ал для всех и ) О, что согласуется с тем, что минималь т ный период этой последовательности равен 3. П! 8.23. Замечание. Формула, аналогичная формуле (8.8), спра-' ведлива н в случае, когда кратность каждого корня многочлена, ) (х) не превосходят характеристики р поля !Ео. Рассмотрим этот-;! случай более подробно.
Пусть а,, ..., а„, — различные корни !) многочлеиа 1(х), и пусть каждый корень ас, !' = 1, 2, „ти,':; имеет кратность е, Р, Пусть г! -- 1, если а; — О. Тогда э„:= ~ Рт(и)а"с, и = О, 1..., т=! где Р,, !' — 1, 2, ..., и!, — многочлен степени не более чем а!,,:) коэффициенты которого однозначно определяются начальными 4 2. Импульсная функция. Характеристический миогочлеи 509 значениями последовательности и лежат в поле разложения многочлена ) (х) над полем К .
При этом целое число п естествен„ым образом отождествляется с соответствующим элементом поля Ке. Читатель, знакомый с дифференциальными уравнениями, заметит определенную аналогию с общим решением однородного линейного дифференциального уравнения с постоянными коэффициентами. [:) В случае когда характеристический многочлен является ненриводнмым, элементы линейной рекуррентной последовательности могут быть представлены с помощью соответствующей функции следа (определение функции следа и ее основные свойства приведены во второй главе, см. определение 2.22 и теорему 2.23). 8.24. Теорема.
Пусть зе, з,, ... — однородная линейная рекуррентнач последовательность я-го порядка над полем К вЂ” -- Кр, удовлетворяющая уравнению (8.7), а соответствующий характеристический многочлен ~ (х) является неприводимым многочленом над полем К. Пусть сс — корень многочлена 1" (х) в расширении Г:. К» поля К. Тогда существует однозначно определенный элемент О Е Р, такой, что з„= Тгрук(йач), и = О, 1, Доказательство. Так как элементы (1, сс, ..., ໠— ') образуют базис поля р" над К, то можно задать однозначно определенное линейное отображение ул р — К, полагая Е (сс") = ьи для и = — О, 1 ..., й — 1.
По теореме 2.24 существует однозначно определенный элемент 0 ~ р", такой, что Ь (у) =- Тгр~к (Оу) для всех т ~ р". В частности, =Тгрук(Осе), п=О, 1, ..., А — 1. Остается показать, что элементы Тгрук (Оа"), п = О, 1, ..., обРазуют однородную линейную рекуррентную последорательность с характеристическим многочленом 7' (х). Но если 7 (х) = х» — а„,х» — ' — — ае ~ К [х], то, используя свойства функции следа, получаем '1 ге;и (Оа".~-») — а» ~Тгрук (Ои"-ь» — ') — ° ° ° — аоТгрук (Осс") = = Тгрук(Оа"+» — а» 10а'+'-' — . — аьОсх") = = Тгрук(0апг(а)) = О для всех п ) О, П эхругие соотношения между линейными рекуррентными последовательностями и их характеристическими многочленами могут быть получены из следующего полиномиального тождества. 5!О Гл.
8. Линейные ренуррентные последовательности 8.25. Теорема. Пусть з, зг, ... — однородная линейная ре куррентная последовательность й-го порядка над полем Ко, уд, влстворюощая рекуррентному соотноиоению (8,7) и являющалс чисто периодической последовательностью с периодом «. Пуст ' ! (х) — характеристической многочлен втой последовательности: Тогда имеет место равенство 7 (х) з (х) =- (1 — х') й (х), где з (х) =- з,х' — ' + з,х' —" + + з„,х + з,, Е К [х[, е — ! о — ! — ! й(х) =-- ~ ~~ а!„!чгг!х! Е Ко [х[, аь = — 1. (8.10)' г=о г=о Доказательство. Сравним коэффициенты при одинаковых сте-.
пенях х в обеих частях равенства (8.9), Пусть с, (соответственно) й!) — коэффициент при х', 0 ( г ( й + « — 1, в левой (соответ4 отвеина правой) части равенства (8.9). Так как )(х) = — ~'„агхгт! !=о получаем с! = — ~~~ а!в«! !ь 0 (1(Й+« — 1. (8.11 оч!«ю о:!«« — ! !+!=! Заметим, что линейное рекуррентное соотношение (8.7) мож быть также записано в виде а!з„„=О для всех п)~0.
(8.12 ' !=о Выделим теперь для отдельного рассмотрения следующие четыре. случая. Если й ( 1 ( « — 1, то из (8.11) и (8.12) следует с,= — ~ а!зт ! о,!=-О=й!, -о Если ! .: « — 1 н ! ( К то из (8.11), (8.12) и периодичности нашей, последовательности получаем л Х~ а!з~-г-М~! = 2л! а!в~ !-ое! = $=0 ! —.!+! А е — ! — ! Е а!з!-о-! = Х а! о!.тг! = й!. (=-!+! !=о Если г ) «и ! ) я, из (8.11) следует, что а е — ! — е-!-« с! — -- — ~~ а!з, ! о,! — — — ~~ аса «,гз! = й!. !'=! — ~-~.1 !=о е 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
