AOP_Tom2 (1021737), страница 131
Текст из файла (страница 131)
и выходных данных, что и в алгоритме Е. Он имеет то достоинство, что при поиске наибольших общих делителей коэффициентов требуется выполнять меньше вычислений. Если применить этот алгоритм к рассмотренным ранее полиномам (9), то получится такая последовательность результатов в начале шага С2. п(х) с(х) 1 1 3 9 (15) 1,0,1,0,-3,-3,8.,2, -5 3,0,5,0, — 4, — 9,21 — 15,0,3,0, — 9 65, 125, -245 3,0,5,0, — 4, — 9,21 — 15,0,3,0, — 9 65, 12о, -245 -9326, 12300 -15 25 65 169 В конце алгоритма г(х)/ЯЬз = 260708. Эта последовательность полиномов состоит из целых кратных полиномов в последовательности, полученной с помощью алгоритма Е. Вопреки тому факту, что полиномы не сведены к примитивному виду, коэффициенты остаются в разумных пределах благодаря приводящему множителю на шаге СЗ.
Для анализа алгоритма С н доказательства его корректности рассмотрим полученную с его помощью последовательность полиномов и, (х), иг(х), из(х), ..., где из(х) = и(х) и пг(х) = е(х). Пусть б = и. — и ьз для ) > 1, где пу — — бе8(пз), и пустьд1=Ьз=1,д.=б(и),Ь.=Ь. ' 'д' 'дляг>2.Тогда дг'+ иг(х) = иг(х)дз(х) + д, Ь,'из(х), Яз вг(х) нз(х)дг(х) + ЯгЬг о4(х)~ дз пз(х) = ц4(х)дз(х) + дзЬз нз(х), пз <пг; нз < пз~ пз < п4 (16) и т. д. Процесс прекращается, когда пьчч — — с1ей(иьчг) < О. Покажем, что полиномы нз(х), из(х), ...имеют коэффициенты из о, а именно — что множитель д Ь делит все коэффициенты остатков. Кроме того, покажем, что все значения Ь.
б принадлежат 5. Доказательство весьма запутанно, и его легче понять, рассмотрев конкретный пример. Предположим, как и в (15), что п1 — — 8, нг = 6, пз —— 4, пз —— 2, пз — — 1, пз — — О, так что бз = бг = бз = 2, бз = бз = 1. Запишем и,(х) = азх'+агх + + ао, С1. (Сведение к примитивным полиномам.) Как и на шаге Е1 алгоритма Е, установить И < — йсс1(сонг(и), сопС(с)) и заменить (и(х), п(х)) на (рр(и(х)), рр(с(х))). Установить д +- Ь <- 1. С2. (Псевдоделение.) Установить б < — бей(и) — бе8(е).
Вычислить г(х) с использованием алгоритма В. Если г(х) = О, перейти к шагу С4. Если с)е8(г) = О, заменить е(х) постоянным полиномом "1" и перейти к шагу С4. С3. (Подгонка остатка.) Заменить полипом и(х) на с(х) и с(х) на г(х) ~дпь. (В этот момент все коэффициенты г(х) кратны Я1г~.) Затем установить д ( — с(и), Ь +- Ь' здз и вернуться к шагу С2. (Новое значение Ь будет в области 5, даже если б >1.) С4. [Присоединение содержания.) Вернуть в качестве ответа б. рр(с(х)). 1 иг(х) = ьвх +Ььх + + 6о, ..., иь(х) = е! х »- ео, ив(х) = Хо, так что Ь! —— 1, Ьг —— 662, Ьз = с»766~, Ь4 = »Хггьь~/с»~.
Рассмотрим табл. 1 с учетом принятых обозначений. Для определенности будем считать, что коэффициенты полиномов целые. Имеем Ьвзи»(х) = иг(х)!7»(х) + из(т); так что, если умножить строку Аь на ьвз н вычесть подходящие кратные строк В7, Вв и Вь (соответствующие коэффициентам о»(х)), можно получить строку Сь. Если также умножить строку А4 на 66 2и вычесть кратные строк Вв, Вь и В4, можно получить строку С».
Аналогично получим с»зиг(х) = из(х) ог(х) + 6вьи4(х). Умножив же строку Вз на с4, вычтя целые кратные строк Сь, С4 и Сз и разделив на 666, получим строку 02. Для доказательства того, что и4(х) имеет целые коэффициенты, рассмотрим матрицу ао 0 О а! ао О аг а! ао 0 0 0 0 0 0 ь о о ь, ь, о Ь2 Ь! Ьо аь а4 аз ав аь а4 а7 ав аь Ьз Ьг Ь! ь ь ь ь ь ь Ьв Ьь Ь» 0 Ьв Ь, аг а, аз аг а» аз ь о ь ь ь ь! Ьз Ьг ь ь (17) строками и перестановки строк приводят к преобразованию Ьз Ьг Ь! Ьо 0 ь ь ь ь»ь Ьь Ь» Ьз Ьг Ь! 66 Ьь 64 Ьз 62 О С4 сз сг с! 0 0 С» Сз С2 0 0 Ос»сз О О 0 0 0 0 0 0 0 0 0 ь о о ь, ь о со 0 0 с! со 0 сг с! со Хгй! Х, = ЛХ'.
(1а) В соответствии с тем, каким образом была получена матрица М' из М, имеем Ьв Ь, . Ьг, (СХlьв)»)ес Мо = х»)ес ЛХо, если Мо и М,', — любые квадратные матрицы„полученные в результате выбора вось- ми соответствующих столбцов из М и ЛХ'. Например, выберем семь первых столбцов и столбец, содержащий»Х»; тогда а7 ав аь ав а7 ав 0 ав а7 6ь Ь4 Ьз Ь, Ь, Ь4 0 Ьв Ьь о о ь 0 0 0 а» аз аь а» ав аь ь ь! 63 Ь2 Ь4 Ьз Ьь Ь4 Ьв Ьь Ьвз Ьвз Ьвз (С»7/66)»1ес =хЬ с .а,. 4 З Поскольку Ьвс4 ~ О, это доказывает, что»1! — целое. Аналогично целыми являются »(2 И»»О. 42 А! Ао В» в в в в Укаэанные операции со матрицы М в В4 Вз в В! Сг С! С Х76 ав аг а6 0 ав а7 0 О аз ь ь ь 0 Ь, Ьь о о ь 0 0 0 0 0 0 Ьв Ьь Ь4 о ь ь о о ь 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ав 0 0 Ьв 0 0 0 0 аг 0 аз ао а4 а! Ьо 0 ь! о ь о Ьз Ьо Ь4 Ь! Таблица 1 КОЭФФИЦИЕНТЫ, ПОЯВЛЯЮЩИЕСЯ В АЛГОРИТМЕ С Умножить Заменить на строкой Имя строки Строка Ьг Ьв Ь Ь6 С С4 Сз С С! С С4/Ьа сз/Ьз 64/Ьа 3/Ь3 Вз Ог В1 Ва бгь»/сз тбггЬ6/с»з Е! Еа егс»/Агьв В общем, так же можно показать, что и!+1(х) имеет целые коэффициенты.
Если начать с матрицы М, состоящей из строк с Ап, „,. по Аа и с Вп, „, по Ва, и выполнить указанные в табл. 1 операции над строками, можно получить матрицу М', состоящую из расположенных а некотором порядке строк от Вп, „,. по Вп, затем — от Сп, „,. по Сп, „,+1,..., от/г„, г „, по Р,, от !:/„,, „, по!ба и, наконец, Ва (строки, содержащей коэффициенты и +1(х)). Извлекая подходящие столбцы, покажем, что б!4-1/ »б!)ттг-и»1( бг+1/ Ьбг)!!З-пт+! ~ б! т+1/ /Зб! т)пт-64+1 192 91 1 93 92 2 ' ' ' д! д! 1 ! ! и! пз пг п4 П! г П! П! ! 4+ х не!Ма = хдг дз 9 -1 9!. (19) где г! — данный коэффициент и.+1(х), а ма- — подматрица м.
й выбираются очень хитрым способом (см. упр. 24) — -так, чтобы это уравнение упростилось до (20) де! Ма — — х г!. Аз А4 .4з Аг .4! Аа Вт Ва Вз В4 Вз Вг В1 Ва СЗ С» Сз Сг С! Са Вз Вг »у! Ва Е! Еа Ра ав ат ав 0 ав ат 0 О ав 0 0 0 0 0 0 0 0 0 Ьв ЬЗ Ь4 о ь ь о о ь О 0 0 О 0 0 0 0 О О 0 0 0 0 0 О 0 О 0 О 0 0 0 О 0 0 0 0 0 0 0 О 0 0 0 0 0 0 0 0 0 0 О 0 0 О 0 0 0 0 0 0 0 О аз а» аз аа аз а4 ат ав аз ав ат аа 0 аз ат 0 0 ав ь ь ь! Ь» Ьз Ьг Ьз Ь4 Ьз ьа ЬЗ Ь» 0 Ьа Ьз о о ь О 0 О О 0 О 0 64 сэ 0 О 64 0 0 0 О 0 0 О 0 0 0 О 0 0 0 0 0 0 0 о о о О 0 О 0 0 0 0 0 0 0 0 0 аг ат аа 0 аз аг ат аа а4 аз аг ат аз а» аз аг ав аз а» аз ат а6 аз а4 Ьа 0 0 0 Ь! Ьа 0 0 Ь Ь1 Ь О Ьз Ьг Ьт Ьа Ь» Ьз Ьг Ь! Ьз Ь4 Ьз Ьг Ьа Ь! Ь4 Ьз 0 Ьв Ьз Ь4 сг с! се 0 сз сг с! са с» сз сг с! 0 с» сз сг О О с» сз О 0 0 с» 0 0 тбг тб! 0 0 0 !»г 0 0 0 0 0 0 0 О 0 0 0 О 0 0 0 О 0 0 0 0 0 0 0 0 аа 0 а! 66 а! 61 аз аг 0 О О О 0 0 0 0 Ьа 0 Ьт Ь ь! ь! ь ь 0 0 О 0 са 0 с! са сг с! сз сг 426 0 И1 !/а !т'г И! 0 !Зг 0 ет 0 0 0 0 0 0 0 0 0 О 0 О аа 0 а! аа 0 О 0 О 0 0 0 0 0 О 0 0 ьа о ь ь 0 0 О 0 0 0 0 О са 0 с! са 0 0 0 О !1а О »11 »ба еа 0 е! еа О /6 Следовательно, каждый коэффициент а„+! (х) может быть выражен как определитель матрицы размера (и! + йг — 2п + 2) х (и! + пг — 2п! + 2), элементы которой представляют собой коэффициенты и(х) и е(х).
Остается показать, что выбранные подобным образом й также являются целыми числами. Применима следующая методика: рассмотрим, например, матрицу ав ав а4 аз аг а! ао О й! йв йз й4 аз йг й! йо Ь4 Ьз Ьг Ь! Ьо О О О Ьз Ь4 6з Ьг Ь! Ьо О О Ьв Ьз Ь4 Ьз Ьг Ь! Ьо О О Ьв Ьз Ь4 Ьз Ьг Ь! Ьо А! Ао в Вг В! в, йв а! О аз О Ьв О О О О (21) Операции над строками, определенные в табл. 1, и перестановка строк приведут к матрице Вг в, в С, Со Ьв Ьз Ь4 Ьз Ьг Ь! Ьо О О О О Ьв Ьз Ь4 Ьз Ьг Ь! Ьо О О О О 6в Ьв 64 Ьз Ьг Ь! Ьо О (22) О О О Ьв Ьз Ь4 Ьз Ьг Ь, Ьо О О О О с4 сз с! с! со О О О О О О с4 сз сг с! со следовательно, если рассмотреть любые подматрнцы ЛХо и Мо, полученные путем выбоРа шести соответствУющих столбцов ЛХ н ЛХ', можно полУчить 6вз .
Ьвз . 4(ес ЛХо = х 4(е! Мо. Когда Мо выбирается таким образом, что является первыми шестью столбцами ЛХ, получаем, что г(еС ЛХо = хсг/'Ьв = х/гз, так что /4з является целым числом. В целом, чтобы показать, что 6, целое при Х > 3, начнем с матрицы ЛХ, состоящей из строк с А„, „, ! по .4о и с В„, „! по Во, .затем будем выполнять соответствующие операции над строками до тех пор, пока не получим матрицу ЛХ', состоящуюизстрок с Вьч „, ! по В„, „,, затем — сС„,4., ! по С„, ..., с Р,, „, ! по Ро и с Я„г, „! по Яо.
Рассмотрев ЛХв, представляющую собой первые и! + иг — 2п столбцов матрицы М, получаем (9 !+~/ 141)йг Ш( ~4+1 ! 6~!)~~4 — Ш ( 4 — О~/ 6/ 1)Ш йй 4 !ЛХ Ш Ьз И2 й4 Ш вЂ” 2 ПЯ ЕЧ 1 ! = хУг 'Уз УХ-! 9! (23) и уравнение изящно упрощается до (24) де! ЛХв = ~69 (Хотя это доказательство и приводится для областей целых чисел, оно очевидным образом применимо к любой области единственного разложения.) В процессе проверки алгоритма С мы также получили, что каждый элемент о', с которым мы имели дело в алгоритме, может быть выражен как детерминант с элементами, являющимися коэффициентами примитивных частей исходных полнномов.
Хорошо известная теорема Адамара (см. упр, 15) гласит, что х г/г ! Йе1(а!Х)! < П ~ ~~~ а;.) 4<1<в !<г<п (25) а потому каждый коэффициент, появляющийся в полиномах, которые вычислены согласно алгоритму С, не превышает №14п(гп+ 1)МЗ(н ( «)~з/з (26) если все коэффициенты данных полиномов и(х) и и(х) ограничены по абсолютному значению величиной Ж. Та же верхняя грань применима к коэффициентам всех полиномов и(х) и и(х), вычисленных при выполнении алгоритма Е, поскольку полиномы, получаемые в алгоритме Е, всегда являются делителями полиномов, получаемых в алгоритме С. Эта оценка верхней грани коэффициентов очень хороша, поскольку она гораздо лучше той, которую можно было бы ожидать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
