Следовательно, каждый коэффициент Uj+i{x) может быть выражен как определитель матрицы размера (nj +П2 - 2nj + 2) х (nj + пг - nj + 2), элементы которой представляют собой коэффициенты и{х) и v{x).

Остается показать, что выбранные подобным образом h также являются целыми числами. Применима следующая методика: рассмотрим, например, матрицу

Al /08 о7 Об 05 04 Оз 02 Oj Oq О \ Ао О Og о7 Об 05 04 Оз 02 Oi Оо

Вз be 65 64 63 62 bi Ьо О О О

В2 О 6б 65 64 Ьз 62 bi Ьо О О

Si О О 6б 65 64 63 62 61 Ьо О

Во \ О О О 6б Ьз Ь4 Ьз Ьг bi Ьо /

Операции над строками, определенные в табл. 1, и перестановка строк приведут к матрице

/Ье 65 64 Ьз Ь2 bi Ьо О О О \ О 6б 65 64 Ьз Ь2 bi Ьо О О О 6б h Ь4 Ьз Ьг bi Ьо О

= М.

(21)

Bi Во Ci Со

О О О \ О

О о 6б Ь5 64 Ьз Ьг 61 Ьо

= М;

(22)

О О О С4 сз Сг ci Со О О О О О С4 Сз Сг ci Со/

следовательно, если рассмотреть любые подматрицы Мо и Мд, полученные путем выбора шести соответствующих столбцов М и М, можно получить Ьц bg • det Mq = ± det Mq. Когда Mq выбирается таким образом, что является первыми шестью столбцами М, получаем, что det Mq = ±С4/Ьб = ±Дз, так что Лз является целым числом.

В целом, чтобы показать, что hj целое при j > 3, начнем с матрицы М, состоящей из строк с Ап--щ-г по Ао и с B„-nj-i по Во; затем будем вьшолнять соответствующие операции над строками до тех пор, пока не получим матрицу М, состоящую из строк с S„j „. i по Впз-nj, затем -с C„+nj-i по С„ „., ...

с Pnj 2-nj-i по Ро и с Q„j i-„j-i по Qo- Рассмотрев Мо, представляющую собой первые ni + П2 - 2nj столбцов матрицы М, получаем

{92/9:hi)

П.-П, (д+/дХТ-" {gf/gj-ihZi )"-"- det Мо

9jli

и уравнение изящно упрощается до

det Мо = :hj.

(23)

(24)

(Хотя это доказательство и приводится для областей целых чисел, оно очевидным образом применимо к любой области единственного разложения.)

В процессе проверки алгоритма С мы также получили, что каждый элемент 5, с которым мы имели дело в алгоритме, может быть выражен как детерминант с элементами, являющимися коэффициентами примитивных частей исходных полиномов. Хорошо известная теорема Адамара (см. упр. 15) гласит, что

ч1/2

det(o,,)< п Е 4

l<t<nl<j<n

а потому каждый коэффициент, появляющийся в полиномах, которые вычислены согласно алгоритму С, не превышает

ЛГ"+"(т + 1)"/2(„ + 1)п/2 (26)

если все коэффициенты данных полиномов и{х) и v{x) ограничены по абсолютному значению величиной N. Та же верхняя грань применима к коэффициентам всех полиномов и{х) и v{x), вычисленных при выполнении алгоритма Е, поскольку полиномы, получаемые в алгоритме Е, всегда являются делителями полиномов, получаемых в алгоритме С.

Эта оценка верхней грани коэффициентов очень хороша, поскольку она гораздо лучше той, которую можно было бы ожидать. Например, рассмотрим, что случится, если не корректировать шаги ЕЗ и СЗ, а просто заменить v{x) на г{х). Это простейший алгоритм поиска gcd, традиционно приводимый в учебниках алгебры (в теоретических целях, не для практических вычислений). Если предположить, что 6i = = • • = 1, можно найти, что коэффициенты из{х) ограничены величиной N, коэффициенты U4{x)-величиной N, U5{x) - Л, ... и коэффициенты Ukix) - величиной TV", где o/t = 2ak-i +ak-2- Таким образом, верхняя грань при т = п + 1 вместо (26) приблизительно составляет

jsf0.bi2.4ur (27)

Эксперименты показывают, что простой алгоритм действительно ведет себя именно так; количество цифр в коэффициентах растет с каждым шагом экспоненциально! В алгоритме Е, напротив, рост количества цифр лишь немного превосходит линейный.

Еще одним побочным результатом доказательства корректности алгоритма С является тот факт, что степени полиномов бздут почти всегда увеличиваться на 1 на каждом шаге, так что число итераций шага С2 (или Е2) обычно будет составлять deg(u), если данные полиномы "случайны" Для того чтобы увидеть, почему это происходит, заметим, например, что можно выбрать первые восемь столбцов М и М в (17) и (18). В таком случае можно найти, что U4{x) имеет степень меньше 3 тогда и только тогда, когда ds = О, т. е. тогда и только тогда, когда

/ 08 07 Об 05 04 Оз 02 Ol \

о as 07 Об аь 04 03 02

О О 08 О7 Об О5 04 Оз

6б 65 Ь4 Ьз Ь2 bl bo о

о 6б 65 Ь4 Ьз b-z bl bo

О О 6б 65 64 Ьз Ь2 bl

О О О 6б Ьз Ь4 Ьз 62

V О О О О 6б 65 64 Ьз /

Вообще, Sj будет больше единицы при j > 1 тогда и только тогда, когда подобный детерминант, составленный из коэффициентов и{х) и v{x), равен нулю. Поскольку такой детерминант представляет собой ненулевой полином от многих переменных-коэффициентов, он будет ненулевым "почти всегда" или "с вероятностью 1" (см. в упр. 16 более точную формулировку этого утверждения и связанное с ним доказательство в упр. 4). В примерах полиномов в (15) S2 и S3 равны 2, так что эти полиномы, скорее всего, - исключение, а не правило.

= 0.

Все вышесказанное может использоваться для доказательства хорошо известного факта, что два полинома взаимно просты тогда и только тогда, когда их результант ненулевой; результант представляет собой определитель, имеющий вид строк с Л5 по Ао и с Б7 по Бо в табл. 1* (Это так называемый "детерминант Сильвестра" (см. упр. 12). Свойства результанта рассматриваются в книге В. L. van der Waer-den. Modern Algebra (имеется перевод на английский язык Фреда Блюма (Fred Blum) (New York: Ungar, 1949)), разделы 27-28.) На основании приведенного выше материала можно сказать, что gcd "почти всегда" имеет нулевую степень, поскольку детерминант Сильвестра почти никогда не равен нулю. Однако во многих вычислениях, представляющих практический интерес, нельзя быть уверенным в том, что gcd не будет являться полиномом положительной степени.

Что происходит при работе алгоритмов Е и С при gcd ф 1, можно в точности увидеть, рассмотрев и{х) = w{x)ui{x) и v{x) = w{x)u2ix), где ui{x) и и2{х) - взаимно простые полиномы, а it;(x)-примитивный полином. Тогда, если ui(x), U2{x), из(х), ... - полиномы, получаемые при работе алгоритма Е с и{х) = щ(х) и v(x) = U2{x), легко увидеть, что последовательность, получаемая для и{х) = w{x)ui{x) и v{x) = w{x)u2{x), представляет собой просто w{x)ui{x), w{x)u2{x), w{x)u3{x), w{x)u4{x) и т. д. Поведение алгоритма С несколько отличается: если полиномы щ{х), U2{x), из{х), ... получены при работе алгоритма С с и{х) = ui{x) и v{x) = U2ix) и если deg(uj+i) = deg(uj) - 1 (что почти всегда истинно при j > 1), то в результате применения алгоритма С к и{х) = w{x)ui{x) и v{x) = w{x)u2ix) получается последовательность

w{x)ui{x), w{x)u2{x), ew{x)u3{x), e*w{x)u4{x), lw{x)ub{x), (28)

где (. = i{w) (см. упр. 13). Несмотря на наличие этих дополнительных -множителей алгоритм С будет превосходить алгоритм Е, так как работать с несколько большими полиномами проще, чем постоянно вычислять примитивные части.

Последовательности остатков, такие как получаемые в алгоритмах С и Е, полезны не только для поиска наибольших общих делителей и результантов. Важным применением является перечисление действительных корней данного полинома в определенном интервале согласно знаменитой теореме Я. Штурма (J. Sturm) [Мёт. Presentes par Divers Savants 6 (Paris, 1835), 271-318]. Пусть u{x)-полином над полем действительных чисел, имеющий различные комплексные корни. Из следующего раздела вы узнаете, что корни различны тогда и только тогда, когда gcd(u(x),u(x)) - 1, где и{х)-производная и{х); значит, имеется последователь-

* Для большей ясности приведем полный вид результанта двух полиномов аох" + ajx"

... -I- am и box" + blX- + . . . + Ьп.

..... Om-l От о • • • • О \

-I-

/ао 01 02 •

О Оо 01 02

О • • .

Ьо bi 62

О Ьо bi 62

\0

О ао CLi 0.2 Ьп-\ Ьп о • • Ьп-\ Ьп о

От-1 От О

О Ьо bi Ьг

Om-l От О О

Ьп-1 Ьп /

(см., например. Корн Г., Корн Т. Справочник по математике (для н&учных работников и инженеров).- М.: Наука, 1978, раздел 1.7.4). - Прим. перев.