Geddes, Czapor, Ladahn - Algorithms for Computer Algebra (523146), страница 74
Текст из файла (страница 74)
ОЬч!оик!у, ехасс тейо6к ачоЫ йе Ьюек оЕ еоп6|6оп|пи ап6 ясаЬсйу. Могеочег, т йе саке оГ поп||пеаг вувсетк, пшпепса! тейобк саппос аишапсее йас аИ ко|ипопк счИ! Ье Гоипс$ (ог ргоче йас попе ехскс). Р!па$1у, гпапу кугпегпк счЫеЬ апке !и ргаобее еопсасп "Ггее" рагаспесегк ап6 Ьепое пикс Ье ко|че6 очег поп-пшпепса1 6тпшпк. %е Игкс сопкЫег йе во|и6оп о(Ипеаг кутепь, |п сЬе ргевепс сопсехс оГ ехасс сотриса6оп, |с Ь ойеп 6еягаЫе ш ппарпе йе еоеГИе!епс 6огпат ав йе циобепс Яе16 оГ ап !псеага1 с$отшп ап6 со огиап|хе а!зоб!пик во йас тот оГ йе еотрисабоп ск рег(оппе4 сп йе !псекгас с$огпасп. ТЫв апп |к пю6часес$ Ьу йе Еаес йас куксепь «Ий есйег гасюпа! пшпЬег ог га6опа! Гипс!!оп еоеЕЕ(о!епсв аге агаиаЫу токс еопипоп |и ргасс|ее; апс|, апу кувсет ипй гас|опа| еоеГИесепь гпау Ье шппеп |и сеппк оГ!псеаег ог |псеига! ро1упопиа1 еоеГЕ|с|епск.
)||ге сЬеге(оге бече!ор чапапь оГ Оагьксап е1спппабоп счЫеЬ ехр!огс сЬЫ гбеш. Тяге йеп ЬпеЛу 6експЬе а пшпЬег оЕ осЬег арргоасЬек счЫоЬ арреы |и сЬе Шегаилге. ЕасЬ оЕ йе тейобк йксияке6 тау а1ко Ье аррИе6 со сЬе еотршабоп оГ 6есегпйпапь. ршш1тпсу чбй аП оГ те ге!ечапс геки!ь оГ (Ьа Ис) 1спеш а!иеЬга ск авкнгпе6. р|паИу, вче 6!юикк йе пюге 6сТИеи!с ргоЫет оГ юЬИпИ кувсепь оГ попИпеаг ециа6опк. ТЬЬ сорго )к икиаИу еочеге6 Ьпейу 1п Ьак|е а)аеЬга еоигвек; Ьис, спечпаЫу опе чпооипсегк оп|у кипр!е куксетк чгЫсЬ тау Ье ю1че6 Ьу а еотЬспабоп оГ киЬкисо6оп, Гаес пхабоп ап6 йе Ьпошп Еогпш!ае Еог ип!чапасе ециабопв.
А11ЬоиаЬ йеке сеепп|циек аге хсгеспес у ивеГи|, йе зепега1 ко|и6оп гецшгек а гпоге гоЬикс арргоасЬ. и|ге ргевепс а спейси| сог поп|теаг е!ппта6оп ив!па йе ро!упопйа1 геки|сапс 6ецпе6 |и СЬарсег 7, 1с чИИ Ье овеса||, Гог й|к ап6 |жег еЬарсегв, ш с$ече|ор йе сЛеогу оГ гекйсапсв ап6 с$ьсияя а!кос)сЬтв Еог йегг еоспрша6оп, Сяге !ассе йе ч!ечг сЬас сЬе гооы оЕ а в|ар!е ро!упопиа! ециа6оп аге | пошп (а|йоиИЬ еотрисабоп сч!1Ь йесп гецшгек йе йепгу оГ п|реЬтк гхсепкнъп Иейк), А!добйшя Еог Сошрисег А1ЯеЬга апсс йегеЕоте йас йе гебиссюп оЕ а яуясеш со а я]пд1е ес]иас]оп сопяысшея а яо1ибоп. Ес вЬои16 Ье ро)псе>с оис сЬас йе сесЬпсз]ие бевспЬеб Ьеге!я Ъу по шеапя йе оп!у зпейоб Еог во!чаб попбпеаг есрзабопя.
А шоте гесепс (Ьыс яс!П "с!аяя[са!") арргоасЬ, ыЛЫЬ ыяев а цепегабхеб геяйапс ссие со Масаи1ау, >я йе Ьаяя Еог тпейосЬ беяспЬесс Ьу Ьахагсс [11] апзс Саппу ес а1. [5]. (Яее асяс йе ехсепяче геЕегепсев оЕ сЬе >апет.) 1и СЬарсег 1О, зче беяспЬе а тпоге пшбепз сесЬпсс)ие ивспд йе йеоту оЕ ОгоЬпег Ьаяев Еог ро! упопба! ЫеаЬ. 9.2. Е.Пз)ЕАК ЕЩАТТОЬСЯ АЬ]0 ОА(>ЯЯ1А[з( ЕЕ.ЕМПчАТ!О]ч' > ес ив сопвЫег а 1!пеаг вувсеш оЕ ес>пас[сия очег ап !итра! боша1п Е>, зчгзпеп Ах= Ь (9.!) ы Ьеге А Ь ап т х л шасгЬ зйй епсбев а, х = [хз,..., х„], апб Ь = [Ьз,..., Ь ] . Ав Ь сурзса! ш высЬ йясияяопв, зче ипшеб!асс!у тек!пес оиг аиепиоп со сЬе саяе зчЬете А Ь а яс>пахе (л хи) шапса; ехсепяопя со ойег савея зчП! Ье ечЫепс 1асег оп.
1с Ь зче1! 1зпозчп Егопз сзпеаг асдеЬга сЬас йе ко!ибопя оЕ (9.1) (ог а ртооЕ йас йеге аге попе) шау Ье сопзрисеб Ьу гебис>пЯ йе аирпеигеб таЯх А(о> = [а;С >] = [А ] Ь], 1 6 ! < и, 1 < Е' < л+1, язсЬ йас (чтЬеп А Ь попа!пЯыЬг) йе Еаяс и со1шппя оЕ Ас" з) Еопп ап иррег-и!апЯи!ат шаи[х, апб йе во!ибопя оЕ (9.1) аге ргесзяесу йоке оЕ А("з) ! =О. %е ашшпе Еог пои йас по йабопа1 епиу ш йе аЬоче Ь вето. (Ада!и, йЬ зпау Ье ге!ахеб ас а 1асег рошс Ьу абб(пд а "рсчобпя" ясгаседу со оиг асдопйшя.) ТЬе Ьеяс Сспоып [опии!а Еог йе аЬоче спшяЕоппабоп зя йе огс(!лагу баикк!а» е!!лйиат!о» Еоппы]а: сопзрисе йе епспея оЕ Асс) Ьу з-з) а() = а( ) — — а( ), зС+1<с хл,/с+16!'Ел+1 ч ч 66 з> асс (9.2) зчЬзсЬ Ь арр11еб Еог Ес = 1, 2,..., и — 1, ч>)е аборт йе сопчепиоп йас йе е!степь а>1~> (!с+1 ~ ! < л) аге ашипзезс со Ье хего ас йе епб оЕ втер А., апсс аП ойег е!етпепь пос ехр! ЫЫу ирссасеб гетпап ипспапяеб.
Бя!пя втапбалс сели!по!оду, ас втер Ег йе е1езпепс а„зз '> Ь саУеб йе рйог е>етелт апб гозч 1 Ь саПеб йе рйог тоыз. и Ьеге а>зл> з = Ь„! < з ~ и, Со ыРРег есЬе1оп Еопп ывспд Оаывв>ап е1птипабоп. ТЬаз Ь, зче арр1у а велев оЕ сгапкроппабопв со АС ); Азо) !Сз) з Аззз-з) 9. Зо19408 Бувсеп>в оЕ Ецоас!опв 391 Ехапгр!е 9.1. Сопв!бег йе 1!пеат вувсет: Зх1+'сх2 2хз+ хв хс — хг+ 2хз+ 2хв — — 7, 4х> — Зхг+4хз — Зхв = 2, -х> + хг + Охз — хв = 1 .
ТЬе кес!пепсе оЕ сгапв(попас!опв оЕ йе ап8псепсед гпаспх 8!теп Ьу йе ог6!пату Раева!ап е!Ьсппа6оп Еогп>01а (9.2) !в: 3 4 -2 1 3 4 -2 1 -1 2 1 -2 2 7 -3 2 -1 1 23 3 О— 7 8 3 3 5 3 А 8!)— ; А">= 25 20 Π—— 3 3 7 16 О 3 3 13 3 14 3 4 -3 4 -1 1 6 1 3 3 4 -2 3 4 -2 1 -2 5 23 3 3 72 !59 7 7 !39 278 1 -2 5 23 3 3 7 8 О— 3 3 О— 7 8 3 3 А12) А(з> = О О 20 7 О О 8 72 159 О О 7 7 7 1 8 О О О ттпегех; !в 8!чеп Ьу Хосе йас !Е Р !к пос а Оеуй йе арбате Еоппа1а (9.2) ртобпеев Егае6опв ав !и йе аЬоте ехапзр!е: стЬеп а; п Р, че Ьате а; и рр Еог/с > О. 1п рппе!р!е, с>68 !к !псопвег>пеп6а1 (О> (1> к!псе йе во!06опк со йе 8!чеп вувсесп!!е ш йе срго6епс Ое16 апустау. Нотгемег, йе (Ьсй с!еп) вовс оЕ гебпс!08 йеве (гает!опк со !остевс сего>к ч!а ОСР согпрйа6опв !в а с68псйеапс опе.
ТЬ!в !в рапгсо1аг!у ппропапс сЕ йе еоеЕЕсс!епсв Ьарреп со Ье гасюпа1 Еапебопв. 11 гв йегеуоге <$ев!гаЫе со ссе! ау йе сопгпп8 оЕ гргопепь ав Еаг ав рокк!Ые. 1Е !те авяипе йас т( = ссес(А) е О, 9)е )спета Егогп Сгапзег'в гп!е йас йе во!06опв оЕ !9. !) еап Ье ехргевве6 гп йе Еопп х; л.
= —, 1йт <а, г А)8опйитз Гог Сои)ризах А18еЬга азз азг ... азя з Ьз аз)а! ... азл х; =без = (А~ГЬ)т . (9.3) а„,а„г...а„;,Ь„а„), ...а Гн-1 <! б л, Гт+1 б у < л+1, Еог Г = 1, 2,..., л — 1. Ехапзр1е 9.2. Сопябег йе Ипеаг зуяепз оЕ Ехапзр!е 9.1. ТЬе яциепсе оЕ згапвЕоииаиопв оГ йе аибизепзеб изатбх 8! чеп Ьу йе 6)ч)яоп(тес 0аизв)ап еИпипаз!оп Гопии1а (94) Ь: 3 4 — 2 1 — 2 1-1 2 2 7 4-3 4-3 2 -1 1 6 -1 ! 3 4-2 1-2 0 -7 8 5 23 0 -25 20 -13 14 0 7 16 — 2 1 А Го) АО) = 3 4 -2 ! -2 0 -7 8 5 23 0 0 60 216 477 0 0 -168 -21 -168 3 4 -2 1 -2 0 -7 8 5 23 0 0 60 216 477 0 0 0 35028 70056 А(г) ; А(з) = %е зее йаз зч161е йе ирбые Еоппи!а (9.4) ачо!)Ь ртобис!п8 Екает!оив, йе 8говтЬ зп йе яяе оГ тЬе )пзе8егв !пчо1чеб Ь ехр!ояче. 1т Ь еаяу то зЬов йат! Г тЬе еиибез а„( ) аге б т68!т (ите8егз, зЬе епгиев а)) ) пяу сопка!и 2 б 618!зв.
Непсе, йе созирибп8 зиле Гог йе (а) гИч!кзоп-Ггее всбетие Ь туркаИу ватке йаи Еог йе огтбпагу 0аияк!ап ейииизизп кс1юие. С!еаг!у И Ь розяЬ)е зо согирите йе во!опоив а1пзовз еибге!у илббп Р. 1и авугпрзоис тепла, Ьовечег, со)приз!п8 6езептипаиЬ 6!тест!у (!.е. Ггогп соГастог ехрапяопк) вои!6 зеези ге!абче!у!пеИЬ)сит япсе!з гез!штев 0(гИ) оретабопк сотпрагеб зо 0(лз) Гог 0аивяап е1итииаиоп (сЕ. ЕхегсЬе 9.6).
ЫопезЬе!евв, йе абоче сопсерз гегпыпз а ча1)6 опе; ве йегеГоге вЬЬ то беке)(Ье чаиаизв оГ йе с!азяса! ясЬезпе (9.2) вб!сЬ созприте йе г)иапт(з)ез х;, зг (епбте1у в))Ь(и О) изоте еГГзс)спбу. ТЬе Ьав)с сопсерЬ оГ зо-саИе6 "Ггас6ои-Гзее" Сааза!ап е!ип!пабоп веге ргевептеб Ьу ВагеЬк (1! зи йе соптехзо(тЬе !пзе8га! т)озиази Х. 1атег ВагеЬз !2! ехтеибет) йеве збеав зо а 8епега) зпге8га1 бопъбп. (БисЬ а 8епегаИааиоп ваз аЬо ргезептеб Ьу Глрзоп (12).) ТЬе япзр1екз изеапя оГ ачо!6)п8 Гтасбоиз йзпп8 еИзтииабои Ь то ятир1у с!еаг йе 6епоибиазот оГ (9.2); йЬ у!е16з йе г)зч!гзолугее ебтизабол Гогпзи1а; а() = а(з )а( "— а( ')а1 (9.4) аб = аз аб — а„; а; 393 9.
Бо!чшя Бугаепь о( Ес)оасюпв 9.3. ГКАСТ10)ч)-ГКЕЕ СА15ББ1АХ Е1.1МПч(АТ10)в( (с ы ове(о! ш сопвсбег йе (оппп1ав (9.2), (9.4) ав апа(овсов ш йе Епс!сбеап а!аопбип апс! Еосйдеап РКБ, гевреспче1у, оГ СЬарсег 7. С1еаг!у, и (в рова(Ые со гебпсе йе соесКсс1епь оГ (9.4)!п сЬе п)аппег о( йе рппнпче РКБ, Ьу сотрпсшу бС()(а)„с, а)„,в, ..., а; „) РО .Ф) (г) гог еасЬ )с+1 я с < п, ас еасЬ ясаае. Т)спа Ьоъчечег, в61! гес!паев папу 0СР воЬсопсрошпопя. Рогсопасе1у (ав п4й йе гес$осе6 РКБ а!аоп(Ьгп) Ь К рояв1Ые со 6(ч)6е йе гевп)св о( (9.4) Ьу а рге)Аон р(чос е)етепс илйсп йе )псеБга1 с!оспап 1). То вес Ьосч сЫя К ровпЫе, япррояе йас аЬс., 6 е 7" 4 ... Ь р г7 г ...
в А (о) Айег саго Ьегапопв о( йе 6(ч(вюп-(гее (оопп!а (9.4) ше оЬКОп а Ь с О (ау"-Ье) (ад-се) ... (аЬ вЂ” с(е) О (аг7-Ьр) (аг — ср) ... (ав-ар) А(с) апд йеп а с г( О (ау"-Ье) (ая-се) ... (аЬ-г(е) О О (а~уг-а яа — аЬег ...
(а~ус-а~цЬ-аЬев +аЬАрюсед-асср) +аЬЬр+а)(ед — сп4р) О О (Чос)се йас йе епспея о( йе сЬп6 госч (ап6 а11 1о!1о)ч!па гоч)в) оГ А(в) аге )КисКЫе Ьу йе Рюос а =- а)(с). ТЬеге(оге йе епспев о( йе а)сеге6 гоч)я о( А(~) п)ау Ье )Ичсбес( Ьу а (вАй)п ))) Ье(ого ргосее6!па аА(Ь йе ейпбпа6оп. АКег апойех сега6оп, сче вчоп16 Кпд йас йе ) аИеге6) госчя о( А(в) аге с$!ч)в)Ые Ьу аЯ) = ф' — Ье. 1п (асс, восЬ с)1чсбопв ые роввсЫе а(! с) пооаЬ йе е!! пппабоп ргосевв. Раппа)!у. йК 1я ехргеввес! ав йе (в(пу1е-ягер) угас((оп-гасе гйпнпаг)оп всЬете: 394 А18онйпи Еог Сошраег А18еЬса ,(еп 1 (,.(о)) А(и) Ь а(с) = (а(с с) а.( ') — а(" с) а12 с)) !а(с и; = асс а; — ас а, аз (с), (с+1 < г < л, Ь-1 < / а л+ 1, Еог 8 = 1, 2,..., л-1» ЬссЬ, ассогеПп8 со Вагеьз, ваз 1спо» и со Еогдап. (9.5) (9.6) Кхапср1е 9.3.
рог йе !!пеаг зуяепс оЕ Ехашр1е 9. 1, йе кециепсе оЕ ьапзсониапоиз оЕ сЬе а»8гпепсес( гиаснх Ьдчеп Ьу йе Еьсс!оп-Егее Еоггп»1аз (9.5), (9.6) ии 3 4 -2 1 0-785 0 -25 20 -13 0 7 16 -2 -2 23 14 1 3 4-2 1-2 1-1 2 2 7 4-3 4-3 2 -1 1 6-1 1 А()= 3 4 — 2 1 — 2 0 -7 8 5 23 0 0 20 72 159 0 0 — 56 -7 — 56 3 4-2 1 .4 (3) = 0-7 8 5 0 0 20 72 0 0 0 -556 -2 23 159 -1112 А (2) ас, ад ... асг аО ан и22 ..
аас а2, аш агг ... асс аг. ан а)г .. аа ар и(") = дес (9.8) Е+1 <с' <л, 1+1 а) <л+1 1с сап Ье зЬовп йас йе д!ч!зог икесс ш (9.6) !з йе !зг8екс роза(Ь)е зиоЬ д!ч!зог. 1Е йе епы!ек а,(о) аге ра!упоииа1з оЕ де8гее Б, йеп йе де8геек оЕ йе епгдек аг(с) аге Ьоиидед Ьу (/с+1)Б. (А з!пи!аг геки!с Ьо!дз вЬеп йе соеЕВс1епь аге !псе8егз; зее Ехегоье 9.1.) Япсе спе епсгу а„'„" С) ргос!»сед !п сЛе аЬоче сиейод сз дес(А) (кее ТЬеогегп 9 1 Ье1ов), » е Ьаче а ро!упоииа! Пике десегпипапс а!8опйт. Могеочег, »дй йе адд!Ьоп оЕ ап апа1о8опз Егасдоп-Егее "ЬаоЬ-ко1ч!п8" ксЬепге ве вЕП Ьаче а соспр!есе зо1ч!п8 а!Попс!ии.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
