Geddes, Czapor, Ladahn - Algorithms for Computer Algebra (523146), страница 91
Текст из файла (страница 91)
ТЬе Йе1г( оЕ соп- яапь (ог сопвгапг 6е!4) оЕ Р Ы йе зпЬЕте!г( оЕ Р г(ебгпег) Ьу К=(со Р:В(с)е 6) Сапог)ег Еог а тпойепс йе раптсп1ат 6е!г( 9(х) оЕ гапопа) Еппспопв тп йе чаг(аЫе к очег йе соеЕ6сгепг 6те!г( оЕ гафопа1 потпЬегз. 1.ег В Ье а г(Негеппа) орегагог деЕтпед оп та(х) зпсЬ йат (11.3) В(х) = 1 ТЬеп (4(х) Ы а 4!6егепфа1 йе!й ТЬе Ео!1охч!па йеогетп ргочез йаг В Ы йе Еапп1!аг г(1Е- Еегеппа1 орегагог дейпег( оп йе зпЬг(опп!и Щх) оЕ ро1упопйа(з.
11. !пгеагаьоп оЕ Каьопа1 Гьпсьопз 477 Тьеогеш 11.2. 1Ер и Щх) йеп В(р) и Я[х), ччьеге Р !з а П!ЕЕегепьз) орегагог заьз(у!па (11.3). Моге зресПгсаПу, !Е р = 2.пах и 12[х), айй а„иО йеп О, !Ег(еа(р)=и =0 В(р) и — г 2, (/с+1).аг „г х~, !Еаза(р) = и > 0 . !=о 1п рагьсо!аг, г(еа(Р(р)) = Пеа(р) — 1 гчЬеп беа(р) > О, Ргоой риз! сопз!г(ег йе сазе г(еа(р) = и = 0; Ье, р = ао о (). %ге пшзг ргоче йаг В(р) =0 !ог аЛ р а г2. Ргош Тьеогегп 111 чге Ьаче йагР(0) =0 апг( В(1) =О.
Рог апу роз!Пче шгеаег и, гче Ьаче В(и)=В(1+(и — 1)) =Р(1)+Р(и-1) =В(и-1) апй Ьепсе, Ьу пгг(пег!оп, В(и) =В(0) =0 !ог аП роз!ьче шгеаегз и. Я!псе В(-и) =-В(и) гье гезп!г а!зо Ьо!йз Еог аП пеааьче йгеаегз. Р!паПу, пз!па йе грюьепг гп1е а!чез иВ (ги ) — гиР (и) иг апг( ЬепсеВ(р) = ОЕог аПр и Я. Тшпла поги го йе сазе г(еК(р) = и > О, !ог йе ро1упоппа1 р К!чеп ш йе зьпешепг оЕ йе йеогеш, чче Ьаче И л В Я = В(по+ 2„аз х" ) = 2', В(азха) !=1 е=! пз!пд йе зппппаьоп пг!е Еог В апг( гЬе Еасг йаг В(ао) = О.
рцгйег, арр!уша йе ргойпсг гп1е Еог Р, Тьеогеш 11.1 (гч), апг( (11.3), у!е!Пз л л В(р) = 2, а!В(х") = 2', lгагх~ г г=! !=1 арчь!сЬ !з йе Пезпег( гезь!г (гч!й а зь!Ег ш йе шг(ех оЕ зппппаьоп), ()з!па гье г)поьепг пг1е Егош Тьеогегп 11.1, 11!з с!еаг йаг В !з йе ЕапгП!аг гПЕЕегепьа1 орегагог оп аП шьопа! Еппсг!опз г и Щх).
478 А!8опйшз Еог Сопгршег А18еЬга Ехпшр!е 1120 1.ег г о га(х) Ье йе габопв! Еьпсбоп 1 г= —. х+1' ТЬеп -1 В(г) = хз+2х+! ТЬеогшп 11.3. рог йе 6!ЕЕегепба) Оса г4(х) мг((Ь 6!ЕЕегепбв[ арегагог В вабв(уш8 (11.3), йе сопвгапг ОеЫ ы (2. Ргоо(: ЕЕ с п ([ йеп В(с) = О, Ьу ТЬеогеш 11.2. Сопчегве!у, шррове йы В(г ) = 0 Еог г и Щх). %е пшзг ргоче йаг г и ЕЕ.
Хопг апу габопа! Еьпсбоп г п гг(х) шау Ье ехргезяе6 ш сапопка1 Еопп г = р)г) Еог р, гЕ о (4[х], абй гЕ и О, апд ССР(р, гЕ) = 1. %е Ьаче оц р-ха~~:-гч — е г 50 г) ВОг) -р Р(г() = О, йаг !в, В(р) = ~— В( ) г) Ргош ТЬеогеш 11 2 В(р) и (г[х), апд, з!псе р апб д Ьаче по сопппоп Еасшгв, гче попс!пде йаг йеге ех!ягз аро!упопба1 в и гг[х[ вьсЬ йаг Ш г) Вьг йеп В(1) = з.д ап6 га[6п8 6евшез (побег йе азвьгпрбоп йаг 6е8(г)) > 0) у!е1гЬ бафии) — 1 = с(е8(з) + йе80)) ТЫ в !в йпрозз1Ые; Ьепсе де8(г)) = 0 (!.е.
В(д) = О ап6 з = 0). А ргечшпв ге1абопяЫр йеп у!е16я В(р) = О, %е Ьаче йьз ргоче6 йаг р, 4 о Е) ав 6езьес1. ТЬе ргоЫеш оЕ шдейп!ге !пгевгабоп ы ш сошрше йе Ьшегзе В г оЕ йе 6!ЕЕегепба) орегагог В. С(еаг!у, Еог апу Еьпсбоп г и Щх), В(г) и (4(х) Ьу деЕгп!6оп оЕ а 6!ЕЕегеп6а) орегагог. Опе п68Ы розе йе г)ьеяьоп: Сп[чеп апу Еппсбоп з п Щх), боев йеге ехвг а Еьпсбоп г п (г(х) яьсЬ йаг В(г) = з? 1п огьег гчогйа Ы йе гИЕегеп6а1 Ое16 9(х) с!овег( побег йе шчегзе орегагог В г? Хозе йаг ь !з с!еаг егош тьеогеш 11.2 йаг еог апу ро!упопйа! д = ~; Ьгх п ([[х[ г=о йеге ех(яш аро!упопба! р =В ~О)) и гг[х); зрес!Егса1!у, 479 11. 1птеатайоп оЕ Кайопа! рипсйопв лтт-1 р = ~', — Ьт т х" /т 1п гйе поп-ро!упопйа! саве, сопяЫег Еог ехатпр!е тЬе тат!опа! !ипсйоп -1 я = е те(х) 2+~ +! ргогп Ехаптр!е 11.1, и е зее тЬат !п ййв сазе гйеге ех!зтв а гапопа! Еипстюп т а (4(х) зисЬ тЬат Р(г) = я.
Нотчечег, ав !з тчеП )тпотчп, тЬе аепега! апзитег !з пеаат!че: тз(х) !з пот с!овей ипйег тЬе (пчегзе оретатог Р т. ТЬе Еойотч!па гйеогетп ргочев йте с1азйса1 соиптегехаптр!е. ТЬеогепт П.4. гог тЬе гайопа) Ьтпсйоп 1/х а О(х), тЬеге т1оез пот ех!зт а гайопа1 Еипс6оп г а (4(х) вись йтаг Р(г) = 1(х. Ргоо(т гарроте гйат г =р()а тз(х) вайзйез Р(р(т)) =1Гх, айтЬ рщ а Щх) апй СтСР(р, тт) = 1. ТЬеп дВ(р)-р Р(т() 1 92 х во х т) Р(р) — х р.Р (т)) = т)~. (11.4) %г(те т) =х'4, чтЬеге тЕа Щх) апйСтСЭ(тЕ,х) =1. (11.5) Ву ециайоп (!1.4), х йтчЫев 1пто т)т, апй Ьепсе а1зо тпто т). ТЬеге(оге и > 1. ЗиЬзйтиппд ет)иайоп (11.5) !лто (11.4) а!чез х'+т тзР(р) — лх" р д — х"тт р Р(т)) =хт" д вЫсЬ вппрййев го п р г(=х (тпР(р) — р Р(т)) — х" 'я)" ).
Ейпсе ОСА((),х) = 1, тче стив! Ьаче тЬат х ) р, Вит гйеп р апт1 т) Ьаче а сотптпоп Еастог, а соппай(сйоп. П Еойотчв Египт ТЬеогетп 11.4 тЬат ш огйег то ехргезз тЬе !пйейпйе Ьттеатп! оЕ а тайопа1 Ьтпсйоп, !т птау Ье песеввагу то ехтепй гйе Пе!й (4(х) тч!йт печт Еипсйопв. 11 илП Ье яееп тЬат Ейе оп1у пеит Еипсиопз гетрт!тей аге 1оаапйппв.
ТЬе сопсерт оЕ а 1оааптЬтп ийП потч Ье йейпей а!аеЬга!сайу. 480 А1допйнь Гог Сотприат А!неЬта Рейн!йоп 11.5. Ьег р Ье а 61ГЕетепйа) йе16 апй 1ес б Ье а ййуегепйа) ехмпв!оп йеЫ оГр. ЕГ, Гог а Ьйчеп 8 и б, йеге ехьь апе!етпепт н н Р висЬ йас Р(В) =— Р() н йеп 0(з са11ей!оунг(т)тине очег Р апй тче ич!те 0 = !он(н). 1т зЬои!6 Ье потей йат йе сопсерт оЕ "пш!6р!е ЬгапсЬев" оГ йе 1онаптЬтп Гипсйоп тчЫсЬ апвев ш ап ана1уйс йеГннион оГ 1оцапйпы очег йе сошр!ех пшпЬег йеИ, Ы сошр!ете!у ачоЫей ш гЬе аЬоче а)неЬтас бейл!йоп. БисЬ ап Ьзие зЬои!6 Ье ачойей ш йе сопсетн оЕ шйейпйе штенгайоп япсе тче тчй) оп1у йетеншпе ап шйеГлнге шгента) го ийтЫп ап агЬтиагу айй!йче сопяапт.
ТЬиз "апу ЬгапсЬ" оГ йе алйуйс !онат(йнп Гипсноп ии!1 зи(йсе. бтчеп а ЙГГегепйа) Гте16 р, йе ргосеш оЕ шйейп1те !п!ейтайоп Еог а Ьйчеп е1ешепт у' и р ы ш йетеппше а 6)ГГегепйа) ехтепяоп Гте!6 б = Р(8,,..., 8„) !п тчЫсЬ ап е!ешепт в и б ехыь висЬ йат Р(н) =Г, ог е!ве то йетенпше йат по висЬ ехтепвюп Ве16 ех(вь ийй!и йе сопгехт оГ а не!1-йейпей с1звз оГ "айотчаЫе ехтепяопв".
Рог тЬе 6)ЕГегепйа! Йе!6 Р= б(х) оГ гайопа! Гипсйопв, йе шйейп)те штенш! оЕ а Гипсйоп г н Я(х) сап а)итауз Ье ехргезвсй тп ап ехтепяоп йеЫ шт(и)ппн оп(у пчо !урез оГ ехмпяопв: 1онаййпнс ехтепяопв апй а18еЬгтйс пишЬег ехтепяопз. ТЬе 1анег сопсерт те1яев то йе йе16 оГ сола!апай И йе Ьаве йе16 оГ гайопа) Гипснопз тчаз ехртевзей аз К(х) очег а Гте16 оГ сопяапь К тчЫсЬ 1в а1неЬтшса(!у с!овей (ейр К = С, йе йе16 оГ соптр1ех пшпЬегз) гЬеп оп!у !онат(йпнс ехтепв!опв твои!6 Ье гет(ине<$.
Ноитечег, Гог йе Ве16в оЕ пювт штегея (п а зупйо!к сошритайоп вуяепт тчЬеге ечегу е1ешепт Ьаз а йшш ехаст гергезептаиоп, йе рторену оГ а)неЬгшс с!овиге ь пот ртевепт. Мотайопа()у, апй сопсерша(!у (п йе а)нопйш гог гайопа1 йпсйоп !пгенгайоп, тче и4!1 верагате йезе оно !урез оГ ехтепйопз. Кайег йап ехргевяпн йе ехтеляоп Яе16 )п йе Гопп б = (1(х, 0,,..., 8 ) тчЬеге еасЬ 0; (1 5 т ~ ти) шау Ье е1йег а !онаййш ог ап а)неЬгшс пшпЬег ехтепяоп, тче сЬоозе тпяеи1 то ехргеш йе ехтепяоп йе!6 !п йе Гогш б = (1(ат,..., а,)(х,В,,..., 0„) тчЬете еасЬ 8; (1 й ! й и) 1в а 1онапгЬш влй еасЬ а; (1 й т < Е) ы ап а18еЬгис пшпЬег.
ТЬы, йе Г(е!6 оГ сопвтань оГ тЬе 61ГГетепйа) ехтепяоп йе!6 б ин1! Ье б(а!,..., ат). Айорйпн сопчепйопа! потайоп, тче и!1! ивна1!у ехргеш йе йепчатйе Р(х) Ьу у' апй тче чй!1 ехргеы йе шйейнйе!птента) Р ' Ьу / Г. %е н411 пот иве йе сопчепйопв! т)х зушЬо! го т)еноте йе рагйстйаг чапаЫе Ьесаиве йтв юШ Ье с(еы !тоти йе соптехг. (х и Ш соштпоп!у Ье йе чапаЫе оЕ 61ГГегепйайоп апт( (пфенгайоп.) ритйеплоге, ие сноове пот то ехргезз йе сопчепйопа1 "р! ив ап агЫиату сопзтапт" тчЬеп ехргезз!пн йе гею11 о( )пт)ейптте 1птентайоп.
(1п ойег вонЬ, иге юй) Ье ехргевз!пй а рнгтн н(нг тш(ейпне !амата!.) ТЬиз 481 11. 1п!е()»айпи о( Кайоиа) Ропсйопв Непсе, (гот Ехыпр! е 11.1 чге Ьаче -1 1 = — ч 0(х) хв+2 +1 х+1 ч Ьеге ч!е по!с йа! по ех!епиопв о( йе Ее!й Щх) веге гегршег! !о ехргевв йе 1ишага$. 1п огйег !о ехргевв йе!и!сага! о( йе йисйои 1!х сопвЫегсг( ш ТЬеогеги 11.4, чге (п!гойпсе йе печг (ппсйои О, =! оа(х) йейпсй Ьу йе сопй(йоп О,' = ! !х. ТЬеп ч е гиау чв!1е — = !оа(х) ч г2(», !оа(х)) 1 х юпеге опе!оаапйпйс ех!епвюп !о йе Ее!й г2(х) чав гы(штей ю ехргевв йе !п!е((га).
Ехыпр1е 11.2 вЬовгв а саве !вЬеге гвчо !ойаййпйс ех!епвюпв аге !п!гойпсей; Ехашр1е 11.3 вЬочгв а сазе ч Ьеге йе сопыап! Ее! й пшв! Ье ехгепйей Ьу ап а(аеЬгыс пшпЬег. Кхагпр!е 11.2. — =1оа(х) — — !оа(х +1) ч Щ»,1ой(х),!оф(х +1)).
1 ! ! 2 х +х 2 Ехагпр1с 11.3, — — — 'Г2 !офх -"Г2) - — ~!2!од(х + в2) 1 1 х» — 2 4 4 гвЫсЬ гег)шгез йе ех!епв!ои (2(в2)(х, !оа(х — Г2), !о(г(х + 42)) . Юе Ьаче по! уег в!а!ей йе шгеагайоп а)аог(аппп юЫсЬ шав иве!1 !о согпрше йе !и!еаг!йв 1п йе аЬоче пао ехатр!ев, Ьа! Гог йе сиоп!си! йеу сап Ье мегйвгй Ьу й!1(егеп!иНоп апй гайопа! Йпсйоп поп!а!напои. Хо!с йа! йеге аге ойег !оппв 1п чйпсЬ йеве !п!сага(в соп1с! Ье ехргеввей.
1и Ехыпр!е 11.2, а сопапоп1у-пвег! гпейой гвоо!й ргосесй Ьу сагир!еге!у Еасшппа йе йеиопйпа!ог ав х +х = х(х + !')(х — !), Э юЬеге ! йеио!ез йе а1аеЬгыс ишпЬег вайвГу!па !2+ 1 = О (!.е. йе согпр1ех вг)пате гоо! ог -1). ТЬеп а раг!Ьй (гасйоп ехрапйоп юопЫ уге!й 1 1 112 1П хв+х х х+! х— (гам ч ЫсЬ юе оЬга(п 1 1 . 1 — = !ох(х) — — 1ох(» + !') — — !оа(х — !) х +х 2 2 юЫсЬ йсз !и йе сх!сийаи (2(!)(», !ар(х), !оа(» + !), !ор(х — !')). ТЬе а1ропйгп вгЫсЬ сопзра!сй йс гсха!ь арсе!Ос<! !и Ехаизр!с 1!.2 Ьав йс ргорсг!у йа! Ь ачо!йсг! апу а1рсЬгай 482 А)8опйшв !от Сошритег А18еЬга пшпЬег ехгепяюпы ТЬЫ Ьав ьчо сошришг!опа( абчапш8ев: (!) Ь ачоЫз гЬе сов! о! сошрибп8 а сошр!еге !асгопхабоп о! йе 6епош!паюг, ап6 (й) Ь ачоЫв йе соы о( ппогри!або8 а18еЬгыс пшпЬегв. Ехапгр!е 11.3 кЬовчз йаг 66в а)8огИнп сапоог аЬчауз ачоЫ шгто6«сш8 а18еЬгыс пишЬег ехтепыопя.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
