Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 115
Текст из файла (страница 115)
В обп>ем все коэффициенты с„, с,, ... можно рекурсивно определить из первого уравнения и рекуррентного соотношения я с„= — Ьв ' ~„'Ьдс„д, и = 1, 2,... д=> 520 Гл. 8. Линейные ренуррентные последовательности Получившийся формальный степенной ряд С (х) является обр ' ным к В («1 относительно операции умножения формальных пенных рядов, Таким образом. если для В (х) ~ Г ((х)) существует ратный элемент относительно операции умножения формальн ' степенных рядов, то этот элемент определен однозначно. Обоз чим его через 1!В (х). Произведение А (х) (1)В (х)), где А (х Е !", 1(хЦ, будет обычно записываться в виде А (х),'В (х).
Так к' 'т'з !1«)] — область целостности. то для указанных выше вы ' женпй справедливы обычные правила оперирования с дробя Элемент, обратный к элементу В (х) относительно умножен ' пли выражение А (х)/В (х) можно вычислить с помощью ал ритма, приведенного при доказательстве теоремы 8.37.
Д подобных вычислений применимо также и обычное деление угл ' 8.38. Пример. Пусть многочлен В (х) =- 3+ х+ х' расс трнвается как формальный степенной ряд над полем !Гз. По т ' реме 8.37 В (х) обратим относительно операции умножения мальных степенных рядов. Вычислим 1/В (х) с помощью алгорнт деления углом: 1+О х+О хе+О ха+О «з+О.за+О.хз+...13+«+хе — 1 — 2« — 2«з 12.~-«-~-4«з 1 2хз.1 Зх+Зх'+О хз — Зх — хз — хз 2хз+4хз+О хз -2хз — 4хз — 4«з хе+О х'+О х" Таким образом, мы получили, что , =2 х и4х' 2х'+.. 1 3+х+хе 8,39.
Пример. Вычислим А (х)'В (х) ~ Кз ([х)!, где А (х) = ! л х '; — хз -1- хз -1 ... = ~ 1 х", н=о и В (х) — 1 ' х -и х'. Используя алгоритм деления углом, оп ская члены с нулевымн коэффициентами н учитывая то, что ' поле гс выполняется равенство — 1 =- +1, получаем ! -~-«+хе+хе-нхз+за.~-зл 1-х'+х'+х'+х'з+...11+«+ха 1+х +хз 11, хз) хз 1 хе) хз +хе+ х' хе+ха +хз Раз «з ! «з ! «з х' 4-хе+из+хзз 52! 4 3. Пронаводнжие функции Таким образом, ! + а+ ха+ х' '.. „ г+х-1-ха г.х Для применения теории формальных степенных рядов рассмотрим теперь однородную линейную последовательность й-го порядка э„, э,, ... над полем Г .
удовлетворяющую линейному рекчррептному соотношению (8.7). Назовем многочлен га (х) = 1 — а„,х — а„,ха — - — аах" ~ ]г'и ]х] (8.14) возвратным характеристическим многочленом ') этой последе. вательности. Характеристический многочлен ( (х) н возвратный характеристический многочлен га (х) связаны, между собой соотношением !'а (х) = ха! (1/х).
Можно показать, что для производящих функций справедливо следующее фундаментальное равенсгво. 8.40. Теорема. Пусть эа, и„... — однородная линейная рекуррентная последовательность й-го порядка над полем Гч, удовлетворяющая линейному рекуррентному соотношению (8.7). Пусть )и (х) ~ Г (х] — возвратный характеристический много- член этой последовательности, а 6 (х) е Гч ЦхЦ вЂ” производящая функция этой последовательности, определенная в (8.13). Тогда имеет место равенство (8.15) где (8.16) у(х) = — Е Е а„а ~э~я! Е Г, (х] !=а !=а и аа =. — 1. Обратно, если у (х) — производящий многочлен над полем Кч, дед (д(х)) < й, а Га (х) ~ ]Гч(х] задаетсЯ Равенством (В 14), то формальный степенной ряд 0 (х) Е ]г'ч ЦхЦ, задаваемый равенсгпвом (8.15), является производящей функцией однородной линейной рекуррентной последовательности й-го порядка над и"лем Гн, удовлетворяющей линейному рекуррентному соотношению (8 7) г ) н литературе атот ииогочлен иааываатсн также двойственным харанже.— Пр .
р. 522 Гл. а. Лииейиые реиурреитиые последовательности Доказаптелосптво. Имеем ь Ф )е (х) 6(х) =. — ~ ~„'ав „х") ~ ~„'авх" ) = е — ! / / т=о ~=о ' ' ' т=-и т=1-е О г и =. е) — В (Х,.е.„). ,=ь .=е (8.1 ' Теперь, если последовательность ае, з, удовлетворяет (8.77 то из (8.!2) следует, что !"' (х) 6 (х) =-= а (х). Тогда в силу то что по теореме 8.37 7е (х) имеет обратный относительно оп' рации умножения элемент в т [[х11, получаем справедливо равенства (8.15). Обратно, из (8.17) следует, что произведен 7' (х) 6 (х) равняется многочлену степени, меньшей чем К тальк тогда, когда ~ а зт „и —— О для всех 1) й.
в=о Последнее как раз означает, что последовательность з,, з,, ... составленная из коэффициентов формального степенного ряда 6 (х; удовлетворяет линейному рекуррентному соотношению (8.7). Приведенную выше теорему можно коротко сформулироват следующим образом: существует взаимно однозначное соотве стане между однородными линейными рекуррентнымн послед ' вательностями Ьго порядка с возвратным характернстическн многочленом 7*(х) н дробями вида д(х)~7*(х), такими, ч дея (а (х)) < и, Равенство (8.! 5) в этом случае может быть испол зовано для вычисления членов линейной рекуррентной послед вательности с помощью алгоритма деления углом.
8.4!. Пример. Рассмотрим линейное рекуррентное соотнош ние зпее ввез 1 зве1 + ап над полем тт. Соответствующий возвратный характеристическн многочлен имеет вид )' (х) = ! — х — х' — х' = 1 + х -ь- х'+ х' ~ ) т [х) Если вектор начального состояния равен (1, 1, О, 1), то много". член а (х), определенный в (8.18). равен а (х) =- 1 + х'. Тогд ." 323 4 3. Произиодищие функции производящая функция 6 (х) рассматриваемой рекуррентной последовательности может быть получена с помощью деления углом: 1 +хи ~! + х + хз + хв 1+х +х'+х' ~!+х+хз+х'+хе+ ...
х+ х'+ хз+ х' х+х' +х'+хз +хе х'+ х' + хе+ х' хе+ хе+ хв+ хз Хв+ Хз + Х'+ Хз хв +хе Таким образом, 6(х) = + = 1+х+хз+хв (-хв )- ... по соответствует бинарной последовательности 1, 1, О, 1, 1, О, 1, ..., имеющей мииимальиый период 3. Импульснуюфункцию, связанную с данным линейным рекуррентным соотношением, можно получить, если положить и (х) = х'. Алгоритм деления углом дает в этом случае производящую функцию 6(х) — — + + + хз+хзв+ хм+ что соответствует периодической бинарной последовательности О, О, О, 1, 1, 1. О, О, О, 1, 1, 1, ... с минимальным периодом, равным 8, (:) Из равенства (8,15) можно получить другое доказательство теоремы 8.25.
Действительно, ввиду того что последовательность является чисто периодической последовательиостью с минимальным периодом равным г, ее производящая функция 6 (х) может быть записана в виде 6 (х) = (з + з,х + ° ° ° + з,,х' — ') (1 + х' + хз" + ...) = —,, где зз (х) = а, + а,х+ ... + з,,х' — '.
С другой стороны, используя обозначения теоремы 8.40, из (8.! 5) получаем, что 6 (х) = 8 (ХЦ* (х). Приравнивая полученные выражения для 6 (х), "Риходим к полиномиальиому равенству ~з (х) зв (х) = (!в — х') д (х). Если ~(х) и з (х) такие же, как в (8.9), то ((х) з(х) = хе~в(1!Х) х' — 'аз(1~Х) = (х' — 1) хз 'я(1~Х). 524 Гл. 8, Лииейиые рекурреитиые послеловательиости Сравнивая (8.10) и (8.!6), получаем х"-'у (1/х) =- — И (х), откуда и следует равенство (8.9). (8.18/ й 4.
й4инимальиый многочлеи Хотя до сих пор мы этого не отмечали, очевидно, что линейная' рекуррентная последовательность удовлетворяет множеству дру-" гих линейных рекуррентных соотношений помимо того, которов определяет эту последовательность. Так, если последовательность) зв. з,, ... является чисто периодической последовательностью а/1 периодолт г, то она удовлетворяет линейным рекуррентным соот;: ношениям з„„= з„(п = О, 1, ...), зв,м = ьв (и = О, 1, ...) т. д. Экстремальный случай представляет собой последователь':, ность О, О, О, ..., которая удовлетворяет любому однородному" линейному рекуррентному соотношению. Следуюц(ая теорема описывает, как связаны между собой различные линейные рекуррент-! ные соотношения, которым удовлетворяет данная однородная/ линейная рекуррентная последовательность.
8.42. Теорема. Пусть зв, з„... — однородная линейная рекур«": ренпщая последовательность над полем !г'д. Тогда существует',, однозначно определенный нормированный многочлен т (х) Е Кд !х)', обладающий следующим свойством: нормированный многочлен по ' ложительной степени / (х) Е Кр !х1 является характеристиче-'' ским многочленом данной последовательности з„, з,,, тогда' и только тогда, когда / (х) делится на т (х). Доказательство.
Пусть /в (х) р Е 1х] — характеристический~ многочлен однородного линейного рекуррентного соотношения„'1 которому удовлетворяет наша последовательность, н пусть И (х) Р Р !г'д !х! — многочлен вида (8.10), определяемый многочленом"; /, (х) и исходной последовательностью з„з, ... Если й (х) — '„' нормированный многочлен, являющийся наибольшим общим де-.' лителем многочленов /, (х) и Ив (х), то мы можем записать /в (х) =л4, =- т (х) с((х), И, (х) = Ь (х) с((х), где т (х), Ь (х) Р Гд !х1.
До.'Т кажем, что т (х) и есть искомый многочлен. Очевидно, что т (х) —- нормированный многочлен, Пусть теперь / (х) Р !('д !х1 — произ- ' вольный характеристический многочлен данной последователь-"- ности, н пусть И (х) Е Кд !х1 — многочлен вида (8.10), определя-;,~ емый многочленом / (х) и данной последовательностью. Применяя, теорему 8:40, получаем, что для производящей функции 6 (х) ' нашей последовательности имеет место равенство 6(х) = —, Кв (") а (") /е(л) /' (х) ' 4 4.
Минимальный миогочлеи 525 „де схс (х) и я (х) — многочлены, задаваемые формулой (8 16). Следовательно, я (х) )о (х) = дс (х) с'* (х) и, используя (8,18), приходим к равенству >с(х)й(х) = — х 'аы "»д(1!х)х"хасы сх»Д(1>х) д (1>'х)х ам»)и(1/х) й„(х) с(х) После деления обеих частей равенства на с( (х) получаем й (х) и (х) = Ь (х) 1 (х). Тогда в силу того, что и (х) и Ь (х) взаимно просты, и (х) делит > (х).
Предположим теперь, что ) (х) Р >>'а (х) — нормированный и~огочлен положительной степени, который делится на и (х), т. е. )' (х) = и (х) с (х), с (х) Е 'г'а (х). Переходя к возвратным мно>очленам, получаем (* (х) =- и* (х) сь (х), Кроме того, имеет место равенство»с (х) и (х) =- Ь (х) >с (х). Отсюда, используя соотношение (8.18), получаем ао(х)и*(х) = — хс асыс » — >йс(1'х)хсеастсх» сп(1>х) = = — хс ас сх» — >Ь(1)х)хсеасисх»С (1>х) Так как с)ед (Ь (х)) < с)ея (и (х)), произведение первых двух сомножителей (включая знак минус) в правой части приведенного выше равенства является многочленом а (х) Е Ко (х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
