Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 99
Текст из файла (страница 99)
4(х) =1 2'х'+0 2'х' — 2 2х+8 = 8х' — 4х+8; г(х) = 28х'+4х+8. 2. Последовательность яормированных полииомов, полученная при работе алгоритма Евклида, имеет коэффициенты (1,5,6,6,1,6,3), (1,2,5,2,2. 4„5), (1,5,6,2,3,4), (1,3,4,6), О. Следовательно, наибольший общий делитель равен ха + Зх" + 4х + 6.
(Наибольший общий делитель полинома и "обратного" к нему всегда симметричен в том смысле, что он равен своему "обратному", умноженному на обратимый элемент.) 3. Алгоритм 4.5.2Х остается корректным при замене целых чисел полиномами иад Я, По завершении алгоритма мы получим П(х) = вт(х), И(х) = ив(х). Пусть гл = с!еб(п), и = г(еб(о). По индукции легко доказать, что после шага ХЗ в процессе выполнения алгоритма Йеб(из) + боб(о~) = и, йеб(из) + йеб(из) = т при условии, что ю > и, Следовательно„селили пбольше, чем г! = деб(бс4и,с)), тобеб(У) < т — 4,4еб(Г) < и — 4; точные степени равны гл — 4 и н — А, где гЬ вЂ” степень предпоследнего ненулевого остатка.
При 4 = ппп(гп, и), скажем, г( = и, имеем У(х) = 0 и 1'(х) = 1. При и(х) = х — 1 и «(х) = х — 1 тождество (х~ — 1) шея)(хь — 1) хт мья к показывает, что все полиномы, образующиеся во время вычислений, нормированы и имеют целые коэффициенты.
При и(х) = хз' — 1 и «(х) = х'з — ! имеем 1'(х) = хм+хе+хе+ха+1 и Цх) = -(х'э+хе+х" +х" +хэ.!хе+ха+х). (См. также равенство 3 33-(29), дающее альтернативную формулу для П(х) и К(х), а также упр, 4.3.2-6, в котором 2 заменено иа х.) 4. Поскольку частное д(х) зависит только от «(х) и первых гл — п коэффициентов в(х), остаток я (х) = в(х) -д(х) яя(х) равномерно распределен и независим от «(х). Следовательно, каждый шаг алгоритма может рассматриваться как независимый от других. Этот алгоритм ведет себя существенно лучше, чем алгоритм Евклида над целыми числами. Вероятность того, что яяя = и — Й, равна р' "(1 — 1/р), и ! = О с вероятностью р ".
Каждый последующий шаг, по существу, ведет себя так же, поэгому любая данная ношяедовательиость степеней и, и,, ..., пм -оо появляется с вероятностью (р — 1)'/р". Чтобы найти среднее значение /(пп..., пя ), введем обозначение Я для суммы /(им, .,, ія) по всем последовательностям п > пя » . и, > О, имеющим данное значение й тогда сРеднее значение составлЯет 2 я Я,(Р— 1)'/Р". Пусть /(пп..., пя) = К тогда Вя = (",) К так что среднее равно п(1 — 1/р), Точно так же при /(гя„..., пя) = пя + + и, получим Яя = () (", ') и среднее значение ( ) (1 — 1/р).
И наконец, для /(пя,...,пя) = (п — пя)гяя+ . +(пя-г — пя)пя =("„";)-( + )(т,',') (""и",) и среднее значение составляет ("~з') — (и+ 1)р/(р — 1) + (р/(р — 1)) (1 — 1/р"+ ). (Вероятность того, что п,„я = и, — 1 для 1 с !' < 1 = и равна (1 — 1/р)", получается, если выбрать Яя - -)!=и); эта вероятность стремится к 1 при р -о оо. Как следствие имеем дополнительные основания утверждать, что алгоритм С всегда дает бз = ез = = 1, поскольку любые полииомы, не удовлетворяющие последнему условию, не будут удовлетворять и прежнему условию по модулю р при любом р,) 5. Используя формулы из упр.
4, при /(пп..., и,) = [ия = 0) найдем, что вероятность равна 1 — 1/р при и > 0 и 1 при и = О, 6. Полагая, что постоянные члены в(0) и «(0) ненулевые, представим себе алгоритм деления "справа налево", к(х) = «(х)д(х) + х "г(х), где деб(г) ~ деб(«). Получим алгоритм поиска боя), аналогичный алгоритму 4.5.2В, который, по сути, представляет собой алгоритм Евклида, приложимый к "обратному" полин«му (в смысле упр. 2).
Впоследствии ответ обращается и умножается на подходящую степень х, Существует подобный ютгоритм, аналогичный методу из упр. 4.5.2-40. Среднее количество итераций для обоим алгоритмов найдено в работах Сь Н. Хогяоп, 61СОМР 18 (1989), 608-624; К. Ма аяяб Л. топ хвг Саебев, Х Яушбо!!с Сошр. 9 (1990), 429-455. 7. Обратимым элементам Я (в качестве полииомов нулевой степени). 8. Если и(х) = «(х)ш(х), где к(х) имеет целые коэффициенты, а «(х) и ш(х)— рациональные коэффициенты, существуют ненулевые целые т и и, такие, что гл е(х) и и. я«(х) имеют целые коэффициенты. и(х) примитивен, так что (4) означает следующее: и(х) = рр((пт «(х))(п «я(х))) = хрр(гп «(х)) рр(п ш(х)). 9.
Алгоритм Е можно расширить гледующим образом. Пусть (ия(х),вз(х),вз,ия(х)) и («~(х). яп(х), ез, щ(х)) представляют собой четверки, удовлетворяющие соотношениям кя (х)п(х) + пз(х) «(х) = пзкя(х) и «я(х) в(х) + «з(х) «(х) = «з«я(х), Расширенный алгоритм начинается с четверок (1., О, сове(и), рр(к(х))) и (О, 1, сове(яя), рр(«(х))) и работает с ними таким образом, чтобы соблюсти указанные выше условия, где кя(х) и «я(х) проходят по той же последовательности, что и и(х) и «(х) в алгоритме Е. Если акя(х) = 4(х)«я(х)+Ьг(х), то аиз(ие(х),иг(х)) — д(х)из(е)(х), иг(х)) = (г)(х),гг(х)), где г)(х)и(х)+гг(х)и(х) = 6изезг(х), так что расширенный алгоритм может сохранить требуемые соотношении. Егги и(х) и е(х) взаимно просты, то расширенный алгоритм в конечном счете находит г(х) нулевой степеня и мы получаем У(х) = г г(х), \'(х) = и (х), как н требовалась.
(На практике можно разделять гг(х), гг(х) н 6изиз на бее((сопг(г)), сов»(гг)) ) Обратно, если такие В(х) н Ъ'(х) существуют, то и(х) н и(х) не имеют общих простьгх делителей, поскольку онн прнмитнвны н не имеют общих делителей положительной степени. 10. С помощью последовательного разложения приводимых полнномов на полиномы меньшнх степеней мы должны получить конечное разложение любого полинома на непрнводимые.
Разложение содержимого единственно. Чтобы показать, что существует не более одного разложения на примитивные части, необходимо доказать, что если и(х)— непрнводнмый делитель пронээедення е(х) гэ(х), но не произведение обратимого элемента н непрнводнмого полннома е(х), то и(х) являетсв делителем и»(х). Это можно доказать, обратив внимание на то, что и(х) представляет собой делитель е(х)ш(х)с)(в) = гю(х)— ю(х) и(х) К(х) согласно результату упр. 9, где» вЂ” ненулевая постоянная. 11. Потребовались бы талы»о строки А), Ао, Ве, Вз, Вг, В), Вэ, Сг, Сз, Рг.
В общем, пусть и +г(х) = О. Тогда строкн, необходнмые для доказательства, — от А„„» до Ао, от Вв»-и» до Во, от Свг-в до Са, от Рв»-в» до Ре н 'г, д. 12. Если и» = О, доказательство, приведенное в тексте для (24), показывает, что значенне »-» З»-»)З»-г) детерминанта составляет х6», что равно хе»» / П» <» г . Если полиномы имеют множнтель положительной степени, можно искусственно положить, что нулевой почином имеет нулевую степень, и использовать ту же формулу с 4» = О. »7римечаниг.
Значение детерминанта Сильвестра Я(и, е) называется регула»панн»ам И Н и, а ВЕЛИЧИНа (-1)в»Зов)»З'гш) ))»~г(и) )й(и, и') — диехриМииаи»ИОМ и, Гдв и — ПРОИЗ- водная и. Если и(х) имеет разложение внда а(х — а))... (х — а ) и если и(х) = Ь(х -)1))... ... (х — Вв), то результант В(и,е) ранен а"и(а))...е(а ) = (-1) "Ь и()3»)...и()»в) = а"6 П„, П„".,(а, — Д).
Отсюда слелует. что полиномы степени»пп от д определены как соответствующие результанты и(д — х), и(д+ х), х и(д/х) н и(дх) с и(х), имеющие в качестве соответствующих корней суммы а; + Д, разности а, — )у»ч произведения аай» н частные а,/)3» (при и(0) ~ 0). Эта идея была использована Р. Г. К. Лаосом (Н, С.
К. 1.ооз) для создания алгоритмов арифметики алгебраических чисел [Сотригп»8, Барр)ешеаг 4 (1982), 173-187]. Если каждую строку А, в матрице Сильвестра заменить строкой на (ЬоА»+Ь!А+) +'''+Ьвг-)-»Авг-)) (аоВ, +а)В)е) +. +авг-» »Ввг-)), а затем удалить строки с В г» по Во и последние пг столбцов, то получим детерминант размера и) х щ в качестве результапта вместо исходного определителя размера (и) + пг) х (и)+пг), В некоторыхслучаях результант может быть эффективно вычнслен по значению этого детерминанта [см.
САСМ 12 (19б9), 23-30, 302-303[. Я. Т. Шварц (Л. Т. Ясбпэггг) показал, что можно вычислить результанты и последовательности Штурма для полнномов степени и с помощью всего 0(п(!об и) г) арифметических оперений прн и -» оо [см. дАСМ 27 (1980), 701-717[. 13. С помощью нндукпкн по ) можно показать, что значения (и»+)(х) д+),6») замещены соответственно значениями (еь»г» и»(х)и (х) е+г»д», ег» 6») при ) > 2, где р» — — и) +п»-2п». [Несмотря на этот рост граны (26) остаются справедливыми.) 14. Пусть р — простой элемент из данной области и пусть 1,6 — максимум, такой, что р~1и~ = 4(е), р»1е -).
Пусть Р = р». Согласно алгоритму В можем записать 4(х) = аг+Ра)х+ +Р а,х', глез = пг-и > 2. Рассмотрим коэффициентыприх"+', х" нх" ) в «(х)9(х), а именно — Разе„+Р аги )+, аги +Ра)и„-)+ и аэе„)+Ра»и,—.»+ каждый из которых кратен Р . Иэ первого делаем вывод, чта р)'!ам из второго — что з рамы' у)')аа, а ИЗ трЕтЬЕГΠ— Чта Р~ аа. СЛЕдаэатЕЛЬНО, Р))Г(Х). (ЕСЛИ ГЛ ж И+ 1, ЛУЧШЕЕ, что можно доказать, — вто то, что р'")г) делит г(х).
Например, взгляните на в(х) = хе+1, е(х) = 4хг+ 2х+ 1, г(х) = 18. С другой стороны, можно воспользоваться аргументом, основанным на детерминантах матриц наподобие (21) и (22) для того, чтобы показать, что с(г) зш)-г з) ) гг(х) всегда кратно у(с)ыы! )-мзы))шгзм)-ггзр)-)) ]' 16. Пусть с,у --а;)а ) + ° +а,„апа Можно положить, что си > 0 при всех г. Если с, ф 0 дэя некоторого г уз у, то можно заменить строку г и столбец г нв (са -усуи ..., сы — Фсг„), где г = со /с))", эта опеРациа не изменЯет значение ))щ С и Уменьшает значение веРхней гРани, которое мы доказываем, поскольку сн заменяется на сн — см/ело Такое замещение можно 2 производить систематично ддя увеличивающегося ! и у < г, пока не будет достигнуто су = 0 для всех г уг у'.
(Этот алгоритм называетсл ауивогонализацвеа Грома-ШмюЬпа (см. Сгейе 94 (1883), 41-7З„.Мас)). Аппа)еп 63 (1907), 442).] Тогда гуез(А) м без(АА ) = си... с„„. 16. Полинам от одной переменной степени 4 над любой областью единственного разложения имеет не более г( корней (см.
упр. 3.2.1.2-16(Ь)); так чта если и = 1, то ясно, что ]г(Я)! < )Уь ПРи и > 1 имеем /(х),...,хн) = до(хг,,х ) + хгд~(хг, .,х ) + . + х)'дг, (хг,..., х„), где дь ненулевое минимум для одного уг, для данных (хг,..., хн) следует, что /(х),...,х„) равна нулю не более чем при )Уг значениях х), кроме случая, когда дг(хг,...,хн) = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
