Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 14
Текст из файла (страница 14)
г (х] =-. — ( — Н" Л',", (х] и НОД( ( ], ! (хЛ Докозателостоо. Обратим первое равенство в доказательстве следствия 2.7.7, используя выведенную фориулу длн !Ао' (х) ] '. [з(х) ~ [ А!т(х) — Л,',~ (х) ~ [з~ю (х) 1 Отсюда утвержление следствия очевидно С] 7! 2 б К ас а* а б о х тб Гл 2 Вз д ие» б:тв» т«уа г тару В качестве примера нспользованмя илгаритма Евклида для многачленав вычислим НОД Ь (х), 1(4 ! при з(х) -- х' — 1 и 1(х) х» г 2х ' 2х ) 1.
Имеем -(и — , ,х' †,х » г .т — 1 Таким образам, НОД !х' — 1, х' -1 2х' Ф 2х -1- 1! = х ; 1. Кроме тога, 2 х 1 — ( — —, х — — ! х (х), ( — х — х, —.! Г (х), 3 3!' ' (3 г! иак обещана следствнем 2.7.7. Можно вызволить значенае многочлева р (х) над полем Р в любом элементе 6 этого паля. Для этого надо вместо неопреде. ленной переменной х подставить соответствующий элеыент Р и найти элемент р (6) этога поля. Можно также вычислять значение маагочлсна в элементе из любого большего поля, содержащего поле Р. Для атаги надо, вместо неопределенной переменвой х подставить звачение элемента из расширения поля. Ясли Р— поле вещттвенных чисед, та вычисление многачлена в расшире.
нии ноля является знакомой ояерацией.Многачлены с вещественными коэффипнеатами чаша нриходится вычислять в поле «ом. алексных чисел. Эле»»ент 0 поля называется карлам миагачлена р (х), если р (6) — О Корни мнагочлена ие обязательно лежат в его собственном поле. Многачлен р (х) = х' + 1 не имеет корней в ноле вещественных чисел Теорема 2.7.0. Эммеит 6 лохи ягхягтся карием иеяулгзсга миагачлгиа 'р (х) гпогди и то ько тогда, когда (х — О! ябхяглмя дгхггтглггг много гхгяа р (х) Болев того, если стелеиь митачггии равна и, то многа»лги имеет в лоле лг более л корней.
Дтсазитехбстга. Согласно алгоритму. делении, р (х) =- (х — 6) Ц (х) + з (х), где стбпеиь многочлеиа з (х) меньше единицы, так что з (х) является элементом поля, см Следовательно, О - р (6) = (Р— О) Е (Р) Ф , так что з (х) — к» вЂ” О. Наоборот, если (х — О) давит р (х), то () -( — 6)Е(.) и Р (Р) — (й — 6) Я (Р) = О, так цо 6 явлиется «орнем мнагочлена р (х). Теперь разложим многочлен В произведение скадара и простых ниагочленав.
Степень многачлена р (х) равна сумме степеней простых делителей, и одни такай простой делитель имеется для каждого корня. Следовательно, число корней не может превасхад»иь я. П Теорема 2.7.10 (Интерполяция Лагранжа). Луста р, — мяамгстга иэ и .! 1 различных тачек, и пусть р (6») заданы дгя бсгх 2 =- О, 1, ..., л. Тогда нийде лсч в точности сдан мгшгачггя р(х) сигпеии а или мгиьшг, принимаюи)ий зяачгиия р (0») дхя всех 2 — О, ..., л. Эают мяагоч ги да тся разеястбам И 1* — йд Р( г',Р(В) гиг Даказатгльстао. Непосредственной подстановкой Р» вместо х можно убедиться, чта мнагачлен Р (х) приивмает в этих точках указанные значения. Однозначность представления следует из того, что если р'(х) и р"(х) — два таких многачлена, та много- член Р (х) .— р' (х) — р' (х) имеет степень, не превосходящую и, но а-1- 1 корней Р» прн й — — О, ..., л, Следовательно, Р(х) является нулевым многочленом.
Е) 2.8. Китайские теоремы об остатках Любое неотрицательное целое число, не превосходящее произведения модулей, можно однозначно восстановить, есле известны ега вычеты по этич модулям. Этот реаультат был известен еще в лревнем Китае и носит название ««тайской теоремы об остатках. Формуаировка ««тайской теоремы об остатках приведена на рис 2 2 Мы будем доназывать ее в два этапа.
Сначала будет доказана единственность решения, а затем (построением пропедуры отыскания решения) его существование. ПРежде чем строить формальную теорию, приведем простой пример. Выберем в качестве модулей т, = 3, т, = б г» т, =- 6 и положим М = т»т»~ — 60. Для заданного числа с, лежащего в иигеРвале 0 чй с < 60, обозначим сг = Р„(с!. Китайскаа теорема утверждает, что между шестьюдесятью такими числами с и шестьюдесятью векторами (сб сн сй соответш.вующих вычетов 72 Гл 2. Ввд ш з аб гэв тяую ю бру та Кю Зс*; бэ и б тт» существует взаимно однозначное саответстаие Предположим, что с, = 2, с, -- 1 и с, = 2.
Тогда эти условия приводят к следующим возножностям. с 6 )2, 5, 8, 11, 14, 17, 20, 23, 26, 29, ...), с 6 ) 1, 5, 9, 13, 17, 21, 25, 29, ЗЗ, ...), с Е )2, 7, 12, 17, 22, 27, 32, 37, ...). Единственнын решением служит с = 17. Позже будет дан простой алгоритм вычисления числа о по его вычетам.
В рассмотренном првмере число однозначна было восстановлено по его вычетам. В следующей теореме доказывается, что это имеет место в общем случае. Теорема 2.8.1. Для заданного миожеслыа целык иоложитель- ныг лолиряо взаимно лрштых чисел те, т, ..., т„и множества нготрицательнык целик чисел сю см ..., сь лри с, < т, си тема с,=с (шодт,), 1=0, ..., й, имеет не более одмого решения в интгреале 0 < с < Цгпи г г Доказшлельслыс.
Предположим, что с и с' являютхя двумя лежащвми в рассматриваемом интервале решениями. Тогда с =-!ггт~ — с~ и с = г))тг — с! и, следовательно, с — с' «ратно т, для каждого 1, а так нак т, попарно взаимна просты, та с — с, кратно Ц сги Но число с — с' г в лежит между — ~Ц т, — 1) и Цть Единственным положитель. ным числом, удавлетаоряющйм этим условиям, является с — с' —.- = О. Следовательно, с .-- сС !3 Имеется простой путь построения решения системы сравиени й аз теоремы еоремы 2.8 1, основанный на слелствии из алгоритма Евклида.
и1 Согласно этому следствию, в кольце целых чисел дл» каждого в и нандутся такие о и Ь, что НОД )з, !) = т М Ьй Длн заданного множества попарно взаимва простых положнтельчисел ты т, ..., ть, исполшуемых в качестве модулей, положим М =- Цт, и М, =- М)т, Тогда НОД [Мь т,) = 1, г б н, следовательно, существуют такие целые У, и ли что Лг,Л4,-'; —,т,. 1. г=О,..., й. Теперь можно доказать следующую теорему. Теорема 2.8,2.
Пу ть М = Цт, — лроизведение онорио вза. г-б омно простых положительных чисел, иуале М, .= М!т. и пусть длл каждого г Лг, удавлелыормот раве ел вам Ц,М, -1- л,т, — 1. Тогда единсл енным решением висте ы сро наша с,=-с[гподт,), г=О,...,Ь, является с =- ~ сну,гИ, (шод ЛП. г-е Доказателжпва. Пжкольку мы уже знаем, по решение рассчатриваеыай системы сравпени» единственно, надо талька даказат~, что выписанное выше с действительно является решением.
Но для такого с с = ~ с)УМ, =сУМ, (пюд т), .=е бо , делит М„ при г ~ !. Наконеи, так кзк ЛггМ, -1 л.т, = 1, то У,М, = 1 (тад т,) и с .— с, (пгод т,), гга н завершает д чательство (3 Чтобы проиллюстрировать теорему 2.8.2, продолжим прелыдущий пример. Заметим, что М = 60, М, = 20, М, = =20, М,=!5 и М, —.. 12 Далее, кзк нежно вычислить по алгоритму Евклнла или проста проверить, 1 = ( — 1) М, -1 7ты 1 .= ( — 1) М, + 4ти 7б 7г Гл 2 В е* е е гб тс у лгебоу 22 Ке Зс««р бы пр, рр„„„, ~г~(*)=' и,, ! ()К !=а, гл ~п() ми р г Обре т гре е ,1)= ~Р'()н"~()м'"(х) ( бм(2 О! (.) = П ' " (*), И ~г> (*) — М !.)Гмщ 1,1 г-ч лаг 1,1 м~гг 1,1 ш Мг> 1„) ю 1„),, 1 —.
( — 2) М, — Бтю Следовательно, )У,М, =- — 20, Л',М, = — 13, )УеМг = — 24 и с = — 20с, — ! Бс, — 24с, (шоб БО). В частности, при с, = 2, с, = 1 н с, =. 2 имеем с = †1 (шоб БО) -- 17, по мы видели н раньше. Китайская терреме об остатках является основой предстввле. ни» целык чисел, н шпорам просто выполняется операция умна. щения. Допустим, что надо выполнить умножение с =- аЬ. Пусть а, =- П г (а), Ь, = П г (Ь) и с, = И г !с) для каждого = О, ..., й. Тогда с, = а,Ь,(шоб тМ и эта умножение вычислить легче, так «ак а, и Ьг являются малыми целыми чнсламн. Аналогично, при сложении с — а Ь имеем с, — а; †.
Ь~(шоб те) для всех г =. О, ..., й В обоих случаях дл» получения окончательного ответа с должно бъпь восстановлено по вычетам в соответствии с китайской теоремой об остатках. Переход к системе вычетов позволяет разбить большие целые числа на ыаленькие кусочки, которые легко складывать, вычитать и умножть. Если вычисления состоят только нз этих операций, то такое представление является альтернативной арифметической системой.
Если вычисления достаточно просты, то переход ст естественной записи целых чисел к записи через систему остатиов и обратное восстановление ответа в целочисленном виде могут свести на нет все возможные преимущества прн вычислениях Если, однако, объем вычислений достаточно велин, то таней переход может оказаться выгодным. Это происходит по. тому, чга при вычислениях все промежуточные результаты можно сохранять в виде системы остатков, вмполняя обратный переход к целачисленноыу виду только при оиончательном отваге. В кольце многочленав над некотормм полем также имеегсн китайская теорема об остатках, формулировка которой приведеаз на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
