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

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

§ 3.9. Взаимные многочлены 181

Теорема 88 (Муавр). (i) Если f

––

возвратный многочлен степе-

ни 2n, то

−n

f(x) = F

(x +

где F

––

многочлен степени n.

(ii) Если f

––

возвратный многочлен степени 2n + 1, то

f(x)

(x + 1)

––

возвратный многочлен степени 2n.

Д о к а з а т е л ь с т в о. Доказательство (i) основано на тождестве

−n

f(x) =

k=0

+ x

−k

) =

k=0

(x +

и в качестве F

берем

k=0

(x).

Доказательство (ii) основано на тождестве

f(x)

x + 1

= g(x) =

k=0

+ x

2n+1−k

1 + x

k=0

и замечании, что, хотя многочлены q

и не возвратные, но

+ x

2n+1−k

1 + x

= x

−x

k+1

+ ... −x

2n−k−1

+ x

2n−k

и их коэффициенты удовлетворяют равенствам a

= a

2n−k

, значит, и мно

гочлен g(x) тоже удовлетворяет этим равенствам и является возвратным,

так как его степень равна 2n.

Следствие из теоремы 88. Возвратное уравнение n-й степени

сводится к уравнению степени ⌊n

2⌋.

Определение 85. Многочлен p(x) называется четным, если он удо

влетворяет тождеству p(x) = p(−x), и нечетным, если он удовлетворяет

тождеству p(x) = −p(−x)

Упражнение 78. 1. Любой многочлен однозначно представим в виде

суммы четного и нечетного многочленов.

2. Четный многочлен степени n представим в виде f(x

), где f

––

много

член степени n

2 и содержит только четные степени, а нечетный

––

в виде

xf(x

), где f

––

многочлен степени (n −1)

2 и содержит только нечетные

степени.

3. Четное или нечетное уравнение n

й степени сводится к уравнению

степени ⌊n

2⌋.

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

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

1. Решите уравнения

(i) x

+ 3x

−5x + 3x + 1 = 0;

(ii) x

+ 2x

−4x

+ 2x + 1 = 0.

2. Многочлены Чебышёва определяются равенством T

(cos x) =

= cos nx. Докажите, что P

(x) = 2T

2).

Последовательность P

(x) можно формально продолжить и для отри

цательных индексов, при этом, очевидно P

−i

(x) = P

(x).

3. Многочлены P

c четными номерами сами четные, а многочлены

с нечетными номерами

––

сами нечетные. Поэтому их удобно представлять

в виде

(x) =

⌊i

2⌋

j=0

i,j

(−1)

i−2j

4. Для последовательности P

(x) справедливо тождество

(x) = P

(x)) = P

(x)).

У к а з а н и е. Положите x = z + z

−1

, тогда

(z + z

−1

)) = P

+ z

−m

)) = z

+ z

−nm

= P

(z + z

−1

5. Для последовательности P

(x) справедливо тождество

n+m

(x) + P

n−m

(x) = P

(x)P

(x).

У к а з а н и е. Действительно,

n+m

+ z

−n−m

+ z

n−m

+ z

−n+m

= (z

+ z

−n

)(z

+ z

−m

6*. Для последовательности P

(x) справедливы следующие равенства

(i) P

(x) =

⌊i

2⌋

j=0

i,j

(−1)

i−2j

, a

i,j

= C

i−j

+ C

j−1

i−j−1

(ii) x

⌊i

2⌋

j=0

i−2j

, где для удобства положим P

= 1.

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

основания шага индукции ввиду тождества

i+1

(x) = xP

(x) −P

i−1

(x)

достаточно проверить, что всегда a

i+1,j

= a

i,j

+ a

i−1,j−1

, а это вытекает

из тождества Паскаля:

i,j

+ a

i−1,j−1

= C

i−j

+ C

j−1

i−j−1

+ C

j−1

i−j

+ C

j−2

i−j−1

= C

1+i−j

+ C

j−1

i−j

= a

i+1,j

§ 3.10. Симметрические многочлены 183

Для доказательства (ii) достаточно умножить обе его части на x

и опять применить тождество Паскаля:

i+1

= xx

⌊i

2⌋

j=0

i−2j

⌊i

2⌋

j=0

i−2j+1

+ P

i−2j−1

) =

= P

i+1

⌊i

2⌋

j=1



+ C

j−1



i−2j−1

⌊i

2⌋

j=0

i+1

i−2j+1

§ 3.10. Симметрические многочлены

Пусть K

––

кольцо. Напомним, что через K[x

, ..., x

] обозначается

кольцо многочленов от переменных x

, . .., x

с коэффициентами из коль

ца K .

Пусть дан многочлен

f(x

, ..., x

) =

...i

... x

∈K[x

, ..., x

]

и перестановка α ∈S

, где S

––

группа перестановок символов {1, 2, .. . n}.

Определение 86. Определим действие перестановки α на много

член f равенством

, ..., x

) =

...i

−1

(1)

... x

−1

(n)

Определение 87. Многочлен f(x

, . . ., x

) ∈K[x

, . .., x

] называется

симметрическим, если для любой перестановки α ∈S

справедливо ра

венство

, ..., x

) = f(x

, ..., x

Определение 88. Элементарные симметрические многочлены

––

это многочлены

, ..., x

) = x

+ ... + x

, ..., x

) = x

+ x

+ ... + x

+ x

+ ... + x

n−1

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

, ..., x

) = x

... x

+ ... + x

n−k+1

... x

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

, ..., x

) = x

... x

Упражнение 79. Симметрический многочлен можно записывать в

виде

f(x

, ..., x

) =

6. . .6i

. . .i

... x

+ ... ),

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

где последним знаком

...

отмечены все одночлены, получающиеся

из x

... x

перестановками (нижних индексов) переменных.

Теорема 89 (Виет

∗

). Многочлен

f(z) = z

+ a

n−1

+ ... + a

имеет n (не обязательно различных) корней x

, ..., x

тогда и толь-

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











= −σ

, ..., x

);

= σ

, ..., x

);

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

= (−1)

, ..., x

Д о к а з а т е л ь с т в о заключается в раскрытии скобок в произве

дении f(z) = (z − x

)(z − x

) ... (z −x

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

+ a

n−1

+ ... + a

= z

− (x

+ ... + x

n−1

+ ... + (−1)

... x

Если два многочлена равны, то равны их коэффициенты. Поэтому











+ ... + x

= a

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

(−1)

... x

= a

Теорема 90 (о симметрических многочленах). Предположим,

что f(x

, ..., x

)

––

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

и притом только один многочлен ϕ(y

, ..., y

) такой, что

f(x

, ..., x

) = ϕ(σ

, ..., x

), ..., σ

, ..., x

)).

Д о к а з а т е л ь с т в о. Докажем существование такого многочле

на. Достаточно сделать это для симметрических многочленов вида

... x

+... Всюду в дальнейшем будем выписывать только одно сла

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

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

Можно считать, что i

> i

> ... > i

. Будем говорить, что одночлен

... x

старше одночлена x

... x

(имеет больший вес), если выпол

няется нераавенство

+ ... + i

> j

+ ... + j

* Ф. Виет (François Viète, 1540

–

1603)

––

выдающийся французский математик, при

дворный криптоаналитик Генриха IV, по основной профессии

––

юрист.

§ 3.10. Симметрические многочлены 185

или выполняется равенство

+ ... + i

= j

+ ... + j

и одно из следующих условий:

> j

;

= j

, i

> j

;

и т. д. Записываем отношение старшинства в виде

... x

≫x

... x

Будем выражать симметрические многочлены x

... x

+ ... через эле

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

вида x

... x

+ ..., где x

... x

≫x

... x

. Заметим, что при раскрытии

скобок в произведении

−i

... σ

n−1

−i

n−1

в сумме будет присутствовать одночлен вида x

... x

(и все одночле

ны, получающиеся из него перестановками переменных). При этом среди

одночленов в этой сумме он будет старшим. Тогда у симметрического

многочлена

... x

+ ... −σ

−i

... σ

n−1

−i

n−1

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

процедуру. Продолжая этот процесс, мы выразим наш многочлен через

элементарные симметрические многочлены за конечное число шагов.

Доказательство единственности этого выражения проведем от про

тивного. Пусть

(σ

, ..., x

), ..., σ

, ..., x

)) и ϕ

(σ

, ..., x

), ..., σ

, ..., x

))

––

два различных выражения для f(x

, ..., x

). Тогда ненулевой многочлен

ϕ(y

, ..., y

) = ϕ

, ..., y

) −ϕ

, ..., y

)

при подстановке y

= σ

... x

) обращается в нуль. При этой подста

новке одночлен ay

... y

в многочлене ϕ(y

... y

) с ненулевым ко

эффициентом a перейдет в сумму одночленов, в которой старшим будет

одночлен

+. . .+ j

... x

n−1

+ j

n−1

Упражнение. Докажите это.

Из всех одночленов ay

... y

многочлена ϕ(y

... y

) выберем такой,

что одночлен

+. . .+ j

... x

n−1

+ j

n−1

будет самым старшим из всех возможных.

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

Упражнение. Докажите, что такой выбор возможен.

Тогда при подстановке элементарных симметрических многочленов

в многочлен ϕ(y

, ..., y

) этот одночлен будет старшим в полученном

многочлене. Поэтому ему не с чем будет сократиться и ϕ(σ

, .. ., σ

) 6= 0.

Противоречие.

Симметрические многочлены и доказанная теорема имеют много при

ложений. Например, ее использование облегчает решение симметриче

ских систем уравнений.

Определение 89. Система называется симметрической, если ее

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

С помощью упоминавшейся теоремы симметрическую систему можно

свести путем замены переменных к несимметрической, но, как правило,

более простой системе, а для нахождения исходных переменных решить

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

(

x + y = u;

xy = v,

а в случае, например, трех переменных выглядит так:











x + y + z = u;

xy + xz + yz = v;

xyz = w.

Ее решение с помощью теоремы Виета сводится к решению соответству

ющего алгебраического уравнения.

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

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

иногда под не вполне вразумительным, но коротким названием мето

да квадратного корня. Этот метод независимо был открыт Данделеном,

Лобачевским *, Греффе и Энке. Он приложим только к алгебраическим

уравнениям и требует большего объема вычислений, чем метод Ньютона,

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

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

тельного разделения корней и нахождения их приближений с невысокой

точностью, как метод Ньютона.

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

Виета и теорему о симметрических многочленах, построить для любого

* Лобачевский изложил его в своем учебнике

Алгебра, или вычисление конечных

изданном в Казани в 1834 г.

§ 3.10. Симметрические многочлены 187

уравнения

+ a

n−1

+ ... + a

= 0

новое уравнение

+ b

n−1

+ ... + b

= 0,

у которого все корни являются заданной m

й степенью корней исходного

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

личны:

|> |x

|> ... > |x

Впрочем, если мы предварительно проведем отделение кратных корней,

как будет показано в § 3.12, вероятность появления равных модулей будет

очень мала.

Если m достаточно велико, то |x

| будет значительно больше |x

поэтому можно считать, что

|= |σ

, ..., x

приближенно равно |x

|, откуда имеем приближенную формулу

ln |x

|≈

ln |b

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

ния |x

| замечаем, что если m достаточно велико, то |x

| будет значи

тельно больше всех остальных |x

|, поэтому можно считать, что

|= |σ

, ..., x

приближенно равно |x

|, откуда имеем приближенную формулу

ln |x

ln |b

а так как |x

| уже найден, то приближенно

ln |x

(ln |b

|−ln |b

и т. д.

Однако находить указанное уравнение для очень больших m чрезвы

чайно трудоемко, и кажется, что это обесценивает идею. Но можно делать

это только для m = 2

, k раз повторяя процедуру построения уравнения,

корни которого равны квадратам корней исходного (применяем бинарный

метод!). Еще некоторое упрощение вычислений достигается введением

понятия корней Энке.

Определение 90. Корнями Энке назовем корни уравнения, взятые

с обратным знаком.

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

Очевидно, что квадраты корней Энке совпадают с квадратами обыч

ных корней, а теорема Виета для корней Энке приобретает особенно

простой вид, так как в ней можно не следить за знаками коэффициентов.

На каждом шаге итерации будем по исходному уравнению

+ a

n−1

+ ... + a

= 0

строить новое уравнение

+ b

n−1

+ ... + b

= 0,

у которого корни Энке являются квадратами корней Энке исходного

уравнения. Для этого в исходном уравнении перенесем нечетные степе

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

(далее в выкладках для определенности положим, что n

––

четно)

+ a

n−2

+ a

n−4

+ ...)

= (a

n−1

+ a

n−3

+ ...)

и введем новую переменную, полагая y = −x

, откуда имеем

+ (a

−2a

n−1

+ (a

−2a

+ 2a

n−2

+ ... = 0.

У полученного уравнения корни Энке как раз и равны квадратам корней

Энке исходного уравнения.

Упражнение 80. Проверьте, что остальные коэффициенты нового

уравнения вычисляются по формулам

= a

−2a

+ 2a

−2a

= a

−2a

+ 2a

−2a

+ 2a

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ,

= a

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

2 + Cn операций сложения

вычитания и умножения чисел, где C

––

некоторая константа.

Правило вычисления коэффициентов может быть выражено словесно

следующим образом: i

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

бавлением к квадрату i

го коэффициента исходного уравнения удвоенно

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

с обеих сторон и взятых с чередующимися знаками.

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

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

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

краткости записывать получающиеся очень большие коэффициенты в ви

де, например, 2002

вместо 2002 ·10

§ 3.10. Симметрические многочлены 189

Приведем пример * вычисления корней уравнения f(x) = x

+ 9x

+ 23x + 14 = 0. Для краткости уравнение, полученное из f одним ша

гом итерации, обозначаем f

, следующее уравнение обозначаем f

и т. д.

Вычисления прекращаем, когда квадраты коэффициентов уравнения f

совпадают (при применяемой точности вычислений) с коэффициентами

уравнения f

k+1

Расположим сначала коэффициенты уравнения в следующем порядке:

1 9000

−3

2300

−2

1400

−2

На каждом шаге вычисления возводим в квадрат эти коэффициенты

и прибавляем удвоенные произведения согласно приведенному правилу,

располагая вычисления в таблицу *.

1 8100

−2

5290

−1

1960

−1

−4600 −2520

1 3500

−2

2770

−1

1960

−1

1 1225

7673

3842

−0554 −1372

1 0671

6301

3842

1 4502

3970

1476

−1260 −0052

1 3242

3918

1476

1 1051

1535

2179

−0078

1 0973

1535

2179

1 9467

2356

4748

−0031

1 9436

2356

4748

1 8904

5551

2254

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

согласно указанным выше правилам:

|= 4,861, |x

|= 3,254, |x

|= 0,8851.

Знаки корней можно определить, подставляя оба варианта в уравнение

(используя при этом схему Горнера).

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

же и комплексными числами, при этом приближенно вычисляются их

модули. Метод квадратного корня можно приспособить и для нахождения

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

стью.

* Заимствованный из прекрасной книги Э. Уитткера и Г. Робинсона

Математическая

обработка результатов наблюдений

(ОНТИ, 1935).

* Раньше для этого использовали таблицы возведения в квадрат и таблицы логарифмов

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

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

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

1. Выразите через элементарные симметрические функции

а) x

+ y

+ z

−3xyz; в)

;

б) (x −y)

(x −z)

(y −z)

; г)

2. Пусть x

––

корни уравнения ax

+ bx + c = 0. Выразите через

a, b, c величины x

+ x

и x

−3

+ x

−3

3. Пусть x

––

корни уравнения x

−7x

+ 1 = 0. Составьте для

i = 1, . . ., 4 уравнение с корнями (i) x

, (ii) x

, (iii) x

, (iv) x

4. Решите методом квадратного корня уравнение x

−3x + 2 = 0.

5*. Решите методом квадратного корня уравнение c кратными корня

ми x

+ 7x

+ 16x + 12 = 0.

6*. Пусть x

––

корни уравнения золотого сечения x

−x −1 = 0. Со

ставьте уравнение с корнями x

, i = 1, 2.

7*. Пусть x

––

корни уравнения x

2005

−7x

+ 1 = 0. Найдите сумму

2005

i=1

2005

8. Решите систему уравнений

(

y + x

+ 2x

+ x

+ xy

= 30;

y + xy + x + y + xy

= 11.

9. Решите систему уравнений











x + y

1 + xy

;

+ y

1 + x

257

10*. Обозначим через s

+...+x

степенные суммы и через

... x

элементарные симметрические многочлены. Докажите

формулы Ньютона:

(

−s

k−1

+ ... + (−1)

k−n

= 0 при k > n,

−s

k−1

+ ... + (−1)

k−1

+ (−1)

kσ

= 0 при k 6 n.

11*. Пусть p

––

симметрический многочлен от n переменных степе

ни k, и многочлены p

, ..., p

алгебраически независимы, т. е. не суще

ствует ненулевого многочлена Q(x

, ..., x

) такого, что

Q(p

, ..., p

) = 0.

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

жается через многочлены p

, ..., p