AOP_Tom2 (1021737), страница 130
Текст из файла (страница 130)
(Знак равенства здесь означает равенство по модулю 13, так как все арифметические действия над коэффициентами выполняются по модулю 13.) Проведенное вычисление показывает, что 12 является наибольшим общим делителем двух исходных полиномов. Так как любой ненулевой элемент поля представляет собой обратимый элемент области полнномов над полем, для полей принято делить результат выполнения алгоритма на его старший коэффициент, получая нормированный полином, и именно его имеют в виду, говоря о наибольшем общем делителе (в оригинале— "1э са!1ед йе 8театеэ1 согапюп йлэог".— Прим. перев.) двух данных полиномов.
боб, вычисленный в (6), таким образом, оказывается равным 1, а не 12. Последний шаг в (6) может быть опущен, так как если с)ей(е) = О, то йод(и(х),е(х)) = 1 безотносительно к выбору полинома и(х). В упр. 4 определяется среднее время работы алгоритма Евклида нэд случайными полиномами по модулю р. Вернемся к более общей ситуации, в которой полнномы даны над областью единственного разложения, не являющейся полем. Из (4) можно вывести важные соотношения сопт(йсб(и, е)) = а . 8сд(сопт(и), соп1(е)), (7) рр(йод(и(х),е(х))) = 5 йсб(рр(и(х)),рр(с(х))), где а и 5 — обратимые элементы. Здесь ясд(п(х),е(х)) означает любой полипом от х, являющийся наибольшим общим делителем и(х) и е(х). Формулы (7) сводят проблему поиска наибольшего общего делителя произвольнык пачиномов к поиску наибольшего общего делителя примпгаивнмх полиномов. Алгоритм В деления полиномов нед полем может быть обобщен для псеедоделенил полиномов над любой алгебраической системой, представляющей собой коммутативное кольцо с единицей.
Можно заметить, что алгоритм В требует явного деления только на 4(е), старший коэффициент — е(х) и шаг 02 выполняется в точности тп — п+ 1 раз. Таким обрезом, если и(х) и е(х) начинаются с целых коэффициентов и если мы работаем нэд полем рациональных чисел, то единственными делителями 1(и)'" "+' будут знаменатели д(х) и г(х). Это наблюдение приводит к мысли, что всегда можно найти полиномы в(х) и г(х), такие, что (8) с(и) "+'и(х) = й(х)и(х) + г(х), бей(г) < н, где т = деб(и) и и = деб(и), для любых полиномов и(х) и и(х) ф О при условии, что т > и. Алгоритм К (Псевдоделение налиномов). Даны полиномы и(х) = и„,х + + и~х+ ио, и(х) = и„х" +... + и~х+ ие, где и„ф О и пз > н ) О.
Этот алгоритм находит полиномы д(х) = д „х "+...+дв и г(х) = гь ах" ' + + го, удовлетворяющие (8). К1. (Итерация по 6.] Выполнить шаг К2 для Ь = т — а, т — п — 1, ..., О; после этого алгоритм завершается, выдав ответ (г„м..., гв) = (и„ы ..,, ио). К2. [Цикл умножения.) Установить сначала дь +- и„+„и„", а затем — иу < — и„иу— и„ч.ьи1 ьдляу = и+6 — 1,п+Ь вЂ” 2,...,О. (Приу < йэтоозначэет, чтоит ~ — и„ит поскольку мы рассматриваем и м и э, ... как нули.
Этих умножений можно избежать, если начать алгоритм с замены и~ на и„" 'и, для О < 1 < т — н.) 3 Пример вычислений приведен ниже, в (10). Правильность алгоритма К легко доказать индукцией по т — н, поскольку при каждом выполнении швов К2, по сути, и(х) заменяется на Х(и)и(х) — с(и)х"и(х), где Ь = деб(и) — стеб(и). Заметьте, что в алгоритме не использовано деление; коэффициенты д(х) и г(х) сами по себе представляют некоторые полиномиальные функции от коэффициентов и(х) и и(х). Если и„= 1, то алгоритм идентичен алгоритму Р.
Если и(х) и и(х) — полиномы над областью единственного разложения, можно, как и ранее, доказать, что полиномы д(х) и г(х) — единственны, поэтому другой способ псевдоделения над областью единственного разложения состоит в умножении и(х) на и„"' "+' и применении алгоритма 1У, если известно, что все частные на шаге 112 будут существовать. Алгоритм К может быть расширен до "обобщенного алгоритма Евклида" для примитивных полиномов над областью единственного разложения следующим образом.
Пусть и(х) и и(х) — примитивные полиномы с бей(и) > деб(и). Определим при помощи алгоритма К полинам г(х), удовлетворяющий (8). Теперь можно доказать, что бей(и(х), и(х)) = бед(и(х), г(х)); любой общий делитель и(х) и и(х) делит и(х) и г(х); и обратно, любой общий делитель и(х) и г(х) делит 0(и) "е'и(х) и должен быть примитивным (поскольку примитивен о(х)), так что он делит и(х). Если г(х) = О, имеем 8сд(и(х),и(х)) = и(х); с другой стороны, если т(х) ф О, из-за примитивности и(х) имеем 8сд(и(х),г(х)) = бед(и(х),рр(г(х))), так что процесс может быть итерирован.
Алгоритм Е (Обоби1еннмй алгорипьи Евклида). Даны ненулевые полиномы и(х) и и(х) над областью единственного разложения Я. Алгоритм вычисляет наибольший общий делитель и(х) и и(х). Предполагается существование вспомогательных алгоритмов для вычисления наиболыпего общего делителя элементов 5, а также для деления а на 6 в 5 при 6 ф О и а, кратном Ь.
В качестве примера работы алгоритма Е вычислим ба полиномов и(х) = х'+х — Зх — Зх +8х + 2х — 5, в(х) = Зхв + 5х4 — 4хз — 9х + 21 (9) над целыми. Эти полиномы примитивны, так что на шаге Е1 устанавливается 4 е- 1. На шаге Е2 выполняем псевдоделение. 1 0 — 6 3050 -4 — 921 2 -5 6 — 15 1 0 1 0 — 3 — 3 8 30 30 — 9-924 30 50 — 4 — 921 0 -20 — 5 0 3 6 — 15 0 -60 -15 0 918 -45 0 00 0 0 0 0 0 -60 -15 0 918 -45 -18 0 -45 0 27 54 -135 -18 0 -30 0 24 54 -126 -15 0 3 0 — 9 Здесь частное д(х) равно 1 Ззхт + О. 3'х + — 6 3е.
Имеем 27и(х) = е(х) (9х~ — 6) + ( — 15ха + Зх — 9). Теперь шаг Е3 замещает и(х) на е(х) и е(х) на рр(г(х)) = 5хл — хз + 3. Даль- нейшие вычисления приведены в следующей таблице, в которой показаны только коэффициенты. г(х) — 15, О, 3. О, — 9 -585, -1125, 2205 -233150, 307500 143193869 и(х) 1, О, 1, О, -3, -3, 8, 2, -5 3, О, 5, О., - 4, — 9, 21 5,0, -1,0,3 13, 25, -49 (х) 3,0,5,0, -4, — 9,21 5,0, -1, 0.,3 13, 25, -49 4663.
-6150 (12) Поучительно сравнить данные вычисления с вычислением того же наибольшего общего делителя над рациональными числами, а не над целыми, с использованием е1. (сведение к примитивным полиномам.] Установить и е- 8сс)(сопс(и), сопс(е)). используя вспомогательный алгоритм для вычисления наиболыпего общего делителя в У. (По определению сопс(и) представляет собой наибольший общий делитель коэффициентов и(х).) Заменить и(х) полиномом и(х)/сопс(н) =рр(и(х)); точно так же заменить е(х) на рр(е(х)).
Е2. (Псевдоделение.] Вычислить г(х) с использованием алгоритма В. (Нет необходимости вычислять полином-частное 9(х).) Если г(х) = О, перейти к шагу Е4. Если бей(г) = О„заменить е(х) постоянным полиномом "1" и перейти к шагу Е4. Е3. [Сделать остаток примитивным.] Заменить и(х) на ь(х) и заменить е(х) на рр(г(х)). Вернуться к шагу Е2.
(Это — "евклидов шаг", аналогичный другим рассмотренным нами алгоритмам Евклида.) Е4. (Присоединение содержания.] Алгоритм завершается, выдав ответ с1 е(х). ! алгоритма Евклида для полиномов нвд полем, описанного ранее в этом разделе. Получается неожиданно сложная последовательность. и(х) в(х) 1,0,1,0, — 3, — 3,8,2, — 5 3,0,5,0, — 4,— 9,21 3,0,5,0„— 4, — 9,21 — 9,0, 9,0, — 3 5 1 1 117 441 — — 0 — 0 —— 9 9 З вЂ” — — 9— 25 ' ' 25 9 441 233150 102500 25 ' ' 25 19773 ' 6591 233150 102500 1288744821 19773 ' 6591 543589225 Для улучшения этого алгоритма можно свести и(х) и в(х) к нормированным полиномам на каждом шаге, чтобы удалить обратимые множители, слишком усложняющие коэффициенты. В действительности получится алгоритм Е над рациональными числами: в(х) и(х) 10 5,0 — -',— 3 7 з» з 5' '5 1,— 25 49 1З ~ 1З 6150 4663 1 Алгоритм Коллинза.
Остроумный алгоритм, в целом превосходящий алгоритм Е и, кроме того, предоставляющий информацию о поведении алгоритма Е, был разработан Джорджем Э. Коллинзом (Сеогбе Е. Со!!ш5) [дАСМ 14 (1967), 128 — 142) и впоследствии улучшен В. С. Брауном (13'. 8. Вгони) и Дж. Ф. Траубом (д.
Г. ТгапЬ) (ЛАСМ 18 (1971)., 505-514; см. также %. Я. Вгони, АСМ Тгапб. Маг)7. 8оЕ1жаге 4 (1978), 237 — 249), Он позволяет избежать вычислений примитивных частей на шаге ЕЗ, вместо чего производится деление на элемент 8, о котором известно, что он является множителем г(х). Алгоритм С (Поиск наибольшего общего делителя над областью единственного разложения). В этом алгоритме используются те же предположения о входных 1, О, 1, О, -3, -3, 8, 2, -5 5 4 10зО з 37 (14) 0 103 5' '5 1 25 49 1З 1З 1 —— 6150 4663 И в (13), и в (14) последовательность полиномов, полученная при помощи алгоритма Е над целыми числами, по сути, та же, что и в (12).
Единственное отличие состоит в том, что полиномы умножаются на некоторые рациональные числа. Каким бы ни был полипом, будь то ох — х + 3, — бх + бх — — или х — -х + „-,, 4 2 5 4 1 2 1 4 1 2 3 вычисления остаются теми же. Но любой алгоритм, использующий рациональную арифметику, имоет тенденцию к более медленной работе, чем "всецело целый" алгоритм Е, поскольку рациональная арифметика обычно требует большего количества вычислений целых 804) на каждом шаге при полиномах больших степеней. Поучительно сравнить (12), (13) и (14) с (6), где мы определяли 8сд тех же полиномов п(х) и в(х) по модулю 13 со значительно меньшими усилиями.
Поскольку 4(и) и 41(в) не кратны 13, того факта, что йсд(и(х), в(х)) = 1 пю11 13, достаточно для доказательства, что и(х) и в(х) взаимно просты над кольцом целых (и., следовательно, над полем рациональных чисел). Мы вернемся к этому сохраняющему время наблюдению в конце раздела 4.6.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
