Geddes, Czapor, Ladahn - Algorithms for Computer Algebra (523146), страница 47
Текст из файла (страница 47)
Езагпр1е №.5. СопвЫег гЬе ргоЫегп ог" Гас!ох)пд йе ГоПо«4пз пюпге ро1упоппа1 очаг йе )иге пега: а(х) = ха + 10х — 432х + 5040 а Х[х]. СЬоов(па р = 5 апг$ арр!ушз йе тог)п)аг ЬотопюгрЬНт фв го а(х) у)е!г)з фв(и(х)) = х — 2х и Хв[х]. А1ьог)гьт 6.1.
Бп!саг!аге Непзе! (хП!пз А!пег!гьт. ргосег)пге $)п!чаг!агеНепве1(а,р, ир), и (!), В, у) № $Ь)Р()тг № (1) А рг!ппг!че ро!упогта1 а(х) и Х[х]. № (2) А РПгпе $птеег р «Фись г)сев по! гПиафе!соегг(а(х)). № (3) Тгго ге!а!(че!у рпгпе ро!упопьа)з и!')(т),м (г)(х) е Х„[х] вьсЬ $1иг № а(х) ш и(г)(х) гг! )(х) (тог) р). № (4) Ап )пгезег В ггЫсЬ Ьоппг(з йе тадп[тг(ез ог" аП 1пгезег соегу)с[епгз арреаппз ш а(х) апб ш апу ог" 1гв розгПЫе гас!оса «4$Ь г)езгеев № пог ехсеес$$пз тах[г)ед(и!0(х)),г]ед(«(г)(х)) $, № (5) ОрьопаПу, ап 1пшиег Ть Х ггЫсЬ ы Ьпо«гп со Ье а пш16р!е ог" № )сое(г(и(х)), вЬете и(х) (зее О()ТР()Т Ье1о«г) гв опе ог" йе Гасгогз о1 № а(х) и Х[х] го Ье согпршег$. № 0()ТР()Т: № (!) )гйеге ехьг ро1упоппа)з и(х), и (г) и Х[х] впсЬ йаг № а(х) = и(х)ги(х) и Х[х] № апд № п(и(х)) и п(и'0(х)) (тог) р), п(гг(х)) и п(гс(')(х)) (тог$ р) № «Ьеге п г)епогез йе поппаПхаьоп "та)ге йе ро1упоппа) пгоп!с аз ап № с)степ! ог" йе $$огпагп Х [х]", йеп и(х) ап<$ ю(х) «чП Ье согпрпгег$.
№ (2) Огьегичве, йе га1пе гегпгпес$ «ПП в!апа$ "по зпсЬ гас!опав!!оп". 234 А!пог!гЬшя Гог Согпрагег А1ееЬга А)еог]йш 6.1 (сопйписй). Уп!чапаш Непяе! (л(йпе А!еопйш. (! 1. Ое(!пе пегч ро!упопйа1 апй Ьп |пайп!о р(асгогя а г- 1сое!((а(х)) 1( у !я ипйершей !Ьеп у л- а а(х) л — у а(х) и")(х) +- ф (у п(и("(х))); гч("(х) +- ф (а п(ч(!)(х))) Ф 2. Арр1у ехгспйей Еас1!г!сап а1еопйнп го и!!)(х), в1п(х) е Хр[х] л(х). г(х) +- ро1упопйа!я ш Хр[х] сошрипх( Ьу А1еог!1Ьш 2.2 яисЬ йаг л(х) и(11(х) + г(х) в(г)(х) и 1 (гпой р) () 3.
]и!г!а)!аапоп (ог йе !шгайоп и(х) г- гер!асс 1с(и(')(х),у); ю(х) <- гер1асе )с(иФ"(х), а) е(х) г — а(х) — и(х) . ю(х); тог!и!иг г- р () 4. 1гегаге ип61 еиЬег йе гасшпяапоп пг Х[х]!я оЬга!пей ог () е1яе йе Ьоши1 оп тог(и(иг !я геасЬей юЬ!1ее(х)иОапйтогЫш<2 В уйо( (! 4.1. Зо!че гп йе йопи!и Х [х] йе ро!упопйа1 егрибоп Ф о(х) и(~)(х) + т(х) ш(П(х) и с(х) (гпой р) (! гчЬеге с(х) = е(х)Апойи!иг с(х) я — е(х)Апогйг)ш; о(х) < — ф (л(х) . с(х)); с(х) л — ф (г(х) с(х)) г)(х), г(х) +- ро1упопйа)я 1п Хр[х] шсЬ йаг о(х.) = гч(')(х) д(х) + г(х) о Хр[х] о(х) г — г(г); е(х) ~'.— ф (г(х)+ф(х) ° и )(х)) М 4.2.
()рйагс йе Гас!ага апй согпрпяе йе епог и(х) +- и(х) + с(х) тойи!ил; ю(х) г — ш(х) + а(х) тойи!ил е(х) +- а(х) -и(х) в(х); тогйг(ил г- тог(и!ил р ) Ф 5. СЬес1г гепшпайоп ягашя !г е(х) = 0 !Ьеп ( Ф Расгойгайоп оЬышей — гепюче сопмпгя Ь - г(и(х));и(х) (х)(Ь; (.) (хИу!Е) () Ь)олег а(х) г-а(х)гуюоиЫ геягоге а(х) го ггя !прог ча!ие ] ге!игп( и(х), в(х) ) е)яе ге!игп( оо лисА гас!салаг!оп ехип ) епй 235 б.
Хетт!оп'а 1гешьоп апг( йе Непте! Сопяпкьоп ТЬе пп)пое пшт поппа! (1.е. шошс) Гас!опта!гоп !п Ет(х) от бпт ро!упоппа! !в фт(а(х)) = х (х — 2) и Хт(хЬ %е йеге(оге г)еГше ии!(х) =х, гч(г)(х) =х — 2 апд гбпсе ии)(х) апд ю(0(х) ые ге1абче1у рпгпе ш Ет[х), йе Непае) соптгпгсьоп тау Ье арр!!ег!. Арр!ушб А18огпЬпг б,1 !п йе 1опп погег) аЬоче гог йе шоп1с саге, тче Егтт арр!у ш атер 2 йе ехгепг)ед Еос!!т)сап а)8обдпп тч)псЬ у(е!ба г(х) =-2х, г(х) = 2. ТЬе 1п1т1а1!хабопт ш ыер 3 у)е!б и(х) =х, в(х) =х — 2, е(т) = 10хт-430х+ 5040, апт) сии!и!иг = 5. 8тер 4 йеп аррбеа йе Непте! соптьосьоп ргес!те1у ат опб!пей 1п йе ргоот" от" Нептерт 1ешгпа.
(рог пою тче аге т8попп8 йе кеосаян сегпйпаьоп сопб!ьоп от" тЬе тчЬ!!е-!сор.) ТЬе тсг!пепсе о(ча1пет сошршеб (ог о(х), т(х), и(х), ю(х), апг) е(х) ш егер 4 Н аа (о1!отче. ~)оге йаг ат йе епг) ог" еасЬ 1тегаьоп атер й, е(х) Н ехасбу б!ч!а!Ь)е Ьу вог(и)их =5 аз и бгбгсд ас йе Ье81ппш8 о( тЬе пехт 1гегабоп. ТЬе Ьегаьоп гептйпатет чч!й и(х) = х+ 30 хш1 и (х) = ха — 20х+ 168, %ге тьеге(оге Ьаче йе Гасгобгабоп очег йе ипебегт х~ + !Ох т - 432х 4 5040 = (х + 30) (хх - 20х + 168). Етагпр1е 6.6. !п унт ехагпр)е чге тьа!1 яее йат йе Непте! соптьпсьоп пву арр!у ечеп » Ьсп йе Ьбчеп ро1 упош!а) саппот Ье (астогег) очег йе 1пгебегт.
Сопт!г)ег гЬе гпоп!с ро1упоппа! 236 А1аопйшя Гог Созпрнзег А1аеЬга и(х)=х'+!н Х[х) нзЫсЬ зк 1пейю!Ые очег йе !пюнеш. СЬоов(па р = 5 ап6 арр1уша йе пни)н1аг ЬонаипогрЬЫгп фв го а(х) у1е!з(к фк(а(х)) =х +1. ТЬе нп!з)не нп!з поппа1 Тассопгабоп зп Хк[х[ о! йЫ ро1упонйа! Ь х + 1 = (х~ + 2) (х~ — 2) н Хк[х). 3!псе йе ро!упопйа1к из'1(х) =х~ е 2 апа зч(')(х) = х — 2 аге ге1анче! у ргипе ш Хв[х), йе Непве) сопвннс6оп шау Ье арр!)елЕ 1п й1к саве ше нег ап зпйп1зе коз)пенсе ог" Гас!ой а(х) ни( 1(хЬч( з(х) (нни)р ) !ог/г =1,2,3,....
)г" ше арр1у А1аопйш 6.1 ю йЫ пюп!с саяе ак 1и Ехашр!е 6.5, йе гека!з о( вшр 2 Ы к(х)=-1; г(х) =1 апб йе!пЫа1ыабопк 1п вшр 3 у1е!6 и(х) = х~ + 2; и (х) = х — 2; е(г) = 5; июз(и(иг = 5. 1з" зче а1!он йе зчЫ1е-1оор ш взор 4 го роквелл 6нонаЬ 1онг Ьеи6опв (ааа1п ше аге !люппа йе весоп6 сепшпа6оп сопгбз!оп оГ йе нЫ1е-1оор), йе кез)пенсе о( ча1нея сошрнш6 (ог о(х), г(г), и(х), ш(г), апз1 е(х) зв ак зо)1озчк. ТЬеке Ьеганопя сон16 Ье соп6пне6 )пбеГнизе1у у!е!6!па ап ш6п1ге яег(пенсе о( (асзогк ка6вГу1пд НепвеГв 1епнпа. Ыоге йаг аз йе еп6 оз 1гегазюп вгер )з нзе а1гчаук Ьаче и(х)и(х) шх +1(пю65з") ав с1апю$ !п Непке1'к 1епнзза. Нозчечег гче нз61 печег оЫа[п пна6га6с Гас!ока и(х), ш(х) и Х[х) внсЬ зЬаг и(х)нз(х) =г + !и Х[х).
зз((е гелзаг1з йаг ош ро!упопна) а(х) 1п зЫк саяе Гасюгя пно ьчо ннабгабс !асзогя!и Хр [х) (ог ечегу рпзпе р (кее Ехегсйе 6.12!п СЬаргег 8). ТЬнк сЬоовзпа а рпгпе б)г(егепз йап 5 нлП пог сЬапне зЫв ехашр1е. 237 б. ]ю]е«ююп'з 1юетаьоп апд йе Непве1 Сопяюпкбоп ТЬе Е,еад]68 Сое((к]епг РгоЫет Тье Непзе! сопягисйоп ргочЫез а юпейь$ тот Ибйпй а Еасюоптайоп юподи1о р ир юо а Еасюопхабоп моди)о р Еог апу зпюе8ег ! > 1.
Ехашр1е 6.6 збоючз йаз йпя сопвюпзсйоп доев пою песеззап!у !сад юо а Еасзопхаю!оп очег йе 1шебегз. Ноючечег !Е йе пюпк ро!упопда1 а(х) а Х[х] Ьаз йе пююьйо р Еасюот!тайоп а(х) и и( )(х)» ( )(х) (пюд р) ючЬеге и(О(х),» Оз(х) а Х [х] ые ге1айче!у рг!юпе зпоп1с ро1упопйа)в апд Н йеге ех1вь а з Еасюопхай зп очет юЬе юпюебетв (6.57) а(х) = и(х)» (х) и Х]х] зисЛ юЬаю и(х) паз З(х) (юподр), »(х) и»ЮО(х) (юпою]р) (6.58) йеп йе Непяе! сопзюпзсбоп юпивю оЬюв!и ййя йсюопгайоп. Зрес!Пса]!у, 1ею ! Ье 1аг8е епои8Ь зо йаз рю > 2В «Еюеге В Ь ап 1пюебег «ЫсЬ Ьоипдв йе юпайп!!идея оЕ аП юпюе8ег соей!- с1епь арреагш8 !п а(х) алд ш апу оЕ !ь ровяЫе (астора «дй йе разбои!аг де8геез ю$с8(июю)(х)) апд де8(ючй)(х)). (рог а ю$ькизззоп оЕ юесЬзйрзез Еог союприйп8 висЬ а Ьоипд В яее М$8поье [4].) ТЬеп йе Непзе! сопягисйоп гпау Ье аррйед юо сотриюе пюп]с ро!упоюйа]я иююз(х), юР(х) а Х [х] заьзЕуюп8 а(х) и ию')(х)юр)(х) (пюд р') (6.59) ий)(х) пи!')(х) (пюю1р), юи!(х) п»О)(т) (пюдр) (6.60) апд Ьу йе сотойагу м ТЬеотепю 6.2 йе Еасюгз и(ю)(х),зчрю(х) а Х ю[х] ате шз!срзе1у деюегпипед Ьу сопдШопя (6.59)-(6.60).
]ю]оюч! Е йеге ехьюв а Еасюопхайоп (6.57) вайяЕу!п8 (6,58) йеп апойег зисЬ юпоп1с Еасюопгайоп зп Х [х] зв рточЫед Ьу ф (и(х)) апю$ ф ю(и (х)) апд Ьспсе Ьу ип!ю)иепевя и(ю)(х) = ф ю(и(х)), »ю(~)(х) = ф ю(ю(х)). 1)ию, япсе рю > 2В, юче Ьаче ф ю(и(х)) =и(х) апд ф ю(» (х)) =ю(х), «ЫсЬ рточез йаю ир~(х) зюм! ююю)(х) аге йе ю$еягсд Еасюоь очег йе !пк8егя.
ТЬе аЬоче д!ввозя!оп зьо«в йаю !п йе зппп!с сазе, йе Непзе! сопягисйоп юпау Ье ююайею$ «Ьеп рю > 2В аю ючЬ!сЬ ро]пю е1йег игп(х)» ЮО(х) = а(х) очет йе зпюебегз от е1ве йеге гхйь по Еасюоптзьоп вадя(у!п8 (6.57)-(6.58). ТЬе зесопд юпшпаьоп сопюйьоп оЕ йе ючЬПЕ-$ООр !П Ззср 4 ОЕ А18ОПйт 6.1 Пи ]П йЕ ПЮПК Саяс, ртЕСЬЕ1у йй Спид]йси. НОЗЕ ю!ни япсе йе Ьоипд В 8!чеп юо А18опйгп 6.1 ючй! 1пчапаЫу Ье чеюу резяпдзйс, йе Еьвю и ишпайоп сопд!ююоп оЕ йе ючЫ1е-! оор ь гею]ипед юо ачои$ ехюга созйу !юегайопз а(кг а Еасю«птайоп Ьав Ьееп йвсочегед, 1п йе поп-пзошс сазе йе в!Ыаиоп Ь пою ю]и!к ъо вйпр!е. ТЪе Непяе! сопяпкйоп и йиюггз (т яер 4.
! о( А18опйгп б.!) йс юо)нйоп а(х),т(х) а Х„]х] оЕ йе ро]упопиа] А18опдппя тот Согпризег А18еЬга 238 сИорЬапдпе ес)иаз!оп о(т)и(з)(х) + с(х)и Сзт(х) я с(х) (шод р). (6.61) ТЬе зо!одоп оз й!з есрипоп ы пос ип!с)ие!у дезептдпед Ьис ишс)оепезз Н (яопкзчЬаз ыдйс!аПу) ппровед Ьу гесрппп8 йаз йе яо1идоп вадззу дефо(х)) < де8(зч")(х)) (6.62) (все ТЬеаепз 2.6). )з(обп8 йаз сЬе ирс$асе топпы1аз (1п яер 4.2 о( А)8опйш 6.1) ате йеп и(х) с — и(х) + с(х)р; и(х) с- зч(х)+ о(х)р, зз!я с!еат йаз зЬе с)едгее сопята!пз (6.62) 1пзрйез йас йе 1еадш8 сое%с1епс от" и (х) $з печет ирсЬззед. 1п йе шошс саве, й! в 'ь ехасс!у и Ьаз зче и апз. Мотеочег, япсе а(х) — и(х)и (х) (6.63) икди(из зз (оПозчя 1п йе зпопк саяе йаз с$е8(с(х)) < с$е8(а(х)) = дефи(')(х)) + де8(зч('>(х)) апд сЬететоге йе во1ипоп ог (6.61) а1яо яадяйев, Ьу ТЬеогеш 2.6, с$е8(с(х)) < де8(ис~)(х)).
1с (оПозчв сЬас йе 1еасПп8 соегбзс1епз ог" и(х) а1во!з печет ордасед зп йе зпопзс саве. Тшпзп8 зо сЬе поп-пзошс саяе, зче пшвз (Ьвз авяппе йаз йе сЬозеп рпзпе р с)оез пос д!чх(е йе 1еасПп8 сов%с(епс ог" а(х). ззз!й зЬ!в аышпрдоп зче аге аввшес$ сЬаз и(П(х) апд и С')(х) Ьаче "соггесз" де8геез!п йе вепве йаз де8(и(з)(х)) + дефи Сз)(х)) = де8(а(х)).
ТЬеп зче Ьаче (гош (6.63) йаз де8(с(х)) ~ с$е8(а(х)) = де8(и(з)(х)) + с$е8(и С )(т)) (тош изЬ(сЬ зз (оПозчв ехасду аз !п ТЬеотезп 2,6 йас де8(с(х)) < с$ефи( )(х)). (6.64) ТЬе с)е8тее сопязгяпз (6.64) аПозчв йе 1еадш8 сое%с!епз о! и(х) зо Ье прс$азед япсе, ипйсе (6,62), йе !пес)иабзу Ьете Н пос япсз $пя)оа)1зу. $з(о» аз йе епд оГ еасЬ !зегадоп ясер /с, зче Ьаче йе ге1адопвЬ!р а(х) я и(х)зч(х) (зпод рз+з) апд зЬетегоге япсе (6.62) 1огсез йе 1еябп8 сое%с!епс ог" из(х) зо тезпяп ипсЬап8ед, аП о( йе прс$адп8 тесунгед Ьу йе 1еадш8 сое%зс!епз ог а(х) !з (огсед опсо зЬе 1еайп8 сои!1!с!епз о( и(т).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
