Geddes, Czapor, Ladahn - Algorithms for Computer Algebra (523146), страница 102
Текст из файла (страница 102)
7$ Ь(0) «,.(6)' Ь(0), г «г(8) (12.19) ч«Ьете с; (1 < г < пг) аге гье д!здпсг тоси аЕ)$(г) апд «;(6) (1 К г' < пт) аге дейпед Ьу «,(8) = ОСР(а(8) — с;.Ь(8)', Ь(8)) и Р(сг,..., с„)[6[. (тВ) Елт Е' Ье йе пдгдгпа1 а[ась»и(с ехгепз!оп Пе1д оЕ Р висЬ йаг а(8)/Ь(6) сап Ье ехргеззед $п йе Еопп (12.19) идгЬ сопя!алев сг и р" апд «дй «,(8) и Р'[О[. ТЬеп Р' =Р(г,,..., г )»«Ьеге г, (1 З( Зпг) иге йе йвдпст гоояя о($$(т). ТЬеогегп 12.7 (Койзте)п/ТгаВег Мейод — Е.оВалтьпис Саве).
1.ет Р Ье а Ве[д аЕ е1етпепгагу Еипспапз «дй сопвгапс Ве1д К. Ьет 0 Ье гтапясепдепга! апд 1оВапйпис очег Р (!.е. В' = — Ест вогпе и и Р) апд виррояе йаг йе папзсепдеппд е1егпептату ехгепз!оп Р(8) Ьаз и' йе загпе сопзгапт Ве!д К. Е.ег а(0)/Ь(8) и р(0)»«Ьеге а(0), Ь(8) и Р[8[, ПСЕ»(а(8), Ь(6)) = 1, дед(а(6)) < деВ(Ь(0)), апд Ь(6) $з тпоп1с апд п)саге-(гее. 538 А!вопйшк Еог Сошршег А]веьи Ргоо[с Биррозе йас ~ — Ь е!ешепсагу. ТЬеп Ьу [кои«$$[е'з Рппе[рсе, га(6) .
3 Ь(В) о!в), ю «;(8)' — = о(0)'+Хе,— ' Ь(6) ' , ' г(0) (12.20) вЬеге с, и К апс$ «;(В) е Р"(9) (О Б с Бш), вЬеге К' с[епосез йе пипипа[ а1веЬга[с ехсепзюп оЕ К пееекзасу ш ехргеш йе [пшвга[ апс[ Р' с[апоша Р ийй 1сз сопиапс Е[еЫ ехшпс[ес[ со К . ««[йоис 1ош оЕ Бепета[[су, ве пшу акяппе йас «;(6) (1 Б с' < ш) аге ро[упопиа!з 1п Р*[Щ (Ьу арр[ушв йе пг!е оЕ!овысйпп).
Могеочег, из[ив йе агвишепс ргезепсес1 ш йе ргооЕ аЕ ТЬеогеш 11.8, ве шау аззипш йас сг е К' (1 < Е < т) ые йзппес попхего сопзсапш апс$ сЬас «;(8) и Р"[О] (1 Б г' < ш) ате и[паке-Егее апс[ рапв[ке ге1аиче!у рпше. [Е «о(0) и Р" (0) сап Ье ехргеззес$1п йе Еоггп «о(8) = ~ — в!й р(0), с)(8) и Р'[6], ПСО(р(6), с((8)) = 1, (8) и(8) апс$ с[ив(д(9)) > 0 йеп «о(8)' сопсипк а Еассог (п 1ш с[епопипасог вЬ)еЬ й пос кс[иые-Егее.
(Рог а с]еш)!ос[ агвишепс аЬоис йе Еопп оЕ йе с[епчайче, зее йе ргооЕ оЕ (аои«$!1е'з Рппс1- р!е.) Б[пее Ь(6) [з ю[иаге4гее, ве оопс1а$е йы «о(6) е Р'[8]. Ь[ов Ьу ТЬеогеш $2.2, «о(0)' е Р*[6], Вис 1Е чо(8)' Ек апу поптего ра!упопиа1 йеп йе пВЬс Ьапс) з«8е оЕ о[иаВоп (12.20), вьеп Еотшес[ очег а сопипоп с$епопипасог, в[$! Ьаче а пшпегасог оЕ с[евсее Бгеасег сЬап ог есрса1 со йе с$ерее оЕ сй с(епопипашг. Б[псе йе 1е(с Ьых) к[с)е оЕ ес[иаВоп (12.20) зайкЕ!ез с[ев(а(9)) < с)ев(Ь(9)), ве оопс1ис[е йас «о(6)' = О.
'«С'е Ьаче кЬовп йас $1 з! — [з е1еспепсагу йеп п]иаиоп (12.19) Ьо1сЬ вЬете г а(6) 3 Ь(6) сг и К (1 < с <е) аге с0ксшес поим«о согсзсапш апс[ «;(9) е Р'[О] (1 < г Бог) ые кс[иакеВее апс[ ра[гв[ке ге1ас[че1у рпгпе. Арр1у[пв сье агвишепс ргезепсес[ (п сЬе ЕЬзс рыс оЕ йе рпюЕ оЕ ТЬеогеш 1 !.7, ве сопс!ис[е йас Ь(0)[ П « (8) апс[ П ч.(0) [ Ь(9). $=! Бшее Ь(9) Ь споп[с, ве пшу ашшпе в[йош 1озз оЕ Бепега1[су йас «;(8) (1 < с' < т) аге ав гпоп1е апс[ Ь(В) = П;(6). ТЬе гезс оЕ йе ывишепс ргезепсес[ ш сЬе ргооЕ оЕ ТЬеогеш 11.7 сагпек йгоиБЬ сп йе ргекепс саке (Еог йе ро!упопиа$ с[опш[п Р'[Щ), у[е1йпв йе еопе1ик1оп йас е; (1 < г' < ш) ате йе с[[к![пес гоосз аЕ йе ро1упопиа[ $$(г) с[е([пес[ сп рап (1) оЕ йе зсыешепс оЕ йе йеогесп апс[ «$(8) (1 < с' Б т) ые аз с[е(вес[ го рап (0).
%е Ьаче йш ргочес[ рагс (0) оЕ йе йеогеш апс[ че Ьаче ргочес[ йе "оп$у 1Г' саве оЕ рыс (1). (ТЬе рагепйек[тес[ гепсай йас $$(т) = 5$$(т) вЬеге Я(г) и К[т] апс[ Б и Р сап Ье ргочес$ ик!пв зшпс(асс[ а[веьга гези[ь; йе ргоо( $к опшсес$ Лете.) %ге Ьаче аЬо ргочеВ рап (й!) ыпсе ве азкишесс Р* со Ье и тишпа! 539 12. Т)зе К!ксЫпшагапоп А!дог(йш а)аеЬгшс ехгепк!оп оЕ Р апз! йеп ргочпМ йас йе гооь оЕ )Е(т) зпвкг арреаг.
То ргоче йе "!Е" саке оЕ рап (з), корроке йас а!1 йе гоогк оЕ ЕЕ(т) аге сопкьпзк. ! ез с; (1 < з' < т) Ье йе г(!кпсс! гооь о!Я(т) апз! г(еЕзпе «(6) (1 < з < т) Ьу «,(8) =ССР(а(6) — с; Ь(6)', Ь(6)) в Р(с,..., с )(8!. Хозч !ЕЕог з »Е, РСР(«з(8), ч (8)) = и йеп з«! (а(8) — с;.Ь(8)'), з«/ (а(8) — с Ь(8)'), авз! ш! Ь(8), ТЬе Огш гзчо совз!!з!опя зпзр1у йас з«/ (с; — с.) Ь(8)', апз( созпйп!ва й!к зч!й гйе гйгг1 сопз!!поп к)коз«к йаз !Е а оопп!ч!а! сопвтюв з!!ч!кот ш ехйь, гЬеп!г зк а сопвпоп йчйог оЕ Ь(8) апз! Ь(8)'.
Ввз Ь(8) !к и!вате Егее, ко зче сап сопс1ш!е йас ССР(ч,(8), «.(8)) = 1. 5!псе еасЬ «з(8) з!1«!з)ек Ь(6), 11 Ео0о» к йаз г(6) = П з,(8) ш! т(!«Ыек Ь(6). 1п ойег» огг)к Ь(6) = (6) (6) Еог коше к(8) и р(сз,..., с,и)(8). Яврроке йаг г!еВ(к(6)) > О, Т)зеп гека(а(6) — г Ь(8)', я(6)) зк а ро!упопва1 о(рокШ«е з!ебтее ко 1ег тоЬе а гооз. 'зче Ьаче (12.21) СзСР(а(6) — то.Ь(8)', к(6)) / РСР(а(В) — то Ь(8)', Ь(6)) апг1 йе!ей кЫе (йе гИчйог) 1к попс«!ч!а), Ьевсе тека(а(8) — то Ь(8)', Ь(8)) = О.
1г Ео!!озчк йаг го Ь опе оЕ йе с„кау сз = го Ввг йеп йе пап! кЫе оЕ(12.21) Ь чз(8) апз! зче Ьаче а поппзчш1 сопвтзоп О!ч1ког оЕ к(6) апз( «з(8). Т1шк РСР(к(6), г(8)) и 1 з«Ысп сопзтайсгк йе Еасз йаг Ь(6) ь п)вше-Егее. ТЬЬ сопзтайсйоп рзочек йаз т)е8(к(6)) = О. Яссе Ь(8) ь пюпзс апз( ч;(6) (1 < з < ш) аге пюшс (Ьу йеп РСР з)еЕзв!поп), » е сопс1вг!е йаг к(6) = 1 апзЕ Ь(8) = П з;(6). з=з Хозч з(еЕ!пе А)попйгм Ьл Со«про«от А1пеЬ»п а(0) = 2; с;.«;(9)' П «(8).
гг'' /и' 6!псе Ь(8)'= Т «т(0)' П /(О) /ча ' тче Ьаче, (от 1 й» < ти, а(6) — с» Ь(0)' = 2. (с; — с„) «,(6)' П ч (6) !=! /ча (топя т«Ь|сЬ!г то11отчз йат «»(8) ) (а(8) — с» й(6)'). Ву т!еГнппоп, ч»(8) ! (а(8) — с» Ь(8)') во чче сап спас!от(е йат «»(8)) (а(0)-а(8)). ТЫв Ьо!»Ь (от еасЬ /т. Рптйеппоге, в!псе СтС(У(ч;(6), ч (6)) = 1 тот еасЬ г' и / тче Ьаче Ь(В)((й(6) — (6)). 3!псе «т(8)(1 К г < ит) аге я1! птоп!с, чте )»пот« 1гогп ТЬеогеюп 12.2 йат т)е0(чт(6)') < т)еД(чт(9)) апг! йттетоге дед(а(0)) < т!еа(Ь(6)). О!псе а)во деа(д(6)) < т(еа(Ь(6)) тче Ьаче т)еО(а(8) - а(0)) < т)еа(Ь(8)) апт) йпз а(0) — а(8) = О, т.е.
а(8) = а(8). Тяте Ьаче рточет)йат а(9) «г(6)' Ь(В) , ! ' ч;(8) апд с!евт1у ~ — !з е!егпептагу ш Впв саве. та(6), Ь(8) %е гептаг)т йат йе $.ахат»)/0!оЬоо/Тгааег птейог! а(чеп а йе 1азт сЬартег сап а)во Ье изет( 1п й!з саве то согпроте йе «;(6) ш рвтт (0) от" ТЬеогетп 12.7. (.о0а«1Инп!с Ехтепв)оп: 1пте9гайоп от" йе Ро1упоппа! Рагт СопзЫег почт йе саве чтЬеге тче ате !псехгаг!пО йе ро!упопаа! рап 1п а 1охапйпис ехтепв!оп.
Рог ап (птепгапд /' е К(х, Вт,.... 0„) и Ьеге йе 1ага ехтепв(оп В = О„!з 1оаапйппс очег Р„т — — К(х, Вт,..., 0„!) (врос!Вса(!у, 0 = 1оа(и) т«Ьете и о Р„т), йе ро1упоютйа! рап!з аро!упоппа1р(0) о Р, г(0). 1ет / = дев(о(6)) апг) 1ет р(6)=р,О/+р, 16 '+ "+р, 12. ТЬе К!асЬ $пыбгаиоп А!6ы16ип 541 вЬеге р! и Р„| (О < |' < 1).
Ву $1ои«111еь Рг|пс!р!е„$1)р(0) !а е1е|пеп|ыу |Ьеп р(0) = «,|(О)'+ 2, с;— ' «;(6) чЬеге сг и К (йе а)6еЬга)с с1ояые о( К) Оы 1 < |' < т ап|$ «;(О) и Р„|(6) (йе $1е!|$ Р„|(0) в(й 1|а сопа|ал| Ве!д ехгепг)е|$ |о К) (ог О ~ | ~ т. Агби)пб аа гп йе ргоо( о( $аои«111е*а Рппс!р1е (ТЬеоге|п ! 2.5), че сап сопи!и|(е |Ьас «о(0) и Р„г(0) Ьесаиае а г(епопипагог г)ерепг(епг оп 6 воиЫ гы! |о йаарреаг ироп $$$«Тегеппайоп. 5!пи!ы1у, «$(0) (1 < | 5 т) |очаг Ье 1пг(ерепг)епг о(8. ТЬеге|оге, т «; р(8) =«о(6) + ~; с;— ;1 «| (12.22) вЬеге с; и К (1 < |' < т), «о(8) и Р„|$8$, ап|$ «| и Р„! (1 < |' < т).
$.е| /с = |$е6(«о(0)) апд !е| «о(8) = Ч«8 + Ч - 6 + ' ' ' + Чо ч4|еге Ч; и Р„! (О<1 КА). Рго|п ТЬеоге|п 12.2 че $|пов йа| «о(0)'и Р„|$0) ап|$ г(еа(«о(0)') = )г — 1 $г" Чг и К (ойегвйе г)еа(«о(6)) = $). Ь (о1!овя йа| йе Ь!6Ьеаг г(е$(гее рога!Ые $ог «о(6) 1а Ь =1+ 1. Рг)иаиоп (12.22) га)ге« йе Гопп в Р|6 +Рг-$0 + ' +Ро=(Ч|«$0+ +Ч|6 + .. +Чо)'+ 2', с!в вЬеге р; и Р„, (О 5 |' 5 1), Ч| | и К„Ч; и Р„| (О й 1 а!). Арр!у(па йе |$$(гегепиапоп ап|$ ег)иаг(п6 соег($с(епга а( Ысе роч ега о( 6 (вЬ)сЬ $а а иапзсеп|$епга1 зугпЬо! о«ег Р„,) у!е!да йе 1оБов1п6 ауыет ог" ециа6опз О=Ч„',, Рг =(!+1) Ч| !6'+Чг', р,, = Р 1,8' + Ч, '|, р| = 2Чг8'+ Ч|', Ро = Ч|6 + Ча вЬеге (п йе 1ап ег(иаиоп ч е Ьа«е 'шпиг(исег) йе пев $пг(егепп!паге Чо = Чо+ 2,' с;1о6(«;). |=| ТЬе 66«еп сое%с(епга ые р; и Р„, (О < | <!) ап|$ ве пыы г(егегпипе ьо!ииопз (ог йе Ч|+| и К, Ч; е Р„! (1 ~ | <1), ап|$ Чаи Р„|(1оа(«г),..., 1оа(«)).
1ио|е йа| !п ециа6оп (12.22), т, го ап|$ «; (1 ~1 ~т) аге ип)гповпа, ао йе гекиЧс6оп оп Чо а|пР!У па|ее йа| печ !обапйгпгс ехгепа(опг о! Р,, ые а$!иве|1. ! п соп|гаы, Ч, (1 а |' а() |пах! $|е хйе0« $п А)аопйшв тот Сошрнгег А1аеЬга йе йе16 Р„!. ТЬезе тевп!сг)опв шнвг Ье оЬвегче6 ав хче арр1у !пш()габоп со во1че йе егрта- попв. Ъ(те сап ргосееб то во!че йе ег)пабопв ав !о11охчв. Арр1ушп Ыгедтапоп го Ьой вЫев от йе йтя щна6оп у1е16в )„г =Ь,„, шЬеге Ья! е К и ап агЬЬгвту сопаапг ог !пте))тат)оп. ЗнЬвбшбпп тот г)т, ! Ы йе весопд ег)наг!оп апд арр!у!па !пшатабоп ш Ьой вЫез у!е16в рт =(!+ 1)Ьтчг 8+ г)г.
ТЬе 1пседшг!оп ргоседнте Ы нотч шчо1гед гесогяче1у со )пш)раве рг е Р„т. Ьт оп)ег ш во1че й!в щнабоп гот Ьг ! е К анжей е Р„г, тЬе гоМотч!па сопс!6опз пшвт ЬоЫ !от)рг . (1) Йе 1пшуга) Ы е!ешепшту. (И) йеге !в ат шов! опе 1оа ехгепяоп от" Р„т арреаппа тп Йе 1пшатаЬ! (ш) !т" а 1оп ехйпаоп оГ Р„т аРРевгв !п Йе !пй!)та1 йеп Ь пшзт Ье Йе РаП!со1ат опе 8 = 1ои(и). 1т" опе от" йеве сопй6опв Ы!в то Ьо!6 йеп 6ге ег)набоп Ьав по зо1пбоп апд тче сап сопс!н6е Йат ) р(8) Ь пот е!ептепгату. Ь' соп6!6опв (1)-(!8) Ьо!6 йеп р, = с!8+ г(г (от гоше сг е К ап6 г(г е Р„т, 1сто11отчв йат йе 6еятед во1н6оп Ь сг тчЬеге Ь, е К гв ап вгЬтпагу сопвтапт от" !птеегабоп.
гехт, знЬв6тн6пп !ог г)г Ы Йе йш! щпабоп ап1 геагтятцшд у1еЫв р,, — ! чтг8' = ! Ь,8'+ й ', ог, Ьу 1птеЬтаг!п8 Ьой вЫев. и 8, г-Ыт — )=!.Ь,8+й, и ТЬе!пгеатап6 оп Йе 1ей сопявш о! )гпочгп !нпсбопв !у!па!п Йе тте!6 Р„г зо тче !пчо)ге йе !птеита6оп ргоседпге геспгячс1. Сошрат!пп го Йе т!хЬт Ьапб вЫе, гче яте йаг Йе аЬоче сопдйопв (!)-(ЬТ) пювт Ьо16 тот й!в !агав! !пгеата1. Ойегв)ве, ше сап сопс!н6е йат ) р(8) !в пот е!егпепшту. )(сопдгбопв (!)-(И) Ьо!д йеп 8гт г — ! т!г — ) =с! !8+с(г г Гог вовне сг г и К апд г(г г а Р„.г. 1т !о11отчв йв! Йе дев!ге6 во!нтюп ш 543 12. ТЬе Е!всЫпщгаиои А!иопйип !вьете Ь, ! и К 1в вп агь)иыу соивгап! о( йаеатаиоп.
Тье аЬоче во1ипоп ргосевв сап Ье соипииег) тот еасЬ ег)иаг(оп ир ю йе репи!типа!е ег)иаиоп, гчьеп а во1и6оп Ьав Ьееи г)емигипед о( йе (опп с! Ьг Ч! И1+Ь1 1 2 ' 1 1 !вьете Ьт и К!в ап агЬ!1гыу сопвгап! о()пгеагапоп. Тьеп впЬвйпьп0 тот ц! !и гЛе !ав! ег!иапоп, геаттапд!ий ап!! арр1уйа шшатаиоп утеЫв Ото-г(! )=Ь!0+)о. и ТЬ!в типе, йе ои1у сопй0оп оп йе !и!сага) 1в йаг 11 иыв1 Ье е1еи1спгЫУ. !г" пот, тче сап сопс!пйе йаг /р(0) !в пог е!еигепшту. !! 0 !в е!ешепгыу. вау ~(ро-А — „) =4» йеп Ь! (рова!Ь!у кето) 1в йе соотг!с)еп! ш !(о о( 0 = 1оа(и) апов Уо = г(о - Ь, )оа(и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
