Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 22
Текст из файла (страница 22)
[Введение к примитивным полнномам.[ Установить с( +- 8сб(сопс(и).сонг(е)), используя вспомогательный алгоритм дли вычисления наиболыпего общего делителя в В. (По определению сощ(и) представляет собой наибольший обпшй делитель козффициентов и(х).) Заменить и(х) полиномом и(х)/сопс(и) = рр(и(х)); точно так же заменить е(х) на рр(е(х)) . Е2.
[Псевдоделение.[ Вычислить г(х) с использованием алгоритма К. [Нет необходимости вычислять поливом-частное 9(х),) Если г(х) = О, перейти к шагу Е4. Если деб(г) = О, заменить е(х) постоянным полиномом "Г и перейти к шагу Е4. ЕЗ. [Сделать остаток примитивным.) Заменить и(х) на е(х) и заменить е(х) на рр(г(х)). Вернуться к шагу Е2. (Это — "евклидов шаг", аналогичный другим рассмотренным нами алгоритмам Евклида.) Е4.
[Присоединение содержания.) Алгоритм завершается, выдав ответ 6 ° е(х). 5 алгоритма Евклида для полиномов над полем, описанного ранее в этом разделе. Получается неожиданно сложная последовательность. и(х) О() 1,0,1,0,-3, -3,8,2, -5 3,0,5,0, — 4, — 9,21 3,0,5,0,-4,-9,21 --0,,0-- (13) 9 '% З 9 25 ' ' 25 111 9 441 2331Я юОДВЗЯЬ 25' ' 25 Фттз 559! 233150 1ОЗЬОО ИВВ14 32 ПЛЗ ' бзз! 543539225 Для улучшения этого алгоритма можно свести и(х) и о(х) к нормированным полиномам на каждом шаге, чтобы удалить обратимые множители, слишком усложняющие коэффициенты.
В действительности получится алгоритм Е нэд рациональными числами: и(х) о(х) 10 103 1 —— ЫЬО 4553 1 1,0,1,0, -3, -3,8,2, -5 1 — —— 25 49 'ш' гз 5150 4553 (14) 11 в (13), и в (14) последовательность полиномов, полученная при помощи алгоритма Е над целыми числами, по сути, та же, что и в (12). Единственное отличие состоит в том, что полиномы умножаются на некоторью рациональные числа.
Каким бы ни был полипом, будь то 5х — х + 3, -Вх + Ох — - или х — -х + гь, 4 2 Ь 4 1 2 1 4 ! 2 вычисления остаются теми же. Но любой алгоритм, использующий рациональную арифметику, имеет тенденцию к более медленной работе, чем "всецело целый"' алгоритм Е, поскольку рациональная арифметика обычно требует большего количества вычислений целых 8сд на кзждом шаге при полиномах больших степеней. Поучительно сравнить (12), (13) и (14) с (6), где мы определяли 8сд тех же полиномов и(х) и и(х) по модулю 13 со значительно меньшимн усилиями. Поскольку 4(п) и 4(и) не кратны И, того факта, что йсд(и(х), о(х)) = 1 шод 13, достаточно для доказательства, что и(х) и о(х) взаимно просты над кольцом целых (и, ыедовательно, нед полем рациональных чисел).
Мы вернемся к этому сохраняющему время наблюдению в конце раздела 4.6.2. Алгоритм Коллинза. Остроумный алгоритм, в целом превосходящий алгоритм Е и, кроме того, предоставляющий информацию о поведении алгоритма Е, был разработан Джорджем Э.
Коллинзом (Сеог8е Е. Сой1пь) [,УАСМ 14 (1967), 128-142] и впоследствии улучшен В. С. Брауном ( тт", 8. Вготтп) и Дж. Ф. Траубом (Л. Г. Тгаи11) [ХАСМ 18 (1971), 505-514; см. также %. $. Вгочп, АСМ Тгалз. МагЬ. Бойчзхе 4 (1978), 237-249]. Он позволяет избежать вычислений примитивных частей на шаге ЕЗ, вместо чего производится деление на элемент Я, о котором известно, что он является множителем г(х). Алгоритм С (Поиск наибольнтего общего делитиелл над областиью единственного разлоотсенил).
В этом алгоритме используются те же предположения о входных и выходных данных, что и в алгоритме Е. Он имеет то достоинство, что при поиске наибольших общих делателей коэффициентов требуется выполнять меньше вычислений. С1. (Сведение к примитивным полиномам.) Как и на шаге Е1 алгоритма Е, установить И <- 8со(сопз(и), сопз(и)) и заменить (и(х), и(х)) на (рр(и(х)),рр(е(х))).
Установить д с- л е- 1. С2. (Псевдоделение.) Установить 5 +- дей(и) — абеб(и). Вычислить г(х) с использованием алгоритма В. Если г(х) = О, перейти к шагу С4. Если Оей(г) = О, заменить е(х) постоянным пачиномом "1" и перейти к шагу С4. СЗ, (Подгонка остатка.) Заменитыюлином и(х) на и(х) и и(х) на г(х)/дала. (В этот момент все коэффициенты г(х) кратны дйз.) Затем установить д +- з(и), Ь е- Ь' "дз и вернуться к шагу С2. (Новое значение Ь будет в области Я, даже если 5 >1.) С4. (Присоединение содержания.] Вернуть в качестве ответа Ы рр(е(х)). $ Если применить этот алгоритм к рассмотренным ранее полиномам (9), то получится такая последовательность результатов в начале шага С2.
и(х) д )з и(х) 3,0,5,0, — 4,-9,21 — 15,0,3,0, -9 65, 125, -245 -9326, 12300 1, О, 1, О, -3, -3, 8, 2, -5 3,0,5,0,-4,-9,21 — 15,0, 3„0, -9 65, 125, -245 1 1 3 9 (15) -15 25 65 169 дз' и1(х) =из(х)дз(х)+дзй,'из(х), 9з' из(х) = из(х)дз(х) + дз/зз"из(х) 94 из(х) = из(х)чз(х) + дзлз'и (х) пз <пз; и4 < пз~ пз < пз (16) н т. д. Процесс прекращается, когда нзч.з = ое8(из+з) < О. Покажем, что полиномы из(х).
из(х), ...имеют коэффициенты из Я, а именно — что множитель д Ь,' де.чит все коэффициенты остатков, Кроме того, покажем, что все значения Лз принадлежат Я. Доказательство весьма запутанно„и его легче понять, рассмотрев конкретный пример. Предположим, как и в (15), что п1 = 8, из = 6, из = 4, и| = 2, пз = 1, пз — — О, так что дз = 5з = 5з = 2; дз = 5з = 1.
Запишем из (х) = азх + азх" + ". + ае, В конце алгоритма г(х)/дйз = 260708, Эта последовательность полиномов состоит нз целых кратных полнномов в последовательности, полученной с помощью алгоритма Е. Вопреки тому факту, что полиномы не сведены к примитивному виду, коэффициенты остаются в разумных пределах благодаря приводящему множителю на шаге СЗ. Для анализа алгоритма С и доказательства его корректности рассмотрим полученную с его помощью последовательность полиномов из(х), из(х), из(х), ..., где из(х) = и(х) и из(х) = и(х). Пусть 5 = пз — ну~1 для у > 1, где и = Ое8(иу), н пусть 91 — — /зз — — 1, д = 4(иу), Ь =- Ьз," ' д ' ' дл» у > 2.
Тогда нз(т) = Ьох~+Ььх + +Ьо,, нь(х) = етх+ео, ио(х) = Ль твк что /зт = 1, 62 = Ььз, йз — сз/Ьь, Ьз = ьрзьо/с4. Рассьтотрнм табл. 1 с учетом принятых обозначений. Для определенности будем считать, что коэффициенты полиномов целые. Имеем Ььент(х) = из(х)йт(х) + из(х); так что„если умножить строку Аь на Ьь и вычесть подходящие кратные строк Вт, В» и Вь (соответствующие коэффициентам Ет(х)), можно получить строку Сь. Если также умножить строку Аз на Ььз и вычесть кратные строк Во, Вь и Вз, можно получить строку Сз, Аналогично получим сзтиз(х) = из(х)оз(х) + Ьоцнз(х).
Умножив же строку Вз на со~, вычтя целые кратные строк Сь, Сз и Сз и разделив на Ьь, получим строку Вз. Для доказательства того, что мз(х) имеет целые коэффициенты, рассмотрим матрицу Аз Ат Ао В» Вз Вз в Во Указанные операции со матрицы М в ао 0 0 ат ао О аз ат ао 0 0 0 О О О Ьо 0 0 ь, ь, о ь ь ь аь аз аз ао аь аз ат ао аь Ьз 62 Ьт ь ь ь ь,ь,ь, ь ь ь 0 ЬьЬь строками и перестановки строк приводят к преобразованию Ьз Ьз Ьт Ь, Ьз Ь, Ьь Ьз Ьз ь ь ь 0 сз сз О Ось 0 0 0 О 0 0 Ьоооо о Ьтьоо 0 0 Ьзьт Ьо 0 0 Ьзьзьт Ьо 0 сз ст со О 0 сз сз сд со 0 сз сз сз ст со ь(2 ат т(о каким образом была получена матрица М' из М, имеем Ьз ° Ьз ° Ьзь ' (с3/Ьоь) ° ась Мо х г(ез Мо если Мо я Мо — любые квадратные матрицы, полученные в результате выбора вось- ми оютветствующих столбцов из М н М'.
Например, выберем семь первых столбцов и столбец, содержащий 4; тогда аз ат аь аь аз аз аз О аз ат аь аь а4 0 аз ат аь аь Ьь Ьз Ьз 62 Ьт ь, ь. ь. ь, ь, 0 Ьь Ьь Ьз Ьз 0 0 Ьо Ьь 64 0 0 0 Ьь Ьь что ь(т — целое. Ьоз Ьоз ° Ьь з(сз/Ьь) с)ес 4 3 — хьо сз т(т . Поскольку 6осо Ь О, это доказывает, ь(2 и Ио. Аналогично целыми являются Вз в. Вз Вт Сз С в В соответствии с тем аз ат ао 0 аз ат 0 О аз ь ь ь О ЬьЬь О 0 Ьо 0 0 0 О 0 0 Ьь Ьь 64 О Ьоьь О ОЬ» 0 О 0 О О 0 ООО 000 000 0 0 6» О 0 0 аз ат аз аз аз аз ь о ь, ь, ь ь ь ь ь ьз аз ао аз ат Ьо 0 ь о ь о Ьз Ьт Таблица 1 КОЭФФИЦИЕНТЫ, ПОЯВЛЯКЗСЦИЕСЯ В АЧГОРИТМЕ О Заменить строкой Умножить на Имя строки Ь«з ь,' Ьвз ь,' Ьз С, С» Сз Сг С! Св С»/Ь«В 643/Ьвв сз»(ьв Вз Вг В! Вв »СЗЬв/сз 4ЬЫ Е! Ев ег«4йгьб В общем, так же можно показать, что и +4(х) имеет целые коэффициенты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
