Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 59
Текст из файла (страница 59)
Прн достаточна больших л это число меньше числа сложений, нсобходимык в прямом метеле вьшисления. При л = 1024 число необходимых в алгоритме сложений примерно равно числу сложе. ний прямого метода вычислений, по число умноже й мерно одной четверти от числа умножений прямого метода вычис. ленин произведения матриц размерности 1024. 10.7. Рекурсивный алгоритм Евклида С тратегия дублирования поаволяет ускорить алгоритм Евклида н построить алгоритм, сложность которого имеет и орядок л ой' л. Основные вычисления в алгоритме Евклида описываютс ваются ураяне. 0 Ч 1 = [рг ар~ эа! '"' 10 ! Аш" г'г(з1= (! ~ огг ( )1 где ГО 1 А<"г(х) = П [! Огг,(х)1 пт фцксярованногс Первая группа УР с~опт из г' итераций, совпадающих с первыми г' итерацияыи нс.
хадной задачи. Вторан группа содержит уравнения для г = г'-1- (, ..., Ш гочленов, «оторое окнзалось столь пригодным хля стратегия дублирования Поз~оку можно ожидаты что стратегия деления задачи пополам и дублирования позволит улучшить хариктеристики алгоритма Енк,аида. Иам яадо набор итераций раз,селить на две группы. Есчи это деление удастся осуществить так, что каждая иа групп будет похожа (нли может быть сделана похожей) на исходяую задачу, то мы получим рекурсивную стр7ктуру. Имеется.
однако, нескоаько деталей, о которых следую позаботиться Первая трудность состоит в том, что мы не знаем заранее число итераций, так что невоаможно сказать, ногд» воловика итераций завергвена. Эту трудность можно исключить, прерыван вычислевия в точке, в которой выполнена примерно половина итераций. другая трулность состоит в том, что 0">(х) зависит от А!' " (х), и, в свою о герсдь, А!о щ) зависит от Оо! (х).
Схедовательно, заранее не известны все участвующие в вычислении Ао! (х) его делители. При разбиеншг нв группы необходимо позаботиться о том, чтобы ни одни делитель не использовался раньше, чем он станет известным. Теорема 10.7.1 утверждает, что если разбиенно алгоритма происходит в правильной тачке, то структура обеих групп аналогична структуре исходяай задачи Пусть матрнпа Ао о (х) фактаризуется в виде А!'!(х) = Ао "ь'!(х)Ао'!(х), где я алгоритм останавливается, исгда многочлен б'ы'(х,' об ан ' (х,' ораЯ сн, чта вычисление матрицы А!и (х) имеет ту же саную уру, показанное на рнс. 10.1 вычисление произведения мно. ужесаиую струк- 0"'(х) = [ — „„~~~~, [„~ А"' аы) [„~.
Эга группа вы шслепий, очевидна, имеет туже фориу, что и исход. ная задача Перваз группа также имеет згу же структуру, но если для ее вычисления использовать тот же путь решения, го стратегия деления задачи не даст ожидземога улучшсвна. г!тобы уменьшать сложность, нада упростить вычаслеиие первой группы Такое упрощение зщ г О Б В лгв, в ни гоы зтщ является нето»нилом значительной экономии числа вычислений н основывается на слепуюгней теореме, описывающей условия, при которых возможно усечение делимого и делителя, не изме. няющее частотного н остатка.
Теорезш 10.7.!. Пуст~ деа задан ых многочхела ! (х) и у (х), степени «отары» связаны соотношением дей у (х) ( дей ! (к), за. писаны е виде / (х) — /' (х) кз -г /" (х) и у (х) — — у' (х) «з .!- у'(;с), где спмпени многочхеног /' (х) и у (х) меньше некоторого числа й, удовлетворяющего нераеенстгу й < 2 деду (х) — дед/ (х). Пушно шггоршпм деления приводит аютеетстеенно х равенствам / (х) = — Г/ (х) у (х) з- г (х) и !' (х) = С)' (х) у'(к) т- г' (х). Тогда (!) Е() =П'(), (В) г (х) = г' (к) х' ш г (х), где степане много»гено г" (х) меньим, чем й —, дей / (х) — дей у (х).
Доказатегштео. Утверждение теоремы является легко доната. ваемым слепо»вием однозначяостн алгоритма деления. Начнем с равенства Г (х) .= (/' (х) у' (х) »- г' (х) Тогда /' (х) к" ч- /" (х) .=- (/' (х) у' (х) к" + г' (х) х' -!- / (х), ! (х) = с7' (х) у (х) .!- г' (к) кь -~'- /" (х) — !)' (к) у (х). В силу однозначности алгоритма деления мы сможем заключить, П (х) = (/' (х) и г (х) = г' (к) к' .ь /" (х) — (/' (х) у' (х), если покажем, что дей !г' (к) к" -~- !" (х) — П' (х) у" (х) ! < дей у (х). Но, нспользун условии теоремы, это легко проверить для каждого из трек многочленов, стоящих в левой засти неравеаства: 0) дей (У (х) х'! ( дей у' (х) -!- !г =- дей у (х), (В) дей /" (х) < й — ! ( дей У (х), (|и) дей (П' (к) й" (х) ! ( дед /' (х) — дед у' (х) т й = = (дед/(х) — й) — (деду (х) — й) —, й ий деду (х) В «е ав тв торсе утверждение теоремы получится, если заметить, р енс (!г) и (и) следует, что степень многочлена !" !х)— т, что из — С)' (х) у' (х) меныпе, чем /г г- дей / (к) — дей у (х).
О Сзедствне !0.7.2. Пуст целое «ис.о й удгмттеоряет не ген спюу т ряет нера. й 2 дей у (х) — дей / (х). а (х) при дг гиии многоюена / (х) шг мншоч агисигл от й младших козффидшнп' й д озффициснтое м точмнт /(х) и у(х) о<азьмают ггалннг томно на те хоэффицшнты остати г(х), инде см поповых меньшг, шм й дей ! (х) — дей у(х), С) Согласно теореме 10 7.1, и многочлеи.частное () (х) в сегнент пюгочлена.остатка г (х) могут быть получены прн усеченнн мво~очлеиов / (х) и у (х) до более норотках мвогочленов. Мы сейчас ажем, что стбргсыввнне сегмента иного»лена.остатка г !х) не покаж Евклнзгтр ° гивзет некоторые последующие нтерапия алгоритма дг Нз самом деле, если выбрать й разумно, то примерно поло вика атераннй может быть вычисчеиа без знания отброшенного сегмента остатка г (х) Теорема !0.7.3. Пусть ! (х) = /' (4 х" -г- ! (х) н у (х) =.
== у' (х) к' ф у" (х), где дей/" (х) (й и деду" (х) < й. Пусть дед/(х) —. и, деду (х) < дед! (х), и луспм А'о> (х) и Аю (т) о ознашют мат б со т атрицм ш ~юритма Евклида, зычисмлные соотес п. х Тогда стггнно дгл штрихошнных и нсштрихоеан ых шргмгнных ш а ещи дей уца (к) ) (и — Ц/2, пго дзя к мдого г гыполнягтся ра. есштго Ао~ (х) = Ачо (х) (Иными сынами. частные остато~ных последоеа шльнштгй, порождаемых г процессе гыпог гния азгоритма Евклида, для нешп рисованных ц штриксааннм перез гнных совладают ш меиьимй мере до гпех пор, лоха яе будет дос шнут остап»он у'гп (х), степень холюрого меньше, шм пологи а стешин /' (х).) Поюззапмгьстео.
Доказательство сводится н применению следе»вия 10.7.2 на каждом шаге мгерании алтари~ма Евклида для не. шгриховаиных и штрихоеанных переменных при начальных уело. виях /' ° г (к) = ! (х), у~г~ (х) = у (х) и /'~ ° ' (х] = !' (т), у'~~г (х) = =. у' (х). Шаг !. Следствие 10.7 2 можно прииеннть на каждом шаге прн условии, славин, что выполняется неравенство й < 2 дей унг(х)— — дед/" (х) Но нам дано, по « — з дей у'~ ~(х)иь — , Мы искажен, что это условие энвивалентно нужному условию, сввзывая степени шгрихованных многочленав со степенями неппризованны» многочленов. Эти свлзи следуют из равенств Ъ 1 ) зая Га Ш В згм гоэ, ш н сра адта«рм и бей)'гм (х) = бей)мг (х) — й, бей йчэ! (х) = бей й~ь~ (к) — й Следовательно, поскольиу многачлен-частное является одним и тем же многачленом в штрихованноы и «ештрнхаваннон слу. чаях, имеют место равенства бей )'!'!(х) = бей )го(х) — )г, бей й'!'! (х) =- бей доЧх)--й.
Таким образом, нам дано, что ш !"(! — а бей рог (х) — й > —, так как л =. Оей Рм Э) > бей (ог (х). Это неравенство сразу сво. дится к условию й (2 бейб!0(х) — осй)о'(х), так что следствие )0.7 2 можно применшь на каждоы шаге итера. ции, если талька на предыдущеы шаге гперадии ьгногачлен Г) (х) вычисчен правильно.
Шаа 2. Согласно следствию )0.7.2, каждый многочлен.частное ' вычисляется правильно, если только предыдуюий многочлен-част- ное был вычислен правильна и послелний полученшяй многочлен- остаток содержит достаточное число ирааильных коэффициентов..
Чтобы проверить последнее условие, опять воспользуемся след.,' ствнен )0.7 2, заменив числа й числом Э'! = й ! бей)о — "(х) — бедро-о(х) и полагая йгзг = й. Согласно следгтаию г0.7 2 к началу г.га шага итерации мнагочлен.остаток будет правильно вычислен за исклю- чением, возможно, младших й!"! членов, *по согласна тому же, следствию не влияет на вычисление мвогочлена-частного при ус. лозин, что йго ( 2 бей йо!(х) — бей )о! (х). Тот факт, что это неравенство выполняется, проверяется слсдуюшнм образом: й!о — 2бебй" (х) -!- бей)о!(х) = й-!-Оей)о орх) — бейб!' — н (х!— - . 2 бей йго (х) -)- бед )!о (х) — й -!.
бед (о-О (к) — 2 дед йо (х) ( -б - — (2 —,"-) =0 где использовавы неравенства бед )о-'г(х) ( л и бейб(о(х) — бейб"г(ш-! й ( —"— Таким образом, йо! ...2дейй!'г(х) — бей("(х) Рм. го.7. ПР шатт н, следовательно, на г.ы шаге итерации многочлен.частное ие зависит от неизвестнык «оэффициентав Это завершает доказательство теоремы (О Условие бей йчо (х) > (л — . й)12» теоремы для нештрихо. зашгых переменных можно переписать в виде «бед йо '(«) . (н -)- ч- й)'2» Эквивалентность этик условий используется в форыули. г ровке рекурсивной процедуры Разбиение алгоритма Евк.чида пополам показано иа диаграмме на рис. )0.7.
В основной то гке ветвления алгоритма выносится ре. наи заа г. !о. В В р л рнн, о сгр иа хус раз а Рнк 1О.э Пршлур Пох а а Еэ Аас жение о немедленном разбнепив аадачи или о выволнсгги да гной иге о. аии стаи. р итерации алгоритма Еекшша, поскольку процедура рак биения и дублирования неприменима. Последнее решение прин»- мается толька атом случае, когда степень многочлева й (х)меньше половины степени многочлене /(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
