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