Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 23
Текст из файла (страница 23)
Если начать с матрицы М„состоящей из строк с А„, „, по Ай и с В„, „,. по Вй и выполнить указанные в табл. 1 операции над строками, можно получить матрицу М', состояпгую из расположенных в некотором порядке строк от В„, „,. по Вйз-щ«г, затем — от С„, „, поС„, „,.«4,..., отР„4, „, поРг, отЯ„„, „, поЯа и,наконец, Вй (строки, содержащей коэффициенты и-«4(х)).
Извлекая подходящие столбцы, покажем, что 34+! 4 434433-44 +! 4 Юг+! ! «33 433-Щ+! 4 34-4+! ! ЕВ»'-! 433-34+! х е = д дз ...д„"., "д," 4( сМ вЂ” ~ 3 щ . 3+!с (19) где г! — данный коэффициент и +! (х), а мс — п»щматрица м. )4 выбираются очень хитрым способом (см. упр. 24) — так, чтобы это уравнение упростилось до (20) Аз А» Аз Аз А! Ав Вт Вв Вз В» Вз Вг в, В« Сз С, Сз С, С! Св Вз Вг В! Вв Е! Ев Е« аз ат ав йз О ав ат ав О 0 ав ат о о о о о о о о о о а ьв ь, ь. ь. о Ь ь, ь, 0 0 Ьв Ьз о о а ь. 0 0 О 0 О О О О о о о о о о о о о о о о о а о о о о о о о а о о о о о о о о о о 0 0 О О о о о о о о о о о о о а о о о о о о о а о о о о й» аз аг аз а» аз йв аз 64 йт йв йз ав ат ав 0 ав ат Ьз Ь, Ьв Ьз Ьг Ь! ь, Ь ь, ь.
ь, ь. ь. ь, ь, о ь, ь, о а ьв о о о с» сз сг 0 с! сз о о о о о о о о о о а о о о о о о о о о о о о о а а о о о о о о а! ав 0 аг а! ав аз аз а! а» аз аз аз а» аз йв йз й» 0 0 0 ь, о о Ь, Ьв О ь, ь, ь. Ьз Ьг Ь! ь, ь, ь. ь, ь, ь, Ьв Ьз Ь» с! св 0 Сг С! Св сз сг с! С» СЗ СЗ 0 е» сз 0 О с» а дг 0 О »сг о о а о о а о а о о о о о о о о о О 0 ав 0 а! ав аг й! йз аг о о о о о о о о Ьв О ь, ь. Ьг Ь! Ьз Ьз о о о о св 0 С! Св сг с! ез сг й« а 44! 36 Аг 43! о дг 0 е! о а а о О О о о о о о о о а! а« о о о о о о а о о о 0 0 ь, о ь, ь, О 0 о о о а о о о Е! Св о о о о дв а 43! »С« Ев 0 е! еа 0 Ув Следовательно, калслыл коэффпшсеит и +1(я) может быть выражен кэк определитель матрлпы размера (п1 + пз — 2п + 2) х (ц1 + пз — 2п + 2), элементы которой представляют собоЛ коэффициенты и(х) п и(х).
Остается показать, что выбранные подобным образом Ь также являются целыми числами. Применима следующая методика: рассмотрим, например, матрицу (22) (убс+1Ху 641)ли-лз( б44-1! ьбв)лб-иб ( 41и!+1/ ф-1)и1-из с)ес бх $-"4 -" ", -в-из ". — -" (23) = ~Уз Уз ° ° У1-1 УХ и уравнение изящно упрошается до с(ет Мо = ~Л1.
(Хотя это доказательство н приводится для областей целых чисел, оно очевидным образом применимо к любой области единственного разложения.) В процессе проверки алгоритма С мы также получили, что каждый элемент о, с которым мы имели дело в алгоритме, может быть выражен как детерминант с элементами, являющимися коэффициентами примитивных частей исходных полинолсов, Хорошо известная теорема Адамара (см.
упр. 15) гласит, что А1 ав ат ав аз аб аз аз а1 ао 0 Ао 0 ав ат ав аз аб аз аз а1 ао В ЬЬЬЬЬЬЬООО ЪХ (21) ВОЬЬЬЬЬЬЬеоо В, 0 0 Ь,1 Ьф 64 Ьз Ьз 61 Ьс 0 В О ООЬЬЬЬЬзЬЬ Операции над строками, определенные в табл. 1, и перестановка строк приведут к матрице Вз ЬвбзббЬзЬзЬ1Ьс О 0 0 Вб 0 ЬвбзЬ4ЬзЬзЬ1Ьэ 0 0 В1 0 ОбвЬзЬ4ЬзЬзЬ1Ьэо В О О ОЬ,Ь,Ь.Ь,Ь,Ь,Ь, С1 0 О О Осбсзсзс1сс 0 Се 0 0 0 0 0 сб сз сз с се следовательно, если РассмотРеть любые подматРицы Мс и Мь, полУченные пУтем выбора шести соответствуюших столбцов М и М', можно получить Ьв з° Ьвз ° с)ес ЛХэ = ~ с)ес Ме. Когда Ме выбирается таким образом, что является первыми шестью столбцами М, получаем, что с)ес Ме = ~слб/Ьвз = хпз, так что Ьз является целым числом. В целом, чтобы показать, что А целое прн Х > 3.
начнем с матрицы М, состоЯщей из стРок с Аи, „, 1 по Аэ и с В„, „,. 1 по Вэ., затем бУдем выполнять соответствующие операции над строками до тех пор, пока не получим матрицу М', состояшуюизстрок сВ„, „, 1 по В,-„б, затем — с С„,э.иб 1 по С„, ..., с Р„,, „,. 1 по Рс и с сб'„1, „,. 1 по Яэ. Рассмотрев Ме, представляющую собой первые п1 + пз — 2пХ столбцов матрицы М, получаем 1Хз )с1ет(аб)) < П ~ ~ а,,) 1<1<И Х 1<1<и (25) а потому каждый коэффициент, появляющийся в полиномах, которые вычислены согласно алгоритму С, не превышает )1! ч ( + ц. Ьг(„+ ц д (26) если все коэффициенты данных полиномов и(х) и е(х) ограничены по абсолютному значению величиной Х.
Та же верхняя грань применима к коэффициентам всех полиномов а(х) и о(х), вычисленных при выполнении алгоритма Е, поскольку полиномы, получаемые в алгоритме Е, всегда являются делителями полиномов, получаемых в алгоритме С. Эта оценка верхней грани коэффициентов очень хороша, поскольку она гораздо лучше той, которую можно было бы ожидать. Например, рассмотрим, что случится, если не корректировать шаги ЕЗ и СЗ, а просто заменить е(х) на г(х). Это простейший алгоритм поиска код, традиционно приводимый в учебниках алгебры (в теоретических целях, не для практических вычислений). Если предположить, что бз = дз = ° ° = 1, можно нвйги, что коэффициенты аз(х) ограничены величиной Лз, коэффициенты аь(х) — величиной Хт, иь(х) — Х~т, ...
и коэффициенты из(х)— величиной 7е""', где ае ж 2аь д + аз з. Таким образом, верхняя грань при пз = а+1 вместо (26) приблязительно составляет )~о.ь!зяьа!" (7) О ае ат О Рае Ь Ь Ь О Ье Ьь О О Ьь О О О О О О ае аь аь аз аз ат ае аь аь аз Ьз Ьз Ь1 Ьо О Ьь Ьз Ьз Ь| Ь Ь Ь Ь Ь Ь Ь Ь Ь Ь Ь О Ьеь Ь Ь деь Вообще, Ьз будет больше единицы при у > 1 тогда и только тогда, когда подобный детерминант, составленный из коэффициентов и(х) и и(х), равен нулю.
Поскольку такой детерминант представляет собой ненулевой полинам от многих переменныхкоэффипиентов, он будет ненулевым "почти всегда" или "с вероятностью 1" (см, и упр, 16 более точную формулировку этого утверждения и связанное с ним доказательство в упр. 4). В примерах полиномов в (15) дз и бз равны 2, так что эти пс~чиномы, скорее всего, — исключение, а не правило. Эксперименты показывают, что простой алгоритм действительно ведет себя именно так; количество цифр в коэффициентах растет с каждым шагом экспоненциельно! В алгоритме Е, напротив, рост количества цифр лишь немного превосходит линейный.
Еще одним побочным результатом доказательства корректности алгоритма С является тот факт, что степени полиномов будут почти всегда увеличиваться на 1 на каждом шаге, так что число итераций шага С2 (или Е2) обычно будет составлять дей(о), если данные полкномы "случайны".
Для того чтобы увидеть, почему это происходит, заметим, например„что можно выбрать первые восемь столбцов М и М' в (17) и (18). В таком случае можно найти, что нь(х) имеет степень меньше 3 тогда и только тогда, когда ь(з = О, т. е. тогда и только тогда, когда аь ат ае аь аь аз аз аз Все вышесказанное может использоваться для доказательства хорошо известного факта, что два полинома взаимно просты тогда и только тогда, когда их результиамт ненулевой; результвпт представляет собой определитель, имеющий вид строк с Аз по Ао и с Вт по Во в табл. 1» (Это так называемый "детерминант Сильвестра" (см.
упр. 12). Свойства результвнта рассматриваются в книге В. 1,. чап бег Жаегдеп, Мое(егп Атйе(зга (имеется перевод на английский язык Фреда Блюма (ггеп В1шп) (Нею Уог)с: 1?пйвг, 1949)), разделы 27-28.) На основании приведенного выше материала можно сказать, что 8сй "почти всегда" имеет нулевую степень, поскольку детерминант Сильвестра почти никогда не равен нулю. Однако во многих вычислениях, представляющих практический интерес, нельзя быть уверенным в том, что 8041 не будет являться полиномом положительной степени.
Что происходит при работе алгоритмов Е и С при 8о1 уз 1, можно в точности увидеть, рассмотрев п(х) = ю(х)пт(х) и е(х) = ю(х)пз(х), где пз(х) и пз(х)— взаимно простые полиномы, а ю(х) — примитивный полипом. Тогда, если 01(х), пз(х), пз(х), ...— полиномы, получаемые при работе алгоритма Е с н(х) = п1(х) и и(х) = нз(х), легко увидеть, что последовательность, получаемая для п(х) = ю(х)из(х) и п(х) = ю(х)пз(х), представляет собой просто ю(х)п1(х), ю(х)пз(х), ю(х)пз(х), ю(х)не(х) и т. д.
Поведение алгоритма С несколько отличается: если полиномы п1(х), нз(х), пз(х), ... получены при работе алгоритма С с п(х) = пз(х) и п(х) = пз(х) и если дей(ну+1) = бей(п ) — 1 (что почти всегда истинно при у ) 1), то в результате применения алгоритма С к п(х) = ю(х)пт(х) и и(х) = ю(х)пз(х) получается последовательность ю(х)нт(х), ю(х)пз(х), 8'ю(х)нз(х?, 8'ю(х)пе(х) 8'ю(х)нз(х)~ "' (28) Дли бопылей ясности приведем полный вид результвите двук полииомов аол'" + а1л ' + лье явь Ля-1+ а-1 во амза„,о ао а1 ат 0 ао а~ ат а,1а„, О 0 0....
0 аоа|аз ьо ь ьт ...ь„, ь„о о ь ьз ь ... ь - ь о 0 Ьо Ь, Ьт Ь„ 1 Ь» (см., иепример, Кори Г., Кори Т. Спрелочияк ао математике (для иеучяых работников и иижеие. ров). — Ыл Наука, 1070, раздел 1.7.4). — Прим. иерее. где 1 = 8(ю) (см. упр. 13). Несмотря на наличие этих дополнительных 6множнтелей алгоритм С будет превосходить алгоритм Е, так как работать с несколько большими полиномами проще, чем постоянно вычислять примитивные части, Последовательности остатков, такие как получаемые в алгоритмах С и Е, полезны не только для поиска наибольших общих делителей и результантов. Важным применением является перечисление действительных корней данного полинома в определенном интервале согласно знаменитой теореме Я. Штурма (3.
81пгш) (Мош. Ргезепьез раг Эзчегз Яазппзз 6 (Рапз, 1835), 271-318?. Пусть п(х) — полипом над полем действительных чисел, имеизщий различные комплексные корни. Из следующего раздела вы узнаете, что корпи различны тогда и тсичько тогда, когда йсс((п(х),п'(х)) = 1, где п'(х) — производная п(х); значит, имеется последователь- ность остатков„доказывающая, что полинам и(х) взаимно прост с и'(х).
Считая ио(х) = и(х), и~(х) = и'(х) (и следуя Штурму), изменим знак всех остатков. Получим сзио(х) = и~(х)!ц(х) — Аиз(х), сои~(х) = иг(х)йз(х) — азиз(х) (29) сапа-1(х) = иа(х)йь(х) — <авиа ~(х) для некоторых положительных констант с! и б, где бей(ив+ ) = О. Будем говорить, что отклонение г'(и,а) полинома и(х) в а равно количеству изменений знака в последовательности ио(а), и~(а), ..., иью(а), не считая нулей.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
