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

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

§ 3.4. Производные и кратные корни 151

Справедливы следующие утверждения о производной многочлена.

Теорема 73.

(i) Производная многочлена нулевой степени равна 0.

(ii) Для любого c ∈ F производная многочлена x − c равна 1.

(iii) Производная суммы двух многочленов равна сумме производ-

ных.

(iv) Для любых c ∈F, f ∈F[x] справедливо равенство (cf)

′

= cf

′

т. е. постоянный множитель можно выносить за знак про-

изводной.

(v) Для любых многочленов f

∈F[x] справедлива формула

Лейбница

)

′

= f

′

+ f

′

(vi) Для любых многочленов f

∈F[x], i = 1, . . . , n, справедлива

обобщенная формула Лейбница

... f

)

′

= f

′

... f

+ f

′

... f

+ ... + f

... f

n−1

′

(vii) Для любого многочлена f ∈F[x]

)

′

= kf

k−1

· f

′

(viii) Для любого элемента c ∈F

((x −c)

)

′

= k(x − c)

k−1

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

средственно из определения. Формула Лейбница (v) легко доказывается

сначала в частном случае, а потом переходим к более общему случаю:

(а) f

(x) = ax

, f

(x) = bx

;

(б) f

(x) = a

+ a

n−1

+ ... + a

n−1

x + a

, f

(x) = bx

;

(в) f

(x) = a

+ a

n−1

+ ... + a

n−1

x + a

(x) = b

+ b

m−1

+ ... + b

m−1

x + b

Утверждение (vi) легко выводится из формулы Лейбница по индукции.

Утверждение (vii) является частным случаем предыдущего. Последнее

утверждение очевидно следует из предыдущих.

Естественным образом можно ввести понятие производных высшего

порядка.

Определение 80. Производная от первой производной называется

второй производной, производная от второй производной называет

ся третьей производной и т. д.; n

я производная

––

это производная

от (n −1)

й производной. Производная порядка n многочлена f обозна

чается обычно f

(n)

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

Справедливо следующее обобщение формулы Лейбница.

Теорема 74. Для любых многочленов f

∈F[x], i = 1, ..., n, и любого

натурального k справедливо равенство

)

(n)

k=0

(k)

(n−k)

где f

(0)

обозначает f.

Д о к а з а т е л ь с т в о. Доказательство проводится по индукции. Ба

за (n = 1) доказана в предыдущей теореме. Шаг индукции обосновывается

с помощью предыдущей теоремы и тождества Паскаля (см. с. 48).

Рассмотрим поле F характеристики 0 и кольцо многочленов над ним.

Определение 81. Элемент x

∈F называется корнем кратно-

сти n многочлена f(x) ∈F[x], если f(x) делится без остатка на (x − x

)

но не делится на (x −x

)

n+1

. Корень кратности 1 называется простым.

Теорема 75. Элемент x

∈F является корнем многочлена f(x)

кратности n (n > 2) тогда и только тогда, когда f(x

) = 0 и он

является корнем кратности n − 1 у производной многочлена f(x).

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

––

корень кратности n многочле

на f(x), тогда по определению f(x) = (x −x

)

·h(x), где h(x) не делится

на x −x

. Применяя предыдущую теорему, отсюда имеем, что

′

(x) = n(x −x

)

n−1

·h(x) + (x − x

)

·h

′

(x) =

= (x −x

)

n−1

· (n ·h(x) + (x −x

) · h

′

(x)).

Следовательно, f

′

(x) делится на (x −x

)

n−1

, но не делится на (x −x

)

так как h(x) не делится на x −x

Обратно, пусть f(x

) = 0 и f

′

(x) делится на (x − x

)

n−1

. Докажем,

что x

––

корень кратности n многочлена f(x). Предположим, что f(x) =

= (x −x

)

·h(x), где h(x) не делится на x −x

. Тогда

′

(x) = k(x −x

)

k−1

·h(x) + (x − x

)

·h

′

(x) =

= (x −x

)

k−1

· (k ·h(x) + (x − x

) · h

′

(x)),

многочлен kh(x) + (x − x

) ·h

′

(x) не делится на x − x

и, следователь

но, x

является корнем кратности k −1 производной f

′

(x), откуда

k = n.

Любой многочлен f может быть единственным образом разложен

по степеням (x −c):

f(x) = b

(x −c)

+ b

(x −c)

n−1

+ ... + b

n−1

(x −c) + b

§ 3.4. Производные и кратные корни 153

Это легко доказывается индукцией по степени многочлена. Действитель

но, разделим f(x) на x − c с остатком. Получим

f(x) = (x −c) f

(x) + b

где b

––

остаток, f

(x)

––

многочлен степени n − 1. В силу индуктивного

предположения

(x) = b

(x −c)

n−1

+ b

(x −c)

n−2

+ ... + b

n−1

откуда f(x) = b

(x −c)

+ ... + b

Опишем алгоритм для вычисления коэффициентов b

. Свободный

член b

разложения есть остаток от деления f на x −c, b

n−1

есть остаток

при делении неполного частного f

на x −c, и вычисление последующих

коэффициентов требует вычисления неполного частного f

при делении f

на x −c. Далее, b

n−2

находится как остаток при делении f

на x −c и т. д.

Красивые формулы для коэффициентов b

указывает следующая теорема.

Теорема 76 (Тейлор

∗

). Любой многочлен f степени n можно

представить в виде

f(c) +

′

(c)

(x −c) +

′′

(c)

(x −c)

+ ... +

(n)

(c)

(x −c)

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

f(x) = d

+ d

(x −c) + d

(x −c)

+ ... + d

(x −c)

Продифференцируем k раз обе части этого равенства. Используя правила

дифференцирования, получаем, что

(k)

(x) =k! d

+ (k+1)! d

k+1

(x −c) +. ..+n(n−1) . .. (n−k+1)d

(x −c)

n−k

Полагая x = c, имеем f

(k)

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

1. Определить A и B так, чтобы (x − 1)

|Ax

n+1

+ Bx

+ 1.

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

(i) x

−nx

n+1

+ nx

−1;

(ii) x

2n+1

− (2n + 1)x

n+1

+ (2n + 1)x

−1

имеют один тройной корень.

3. Найдите условие, при котором многочлен x

+ ax

+ b имеет двой

ной ненулевой корень.

* Б. Тейлор (Brook Taylor, 1685

–

1731)

––

английский математик, член Лондонского ко

ролевского общества.

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

4. Докажите, что трехчлен x

+ ax

n−m

+ b не может иметь ненулевых

корней кратности выше второй.

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

членный многочлен a

+ ... + a

не может

иметь ненулевых корней кратности выше (k −1)

й.

6. Докажите, что многочлен 1 + x + x

2 + x

3! + ... + x

n! не име

ет кратных корней.

7*. Докажите, что многочлен 1 + x + x

2 + x

3! + ... + x

n! имеет

не более одного действительного корня.

8*. Докажите, что многочлен 1+x +x

2+x

3!+...+x

n! не име

ет рациональных корней. У к а з а н и е. Применить формулу Лежандра

о делимости факториалов.

9. Разложите многочлен x

−6x

−4x

+ 9x

+ 12x + 4 на множите

ли, не имеющие кратных корней.

10. Если многочлен с целыми коэффициентами принимает в четырех

разных целых точках значение a, то он не может принимать ни в одной

целой точке значение a + p, где p

––

простое число.

11*. (Эйлер.) Многочлен n

+ n + 41 при n = 0, 1, .. ., 39 принимает

только простые значения, но при n = 40

––

нет. Докажите теорему: не су

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

чения при всех натуральных значениях аргумента.

12*. Существует многочлен f(x) n

й степени с целыми коэффициен

тами такой, что f(0), ..., f(n)

––

различные простые числа.

§ 3.5. Схема Горнера

∗

Деление произвольного многочлена на двучлен может быть выполнено

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

Действительно, если нужно разделить многочлен

f(x) = a

+ a

n−1

+ ... + a

n−1

x + a

∈F[x]

на двучлен x −c, где c ∈F , т. е. найти такие q(x) и r, что q(x) ∈ F [x],

r ∈F , и f(x) = (x −c)q(x) + r, естественно искать q(x) в форме b

n−1

+ b

n−2

+ ... + b

n−1

. Тогда получим равенство

f(x) = a

+ a

n−1

+ ... + a

n−1

x + a

= (x −c) (b

n−1

+ b

n−2

+ ... + b

n−1

) + r,

* В. Горнер (William George Horner, 1786

–

1837)

––

английский математик.

§ 3.5. Схема Горнера 155

равносильное цепочке равенств

= b

−cb

= b

−cb

. . . . . . . . . . . . . . . . . . . .

n−1

= b

n−1

−cb

n−2

= r −cb

n−1

откуда последовательно определяются коэффициенты q(x) и остаток r:

= a

+ cb

= a

+ cb

. . . . . . . . . . . . . . . . . . . .

n−1

= a

n−1

+ cb

n−2

r = a

+ cb

n−1

Заметим, что остаток r равен значению f(c) многочлена f(x) при x = c.

Действительно, переходя в равенстве f(x) = (x − c)q(x) + r к значениям

при x = c, получим f(c) = (c −c)q(c) + r, откуда r = f(c).

Указанный способ вычисления коэффициентов частного q(x) и остат

ка r носит название схемы Горнера (хотя она была, по существу, известна,

например, и Ньютону, и Руффини, и даже в Китае в XIII в.).

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

в нем арифметических операций.

В приведенном выше алгоритме Горнера использовались только опе

рации сложения

вычитания и умножения и фактически была доказана

Теорема 77. Частное и остаток от деления многочлена f(x)

степени n на x −c находятся со сложностью n плюс число ненуле-

вых коэффициентов у многочлена f(x) минус единица.

Упражнение 63. Найдите неполное частное и остаток при делении

многочлена x

на x −2.

Выпишем последовательно коэффициенты многочлена x

и, после

вертикальной черты, число 2:

1 0 0 0 0 0 | 2

Под этой строкой запишем коэффициенты неполного частного и остаток,

пользуясь только что выведенными формулами:

1 0 0 0 0 0 | 2

1 2 4 8 16 32

(остаток

––

подчеркнутое число). Итак,

= (x −2) (x

+ 2x

+ 4x

+ 8x + 16) + 32.

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

З а м е ч а н и е. В связи с этим примером отметим, что деление x

100

на x −1000 на компьютере таким способом выполнить затруднительно,

потому что остаток будет равен 10

и вызовет переполнение. Не все, что

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

Описанному в предыдущем параграфе алгоритму разложения много

члена по степеням двучлена x −c можно придать следующий вид.

Теорема 78. Младшие k + 1 коэффициентов многочлена f(x + c),

равные

f(c), f

′

(c), ..., f

(k)

(c)

k!,

можно вычислить со сложностью (k + 1) (2n −k), где n = deg f(x).

В частности, все коэффициенты вычисляются со сложностью

n(n + 1).

Д о к а з а т е л ь с т в о. Обозначим G(n, k + 1) сложность этого вы

числения. С помощью схемы Горнера со сложностью 2n вычислим q(x)

и f(c), где

f(x) = (x −c)q(x) + f(c).

Тогда

f(x + c) = xq(x + c) + p(c),

и для вычисления остальных k коэффициентов достаточно найти k млад

ших коэффициентов у многочлена q(x + c) степени n −1. Поэтому

G(n, k + 1) 6 G(n −1, k) + 2n, G(n, 1) 6 2n,

значит,

G(n, k + 1) 6 2n + 2(n −1) + . .. + 2(n −k) = (k + 1) (2n −k).

При k = n получаем G(n, n+1) =n(n +1), причем используется n(n+1)

сложений и столько же умножений на константу c.

Тот факт, что коэффициент при x

в многочлене f(x + c) равен

(k)

(c)

k!, следует из формулы Тейлора.

З а м е ч а н и е. Если c = 1, то реально умножений вообще не произ

водится. В общем случае почти все умножения можно сэкономить, если

предварительно вычислить c

, ..., c

, и от многочлена

f(x) = a

+ ... + a

перейти к многочлену

F(x) = f(xc) = a

+ ... + a

вычислив его коэффициенты a

, a

c, . .., a

, далее получить разложение

F(x) по степеням x − 1

F(x) = b

+ b

(x −1) + . .. + b

(x −1)

§ 3.5. Схема Горнера 157

с помощью n(n + 1)

2 сложений, откуда при y = xc

f(y) =b

c −1) +. ..+b

c −1)

(y −c) +. ..+

(y −c)

значит, нужные нам коэффициенты f

(k)

(c)

k! находятся по формулам

с помощью n делений.

Упражнение 64. Разложим многочлен x

по степеням x −2. При

меняя схему Горнера, получим:

1 0 0 0 0 0 | 2

1 2 4 8 16 32

1 4 12 32 80

1 6 24 80

1 8 40

1 10

где остатки подчеркнуты. Таким образом,

= (x −2)

+ 10(x −2)

+ 40(x − 2)

+ 80(x −2)

+ 80(x − 2) + 32.

Для приближенного вычисления корней многочлена бывает нужно

найти одновременно f(c) и f

′

(c). Выполнить это можно при помощи схемы

Горнера, вычислив два коэффициента разложения f по степеням x −c.

Упражнение 65. Для многочлена x

−x −1 вычислим f(1,2) и f

′

(1,2).

Применим схему Горнера:

1 0 −1 −1 | 1,2

1 1,2 0,44 −0,472

1 2,4 3,32

Итак, f(1,2) = −0,472 и f

′

(1,2) = 3,32.

В качестве еще одного применения схемы Горнера опишем алгоритм

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

Сначала переведем число из двоичной системы в восьмеричную. Для

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

на самом деле может быть парой или одной цифрой) и переводим их

в восьмеричную систему схемой Горнера (выполняемой устно). Например,

(1111110000)

= (1.111.110.000)

= (1760)

Выполним перевод из восьмеричной системы в десятичную. Пусть

число u = (u

... u

)

. На k

м шаге выполняем над полученной на пре

дыдущем шаге записью в десятичной арифметике действия

... u

n−k−1

−2 ·u

... u

n−k

= v

n+1

... v

n−k−1

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

и получаем запись

n+1

... v

n−k−1

n−k−2

... u

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

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

дут. На (n −1)

м шаге получаем десятичную запись числа u. Например,

(1760)

= (1008)

(1.7 6 0)

−

1 5.6 0

−

3 0

1 2 6.0

−

2 5 2

(1 0 0 8)

Алгоритм перевода из десятичной системы в двоичную почти та

кой же. Сначала переводим в восьмеричную запись. Для этого, пользу

ясь восьмеричной арифметикой, на k

м шаге выполняем над полученной

на предыдущем шаге записью действия:

... u

n−k−1

+ 2 ·u

... u

n−k

= v

n+1

... v

n−k−1

и получаем запись

n+1

... v

n−k−1

n−k−2

... u

(поначалу (n + 1)

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

ниях участвовать не будут). На (n −1)

м шаге получаем восьмеричную

запись числа u. Например, (1945)

= (3631)

(1.9 4 5)

2 3.4 5

4 6

3 0 2.5

6 0 4

(3 6 3 1)

Здесь числа левее точки записаны в восьмеричной системе. Далее пере

водим восьмеричное n

значное число в двоичное (вычисляя для каждой

восьмеричной цифры двумя делениями на два с остатком ее двоичную

запись).

§ 3.5. Схема Горнера 159

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

1. Укажите ускоренный вариант схемы Горнера, удобный для вычис

ления четных и нечетных многочленов, и дайте оценку его сложности.

2. Переведите из десятичной в двоичную число 12345678987654321.

3. Переведите из двоичной в десятичную число 10101010101010101.

4. Дайте подробное обоснование изложенных в этом параграфе ал

горитмов перевода из двоичной в десятичную систему и обратно.

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

+ 10 ·60

. Переведите его из шестидесятеричной системы в десятичную.

6*. (Параллельная схема Горнера.) Если компьютер имеет k парал

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

нимают пренебрежимо малое время, то вычисление значения многочлена

степени n в заданной точке требует не более

k + max

j6k

l(j) + log

k + O(1)

единиц времени, где l(m)

––

время вычисления x

У к а з а н и е. Положим n = mk + s, 0 6 s < k, и представим p(x)

в виде

k−1

j=0

) =

j=0

i=0

ki+ j

k−1

j=s+1

m−1

i=0

ki+ j

На j

м процессоре вычисляем x

). Для этого на (k −1)

м про

цессоре вычисляется со сложностью l(k) + O(1) степени x

k−1

и x

и по

следняя передается на остальные процессоры, которые тем временем

вычисляют степени x

. После этого все процессоры вычисляют x

)

со сложностью 2n

k + O(1) каждый (используя обычную схему Горнера).

Остается сложить полученные результаты за время log

k + O(1), ис

пользуя параллельно k

2 процессоров.

7*. Для одновременного вычисления значений многочлена в несколь

ких точках схему Горнера иногда можно немного ускорить.

Докажите, что для одновременного вычисления значений p(c) и p(−c)

достаточно 2n + 1 операции, где n

––

степень многочлена p(x).

У к а з а н и е. Разделим p(x) на x

−c

. Получим равенство

p(x) = q(x) (x

−c

) + r

x + r

Представляя p(x) в виде суммы многочленов, содержащих только четные

и только нечетные степени переменной, получим, что p(x) = p

) +

+ xp

), где сумма степеней многочленов p

(x) и p

(x) равна n −1.

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

Деля их на x −c

, имеем

(x) = q

(x) (x −c

) + k

, p

(x) = q

(x) (x −c

) + k

Отсюда

q(x) (x

−c

) + r

x + r

= p(x) = p

) + xp

) =

= q

)(x

−c

) + k

+ x(q

)(x

−c

) + k

) =

= (x

−c

)(q

) + xq

)) + k

x + k

значит,

= k

, r

= k

, q(x) = q

) + xq

Сложность деления на x

−c

не превосходит 2n −2. Для вычисления

p(c) = q(c) (c

−c

) + rc + r = rc + r,

p(−c) = q(−c) (c

−c

) + r

(−c) + r

= −r

c + r

нужно дополнительно 3 операции.

§ 3.6. Аддитивные цепочки

Назовем аддитивной цепочкой любую начинающуюся с 1 последо

вательность натуральных чисел a

= 1, a

, ..., a

, в которой каждое число

является суммой каких-то двух предыдущих чисел (или удвоением

какого

то предыдущего числа). Обозначим l(n) наименьшую длину ад

дитивной цепочки, заканчивающейся числом n. Для определенности под

длиной цепочки a

= 1, a

, ..., a

понимаем число m.

П р и м е р ы. 1. Последовательность 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,

12, 13, 14

––

аддитивная цепочка.

2. Последовательность 1, 2, 3, 5, 7, 14

––

минимальная цепочка для 14,

т. е. l(14) = 5.

3. Аддитивные цепочки можно изображать в виде ориентированно

го графа, в котором в вершину a

идут ребра от вершин a

, a

, если

= a

+ a

(в случае, если такое представление неоднозначно, выбира

ем любое из них и рисуем только два ребра). Если из какой

то вершины

выходит только одно ребро, то для краткости можно

склеить

эту вер

шину с той вершиной, в которую ведет это ребро. Граф для предыдущего

примера см. рис. 21.

1 2 3 5 7 14

Рис. 21