Geddes, Czapor, Ladahn - Algorithms for Computer Algebra (523146), страница 27
Текст из файла (страница 27)
ТЬаг !К, »Е я«Е 5!ЧЕИ а КЕГ ОГ Л рОШГК (дн,..., 9» Г) аПГ$ КЧЕ ые 1ооь)пн (ог а ро(упопна1 а(х) о( г(енто аг гповг л — 1 вась йаг и) = а(х;) = дп Гог $ = О, 1,..., л-1. То во1че йе ргоЫет о( Ичоп!пи онг $) РТ, с оп вЫег гчЛаг Ьаррепк ш йе саке о( 1пчегг$ир гЬе солгишоиг Ронпег ггат(огт нксг(1и епн!пеег!па.
Тье зпа!уг!с Ронпег напк(опп о( а сопьпнонв Гниении у(х) Ы г(е(!пег! Ьу Р(з) = )Гу(х) епшч»г(х. (4.15) ыог$се йаг, !( йе Ипсйоп г"(х) 1к г(е(!пег! Ьу а г$(аскезе (1.е. (1и!ге) кег о( кагпр1ев, / >., г"„$, тйег йап а сопЬпнонв кыпр1е, йеп йе йясгеге чегыоп ог(415) Ьесопгек -! «-1 Р ~~ 2и'иг ггл ~У (шл)г з=о зм (4.1б) »!гоге го = с "'~". 5!псе ш гя а ргоийче л-й гоог о( нпьу очег йе сотр!ех пшпЬегк, йе й» гсге чегв)ои о((4 $5) $$!чеп Ьу (4.
$й) 1к ргесйе!у йе (огкчы«$ ОРТ о( йе ргессг$1ин кесшш '!Ъ!к скр1нни Логч онг Йксг«$« $5шпсг !гнив(опи нен Ьк икте. $$ гч!!! а)ко Ьсй нв )п ТЬов, йй ргоЫет сап Ье ко(чег( нк!ин егйег $.за«анне $пьнро1аьоп ог Ые»поп Имгро!айни (с(.
СЬаргег 5) аг йе гег(нсег$ сок! о( О(л~) орегаьопк, ап!тргочегпепг ог опе оп)ег о( тани(гнг(е. Ноыечег, ак тепьопег(1п Яесг(оп 4.4, соичегьи5 гтт а сое(((с1епг г(отав го а тог(н1ы г)отан ш ш)ге и5чапш5е о( йе е((1с)епг пш!ьрьсайоп )и а тог)н!аг г(опгапшн апг( йеп сопчепшн Ьас(г ада(п, Н оп!у нкегн1»Ьеп Ьой напк(опгн сап Ье г(опе гч!й 1екк йап О(лг) орегаьоик. Непсе» е кое)г а (акшг шчегзе напк(опп. А5ып рппйьче гоогв о( нпьу апг( йе соп екропг$)ин Ронг)ег рот!к ргоч!г(е йе сопесг тесЬашып Ыа йе ОГГ.
$$(Ге позе йаг напк(оптпц ргоЫетк ггот опе г(отти го а кесопг) (ытр!ег) г(отып ап0 йеп Ьас)с анап Ы а сопнпоп гесьпн)не $и пшйетапск апг$ !гк ге1агег$ йкс(р!шея. $иг(сей а ~ганг(агг$ гесьпа)не ш епрпеег)пй 1о» 1ече! Лиане ргосекппй пъйек нке о( йе Роы1ег $гапкгопп ш сопчегг (гот йе гнпе г(ота)п го йе (гег(пенсу г(огпып апг( Ьась анти. ТЬе нг)чапшне ог" кось а папкгоппаьоп И йаг йе (гсг(неону 0отып гергезепгк а тоге пагнга1 спч4гоптепг (ог Гонии!аг!пн апг$ зо1ч!пн ргоЫепгк. А18ог!йпп Еог Согпризет А18еЬга 1ЗО 1пчегип8 оог папа(опп.
1п йе сопйпиоив апа1у6с саяе. Яе 'шчегяе Во«пег папа(опп ргоЫегп Ы я(пи!аг го йе Роиг!ег !галя(опп ргоЫепз. 1Е р(я) 81чеп !п (4.15) !в йе Роипег папа(опп оЕД(х), йеп йе зпчегяе Роипег згяпягопп Ы 8!чаи Ьу Е()= — )р() -"™«ж 1 (4.17) 2к ТЬе с(!ясзезе згапв(опп сопеяропйп8 со (4.17) Ы 81чеи Ьу л-1 л-1 Е; = — 2, рз (е зл" и) = 1!п. Т ря (со ') и яаз ео «Лего оз =е™мл п а рплйпче и й гооз оЕ ил!зу очес йе Ве!д о(сопзр1ех папЬегя.
1)ее(п(ьоп 4.2. тье зпчегяе сезясгеге Роигеег ггаарогпз (еезрт) еог а Роипег ве1 ое ро!пгя (4.12) Ы 8(з,п., . «.-з)(ЧО, Чл 1)=(Чо ° Ч»-1) зчЬеге л-1 суз =и .2,41 (со Е), 1 аз аиз( Оз зя а рппййче и-й гоог оЕ ипЬу. ТЬеогепз 4.2. ТЬе Е)гТ апс( йе П)РТ !галя(опп аге 1пчегяея оЕ еасЬ ойег.
Ргоой ЬезО <р < и. ТЬеп (ОК)" =(ОЗ")Г =1, пзс( (ОЗР)«1, Ыпсе со ы а рппииче и-й гоо1 оЕ ипЬу. 88псе (хл — 1)=(х — 1).(х '+х" з+ . +х+!) Озг зпия1 Ье а гоо1 оЕ 1Ье яесопс( Еаспзг, 1Ьа1 Ы О=(озр)л-1 +(Ок)"-2+ . +(Ок)+1. (4.18) Ву пзи!пр!у(п8 йгои8Ь Ьу со я сл 1), 11 1я а1яо рояЫЫе зо яее йаг ес!иаг!Оп (4.18) !я згие Еог -и < р < О. ОЕ сошяе, чгЬеп р = О йе п881 Ьапс! в!с(е ОЕ ециапоп (4. 18) «лй Ье п гайег йап О, ТЬе юпр(е ОЬвезчапопя оЕ йе ргвлоия рага8тарЬ ргоч)с(е йе зоо1я иесеявыу Еог а ргооЕ оЕ ТЬеогпп 4.2. Яиррове йаз тс,„„.-). (ао,..., а„,) =(ао,..., а„,) 1Ьаз !я, 4.
Апйп)епс оГ Ро1 упоппа)в !3! л-1 и) = 2.а-(со))), 1ог !'=0,1,..., л-1. )о Рог апу !п1еаег )г ше Ьаче л-) и .2', а;о) шо в!псе )Ье 1пвЫе ватппабоп )чог)(в ош !о О !п йе савва огЬеп ! — Г и О, ап)! и гп йе саве «Ьеге Г = /г. $/в!па Г)еО)п)поп 4.2, )че оЬ!а(п В(),е„„,Ш»'(ИО П„))=(па и -1) вЬо)ч!па йа) У(! щ л. ~) !в !Ье )пчегве о(Т(! щ „.л). ТЬ!в ргочев ТЬеогегп 4.2. 1п )еппв оЕ ош гпа!пх 1п1егрге!абоп 1ог йе !п(егро!абоп, ТЬеогет 4.2 а!чев йе )пчегве оГ йе Чап((еппоп()е гпа1пх ав 1! . 1 — 1 -(л-1) Ч(1, о),..., шл ') ! =л ' -(л-1) -(л — 1) -1 1, (! -1 -(л-1)) Ехап)р!е 4.7. 1.е1 йе Г!е16 Ье Х)1 «!й !О = 4, а рг!плоче 4-й п)о! оГ шп(у.
ТЬеп йе 'ШЧЕГВЕ !Галя(ОПП 5(1„!в!1) Гя а!!ПЕат !Гаия1ОППабОП ЕГШП (Х)))" )О !(ВЕ(Е Ьалйа ая ИВ шап1х чч)й !еврее! !о йе в(ап(!ап) Ьав!в 4' 1'Ь)я !в еав!!у сЬес)гег) !о Ье йе шчегве оГ йе п)ап!х (4.14) оЕ Ехагпр1е 4.4. ТЬе в!риГ)сапсе оГ ТЬеогегп 4.2 !я йаг Ьой йе Еопчап( ап(( )пчегве !гапвГоппапопв .иг Рош!ег папяГогпп.
ТЬов йе )тапяГогпшбоп Ггогп соеГГ)с)еп! (Гоп)ап го гпо()о!аг))оп)а!п и ч!а йе са!со)апоп о( 1 1 1 1 11316 4 116 1 16 14164 л-1 л †! и '. ,')" 2, а, оУ)»(о в) )е) )хо л-1 л-! и ' 2, а. 2', оу)»гп вг ) )м) )=о л-! л-1 и ' 2, а, (2; о)О "У) = а! ) 1'л) !3 13 13 13 !3 !6 4 ! !3 4 13 4 13 1 4 !б 1Зг А)аопгпгпв Еог Согпряег А)деЬга ТГг, -~)'Р = г( яЫ1е йе папвгоппапоп (гоги йе гподп1аг г(отап го йе соегйс!епг г(огпяп !в г!а йе са1сп!айоп о( и 'Т(г -~ и -и~'г( = р. -г ТЪе согпр!ехЬу !п е!йег саве !в О(л.(пал), п4псЬ гв гагах йап 0(и~). 4.7. йАБТ РО1 ХЫОМ$А$. МИЕТ1И.1САТ10г ) 1.ег пв поги гегшп го ош опупа) доа), йаг о( гпп!ар!у!па гч|о ро1упогп!а(в а(х) апг( Ь(х), 1г ош ро!упоппа1в аге о1 дехгее т апг) и, апд ош осе%с)епг г!е!г! Р Ьав а гщпйег( Аг-гЬ гоог ог" пшгу еЬеге Аг !в йе ягвг роггы о( 2 агеагег йап йе япп оГ йе гео де(реев, йеп а (авг пай!р!1сапоп а)аопйгп !в а)реп Ьу А!аопйгп 4.5.
ТЬе Гав! гпп1пр!!сапоп а)аог!йгп аЬоче Ьав а согпр!ехЬу ог" О((т+л) 1оа (т+л)) сотряег! я1й 0(т.и), йе согпр1ехЬу ог" йе с1авяса1 спейси, а сопвИегаЫе Ьпргочепгепг. Ог" сошве, йй доев пог га1ге !пго сопяг(егаг!оп йе сола!апов о( ргоропгопа1Ьу ог" еасЬ тегЬсг). 1п ргасг!се, 4ереп4)па оп йе спейс ог" геспгяоп пвег(, йе Гав! гпейог1 гв Ьепег йап йе с1авяса! гоейог) арргохппаге!у реп т + и > 600 (сГ. МоепсЬ 19!).
133 4. Апйгпет!с о( Ро1упопиа)г Ехатр!е 4.8. Ми!Ор1у йе !что ро!упопиа!а а(х)=Зха+хт-4х+1, Цх)=хт+2хх+5х-3 ш йе Ке!4 Х4$. ()ае 14 аа а рппйбче 8-й гоот оЕ ишту $ог йй ргоЫепх Ггогп йе ртечюиа зесгюп чче Ьаче А г- РРТ(8,14,а(х)) =(1, 9,-19,-18, 3, 16, 19, — 3) апд В т- ГРТ(8, 14, Ь(х)) = (5, 5, О, 14, -7, -6, -10, 16). Ми18р!у)п8 йене го8ейег 81чеь С т- (5, 4, О, -6, 20, -$4, 15, -7) и4псЬ (а йе РРТ оЕ с(х) = а(х).Ь(х).
То оЬтаа с(х) Егогп С чге г)о с < — 8 ~РРГ(8, 3, — 7хт+ 15х — 14х~ + 20ха — бх~ + 4х + 5) = (-3, 17, 20, -11, 13, 7, 3, О); Ьепсе йе ргог)ист Ь с(х) = Зх~+ 7х~ + 13х — $1хт+ 20х~+ 17х — 3. 4.8, СОМР()Т1)ч)О РК1М1Т1ХК Ь$-1Ь КООТЯ ОР ($)ч(ЕТХ 9(гЬеп арр!у1п8 йе РРТ Еог ро1упоппа( пш11!р11сайоп очег а 8(чеп Ке!д Р, пе ате !асад ъ(й йе ргоЫегп оЕ Кпб)п8 а рппйтче л-й гоот оЕ ипЬу $п К 9(ГЬеп Р Ы йе йе!д оЕ согпр1ех пигпЬега йеге Ы по ргоЫет п(й г)ететпппш8 а рппйтйе л-й гоог оЕ ипЬу Еог а $0чеп гпсе8ег л.
А ягпр1е ехагпр1е оЕ аисЬ а рпгшпче гоог )а тлгп $'ог ехатпр!е, еклп = (~)3+1)д2 ~т а рпгшт(че 12-й гоог оЕ ипЬу очег йе согпр1ех пигпЬегз. %Ьеп г)еа))п8 в)й ойег ЙеЫа, 1ог ехатпр1е, йе Е(п)те Ке!т$а Хр, йе а!гиаОоп Ы пот аа аппр1е. 1п 1$иь аес0оп иге дйсиаа йе ргасОса1 ргоЫегп оЕ Кпд1п8 рт)гяпче л-й гоотв оЕ ип!!у Еот Оп(те КеЫа. ТЬеогеш 4.3.
ТЬе Оп!ге Ле!д Х Ьак а рппит)че л-й гоот оЕ ипЬу $Е апг) оп1у )Е и 48чЫеа р — 1. Ртоой 11 от !а а рппиОче и-й тоог оЕ шиту Ы Хр, йеп йе ает оЕ Гоипег ро)пта (1,от,..., от" 1 !опиа а (сус0с) аиЬ8гоир оЕ йе пш)пр1$саОче роир оЕ Хр. Бйсе гЬ)а гпи10р1!са0че 8гоир ьгп р-! е)ептепь тчЫ!е гпе апЬ8гоир Ьаг и е)егпепга, (.а8гап8е'я йеогепт $гот 8тоир йеогу ~ ! 1$сгятегп (41) )гпр)!ег йат л пюаг 4)ч)г)ар — !. А18опйип Гог Сошршег А18еЬга 134 Сопчегзе1у, ве Ыю н Ггош Гш!се Гге1с1 йеоту йат йе пшЫр1!сабче 8гоир оГ йе ВеЫ Х !з а сус!Ы 8юир (йй !з тгие ш 8епега1 Гог а110шсе йе1сЬ оГоп!егр !ог аписе 1пте8ет Гс). 1.ет а Ье аиу 8елепиог оГ сЫз пш! Йр1тсаиче 8тоир, йас !з Х = ( 1, а, аа,..., а" г) члй аГ ' = 1. ) от л Ье ел!псе8етвЫсЬс!)чЫезр -1.
1(везет со= ай ')'" (4.19) йеп а"=аг '=1: зо, со В ап л-й гоос оГ ип!су. Рог 0 < /с < л, ве Ьаче йе !пес(иа(1су (р — 1) /стл «р-1), зо со =ай ) '"в1 (4.20) Ес!иайоп (4.20) )шрИез йат со Ь а рппиВче л-й гоос оГ ишсу, согпр!ейп8 оиг рсооГ. Ехаптр1е 4.9. 1и Х4! ве Ьаче 8 ! (41 — 1) зо йаг йети аге рпииВче 8-й гооа о( шиту ш Хат. 1пс)сес), йе е!ешепс 14 !з а рппийче 8-й гоос оГ ипЬу!и Хат. Тие ргоЫеш не пои Гасе ь йат, а1йои8Ь ве шау Ьпов виси а рпгшйе л-й гоос оГ ип!су ех(зсз (п Хр, ве Ьаче по и ау оГ с(ештпипш8 иЬат йас рппибче л-й гоос пи8Ьс Ье.
Опе арргоасЬ тз со сЬес)с еасЬ го !и Хр апс) асор вЬеп йеге В опе заиз(у!и8 ш" = 1 аис) ш" и 1 !ог /с < и. ТЬ(з (з а чесу созс(у ргосес)ше Ьовечег (аз соиМ ве11 Ье 1ша8!пес0. А Ьеиег арртоасЬ поиМ Ье со Гспс( йе рагс(си!ах а йас 8еиегагез йе ши16р!1сас!че 8юир аис) йеп изе ециайоп (4.19) Со с)е(ше ш. !и оиг сазе, ве аге асшаПу (пшгезтес( 1п рпптез р аис) шсе8егз л оГ йе !опп л = 2', Гог вЫсЬ йете В а рппис!че л-й гоот оГ ип1су (и Х„. Ву ТЬеотегп 4,3, Х Ьаз зисЬ а тоос Е аис) ои! у Е 2' сВчЫез р-1, йас а,!Г аис) оп1у !Г р гз а рппсе оГ йе Голи р =2'.Г+1 Гот зопте осЫ !пте8ег lс.
ЗисЬ рг!шез ате са11ес) Роиг!ег рпхлег. !и сЬе сазе оГ Роиг(ег ргппез, йе Ьпле Гоке шейос( гпепиопес) ш йе 1азс рага8тарЬ йгез Ьаче гоше исси!. ТЫз !з Ьесаизе йете аге а 1аг8е пшпЬет оГ рппи6че е1егпеиь 1и Х !и й!з сазе. То зее Ьов шалу, ве с(поте а Гипс)атпеиш( тези!с Гхош апа1уг)с ишпЬег йеоту. ТЬеогеш 44. 1ес а апс) Ь Ье сво ге!аиче!у рпше !псе8егз. ТЬеп йе иигпЬег оГ рпшез <х 1и йе апйше6с рго8тезз)оп а/с +Ь, /с =1,2, 135 4. Ап0ипефс ог Ро!упоииа) в !в арргохииаге1у «гЬеге ф(а)!в йе Еи!ег р!и Ьзпсйоп (!.е. Йе пшпЬег ог" Ыге0егв 1оа х.ф(а) 1евв йап апд ге1аяче!у рпше го а). Бйсе а)! очаг) 1п1еаегв 1евв йап х" вге ге!аяче!у рппге го 2", апг( йеве ассоипг !ог арргох(- гпаге!у Ьа)г" йе гога! пшиЬег оГ 1пгеаегв, гче Лаче ф(2') = 2" '.
ТЬеогеш 4.4 йеп ш0в ив йаг йеге аге арргохипаге!у !о0к 2" г Рош!ег рппгев 1евв йап а и!чеп !пйцегх. Ехашр1е 4.10. 1.ег х = 21', гчЫсЬ гергевепгв йе ивиа1 яхе гегрше4 1ог в(па1е ргесЬгоп !игеаегв ги шоя согириштз. %Ьеп г = 20 йеге аге арргохгшаге1у 2вг 19 1оц(2Я) ф(2~~) рпгиев ог" йе аппп 2'чс+ 1 афй е > 20 1п йе !пгегча! 2 го 21', Апу висЬ Роипег рппге сои!4 Ье ивег) го сошрше РРТ'в оГ яхе 2!о. Ечеп йоиаЬ чге !спочч йаг чче сап иве Ьпие гогсе го йид оиг рг!ийяче аепегагогв о( йе пш10р!каиче агоир о( Хр (аиг! соиевропс1!и01у ош рпиииче гоогв ог ип!гу), гче я!11 пеег) а яшр!е игау го гесоап!ве йаг а а!чеп е!егпепг Ы а рпгшиче аепегагог. Рог ЙЬ гче Ьаче ТЬеогеш 43. Ап е1етепга !в а аепегагог о(йе ши!йр1!сайче агоир о( Х 11( ага-гхг и1 пюа р Гог ечегу рппге (асгог, г), ог йе 1пгеаег р — 1. Ргоой ТЫв !в а ятр1е сопвециепсе ог (.аагап0е'в йеогеш Йош роир йеогу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
