Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Определение 2.7.1. Пусть г (х) = г х" -1- г„ю" — ' -1- -1- ф г,к -1- г, есть многа шеи над полем Р. Формохэлой лроизеодяой от г (х) назывзется мноючлен вида г' (И) = (лг ) х" — '+((я — 1) г„,) х" — '.1- ... +гг, где новые коэфф»цненты вычисляются в поле р как суммы г калий элемента гб ((гг) = гг + О -1- -'- ' Легко проверить, что сохраняются многие полезные с»айства произ»одных, а именно, что (г (х) 3 (х)1 = г (х) з (х) -1- г (х) 5 (х), и что если о' (х) делит г (х), то о (х) делит г'(х). В кольце мнагочленов яаа полем возмангно сокращен ° , если с (к] о (х) = с (х) Ь (х) н с(х) отличен от нуля, то о (х) =.

Ь (х). Кроме того, в пальце многочленов имеется слабая форма деления, иэвестаая пад названием деления с остатном или алгоритма деления. Теорема 2,7.2 (Алгоритм деления для много»пенсе). Дхя каждого млогочлеиа с (х) и иелутвога миогочлеиа б (х) сущесвтует единственная лоро много мелов () (х) ( еюлмое) и з (х) (остаток), таких члго (.) =Е(.)б()+ () и бей з(х) < бейб (х). Докалатееьство. Частное и остаток находятся по элементар- ному правилу деления мнаючленов. Оии единственны, так нак если с(х) = Ю (х) б(х) ф г,(х) = Я*(х) б(4 ф Ъ(х), то б (х) 1Ц~ (х) — (г (х)1 = гг (т) — 5 (т). В правой части равенства стоит ненулеюй многочлен, степень которою меньше бейб (х), в в левой — ненулевой многочлен, степень которого не меньше бей У (х).

Следовательно, оба много- члена равны нулю, и представление единственно О Практически вычисление частного и остатка выпочняется с помощью простого правила деления уюлком . Частное иногд» обозначается Обычно мы будем больше нгпересаваться остатком, чем частным. Остаток часто записываетс» в виде а (х) = Рвет !с (к)1, или е (х) = с (х) (пгаб б (х)). Мошна записать также срази»ние з (х): с (х) (тоб б (х)), нагорав обозначает, что мнагочленм г (х) и с (х) имеют один н тот же остаток при делении иа б (х). Чтобы найти Рвы~ )с (х)1, казалось бы, надо выполнить деле»ее. Однако имеется несколько приемов, позволяющих сократить я упростить необходимую для этого работу. Прежде всего заметим, что Рам !с (х) 1 = Рвем (с (4 -1- о (х) б (х)!.

Нс «змеияя остатка, к с (х) можно прибавить любое кратное много- члена У (х) Следовательно, не изменяя остатка, можно искдючить старший коэйфнциент миогочл нз с(х), арибавляя саответству. ющее нратное мнагочлена б (х) Используя этот метод при »ри- ведении многачлена с(т) по модулю приведенного мвогочлена б(х)=. х'+ хг б.хг, — 1 для упрощения можно член к" заменить мнагочленам — ~„,ь ~б,х всюду, где это улобно. Такой прием упрощает вычисление остатка путем деления ьшогачлевов «уго.тиомь Другой способ упрощения аадачи вычисления остатка от деле- нна дается следующей теоремой.

Теорема 2.7.2. Ес и миоючлел б (к) кр еч много«лену у(х), то Рв ю !а (х)1 = Р, гт (Рв < г (о (т))1 для любого о (х) Дскитсл юстас, Пусть б (х) .— у (х) И (х) для некоторого И (х). Раскрывая правую часть, получаем о (х) =. Я, (х) б (х)+ Рггт !а (х)] = = 0 (х) И(х) у(х)-ЬЯ (х) у(х)+Рею !Р ыг !'(х)11 где степень остатна меньше бейб (к). Раскрывая левую часть, имеем о (х) = О (х) у (х) + Рвы, (о (х) 1, я, согласно алгоритму деления, такая запись однозначна при степени остатка, меньшей бей у (х).

Теорема вытенает из отождествления подобных членов в обоах выражениях. С) В качестве примера использования теоремы 2.7 3 разделим Зз вт г. 66 Га. 2 В х» Заза иигю шгюру х' ф х ф 1 на х' — , 'к' 1 к'-1 х -1- 1. Деление «уголком» было бы утомительно, ио если вспомнить, что (х — !) (х" -1- х' 1- х' -'г ф х 4-!) =-хд — 1, то можно сначала разделить на х' — 1, а затем на х' -~- х' -1- к' -1- х 1- 1. Тогда ](, г ]х' -1- к -1- 11 = к* ф х ф 1, н теперь деление на х' ф «' -1- к' к — 1 трввнально, тан чта Я*6ш ем.г*», ]х' -г х .!. 1) .— х' — . 'к 1- 1. Другое удобное правило дается следующей теоремой.

Теорема 2.7.4. (1) Рг го (а (х) !-Ь (к)) —... Рг,ю ]а (х)) 4- Рг„,]Ь (х)). (В) Ргел !а (х).Ь !х)1 = ](го~ ]Ргм,]а (х)) Рг ~и !Ь (хб! Дагазишггьстаи Прнмення алгоритм деления я абенм частям первого равенства, запишею а (хбф Ь (х) — 0 (х) д (х) -1- Ю <и ]а (х) -1- Ь (х)) н а (х)-'. Ь (х) — Я' (х) д(х)-1 Ргм» !а (х)]-!. -'- О (х) д щ) -1- Я«ю (Ь (х)]. Часть (1) вытекает на однозначности алгоритма леаенвя. Часть(И) доказывается аналогичным образом. О Надобно тому нак часто бываег полезным представленне пелых чисел з виде произведения простых сомножнтелей, часто бывает полезным представление мнагочленов в виде произведения непрн.

вадямых многочленов. Чтобы сделать разложение целых чисел на простые множителя однозначным, прнходнтся ограничить рас. смотрение только положятельнымн простымн ~ислами. Аналогично, для однозначности разложения многочленов приходится условиться, что непа.чьзуемые в «ачестзе простых делителей многочлены являются приведенными многочяенами. Теорема 2.7.6 (теорема об однозначном разложении). Много.

'мел яад игяоторым полем однозначно раз агагшгя г ароиззгдеяие глез»ели~а лала и прогюмх яад даиимм полем мнагочхеяоа. ирикея стелгя» хакдого иэ лих раааа ло мея имй мере 1. Доиазашгхыяию. Ясно, чта входящнм в пранзведенне элементам поля является коэффициент р„, где л — степень разлагаемого многочлена р (х). Этим элементом можно пренебречь н доказывать теорему для приведеннмх многочленов. Предположим, что теорема не верна н пусть р (х) — приве денный многочлем наименьшей степени, для «отораго она не верна 27 К г»и» шг г ноэ Тогда имеются два разложения, р (х) = а, (х) а, (х) ...

а» (х) =. Ь, (х) Ь, (х) ... Ь, (х), где а» (х) н Ьг (х) — пРостые многочлены Все многочлены а» (х) должны отличаться от всех многочле- нов Ьг (х), так кан в пр3тявном случае можно было бы сенратнть общие члены в пшчУчить многочаен меньшей степени, «атоРый можно разложить двумя равными с»»особами. без потери общности предположим, что степень многгмлена Ь, (х) не больше степени многочлена а, (х) Тогда а, (х) = Ь, (х) Ц (х) -1- х (к), где бей з(х) < дей Ь, (х) < бей а,(х). Далее, з(х) а»(х) ..а» (х) = Ь»(х) (Ь (х)...Ь,(х) . ]) (х) а»(х). а» (х)]. Разложим мнагочлен з (х) в стоящий в квадратных снобках много. чден на простые ьгножнтелн, разделив, еслн надо, на соответ- с ушй т прл тая, б а ел б лн приве денными.

Поскольку Ь,(х) не содержатся в левой части, мы пслу. чилы два различных разложения приведенного многочлена, сте- пень которого меньше степени мвогочлена р (х). Эта противоречие доказывает теорему. П В силу теоремы аб однозначном разложения теперь ясно, что НОД ]з (х), 1(х)1 я НОК (з (х), ! (х)! нвчвются единственными ддя любых двух многочленов з (х) я 1(х), тан пан наибольшнй общий делитель равен пронзведенню всех общих для з (х) н 1 (х) простых делителей, причем каждый делитель входнт в наимень- шей нз степеней, в которой он входит в з фй я в 1(х), а наименьшее общее кратное равно произведению всех простых лелнтелей, вхо- дящих лаба в з (к), лнСю в 1(х), прячем каждый делитель входит в наибольшей степени, в которых он входит в з (х) нлн в 1(х).

Из алгорнтча деления для многочленов вытекает важное след- ствие, известное под названием алгоритма Евклндз для ынаго- членов. Для заданных двух многочленов з (х) и г(х) их наиболь- ший общий делптель может быть вычислен с помощью нтератнв- ного применения алгоритма деления. Вез аотерп общности можно полагать, чта бей з(к) Рм мбей 1(х); алгоритм состоит нз последовательности шагов з (х) =- Огп (х) г (х) -1- Рп (х) ! (х) =.

]]гз) (х) 1~»(х)+г~г»(х), ((о (х) Оа» (х) гм» (х) Гггз> (к), )м-з) (х) -. Ом» (к) !Р -и (х] -!. 1(ю (»), 1»"-и (к) =. О~ и (х) Рю (х), зз Гя 2. В яти з зб твзятвг я бву где остановка проггесса наступзег при получении вулевога остатиа. и слелиий ненулевой остаток Рю (х) равен наибольшему общему о делителю. Доказательство этого факта дается следующей теорема . ой. Теорема 2.7.б (Алгоритм Евклида для миогочленов).

Для двух аодгннси многочееное з(х) и ](х) с дейв(х))~бей((х) пусть де> (х) .—.- з (я) и Рог (х) = ! (х). Решение рекуррентних уравнений 1[ Оф] ГО ! ](д — (]] !" (х) ! ! ! — (]гю (х) ] ! ]о и (х) ) лри г = 1, ..., л доился величиной Ую (х) = и ПОД Н (х), ! (х)1, где л — наименьшее пояожигпем,нос число, для которого бю (х) = =- О и и чь О принсдтгкит полю. Дояитотсяьстеа. Так «ак дей ]олог (х) ( дей Рю (х), то дле некоторого п обязательно наступит событие Рт (х] — — О, так что алгоритм будет завершен. Легко проверить, что [ О ! 1- [г)! (.] ! 1 ['~:]1=8 ['"" '1ННГ1 так что многочлеи ию (х) должен делить аба миогочлена з (х) и ! (х) н, следовательно, НОД Н (х), ! (х)1, Далее, [Н""'1 =Ы [' .'Н.Д ['(:]1 так что любой делитель обоих многочленов з (х) н ! (х) доажен делить и много шеи дт (х).

Таким образом, НОД 1з (х), ! (х)1 делит ую (х) и делится на з" (к), и, следовательно, ат1 (х) =. и НОД !5 (х], Г (х) 1, где а — ненулевой элемент поля. Это заверишет доказательство теоремы. П Снова, квк и в слу гас с кольцом це,пых чисел, получаем два нажных следствия. Определим матрицу многочленов г 7 Ко.

ю ююго л т где А'с' (х) есть единичная матрица. Тогда мы вмеем следующий результат. Следствие 2.7.7. Дяя яюбмх деук многочгеноо з (х] и ! (х) нод потм Р сущеппзуют део других многочлена а (х) и Ь (х) над тем охе ло.тем, такие что НОД ]з (к), ! (х) 1 =. а (х) з (х) -1- Ь (х] ! (х) Докотитыьстеа.

Так как [ую(х) ~ [з(х) ~ и Ут (х) =- а НОД Н (х), ! (х)1, то утверждение следствия выподняется при а (х) = и 'А]!' (х) и Ь (х) = и 'А]з' (х). С] Многочлеиы а (х] и Ь (х) получаютсв из элементов матрицы Аюг (х) делением на и '. Два других элемента матрицы А (х) также имеют прямую интерпретацию, для описания которой нам вала вычислить обратную к матрице Аш (хй Наооманм, что '(О ! А (.]- П[, Отсюда видно, что определитель матрицы Ао'(х) равен ( — ЦС а обратная матрица дается равенством Л]1'(х) А]з'(х) 1 ', ~ г!зг'(х) — А(7(х) ~ Г:. Г -'~ Аз', (х) Аг' (х)) ' ~ — Л,', (х) А,; (х) Следствие 2.7.й. Вычисляемое е процессе иггоритгга Евклида лемтти Агг' (х] и А'.г' (х) удоолелморяют рагеистеам я(х] =( — 1)" Л],"~ (х) и НОД !з (х), ! (х)], .

Характеристики

Список файлов книги