Geddes, Czapor, Ladahn - Algorithms for Computer Algebra (523146), страница 51
Текст из файла (страница 51)
6. Ыечггоп'в 1гегапоп апй гйе Непзе1 Сопзпасйоп 253 Ро1упопйа!])!орпапйпе Ег!пайопв]п Х ~[хг] А 8епега1 во1ппоп со гЬе ргоЫет ог" зо1ч!п8 ро1упоптй ййорЬапйпе ег!пайоов Ы гЬе пп8 Х г[х,] Ы оЬга!пей Ьу арр1у!п8 нее!оп'з !гегайоп го 1!(г йге во1пйоп !п Хр[хг] ор т а во! пйоп !п Х [х,].
ТЬе "ехгепйей Еос!Ыеап" ргоЫет го Ье зо!чей Ы го йпй ро1упопйа1в гр)(х,), Гй)(гг) е Х [х,] ФисЬ вайа[у гйе ег]пайпс зр)(х,) и(хг) + г(г)(х,) ю(хг) и 1 (той р') гчЬеге и(хг), и (хг) и Х [хг] аге Ьйчеп ро1упопйа)з зосЬ йгаг фр(и(хг)), фр(ю(хг)) аге ге!айче!у рпте ро!упопйа!в Ы гйе Епс1Ыеап йотап Х„[х,]. ТЬе щоайоп со вЫсЬ |че чй11 арр1у Неьггоп'в Ьеийоп !в С(в, г) = в и(х,) + г гч(х,) — 1 = О. ргосеей)п8 вв !и ргеиопь весйопв, и гче Ьаче гЬе огйег-8 р-ай!с арргохйпайопз в( 1, г( 1 го йге ьо1пйоп рак в2 г апй !г гче оЬга!и сопесйоп геппв Лг(г),йг(г) гчЫсЬ ьайзгу гЬе гь]пайоп гг,(ь(в>, г(ЬГ) ч!в(ь) + а(ь(Ь), гГГ>) дг(ь) п -а(в(ьг, г(Ь)) (той РЕН) (6.80) гЬеп гЬе огйег-(8+1) р-ай!с арргохапапопь аге 8!чеп Ьу в(г") = в(г'+ Аг(г), г(г") = г(ь'+ гьг(ь).
ЪУг]йп8 гЬе сопесйоп геппь т гЬе !опп Лв® =гг(х,)Рг, Аг(г) = гг(хг)Рг гчЬеге вв(хг), Гг(хг) е Хр[хг], зпЬзйгпйп8 Гог ГЬе Рагйа1 йепчайчез. апй ййчЫ!п8 йпоп8Ь ЬУ рг, ецпаг!оп (6.80) Ьесопгев 1-в("ьи(хг) — гйг гч(хг) и(хг).вв(хг) + гч(хг) гг(хг) п (той р). (6.81) Р ТЬе огйег-1 р-ай!с арргохппапопь вй),г(г) а Х,[хг] гог йге во!пйоп ог ег)оайоп (6.79) аге об!а!пей Ьу йге ехгепйей Еос1Ыеап а18опгЬпг (ог, !п гЬе сопгехс ог" Р!8оге 6.2, йгеу Ьаче а)геайу Ьееп острогой т А18опйип 6.1 Гог гЬе птчапаге Непье! сопзппсйоп). Рог ь = 1, 2,..., 1-1, егргайоп (6.81) сап Ье зо!чей !ог йге сопеспоп геппз Н(х,), гг(хг) а Хр[хг] Ьу ТЬеогегп 2.6, гЬпв 8епегапп8 йге йезпей ьо1ойоп ог егргапоп (6.79). ТЬе Го!!оайп8 гЬеогет зЬогчз гЬаь гче сап зо1че, 1п йге пп8 Х йхг], гЬе Ро1Упопйа) сйорЬапйпе ег)оайопв мгЫсЬ апзе Ы гЬе то! Ьчалаге Непве! сопзппсйоп.
А!8оьйпп гог Совпровег А18еЬга ТЬеогегп 6.5. Рог а рпте тге8ег р апд а роадче ипе8ег 1, 1ев и(х,), и (х,) и Х в[хв] Ье отчапаве ро!упопьа!з яадзгу!п8 (1) р [ [сое!в(и(хв)) апд р [ 1сое(г(вч(хв)), (И) фр(и(хв)) апд фр(мв(хв)) аге ге!адче!у рите ро!упопда[з т Х [хв]. йоге ех!зв ип(в[пе ро!упопда[з ТЬеп вог апу ро!упопйд с(хв) и Х [хв] п(хв)„ г(хв) и Х [х,] япсЬ йав п(хв) и(хв) + г(хв) ив(хв) п с(хв) (тод р в) (6.82) (6.83) де8(п(хв)) < де8(ив(хв)). Могеочег, !! де8(с(хв)) < де8(и(хв)) + де8(вч(хв)) гЬеп г(хв) Яаьзйез (6.84) де8(х(хв)) < де8(и(х,)). Ргоовв 'ч(ве (пяв яьочч ех1ыепсе. ТЬе ехгепдед Еьс1вдеап а18опднп сап Ье аррИев1 во совпрпве ро!упоппа(з я(')(хв), г( 1(хв) п х [хв] пвьз()пп8 йе ев!ьаьопз я(в)(хв) и(х ) + вьв(хв) вч(хв) п 1 (пвов1 р).
(6.85) Ву ТЬеогевп 2.6, ев!ьаьоп (6,81) сап Ье зо!чед гог ро!упопда1я яя(хв), гя(хв) и Хг[хв] (ог зьссезз[че тге8евз в! < 1, пвьеге пе дейпе я("в(х,) =я!'1(хв)+яв(х,)р+ .. +я!,(хв)р" '; г!'1(хв) =г(вв(хв)+г,(х,)р+ +гя в(хв)рв ', апд вче тгпв ргоче йав яьв(хв) и(хв) + в( )(хд) ю(тв) и 1 (тод р"). (6.86) чвве члП ргоче (6.86) Ьу 1пдьсьоп.
ТЬе саяе ! = 1 И 81чеп Ьу прладоп (6.85). Зьррозе (6.86) Ьо!дя !ог зовпе х > 1. ТЬеп подп8 йаг яь'ь(хв) = я( в(хв) + яг(хв)р" апв1 г! "~)(хв) = гр)(хв) + гв(хв)р пвЛеге яв(хв) апд гг(хв) аге йе зо1ьдопз огп!ьаьоп (68!), пеьаче я(+ )(хв)и(хв) + Г( + )(хв)ив(хв) = ЯЬ>(Хв)и(Хв) + В(")(Хв)ВЧ(гв) + Р~[зв(хв)и(Хв) + Гв(Хв) И (Хв)] П 1 (тпд РВ+В) ччьеге вче Ьаче аррИев1 гярвадоп (6.81) аввег пв!ьр1увп8 И дпоь8Ь Ьу ря. Тььз (6.86) вя ргочед 1ог аП х Ь 1, апд т рагдса!аг 1ог )в =!. 6.
Ь[емоп'з 1сегабоп апс$ йе Непзе1 Сопзиисиоп 255 Ь[оис йе с[езнес$ ро!упсала]з а(хс), г(хт) е Х с[хс] запасу!п8 ос[пас[оп (6.82) сап Ье са]си1асес$ ехасс]у аз 1п йе ртоог" о[ ТЬеогесп 2.6. Зрес[т[са!1у, йе ро1упопиа1з а(х,) = з(')(х,)с(х,) апс$ г(х,) = г(с)(хс)с(хс) заизгу есрсабоо (6.82) апс$ йеп со тес]исе йе с$е8тее псе арр1у Бис!!с]сап дпбяоп ог" о(хг) Ьу и (хг) у]е!с$сп8 с!(хг), т(хс) и Х ю[хс] зпсЬ йас а(х,) - =ю(х,)ф(х,) + т(х,) (пгос$ р') счЛеге с[е8(т(хс)) < с[е8(и (хс)).
ТЫз с]!ч[з]оп зсер счс11 Ье чаЬс$ сп йе пп8 Х [хс] Ьесаизе сост!!с!оп ($) 8иатагиеез йас 1сое]г(сч(хс)) !з а ипп сп йе пп8 Х (зее ТЬеогесп 6.3). Р[па$!у, дейшп8 сг(хт)=т(хт) апс$ г(хг)=г(тс)+с!(гг)и(хг) е Х [хг] ес[иапоп (6.82) ясс$ йе с[е8тее сопягаип (6.83) аге геа6$!у чепбес$. То зЛоис ип(с[иепезз, 1ес ос(т,), сс(хс) и Х [хс] апс$ аг(хг), гг(хс) и Х [хс] Ье пчо рапз о( ро!упопиа(з зас!згу!п8 (6.82) апс] (6,83). Зибпасбп8 йе ьчо 6$ггетепс ес[иаиопз ог" йе аппп (6.82) у[е1с[з (о;(хс) — аг(хс))и(хс) я — (с,(х,) — тз(хс))ю(хс) (гпос1 р'). (6.87) А! зо, йе с[е8гее сопягипс (б. 83) заизйес$ Ьу а,(х, ) апс$ аг(хс) у1е!сЬ (6.88) с$е8(ос(хг) — аз(хг)) < с[е8Оч(хг)). Та)оп8 йе сопфпсепсе (6.87) пюс$и!о Р исе Ьаче а ге!аС$опзЫР 1п йе с[опий Х [хс] счЛ]сЛ, со8есЬег ъч!$Л сопб!с!оп (И), ппрйез йас фр(сч(хс)) 6$ч]с[ез фр(ас(хг) — ат(хг)) 1п сЬе с(опсасп Х [х,].
Л]ог[п8 (топг сопеОСсоп (с) йас ф (Я(хс)) Ьаз йе загпе с$е8гее аз и (хс), (6.88) 'ппр1!ез йас о,(хс) — аг(хс) я О (пюс] р) апс$ сЬеп п той оп з стоги (б. 87) йас сг(хс) — тг(хг) я О (пюс$ р). Ъ'е посч с1итп йас йе ро!употп]а!з ог(хт) — аг(хг) апс$ гт(хс) — гт(хг) заг]з!у]п8 (6.87) аге с]$ч!з!Ые Ьу рс (от аП роясгче ппе8егз Ь з !. ТЬе ргоо! Ь Ьу !ос[осипа. ТЛе сазе [с = 1 Лаз )изс Ьееп ргочес1. гарроте йас йеу ате с$$ч[з]Ые Ьу рс !от зоспе Ь <!. ТЬеп сче пгау с!сапе йе ро[упопиа!з а(хс) =(а,(х,) — а,(хс)) грг апс$ р(хс) =(гг(хг)-тз(хт)) lр' ппд.
с$$ч(с]$п8 сЛгои8Л Ьу р~ сп соп8сиепсе (6,87) исе Лаче о(хс)и(хс) и — ]3(х,)ю(х,) (псос] р' ). Иу гсрсабпф йс агфюпеы из<с] аЬочс, яе сопс! ис]е йас А18огсйпск Гог Согорпсег А18еЬга а(хс) пО(пюдр) апд [$(хс) »0 (пюд р), 1.е. а,(хс) -ас(хс) апд с,(хс) -ес(хс) все д!чЫ!Ые Ьур ", счЫсЬ ргочез йе с1апп. рспп(!у, сче Ьаче ргочед йас п,(х,) и аг(хс) (гпод р') апд г,(х,)ю гз(х,) (пюд р') »ЬЫЬ ргочез опй!пепезз сп йе пп8 Хр [хс[. 10паПу чге пеесс со кЬочг йас йе с$е8гее сопкиаспс (6.84) Ьо1дз. Ргопс (6.82) сче сап счг!се с(хс) и (с(х,) — гг(х,)и(хс)) / и (хс) (пюг$ р') апд йе д!чск!оп Ьеге Ы ча!Ы сп сЬе пп8 Х ах![ Ьесапзе 1соеЩи (хс)) ы а пп1с 1п Х о Ьу соп- д!с(оп (1).
Ву йсз квасе сопд!поп, » е Ьаче (6.89) г$е8(г(хс)) = де8(с(хс) — а(хс)и(хс)) — де80ч(хс)). Ь(осч 11 де8(с(хс)) > де8(о(хс)и(хс)) йеп Ьосп (6.89) де8(с(хс)) < де8(с(х,)) — де80ч(хс)) < де8(и(хс)) де8(с(хс)) = де8(а(хс)и(хс)) — де80ч(хс)) < де8(и(хс)) счЬеге йе 1азс асс[па)ссу (оПо» з мгспс (6,83). ТЬ»з (6.84) Ы ргочег$. Мп!С!чаг!а(е Непве! Сопвкпзск!оп 'гче аге посв геаду со дече!ор йе пю16чаг1асе Пепега1аапоп о( Непзерк 1епппа.
9(ге розе йе ргоЫегп о1 ПпгПп8 пю16чапасе ро!упопда1к и(хп, .,, х,), и (хп..., х,) и Х 4хс,..., х„! »ЬссЬ када!у йе соп8гпепсе а(хс,..., х„) — и и »0(пюдр') (6.90) зосЬ йас и(хп..., х„) ю иаг(х,) (спод <!, р'>); ю(хс,..., х,) ю и С )(хс) (пюд < 1, р >); (6.91) счбеге и(с)(хс),сча)(хс) и Х ~[хс[ вге Ьдчеп пшчапасе ро1упоппвсз»дисЬ забк(у (6.90) г псод»1о1. Неге, р 1з арпгпе!псе8ег, ! Ы арок!дче 1псе8ег, и(хс,..., х„) а Х 4хс,..., х„[ Ы а 8Ыеп пю!дчапасе ро1упоппас, апд 1= <хс-аз,..., х„-а„> ы йе 1сегпе1 о! а пспсПчапасе еча1»адоп ЬопсопсогрЫкпс. $)епос!п8 йе дегдгед зо!одоп ро!упоппа1к Ьу й апд й, сче счП! дече!ор йезе ко1шюпз сп йеи 1-агПс Гогпск: ав 1оп8 ак де8(С(хс)) < с$е8(и(х,)) + де8(сч(хс)) ак кгагег$.
ОСЬепч!ке $1 де8(с(хс)) < де8(е(х,)и(хс)) (сп счЫсЬ саке йе кгагес$ де8гее Ьоппд (ог с(хс) а1зо Ьо1гЬ Ьесапке о1'(6.83)) йеп йопс (6.89) 6. )к/евйп'к Иегайоп ап|$ |Ье Непке! Сопягпсйоп 257 й = и<') + Ли<') + Ли<2) + . + Ли<"); <1)+Л <1)+Л <2)+, Л <и) (6.92) вЬеге </ |к йе гпахипшп |о|а1 <)еагее оЕ апу |епп |и й ог в, и<') = ф<(~, и < ) = фг(в), ап|$ Ли<|), Ли <") п 1", Еог /| = 1, 2,..., |/.
Ргоп) Бесйоп 6.2 ве $|пов йа| |Ье 1-ад!с гергекеп|айоп оЕ йе ро1упоппа! и !к ргес[ке1у йе пп|!Ьаапа|е Тау!ог кепек гергеке|найоп (6.14), ТЬе 4-й соггеспоп |епп ли<2) и /~ [к йе |епп |и (6.14) ое <ом Лей!ее 4 в!й гекрес| |о 1 ап<$ $| )к гергекепге|$ Ьу А пекю|$ яитипапопк |и йе Еоггп г Ли<1) =;); 2; . 2; и;<Х,)(ХЬ - а! )(Х<;а<,) (Ха-ай) (6.93) ||=2 ||=|| ||=|| | вЬеге ! =(|1,..., /1) [к а кесгог кпЬкспр| ап|$ и|(х|) а Х |[хг). Б!пп!аг1у, |и йе 1-аййс и гергекеп|айоп оЕ й йе Е-й соггесйоп |ег|п Мсек йе Еопп и Лв"- Х Х " Х;(х))(;,— ЬХхй- 6)" (.„- 4) |,=2!|--|, а=а вЬеге в;(х,) и Х йх|). Ош ргоЫе|п пов !к |о со|прае, 1ог еасЬ /| = 1,2,..., й йе /|-|Ь сопесйоп |еппк Ли<к), Ли <1) )п (6.92), [ег и<~), и <~) <[епоге йе ог<[ег-Е !-26<с арргохипайопк |о й, в Б(реп Ьу йе Епкг /| |еппк $п (6.92), [.ейпй Р(и, в) Лепоге йе 1е/г-Ьапйк)йе оЕ (6.90), Ь/евгоп'к пега|юп Еог ко! |Лай Р(и, в) = О !п Х |[х|,..., х„) гайек йе Еопп оЕ йе сопйпгепсе е<[папоп в<)Ли<) + и<)Лв<") я а(х|,..., х,) — и< ) в< ) (пю<$ < 1 +',р'>) вЫсЬ |гюя Ье ко1че6 1ог йе со|гесйоп гегп)к Ли<"), Ли <") и 1" апй йеп и< ' )=и< )+Ли< ) и<+ ) =и< )+Лв< ) в!11 Ье оп)ег-(/|+1) 1-ай!с арргохппа6опк |о и, в.
Ь)ов япсе и<~), и <~) кге ог<)ег-/г 1-а<$!с арргохппайопк ве Ьаче а(х|,..., х„) — и< )и < ) а 1 ап<$ йеге(оге йе г)аЬ1-Ьап<$-к)<$е оЕ (6.95) |пау Ье ехргекке|$ ш йе Еопп с|(х,)(ха-аа)(л;,-ай) (х)„-<га) ||=2 ||=|| г|е)|!|ой йе |$екпе|$1-агйс сое/Е|с!еп<к и|(х,), в|(х|) и Х [х,) вЫсЬ с$еЕЫе йе сопесйоп и.|ив <6.93) ап4 <6.94). Ь/о<с йа| к!псе й|к |к а сопйгпепсе пю|$п)о 1 ве гпау арр1у йе гчз!паып Ыппошограсоп ф| ь йг )гй-ааш1ей<)е, у<сЫЬ|р йе Еойов|пр ро)упопиа< |ог коте соеЕЕ<с<епгк с;(х|) и Х [х|). БпЬкп<пг[пБ <п|о (6.95) й1к пекгед-кппппапоп |сргекеп|айоп 1ог |Ье пй1п-Ьап|$-кЫе ап6 а[ко йе пекка<1-кппппапоп гергекеп|абопк (6.93) ,иЫ (6.94), йе сопагпепсе (6.95) пиу Ье ко!ге<1 Ьу керага|е1у ко)чйй йе Еойов1пй | опргпепсе Еог еасЫегпг |и йе 1-а6!с гергекегиа1юп в<|)га(х) + и<")и<(х<) п с<(х<) (п)ой < 1, р'>) 258 А18опйтв тот Сотрпзег А18еЬга бюрЬапбпе есрваьоп со яо1че !п йе ппВ Е 4хв] (ог еась вест 1п йе 1-айс гергевептаьоп зчт')(хз)ив(хв) + ив ~(хв)вчв(хв) и св(хз) (пни! р ) (6.96) счьесе и('в(хв), зч(зз(хз) е Е [хз] аге йе 81чеп ро!упоппа[в зп тье ргоЫевп (6.90) апс( (6.91) Ьезп8 во!част.
ТЬеогевп 6.5 ясасея йе сопс(вбопя впи!ег вЫсЬ йе сопбпвепсе (6.96) Ьая а оп!с]ое яо)оьоп ив(хв), зчв(хв) а Х 4х,]. ТЬе (о11оияпВ йеогезп топпа1!у ргочея йе ча1ЫЬу о( йе аЬоче впейос1 вчЫсь ь [споивп ая йе гпийчагва/е Непяе/ сопя/пист/оп. ТЬеогепз 6.6 (Мо!с!чаг!ате Непве! Сопвтгосбоп), 1.ет р Ье а рпгпе !птебег, 1ет / Ье а рояь бче !птеВег, ага! 1ет а(хв,..., х„) е Х 4хв,..., х„] Ье а 8[чеп тп!очаг!асс ро(упоппа!. 1.ес Р 1= <х2 — ая,..., х„-а > Ье йе )сете! о/ а тп!бчапазе еча)оаьоп Ьоспотогрь!вт яосЬ йас Р [ 1соеЩфв(а(хв,..., х,))). [.ет ив')(х,), и С )(хз) а Е 4хв] Ье ьчо ппвчапасе Ро1Упоппь а1я вчЫсь яапа!у (1) а(хз,..., х,) и и(')(хв)ив(')(хв) (впос( < 1,р'>), (В) ф,(и(0(хв)) апс1 ф (зч(вв(хв)) агеге!абче!урппзе !и Х [хв]. ро!упоппатя ТЬеп (ог апу тзебег х ~ 1 йеге ехйс пш1ьчяйате и("З, и ("З а Х 4хз,..., х,] /1 япсЬ ВЬас а(х,,..., х,) во и( Ввч! ) (спас! <1,р >) (6.97) и( ) и ив )(хз) (тост < 1р>), и С З ю зч( )(хв) (тост <1р >).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
