Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 101
Текст из файла (страница 101)
Пусть х — корень некоторого ((юзможно, нескольких) и) . Когда Ь увеличивается от х — е до х, знаковая последовательность около б переходит от "+, х, -" к "+, О, -" или от "' †, х, +" к "-, О, +" при у > О; при ) = Π— от "+, -" к "О, -" нли от "-, +" к "О, +"(поскольку и'(х) — производная, и (х) отрицательна при уменьшении и(х)). Таким образом, изменение К составляет †)а. При возрастании Ь от х до х + е подобное рассмотрение показывает, что Ъ' остается неизменным. [Л.
Э. Хайндел (1, Е.Непи1е1) в работе ХАСМ 18 (1971), 533-548, применил эти идеи для построения алгоритма обособления действительных нулей данного палинома и(х) за время, растущее как полинам от деб(и) н 1об)((, где все коэффициенты и, — целые числа (ит( < ))(, а все операции абсолютно точны.) 23. Если в имеет и — 1 действительный корень мех(лу и действительными корнямн и, то, рассмотрев изменения знаков, получим, что и(х) шо(( в(х) имеет и — 2 действительных карня, лежащих между и — 1 корнем в. Э ( 6 эп-д~ ~) Ю~( -бэ)...((-Ю) ~) 24.
Сначала покажите, что Л) = д ' д ' ' ... дт '", а затем — что показатель степени дэ аленой части (13~ имеет вил бе+ 5(х, где х = бэ+ +б, (+ 1 — бэ(бэ+ +б)-) + 1) — бэ(1 — бэ)(б(+ ° +бз-) + 1) — . — б)-)(1 — бэ)... (1 — б)-э)(1). Однако х = 1, поскольку он не зависит от бз ), н можно принять, что б) ( = О, и т. д. Подобное доказательство работает и для дэ, ды ..., а упрощение — дли (23).
25. Каждый коэффициент и)(х) может быть выражен как детерминант, в котором один столбец содержит только б(и), б(в) и нули. Чтобы использовать этот факт, модифицируем алгоритм С слиэующим образам. На шаге С1 установим д +- бсб(б(и),б(в)) и Л +- О, На шаге СЗ, если Л м О, установим и(х) (- е(а), в(х) ( — г(х)/д, Л +- с(и)~/д, д (- г(и) н вернемся к шагу С2. В противном случае будем работать по немадифипированному алгоритму, Эффект этой новой инициализации заключается в простой замене иу(х) иа и,(х)/бед(Р(и),б(в)) для всех б > 3. Таким образом, в (28) сш ~ становится с~) 26. Фактически верно даже большее.
Обратите внимание, что алгоритм иэ упр. 3 вычисляет шр„(х) и ~д„(х) для и > -1. Пусть е„= боб(д,) и ((„ы ()еб(р и — д в). В УпР. 3 мы видели, что (( -) + еп ж ()еб(и) лла и > О. Докажем, что УсловиЯ беб(д) < е„ и ()еб(ри - дв) < б„э влекут за собой р(х) = с(х)р ((х) я д(х) ы с(х)д ((х). По данным р н д можно найти с(х) н б(х), такие, что р(х) ж с(х)р ((х) + й(х)р„(х) и д(х) м с(х)д„((х) + (1(х)д„(х), поскольку р -((х)д„(х) — р„(х)д„((х) = ш1.
Следовательно, Ри — дв = с(Р -(и — д -(в)+(1(д„и — дев). Если (((х) ~ О, мы должны иметь ((еб(с)+е„ деб((1) + г„, так как ()еб(д) < деб(д„). Отсюда слелует, что беб(с) + (( ( > деб(4) + (1, поскольку это, несомненно, верно, если (Ь, = -ш). В противном случае (( ( + е„м б„+е„+( > и +е -(. Таким образом, беб(ри — дв) = беб(с)+(( (. Но мы предположили, что беб(ри — дв) < б„-т = (( -( + е„— е„), так что деб(с) < е„— е„) и ()еб((б) < О, чта приводит к противоречию.
(Этот результат, по сути, получен в работе Ь, Кгопес)(ег, Мопагэбег(сЪсе Кап)81. ргеиб. Абв(Ь И')эк (Вег!)п, 1881), 535-600. Отсюда вытекает следующая теорема. "Пусть и(х) и в(х) — взаимно простые полнномы над полем и пусть б < ()еб(е) < Йеб(и). ~ли д(х) является палиномом наименьшей степени, таким, что существуют полиномы р(х) и г(х), такие, что р(х)и(х) — д(х)в(х) = г(х) н ((еб(г) = ((, то р(х)/д(х) = р„(х)/д„(х) для некоторого п'! Дяя ((„-т > (( > (( ( существует решение д(х), такое, что йеб(д) = е„) + (1 — б ( < е . Итак, все решения столь низкой степени имеют укаэанное свойство.) 27.
Приложимы идеи упр. 4.3.1-40, но в более простой форме, потому что полиномнальная арифметика не оперирует переносами; деление справа налево использует 4,7 — (3). Другой путь заключается в том, чтобы при больших значениях и делить преобразования Фурье коэффициентов с "обратным" использованием упр. 4.6.4-57. РАЗДЕЛ й.б.2 1. Для люба"о выбора Ь < и различных корней существует р" " нормированных полиномов, имеющих как минимум по одному из этих корней. Поэтому согласно принципу включения и исключения (см. раздел 1.3.3) количество полиномов без линейных множителей составляет ~"„с„(~~)р" ь(-1)". Частичные суммы этого ряда попеременно больше или меньше его суммы.
Требуемые границы можно получить, положив н = 2 и и = 3. При и > р вероятность наличия хотя бы одного линейного множителя составляет 1 - (1 — 1/р)". СрЕднее количество линейных множителей в р раз превышает среднее количество случаев, когда величина х делит полинам и(х), так что оно составляет 1+р '+" +р'- =;г-,(1-р-"). [Аналогично находим, что вероятность существования неприводимого множителя степени 2 Равна ~„<„гз (мг „мш)( — 1)ьР зь, Эта веРоатность лежит междУ з — -'Р ' и -' — -'р ' при и > 2 и стремится к 1 — е нш(1+ -'р ') + 0(р з) при н -э оо.
Среднее количество таких множителей равно 1 — -'р з1" гз1.) Примечание. Пусть к(х) — фиксированный полипом с целыми коэффициентами. Петер Вайнбергер (Ресет ЖшпЬегбш) обнаружил, что если н(х) неприводим над кольцом целых чисел, то среднее количество линейных множителей ц(х) по модулю р стремится к 1 при р -э оо, потому что группа Галуа и(х) траизитивна и среднее количество единичных циклов в случайно выбранном элементе любой группы транзитивиых перестановок равно 1. Следовательно, среднее количество линейных множителей н(х) по мгщ"лю р равно количеству непрнвцдимых множителей и(х) над кольцом целых чисел при р -+ со.
(См, примечания в ответе к упр. 37, а также Ргос. Бутр. Рше Маей. 24 (Атег. МасЬ. Бес., 1972), 321-332. ( 2. (а) Известно, что и(х) может быть представлен как произведение непрнводнмых псшиномов н что старшие коэффициенты зтнх полиномов должны быть обратимыми злемеитамн, поскольку они делят старший козффицнепт полияома н(х). Поэтому можно считать, что к(х) имеет представление в виде произведения нормированных неприводимых полиномов рг(х)" . р,(х)", где р1(х), ..., р„(х) различны. Это представление единственно с точностью до порядка множителей, так что условия, налагаемые на о(х), и(х) и ш(х), удовлетворяютсв тогда и только тогда, когда е(х) = р~(х)бч~ 1...р,(х)1'"Г 1, ш(х) р1(х) ' ...р„(х)'" (Ь) Производящая функция для количества нормированных полиномов степени и представляет собой 1 + рх + р~х' + " ж 1/(1 — рх).
Производящая функция для количества полиномов степени н, имеющих вид и(х) з, где и(х) — нормированный полипом, представляет собой 1 + рхз + рзх~ + . = 1/(1 — рзз). Кази обозначить производящую функцию для количества нормированных свободных ат квадратов полиномов степени н через 9(х), то согласно п. (а) этого упражнения 1/(1 — рх) = 9(х)/(1 — рет).
Следовательно, У(х) = (1 — рз )/(1 — рз) = 1 + рх+ (р — р)хз + (рз — р~)аз + .. Таким образом, ответ — р" — р" ' для и > 2. [Любопытно, что это доказывает, что н(х) .1. и'(х) с вероятностью 1 — 1/р; зто та же вероятность, что и вероятность того, что в(х) 1. э(х) в случае кезаепскмостк к(х) и о(х) согласно упр. 4.6.1-5.] Примечание. Аналогично доказывается, что каждый полипом и(х) может быть единственным образом представлен в виде о(х) ш(х)", где и(х» ие делится на г-ю степень никакого неприводнмого полииома; количество таких нормированных поликанов е(х) составляет р" — р""'+' при и > г, 3. Пусть и(х) = ир(х) ., . и,(х).
Имеется не более одного такого полииома р(х) согласно доказательству теоремы 4.3.2С. Существует пр меньшей мере один такой полипом, если Дла кажДого / можно Решить системУ с шр(х) = 1 и ив(х) = О пРи Х ЗЕ У. Решением последней является ер(х) П . ие(х), где ер(х) н ез(х) удовлетворшот соотношению щ(х) Пьаз иь(х) + рз(х)иу(х) = 1, беб(эд) < беб(и ) согласио расширению алгоритма Евклида (упр. 4.6.1-3).
Над кольцом целых чисел нельзя сделать е(х) щ 1 (по модулю х) и е(х) щ 0 (по модулю х — 2) при беб(и) < 2. 4. Исходя из единственности разложения, имеем (1 — рх) ' = П„,(1 — х") '"'; после взатия логарифмов это соотношение может быть переписано как 1п(1/(1 — Рх)) = ~ ау>, аьр* '/У' » 2 1>, Ср(х')Д.
Из утверждения указания следует ответ Ср(х)» 2»>, р(гл)рп ')в(1/(1 — рх )), из котоРого полУчаем а„р» 2 з1„Р(п/6)Р /и. Таким обРазом, Вшр»» а„р/Р" = 1/и. Для доказательства утверждения, приведенного в указании, заметим, что Е„б>,р(п)9( "')и '/ '»Е >рй(х") п 'Е„, р(п)»9(х). [Числа а„р были впервые найкены Гауссом; см. Ргегйе 2, 219-222.] 6. Пусть а„р, — количество нормированяых полииомов степени и по модулю р, имеющих в точности г неприводимых множителей, Тогда Ср(х,ю) = Я„„>еа„р„х" ю" » ехрЯ ь>, Ср(х~)ш"/9) екр(~ >, а 1в(1/(1 - рх" )); см. формулу 1.2.9-(38).
Имеем Е„йа ~ррх" » бар(х/Р, ю)/бю [~-1» (Еь> ~ Ср(х" /р")) Ср(з/р~1) = (Е„>,1в(1/(1-р' "з"))р( а)/и)/(1 — ), следовательно, 4„р» Н„+ 1/2р+ 0(р ') для и > 2, Среднее значение 2" равно [х" ] Ор(х/р, 2) = и + 1 + (и — 1)/р + 0(пр '). (Дисперсия, однако, есть величина порядка пз: положите ю = 4.) 6. Согласно теореме Ферма х-е является множителем хр-х (по модулю р) длв О < з < р. Значит, хР— х кратно 1сш(х - О, х - 1,..., х — (р - Ц) = хх.
[Примечание. Следовательно, числа Стирлиига [ьг] краткы р за исключением случаев, когда 9» 1 или 9» р, Формула 1.2.6-(46) показывает, что то же утверждение справедливо и для чисел Стирлинга (ьр) второго рода,] у. Множители в правой части взаимно просты, и каждый из них являетсв делителем и(х), так что их произведение делит и(х). С другой стороны, и(х) делит е(х) р — е(х) = Пе<„ср(е(х) — з), так что и(х) делит правую часть согласно упр. 4.6.2-2.
8. Вектор (18) является единственным, 6-я компонента которого не равна нулю. 9. Например, начав с х г- 1 и р +- 1. Затем следует сто рзз установить Щх] +- р, х е-2хшоб101, 9+- 51ушоб101. 10, Матрица Я вЂ” Х, приведенная ниже, имеет ядро, порожденное двумя векторами е01 = (1, О, О, О, О, О, О, О), е~э1 = (О, 1, 1, О, О, 1, 1, 1). Разложение представляет собой (х + х + х + в+ 1)(х +я+1). 8=2 0 0 0 0 О 0 1 1 О 0 О 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 1 О 0 1 0 1 1 1 0 1 1 р=б 0 О 0 0 0 0 0 0 4 О О 0 1 О 0 2 2 0 4 3 4 0 1 4 4 4 2 1 2 2 2 3 4 3 2 0 0 4 О 1 3 2 3 0 2 1 4 2 1 О 0 0 О 0 0 О 0 0 0 1 0 О 1 0 0 0 0 1 0 1 1 0 1 11.
После удаления тривиального множителя х приведенная выше матрица Ц вЂ” 1 имеет ядро, порожденное (1, О, О, О, О, О, 0) и (О, 3, 1, 4, 1, 2, 1). Полное разложение полино ма таково: х(х +3х+4)(х +2х +х +4х +х+ 3). 12. Если р = 2, (х + 1)» ы х» + 1, Если р = 8)г + 1, С вЂ” ! представляет собой нулевую матрицу, а значит, существует четыре множителя. Для других значений р имеем: р=бй+7 р = 8/» + 3 р = 8»г + 5 О 0 -2 0 0 0 0 0 О О -2 О 14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
