AOP_Tom2 (1021737), страница 132
Текст из файла (страница 132)
Например, рассмотрим, что случится, если не корректировать шаги ЕЗ и СЗ, а просто заменить и(х) на г(х). Это простейший алгоритм поиска ксб«, традиционно приводимый в учебниках алгебры (в теоретических целях, не для практических вычислений). Если предположить, что аз = бз = = 1, можно найти, что коэффициенты из(х) ограничены величиной Хз, коэффициенты иб(х) — величиной №, иб(х) — №з, ... и коэффициенты ив(х)— величиной №', гДе аз = 2аб, +аб з.
Таким обРазом, веРхнЯЯ гРань пРи т = и+1 вместо (26) приблизительно составляет «ув.з(з.4!4(" (27) ав аз ав аб аб аз аз аз аб аз аз ав Ь Ь Ь, Ь Ьб Ь4 Ьб Ьб О Ьв аб аз аз аб а4 аз Ь, Ь О Ь, Ь, Ь, Ьз Ьз Ьз Ь4 Ьз Ьз Ьб Ь4 ЬЗ Вообще, 61 будет больше единицы при «' > 1 тогда и только тогда, когда подобный детерминант, составленный из коэффициентов и(х) и и(х), равен нулю. Поскольку такой детерминант представляет собой ненулевой полипом от многих переменных- коэффициентов, он будет ненулевым "почти всегда" или "с вероятностью 1" (см. в упр. 16 более точную формулировку этого утверждения и связанное с ним доказательство в упр. 4).
В примерах полиномов в (15) бз и дз равны 2, так что эти полиномы, скорее всего,— исключение, а не правило. Эксперименты показывают, что простой алгоритм действительно ведет себя именно так; количество цифр в коэффициентах растет с каждым шагом экспоненциальио! В алгоритме Е, напротив, рост количества цифр лишь немного превосходит линейный. Еще одним побочным результатом доказательства корректности алгоритма С является тот факт, что степени полиномов будут почти всегда увеличиваться на 1 на каждом шаге, так что число итераций шага С2 (или Е2) обычно будет составлять 4«ея(и), если данные полиномы "случайны". Для того чтобы увидеть, почему это происходит, заметим, например, что можно выбрать первые восемь столбцов М и ЛХ' в (17) и (18). В таком случае можно найти, что и4(х) имеет степень меньше 3 тогда и только тогда, когда 4«з = О, т. е, тогда и только тогда, когда Все вышесказанное может использоваться для доказательства хорошо известного факта, что два полинома взаимно просты тогда и только тогда, когда их резрльгпаипс ненулевой; результант представляет собой определитель, имеющий вид строк с Аз по Ао и с Вт по Во в табл.
1*. (Это так называемый кдетерминаит Сильвестра" (см. упр. 12). Свойства результанта рассматриваются в книге В. 1, ъап бег %аегс(еп, Мос1егп А)йеЬга (имеется перевод на английский язык Фреда Блюма (Ггед В1ипз) (бечо 'зог)с: Епйаг, 1949)), разделы 27-28.) На основании приведенного выше материала можно сказать, что 8сс) "почти всегда" имеет нулевую степень, поскольку детерминант Сильвестра почти никогда не равен нулю. Однако во многих вычислениях, представляющих практический интерес, нельзя быть уверенным в том, что бсср не будет являться нолиномом положительной степени.
Что происходит при работе алгоритмов Е и С при бед ф 1, можно в точности увидеть, рассмотрев и(х) = ю(х)из(х) и с(х) = ш(х)из(х), где ис(х) и из(х)— взаимно простые полиномы, а ю(х) — примитивный полипом. Тогда, если ит(х), из(х), из(х), ...— полиномы, получаемые при работе алгоритма Е с и(х) = из(х) и и(х) = из(х), легко увидеть, что последовательность, получаемая для и(х) = еи(х)ид(х) и о(х) = ю(х)из(х), представляет собой просто тп(х)из(х), ю(х)из(х), ю(х)из(х), тп(х)ио(х) и т.
д, Поведение алгоритма С несколько отличается: если полиномы из(х), из(х), из(х), ... получены при работе алгоритма С с и(х) = из(х) и п(х) = из(х) и если де8(и +з) = с1е8(иу) — 1 (что почти всегда истинно при з' ) 1), то в результате применения алгоритма С к и(х) = то(х)ит(х) и и(х) = сп(х)из(х) получается последовательность Ю(Х)ит(Х), иЗ(Х)ит(Х), С~ш(Х)иа(Х), С~'ш(Х)и4(Х), С~ш(Х)ио(Х), ..., (28) Длн большей исности приведем полный вид результвнта двух полнномов оох + асс~ ..+а„, ИЬОХ" +Ь,Х" '+...Хььо а„, 1 ае, О а -юа1 О ао ас аз О ао аз аз ат-1 а 1 О .
... О ао а1 аз Ьо Ь1 Ьз . ... Ь с Ь„ О о ь ьз ь ... ь„ ь о о ьо ь, ь, . ь„ , ь. (см., например, Кори Г., Кори Т. Справочник по математике (длн научных работников и иижене- роа).— Мс Наука, ЬО7З, раздел Ь7,4).— Лркьс персе. где 8 = с(зп) (см. упр. 13). Несмотря иа наличие этих дополнительных 1-множителей алгоритм С будет превосходить алгоритм Е, так как работать с несколько ббльшими полиномами проще, чем постоянно вычислять примитивные части. Последовательности остатков, такие как получаемые в алгоритмах С и Е, полезны не только для поиска наибольших общих делителей и результантов.
Важным применением является перечисление действительных корней данного полинома в определенном интервале согласно знаменитой теореме Я. Штурма (Л. Бьпгш) [Меш, Ргезепгез раг Пмегз Яауапгз 6 (Райз, 1835), 271 — 318). Пусть и(х) — полипом над полем действительных чисел, имеющий различные комплексные корни.
Из следующего раздела вы узнаете, что корни различны тогда и только тогда, когда 8сс1(и(х),и'(х)) = 1, где и'(х) — производная и(х); значит, имеется последователь- ность остатков, доказывающая, что полинам и(х) взаимно прост с и'(х). Считаи ио(х) = и(х), ис(х) = и'(х) (н следуя Штурму), изменим знак всех остатков. Получим ссие(х) = ис(х)дс(х) — с/сит(х), сзис(х) = из(х)йх(х) с/сиз(х), (29) сьиь с(х) = иь(х)дь(х) — с/лил+с(х) для некоторых положительныхконстанте и с/., тлевшей(иь с) = О.
Будем говорить, что пгпклонение С'(и,а) полинома и(х) в а равно количеству изменений знака в последовательности ио(а), ис(а), ..., иьес(а), не считая нулей. Например, если последовательность знаков представляет собой О, +, †, †, О, +, +, †, получим с'(и, а) = 3. Теорема Штурма утверждает, что количество корней и(х) в интервале а < х < Ь равно И(и, а) — (г(и, Ь), Доказательство этого факта на удивление коротко (см.
упр. 22). Хотя алгоритмы С и Е интересны, история на них не заканчивается. Важные альтернативные пути вычисления 8сс( полиномов над целыми числами будут рассмотрены в конце раздела 4.6.2. Имеется также общий алгоритм для вычисления детерминанта, о котором можно сказать, что он включает в себя алгоритм С в качестве частного случая [см. Е. Н.
Ваге)эв, Май. Соплр, 22 (1968), 565 — о78). Ф В четвертом издании этой книги я намерен переделать материал настоящего раздела, уделив достойгное внимание «ак исследованиям детермпнантов в 19 веке, так и работе Иг. На/ОСЬ, Соппп, /йасЬ. Не/геВс! 21 (1948), 99 — 116. Превосходное обсуждение последней дано в работе В. йооэ !и Сотрпс!п8, Япрр/етепС 4 (1982), П5 — 137. К этим же методам относится и интересный .метод вычисления детермпнантов, который выведен Ч. Л. Доджсоном (С. Б. 1/ос/8эоп) (пзвестныи также пол пменем льюис кэррол (Беш!э сагго!/)) нз теоремы Якоби.
Обзор ранней истории исследований тождественности детермннантов подматрпп можно найти я работе В. Е Кпий, Е/ессготйс 1. СотЬтпасопсэ 3, 2 ('1996), статья В5, 33. УПРАЖНЕНИЯ 1. [10) Вычислите псевдочастное 4(х) и псевдоостаток г(х), т. е. полиномы, удовлетворяющие (8), для и(х) = ха+ хе — х~ + 2х~+ Зх~ — х+ 2 и и(х) = 2х~+ 2х — х+ 3 над целыми числами. 2. [!5) Чему равен наибольший общий делитель полинома Зх +х~+4х~+4х~+Зх~+4х+2 и "обратного" ему полинома 2хл+4хл+Зхл+4хл+4х'+х+3 по модулю 7? (В данном случае под "обратным" подразумевается полинам с обращенным порядком коэффициентов,— Прим.
перев.) 3. [М25) Покажите, что алгоритм Евклида для полиномов пад полем 8 может быть расширен для поиска полнномов П(х) и И(х) над 8, таких, что и(х)У(х) + с/(х) (х) = йса(и(х).п(х)) (см. алгоритм 4.5.2Х). Чему равны степени полиномов П(х) и Р(х), вычисленных при помощи такого расширенного алгоритма? Докажите, что если 8 — поле рациональных чисел и если и(х) = хм — 1 и и(х) = х" — 1, то расширенный алгоритм дает полиномы П(х) н И(х), имеющие целые коэффициенты. Найдите (г(х) и И(х) для и(х) = х ' — 1 и е(х) = х — 1. ~з 4. [МУО[ Пусть р — простое число, и предположим, что алгоритм Евклида, примененный к полиномам и(х) и э(х) по модулю р, приводит к последовательности полиномов, имеющих степени соответственно ш, и, пм ..., ен -со, где т = Оеб(п), и = беб(е) н пс > О.
Положим, что щ > и. Если э(х) и э(х) являются нормированными полиномами, независимо и равномерно распределенными среди всех р"'~" пар нормированных полиномов степеней соответственно ш и и, то чему равны средние значения трек величин 1, пз + + пз и (п — п~ )гн + + (пз-з — п~) нн выраженные как функции от т, и и р? (Эти три величины являются основными факторами, влияющими на время работы алгоритма Евклида с полнномами по модулю р, если считать, что деление выполняется при помощи алгоритма Р.) [Указание. Покажите, что и(х) пюб о(х) равномерно распределен и независим от е(х) [ 5. [МЯЯ) Чему равна вероятность того, что и(х) и е(х) взаимно просты по модулю р, если п(х) и е(х) — независимые равномерно распределенные нормированные полиномы степени п? 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
