Гашков С.Б. Современная элементарная алгебра в задачах и решениях

Подождите немного. Документ загружается.

§ 3.11. Быстрое умножение 191

12. Докажите, что множество симметрических многочленов образует

подкольцо в кольце K[x

, ..., x

13. Многочлен называется кососимметрическим (или антисим-

метрическим), если он меняет знак при любой транспозиции пере

менных. Проверьте, что кососимметрический многочлен меняет знак

при нечетных и не меняет знак при четных перестановках переменных.

14. Докажите, что сумма и разность кососимметрических многочле

нов

––

кососимметрический многочлен, а произведение

––

симметрический

многочлен.

15. Докажите, что любой многочлен от двух переменных представля

ется в виде суммы симметрического и кососимметрического многочленов,

причем единственным образом.

16. Докажите, что многочлен

D(x

, ..., x

) =

16i< j6n

−x

)

––

кососимметрический.

17. Докажите, что любой кососимметрический многочлен представим

в виде произведения D(x

, ..., x

) на симметрический многочлен.

18*. Докажите, что отображение

f(x

, ..., x

) →

α∈S

, ..., x

)

переводит любой многочлен в симметрический, а отображение

f(x

, ..., x

) →

α∈S

ε(α) f

, ..., x

)

(где ε(α)

––

знак перестановки α)

––

в кососимметрический.

19*. Докажите, что если многочлен не меняется при четных переста

новках, то его можно представить как сумму симметрического и косо

симметрического многочленов.

§ 3.11. Быстрое умножение

Первым придумал быстрый алгоритм умножения в 1962 г. А. А. Кара

цуба *.

* Тогда он был аспирантом мехмата. В 1963

–

64 гг. преподавал в ФМШ № 18 при МГУ.

Более 30 лет является профессором мехмата МГУ. Выдающийся специалист по аналити

ческой теории чисел.

192 Глава III. Многочлены

Идею его метода можно пояснить на следующем примере. Пусть пере

множаются восьмизначные числа U =

... u

и V = v

... v

. Предста

вим их как двузначные числа в 10

значной системе счисления: U = U

V = V

. Тогда их произведение можно представить в следующем виде:

UV = U

+ ((U

−U

)(V

−V

) + U

+ U

)10

+ U

Эта формула сводит умножение 8

значных чисел к трем операциям

умножения и шести операциям сложения

вычитания 4

значных чисел

(с учетом переносов в следующие разряды). Обычный способ требует

четырех умножений и трех сложений

вычитаний, но так как три раза

сложить 4

значные числа можно быстрее, чем один раз перемножить,

то метод Карацубы уже 8

значные числа перемножает быстрее. В об

щем случае он требует для перемножения n

значных чисел по порядку

не больше

log

< n

1,585

операций над цифрами, для школьного же метода требуется по порядку n

операций.

Рассмотрим вопрос о сложности умножения более подробно. Начнем

с умножения многочленов.

Лемма 23. Умножение двух многочленов степеней, меньших 2n,

можно свести к умножению трех пар многочленов степеней, мень-

ших n, и сложению четырех пар многочленов степеней, меньших n,

и вычитанию двух пар многочленов степеней, меньших 2n, с помо-

щью тождества

+ f

)(g

+ g

) =

= f

+ ((f

+ f

)(g

+ g

) − f

− f

+ f

Обозначим через M(n) наименьшее количество операций сложения,

вычитания и умножения (выполняемых над коэффициентами многочленов

и промежуточными числовыми результатами), требующихся для перемно

жения двух многочленов степеней, меньших n.

Лемма 24. Справедливы неравенства

M(n) 6 2M(⌈n

2⌉) + M(⌊n

2⌋) + 4⌊n

2⌋+ 2n −4.

Д о к а з а т е л ь с т в о. Применим равенство

⌊n

2⌋

+ f

)(g

⌊n

2⌋

+ g

) =

= f

2⌊n

2⌋

+ ((f

+ f

)(g

+ g

) − f

− f

⌊n

2⌋

+ f

§ 3.11. Быстрое умножение 193

где степени многочленов f

и g

меньше ⌈n

2⌉, а степени многочленов f

и g

меньше ⌊n

2⌋, и заметим, что для вычисления произведений f

требуется не более M(⌈n

2⌉) + M(⌊n

2⌋) операций, для вычисления

сумм f

+ f

, g

+ g

, f

+ f

нужно не более 2⌊n

2⌋+ 2⌊n

2⌋−1

операций (так как число операций равно наименьшему из количеств нену

левых коэффициентов у складываемых многочленов), для вычисления

произведения (f

+ f

)(g

+ g

) используется не более M(⌈n

2⌉) опера

ций, для вычисления разности (f

+ f

)(g

+ g

) − f

− f

достаточна

n −1 операция, так как

+ f

)(g

+ g

) − f

− f

= f

+ f

значит, степень этого многочлена равна ⌊n

2⌋+ ⌈n

2⌉−2 = n −2, сло

жение многочленов f

и f

2⌊n

2⌋

выполняется

бесплатно

, так как

они не имеют подобных членов, причем в их сумме отсутствует член ви

да x

2⌊n

2⌋−1

, поэтому для сложения многочленов

+ f

2⌊n

2⌋

, (f

+ f

⌊n

2⌋

достаточно n −2 операции. В итоге требуется дополнительно 4⌊n

2⌋+

+ 2n −4 операции.

Теорема 91. Если 2

делит n, то справедливо неравенство

M(n) 6 3

(M(n

) + 8n

−2) −8n + 2,

а при любом n

––

неравенство

M(n) < (35

3)n

Д о к а з а т е л ь с т в о. Пусть 2

m = n. Тогда неравенство

M(n) 6 3

(M(m) + 8m −2) −8n + 2

доказывается индукцией по k. База (k = 1) доказана в лемме 2. Шаг ин

дукции обосновывается тем же неравенством.

Выберем k так, чтобы 2

< n 6 2

k+1

. Тогда если 3 ·2

k−1

< n, то

M(n) 6 M(2

k+1

) <3

k−1

(M(4) +30) 63

k−1

·55< 55·





Если же n 6 3 ·2

k−1

, то

M(n) 6 M(3 ·2

k−1

) < 3

k−1

(M(3) + 22) 6 3

k−1

·35 6 (35

3)n

Перейдем к умножению чисел.

Пусть теперь M(n) обозначает наименьшее количество операций сло

жения, вычитания и умножения, выполняемых над числами, меньшими a,

требующихся для перемножения двух n

значных чисел, записанных в по

зиционной системе счисления по основанию a.

13 Гашков

194 Глава III. Многочлены

Лемма 25. Справедливы неравенства

M(2n) 6 3M(n) + 19n, M(2n + 1) 6 2M(n + 1) + M(n) + 17n + 10.

Д о к а з а т е л ь с т в о. Применим тождества

⌈n

2⌉

+ f

)(g

⌈n

2⌉

+ g

) =

= f

2⌈n

2⌉

+ (f

+ f

− (f

− f

)(g

− g

))b

⌈n

2⌉

+ f

где числа f

и g

––

⌊n

2⌋

разрядные, а числа f

и g

соответствен

но ⌈n

2⌉

разрядные, и заметим, что для вычисления произведений f

и f

требуется M(⌈n

2⌉) + M(⌊n

2⌋) операций, для вычисления разно

стей и суммы f

− f

, g

− g

, f

+ f

требуется не более

n(1 + ⌊n

2⌋−⌈n

2⌉) + 2(⌊n

2⌋+ ⌈n

2⌉−1) + 2(⌊n

2⌋+ ⌈n

2⌉) −1 =

= 4n −3 + n(1 + ⌊n

2⌋−⌈n

2⌉)

операций, так как числа f

и f

имеют не более чем 2⌊n

2⌋ и 2⌈n

2⌉

разрядов соответственно, а в случае четного n нужно еще 2⌊n

2⌋= n

операций для предварительного сравнения чисел (чтобы не вычитать

из меньшего большее). Заметим далее, что для вычисления произведения

− f

)(g

− g

) требуется не более M(⌈n

2⌉) + 1 операций (одна опе

рация для вычисления знака у произведения), для вычисления разности

+ f

− (f

− f

)(g

− g

) = f

+ f

требуется не более 2⌈n

2⌉+ 1 + 2⌈n

2⌉−1 = 4⌈n

2⌉ операций, сложение

чисел f

и f

2⌈n

2⌉

осуществляется

бесплатно

(записи этих чисел

просто объединяются в одну запись), а для сложения чисел f

2⌈n

2⌉

+ f

и (f

+ f

⌈n

2⌉

требуется не более 2n −⌈n

2⌉+ n + 1 −1 =

= 2n + ⌊n

2⌋ операций (так как число f

+ f

имеет не более n + 1

разряда, а младшие ⌊n

2⌋ разрядов числа f

не участвуют в операциях).

В итоге требуется дополнительно

4n −3 + n(1 + ⌊n

2⌋−⌈n

2⌉) + 1 + 4⌈n

2⌉+ 2n + ⌊n

2⌋=

= 7n + 3⌈n

2⌉+ n(1 + ⌊n

2⌋−⌈n

2⌉) −2

операций.

Задачи и упражнения к § 3.11

В следующим цикле задач речь идет о том, как по возможности бы

стрее производить арифметические операции с дробями, сводя их к опе

рациям над целыми числами (или многочленами).

§ 3.11. Быстрое умножение 195

1. Допустим, что дроби a

b и c

d несократимы. Пусть (a, d) = g

(b, c) = g

. Докажите, что

((a

)(c

), (d

)(b

)) = 1.

2. Допустим, что дроби a

b и c

d несократимы и числа a, b, c, d мень

ше 10

. Предложите способ умножения и деления этих дробей, в котором

все промежуточные результаты будут меньше 10

, если в окончательном

ответе числитель и знаменатель меньше 10

3. Пусть (a, b) = (c, d) =1, (b, d) = g

, t =ad

+bc

, (t, g

) = g

Докажите, что

, b

) = (t, d

) = (t, b

) = 1,

= (t, g

) = (t, (d

)(b

) g

) = (t, bd

, d

) = 1, b делится на g

, (d

)(b

)) = 1.

4. Допустим, что дроби a

b и c

d несократимы и числа a, b, c, d

меньше 10

. Предложите способ сложения и вычитания этих дробей,

в котором все промежуточные результаты будут меньше 10

, кроме од

ного, который будет меньше 10

, если в окончательном ответе числитель

и знаменатель меньше 10

Отметим, что утверждения этих задач можно перенести и на много

члены.

5. Проверьте, что обычный способ умножения многочленов дает

оценку

M(n) 6 M

(n) = n

+ (n −1)

6. Для умножения многочленов найдите наименьшее n, при котором

M(n) < M

(n).

7. Докажите, что сложение двух n

значных чисел можно выпол

нить за 2n −1 операцию, вычитание меньшего из большего

––

за 3n −1

операцию, вычитание с определением знака разности

––

за 4n − 1 опера

цию, а сложение (n + m)

значного числа с n

значным можно выполнить

за 2n + m −1 операцию.

8. Докажите, что обычный способ умножения чисел дает оценку

M(n) < 5n

Обозначим через K(n) сложность возведения n

разрядного числа

в квадрат и такое же обозначение будем использовать для сложности

возведения в квадрат многочлена степени n − 1.

13*

196 Глава III. Многочлены

9. Используя тождество

ab =

(a + b)

− (a −b)

докажите для случая операций с числами неравенство

M(n) 6 2K(n) + 13n + O(1),

а для случая операций с многочленами

––

неравенство

M(n) 6 2K(n) + 6n + 4.

§ 3.12. Разложение на бесквадратные множители

Для многочленов над произвольным полем дадим следующее

Определение 91. Разложение многочлена

P = q

... q

такое, что сомножители q

не имеют кратных корней и попарно взаим

но просты, называется бесквадратной факторизацией первого типа

многочлена P.

Обозначим

= q

i+1

... q

тогда

P = Q

... Q

, Q

i+1

, i = 1, . . ., k − 1,

и многочлены Q

не имеют кратных корней. Такую факторизацию назовем

бесквадратной факторизацией второго типа.

Упражнение 81. Проверьте, что оба типа бесквадратной факториза

ции однозначно восстанавливаются один по другому с помощью формул

= Q

i+1

, Q

= P

i+1

, P

= q

i+1

... q

k−i+1

Пусть P = q

... q

––

бесквадратная факторизация первого типа.

Следующая лемма справедлива для многочленов над любым полем нуле

вой характеристики. Производную многочлена P обозначаем

Лемма 26. Для последовательности многочленов P

, начинаю-

щейся с P

= P и определяемой равенствами P

i+1





, спра-

ведливо тождество

= q

i+1

... q

k−i+1

= Q

i+1

... Q

(i = 1, . . ., k),

§ 3.12. Разложение на бесквадратные множители 197

где Q

= q

i+1

... q

, откуда

i+1

, q

i+1

(i = 1, . . ., k),

и таким образом оба вида факторизации существуют и опреде-

лены однозначно.

Д о к а з а т е л ь с т в о. Согласно предположению индукции и фор

муле Лейбница

i+1

... q

k−i+1

+ q

i+1

... q

k−i+1

+ ...

... + q

i+1

... q

k−i

k−1

(k −i + 1)q

k−i

= P

i+1



i+1

... q

+ ... + q

i+1

... q

k−1

(k −i + 1)



Сумма, стоящая в скобках, взаимно проста с q

, потому что все слагае

мые, кроме первого, кратны q

, а первое слагаемое взаимно просто с ним.

Действительно все его сомножители взаимно просты с q

, так как q

вза

имно просты друг с другом и не имеют кратных корней, поэтому





= 1.

Аналогичным образом проверяем, что сумма, стоящая в скобках, взаимно

проста с q

i+1

, .. ., q

, а значит, и с произведением Q

= q

i+1

... q

. По

этому



, P



= P

i+1



, Q



= P

i+1

чем и доказан шаг индукции.

В стандартном алгоритме бесквадратной факторизации рекуррентно

вычисляется последовательность многочленов по формулам P

i+1





, где, как только что доказано,

= q

i+1

... q

k−i+1

= Q

i+1

... Q

после чего находятся делением многочлены

i+1

, q

i+1

Изложим алгоритм Остроградского * бесквадратной факторизации

в обозначениях самого Остроградского и оценим его сложность (т. е.

число выполняемых им операций).

* Остроградский Михаил Васильевич (1801

–

1862)

––

выдающийся русский математик

и механик. Один из основателей петербургской математической школы.

198 Глава III. Многочлены

Пусть P = P

––

факторизуемый многочлен, положим





, Q

, R

, q



, R

−



, R

−

, q



, R

−



и так далее, пока не получим R

k+1

. Тогда P = q

... q

––

ис

комое разложение, потому что q

не имеют кратных корней и взаим

но просты. Отметим, что попутно найдено разложение P = Q

... Q

где Q

= q

... q

(i = 1, . . ., k) тоже бесквадратные множители, но уже

не взаимно простые, а последовательно делящие друг друга.

Обосновывается алгоритм Остроградского с помощью его замеча

тельных тождеств.

Теорема 92 (Остроградский). Для определенных выше последо-

вательностей многочленов справедливы тождества

i+1

i+2

−

, q



, R

−



Д о к а з а т е л ь с т в о. Применяя индукцию, получаем, что

−

i+1

−

d(P

i+1

)

i+1

откуда имеем

i+1

−

i+1

i+2

Так как

= q

i+1

... q

k−i+1

, R

i+1

, Q

= q

... q

из теоремы о понижении кратности корня при дифференцировании выте

кает, что (R

, Q

) = 1, откуда следует уже безо всякой индукции, что



, R

−



= (Q

, R

i+1

) = (Q

i+1

, R

i+1

) = (Q

i+1

, R

i+1

) =

= q

i+1

, R

i+1

) = q

§ 3.12. Разложение на бесквадратные множители 199

Заметим еще, что из формул

i+1

, Q

i+1

вытекает, что deg R

= deg P

−deg P

i+1

−1 = deg Q

−1.

Преимущество алгоритма Остроградского перед стандартным алго

ритмом очевидно ввиду того, что на каждом шаге итерации он требу

ет нахождения НОД многочленов меньшей степени, чем в стандартном

алгоритме, и вместо двух делений использует только одно, причем для

многочленов опять же меньшей степени. Кроме того, он допускает хо

рошую оценку сложности при использовании в нем быстрых алгоритмов

умножения, деления и вычисления НОД.

Оценка сложности алгоритма Остроградского получается довольно

просто, если воспользоваться следующим замечанием.

Пусть M(n)

––

любая оценка сложности умножения двух многочленов

степени n, удовлетворяющая условию супераддитивности: M(x) + M(y) 6

6 M(x + y), и G(n)

––

такая же оценка сложности вычисления НОД двух

многочленов. Например, в качестве M(n) можно взять Cn

log

, а в ка

честве G(n) можно взять CM(n) lg n при большой константе C (это мы

не будем доказывать).

Положим deg Q

= n

, deg q

= m

, deg P

= p = n

+ ... n

, тогда m

= n

−n

i+1

, deg R

= n

−1. Сложность деления без остатка многочлена

степени m на многочлен степени n оценим как 3(M(m −n) + m −n) +

+ M(m), значит, сложность деления двух разных многочленов степени

не выше m на один и тот же многочлен степени n оценивается как

3(M(m −n) + m −n) + 2M(m), тогда нужная оценка имеет вид

n + G(n) + 3M(n − p) + 3n −3p + 2M(n) +

i=1

(G(n

) + 2M(n

) + 2n

) +

i=2

(3M(n

) + 3n

) 6 n + G(n) + 3(M(n − p) + n − p) + 2M(n) +

+ G(n) + 2M(n) + 2n + 3(M(p) + p) 6 2G(n) + 7M(n) + 6n.

Полученная оценка показывает, что сложность алгоритма Остроград

ского бесквадратной факторизации многочлена степени n асимптоти-

чески лишь в два раза превосходит сложность алгоритма нахождения

НОД двух многочленов степени n.

Интересно отметить, что Остроградский предложил еще один вариант

алгоритма факторизации, основанный на тождестве q



Q, R − j



200 Глава III. Многочлены

где

Q = Q

, R = R

, P



, P



Доказательство вытекает из цепочки равенств (в которой для кратко

сти дифференцирование обозначается штрихом)

R =

)

′

.. . q

)

′

.. . q

k−1

i=1

... q

i−1

)

′

i+1

... q

′

i=1

... q

i−1

)

′

i+1

... q

R − jQ

′

i=1

(i − j)q

... q

i−1

)

′

i+1

... q

обосновываемой правилом дифференцирования Лейбница, и замечания

о том, что в последней сумме все слагаемые, кроме s

го, делятся на q

а оно взаимно просто с многочленом q

(так как все его сомножите

ли с ним взаимно просты), следовательно, (R − jQ

′

, q

) = 1 при s 6= j,

и, очевидно, многочлен R − jQ делится на многочлен q

Указанные формулы Остроградского более элегантны, чем предыду

щие, но сложность последнего алгоритма очевидно больше, чем предыду

щего, так как в нем степени многочленов последовательности, у которых

приходится вычислять НОД, не уменьшаются, и он не допускает оче

видной хорошей верхней оценки. Однако если нужно вычислить не все

множители q

, а только любой один из них, то этот алгоритм, вероятно,

является быстрейшим.

Задачи и упражнения к § 3.12

1. Обоснуйте стандартный алгоритм бесквадратной факторизации

со всеми подробностями.

2. Обоснуйте второй алгоритм бесквадратной факторизации Остро

градского со всеми подробностями.

3. Выполните бесквадратную факторизацию многочлена стандартным

методом и методом Остроградского

+ 3x

−5x

−21x

+ x

+ 45x

+ 17x

−39x

−22x

+ 12x + 8

и найдите его корни.