Главная страница

Многочилен. Лекция 2 Многочлены


Скачать 217.45 Kb.
НазваниеЛекция 2 Многочлены
АнкорМногочилен
Дата14.10.2019
Размер217.45 Kb.
Формат файлаpdf
Имя файлаlinalg02.pdf
ТипЛекция
#90016

Лекция 2: Многочлены
Б.М.Верников
Уральский федеральный университет,
Институт математики и компьютерных наук,
кафедра алгебры и дискретной математики
Б.М.Верников
Лекция 2: Многочлены

Понятие многочлена
Определения
Многочленом от одной переменной называется выражение вида f (x) = a n
x n
+ a n−1
x n−1
+ · · · + a
1
x + a
0
,
где a
0
, a
1
, . . . , a n
— произвольные (комплексные) числа и a n
6= 0. В
дальнейшем, говоря о многочленах, мы опускаем слова «от одной переменной», поскольку многочлены от нескольких переменных мы рассматривать не будем. Число n называется степенью многочлена f и обозначается через deg f . Числа a
0
, a
1
, . . . , a n
называются коэффициентами многочлена f , число a
0
— его свободным членом, а число a n
— его старшим коэффициентом. Любое число является многочленом нулевой степени. Такие многочлены называются константами. Многочлены степени 1 называются линейными.
Б.М.Верников
Лекция 2: Многочлены

Теорема о делении многочленов с остатком (1)
Важную роль в теории многочленов играет следующее утверждение.
Теорема 1
Пусть f и g — многочлены и g 6= 0. Тогда существуют, причем единственные, многочлены q и r такие, что f = qg + r и deg r < deg g .
(1)
Доказательство.
Если deg g = 0, то g — ненулевое число. Но тогда f =

1
g
· g

f =

1
g
· f

g и равенство (1) будет выполнено, если положить q =
1
g
· f и r = 0.
Предположим теперь, что deg g > 0. Если deg f < deg g , то (1) выполнено при q = 0 и r = f . Пусть теперь deg f > deg g . Существование многочленов q и r в этом случае докажем индукцией по deg f . Положим deg f = n и deg g = m. Ясно, что n > m. Поэтому базой индукции будет случай, когда n = m.
Б.М.Верников
Лекция 2: Многочлены

Теорема о делении многочленов с остатком (2)
База индукции.
Пусть n = m. Тогда f = ax m
+ f
1
и g = bx m
+ g
1
, где deg f
1
, deg g
1
< m и a, b 6= 0. Положим q =
a b
. Ясно, что f − gq = (ax m
+ f
1
) −
a b
· (bx m
+ g
1
) = f
1

a b
· g
1
Поскольку deg(f − gq) = deg(f
1

a b
· g
1
) 6 max{deg f
1
, deg g
1
} < deg g ,
равенство (1) выполнено при q =
a b
и r = f − gq.
Шаг индукции.
Пусть теперь n > m и для всех многочленов h таких, что deg h < n, существуют такие многочлены q и r , что h = qg + r и deg r < deg g . Рассмотрим произвольный многочлен f степени n. Имеем f = ax n
+ f
1
и g = bx m
+ g
1
, где deg f
1
< n, deg g
1
< m и a, b 6= 0. Положим h
1
=
a b
· x n−m
. Тогда h
1
g = ax n
+ h
1
g
1
, откуда f − h
1
g = ax n
+ f
1
− ax n
− h
1
g
1
= f
1
− h
1
g
1
Заметим, что deg h
1
g
1
= deg h
1
+ deg g
1
< (n − m) + m = n, и потому deg(f − h
1
g ) = deg(f
1
− h
1
g
1
) 6 max{deg f
1
, deg h
1
g
1
} < n. Применяя к многочлену f − h
1
g предположение индукции, констатируем существование многочленов q
1
и r таких что f − h
1
g = q
1
g + r и deg r < deg g . Поскольку f = h
1
g + q
1
g + r = (h
1
+ q
1
)g + r , шаг индукции доказан.
Б.М.Верников
Лекция 2: Многочлены

Теорема о делении многочленов с остатком (3)
Осталось доказать единственность многочленов q и r . Предположим, что f = q
1
g + r
1
и f = q
2
g + r
2
для некоторых многочленов q
1
, q
2
, r
1
, r
2
таких что deg r
1
, deg r
2
< deg g . Из равенства q
1
g + r
1
= q
2
g + r
2
получаем, что
(q
1
− q
2
)g = r
2
− r
1
(2)
Если q
1
− q
2 6= 0, то deg(r
2
− r
1
) 6 max{deg r
1
, deg r
2
} < deg g 6 deg (q
1
− q
2
)g

вопреки равенству (2). Следовательно, q
1
− q
2
= 0, откуда q
1
= q
2
. С
учетом (2), отсюда вытекает, что и r
1
= r
2
. Теорема доказана.
Определения
В равенстве (1) многочлен q называется частным, а многочлен r —
остатком от деления f на g . Если r = 0, то говорят, что многочлен f делится на многочлен g ; в этом случае f = qg .
Б.М.Верников
Лекция 2: Многочлены

Деление многочленов столбиком (алгоритм)
Из доказательства теоремы 1 извлекается следующий алгоритм деления многочлена на многочлен, который обычно называется алгоритмом деления многочленов столбиком (происхождение этого названия будет объяснено на следующем слайде).
Алгоритм деления многочленов столбиком
Пусть f = a n
x n
+ a n−1
x n−1
+ · · · + a
1
x + a
0
и g = b m
x m
+ b m−1
x m−1
+ · · · + b
1
x + b
0
,
причем a n
, b m
6= 0 и n > m > 0. Положим f
1
= f и q
1
= 0. Шаг алгоритма состоит в замене многочлена f
1
на многочлен f
1

a n
b m
· x n−m g , а многочлена q
1
— на многочлен q
1
+
a n
b m
· x n−m
. Шаги повторяются до тех пор, пока выполнено неравенство deg f
1
> m. Так как степень f
1
на каждом шаге уменьшается на m, алгоритм закончит работу через конечное число шагов. При этом частное будет равно последнему значению многочлена q
1
, а остаток — последнему значению многочлена f
1
Б.М.Верников
Лекция 2: Многочлены

Деление многочленов столбиком (пример)
Рассмотрим конкретный пример деления многочленов. Вычисления записываются так же, как при делении многозначных чисел столбиком
(этим и объясняется название алгоритма).
x
3
− 2x
2
+ 5x + 1 x
2
− x + 2
x
3
− x
2
+ 2x x − 1
− x
2
+ 3x + 1
− x
2
+ x − 2 2x + 3
Таким образом, x
3
− 2x
2
+ 3x + 1 = (x − 1)(x
2
− x + 2) + (2x + 3), частное равно x − 1, а остаток — 2x + 3.
Б.М.Верников
Лекция 2: Многочлены

Корень многочлена
Определение
Число α называется корнем многочлена f , если f (α) = 0.
Из теоремы 1 легко вытекает
Следствие 1
Если α — корень многочлена f , то f делится на x − α.
Доказательство.
Поскольку deg(x − α) = 1, в силу теоремы 1 существуют такие многочлены q и r , что для всякого x ∈ C выполнено равенство f (x) = (x − α)q(x) + r (x)
(3)
и deg r < 1. Последнее неравенство означает, что deg r = 0, т. е. r —
константа. Подставим в (3) α вместо x. Получим 0 = 0 · q(x) + r , откуда r = 0. Следовательно, f (x) = (x − α)q(x).
Б.М.Верников
Лекция 2: Многочлены

Теорема Гаусса
Одним из мотивов расширения множества действительных чисел до множества комплексных чисел является то, что существуют многочлены с действительными коэффициентами, которые не имеют действительных корней. Таков, например, многочлен x
2
+ 1. Между тем, этот многочлен имеет два комплексных корня: i и −i (см. задачу 2 в лекции 1). Возникает вопрос: всякий ли многочлен с комплексными коэффициентами имеет комплексный корень? При этом, разумеется, следует исключить из рассмотрения многочлены степени 0 (т. е. константы). Ответ на поставленный вопрос дает следующее утверждение, которое называют теоремой Гаусса или основной теоремой высшей алгебры.
Теорема 2
Произвольный многочлен с комплексными коэффициентами, степень которого больше 0, имеет по крайней мере один комплексный корень.
Известно несколько доказательств этой теоремы, но все они достаточно сложные, и мы их рассматривать не будем. Отметим только некоторые следствия из теоремы.
Б.М.Верников
Лекция 2: Многочлены

Следствия из теоремы Гаусса (1)
Пусть f (x) — многочлен степени n > 0 с комплексными коэффициентами.
По теореме Гаусса он имеет некоторый корень t
1
. В силу следствия 1
f (x) = (x − t
1
)g (x ) для некоторого многочлена g (x ) степени n − 1. Если n − 1 > 0, то по теореме Гаусса многочлен g (x) имеет некоторый корень t
2
. Вновь применяя следствие 1, имеем f (x) = (x − t
1
)g (x ) = (x − t
1
)(x − t
2
)h(x )
для некоторого многочлена h(x) степени n − 2. Продолжая этот процесс,
мы в конечном счете представим f (x) в виде произведения n линейных множителей и многочлена степени 0, т. е. константы. Иными словами,
f (x) = c(x − t
1
)(x − t
2
) · · · (x − t n
).
(4)
Правую часть этого равенства можно переписать в виде
(cx − ct
1
)(x − t
2
) · · · (x − t n
). Таким образом, справедливо
Следствие 2
Если n > 0, то произвольный многочлен степени n с комплексными коэффициентами разложим в произведение n линейных множителей.
Б.М.Верников
Лекция 2: Многочлены

Следствия из теоремы Гаусса (2)
Для того, чтобы доказать еще одно следствие из теоремы Гаусса, нам понадобится следующая
Лемма 1
Если комплексное число x является корнем многочлена f (x) с действительными коэффициентами, то x — также корень этого многочлена.
Доказательство.
Пусть f = a n
x n
+ a n−1
x n−1
+ · · · + a
1
x + a
0
— многочлен с действительными коэффициентами, а x — его корень. Используя свойства комплексно сопряженных чисел (см. лекцию 1), имеем f (x) = a n
x n
+ a n−1
x n−1
+ · · · + a
1
x + a
0
=
= a n
· x n
+ a n−1
· x n−1
+ · · · + a
1
· x + a
0
=
=
a n
x n
+ a n−1
x n−1
+ · · · + a
1
x + a
0
=
= a n
x n
+ a n−1
x n−1
+ · · · + a
1
x + a
0
= f (x ) = 0 = 0,
что и требовалось доказать.
Б.М.Верников
Лекция 2: Многочлены

Следствия из теоремы Гаусса (3)
Вернемся к следствиям из теоремы Гаусса.
Следствие 3
Произвольный многочлен степени > 0 с действительными коэффициентами разложим в произведение многочленов с действительными коэффициентами, каждый из которых либо линеен,
либо является квадратным трехчленом с отрицательным дискриминантом.
Доказательство.
Пусть f (x) — многочлен степени n > 0 с действительными коэффициентами. В силу (4)
f (x) = c(x − t
1
)(x − t
2
) · · · (x − t n
),
где t
1
, t
2
, . . . , t n
— комплексные числа. Ясно, что c — коэффициент при x n
в многочлене f (x), и потому c ∈ R. Расположив, при необходимости,
числа t
1
, t
2
, . . . , t n
в другом порядке, мы можем считать, что t
1
, t
2
, . . . , t m
— действительные числа, а t m+1
, . . . , t n
— комплексные числа, не являющиеся действительными (для некоторого 0 6 m 6 n). Если m = n,
то все доказано. Предположим теперь, что m < n. Положим g (x) = (x − t m+1
) · · · (x − t n
).
Тогда f (x) = (cx − ct
1
)(x − t
2
) · · · (x − t m
)g (x ).
Б.М.Верников
Лекция 2: Многочлены

Следствия из теоремы Гаусса (4)
Осталось показать, что многочлен g (x) разложим в произведение квадратных трехчленов с действительными коэффициентами,
дискриминанты которых отрицательны. В силу леммы 1 числа x
m+1
, . . . , x n
распадаются на пары комплексно сопряженных друг к другу чисел. Поэтому достаточно проверить, что если z = a + bi — комплексное число, не являющееся действительным, то (x − z)(x − z) — квадратный трехчлен с действительными коэффициентами, дискриминант которого отрицателен. В самом деле,
(x − z)(x −
z) = (x − a − bi )(x − a + bi ) = (x − a)
2
− (bi )
2
=
= x
2
− 2ax + a
2
− b
2
i
2
= x
2
− 2ax + a
2
+ b
2
Очевидно, что получившийся квадратный трехчлен имеет действительные коэффициенты. Его дискриминант равен 4a
2
− 4(a
2
+ b
2
) = −4b
2
Учитывая, что b 6= 0 (поскольку число a + bi не является действительным), получаем, что этот дискриминант отрицателен.
Б.М.Верников
Лекция 2: Многочлены

Следствия из теоремы Гаусса (5)
Ясно, что если многочлен f имеет вид (4), то t
1
, t
2
, . . . , t n
— его корни.
Разумеется, некоторые из корней могут совпадать. При этом, если,
например, t
1
= · · · = t k
, то f делится на (x − t
1
)
k
Определение
Корень t многочлена f называется корнем кратности k, если f делится на
(x − t)
k
, но не делится на (x − t)
k+1
С учетом сказанного выше, получаем
Следствие 4
Многочлен степени n > 0 с комплексными коэффициентами имеет ровно n комплексных корней, если каждый корень считать столько раз, какова его кратность.
Б.М.Верников
Лекция 2: Многочлены

Корни многочленов малых степеней
Все известные доказательства теоремы Гаусса неконструктивны в том смысле, что они устанавливают лишь существование корня, но не указывают способа его нахождения. Естественно возникает вопрос о том,
как найти корень того или иного конкретного многочлена. Для многочленов первой степени ответ на этот вопрос очевиден: многочлен ax + b при a 6= 0 имеет единственный корень, равный −
b a
. Для многочленов второй степени ответ дается известной формулой корней квадратного уравнения. Действительно, проанализировав вывод этой формулы для случая действительных чисел, изучаемый в школьном курсе,
нетрудно понять, что он остается верным и для уравнений с комплексными коэффициентами. Более того, в комплексном случае формула несколько упрощается. Если ax
2
+ bx + c = 0 — уравнение с комплексными коэффициентами и a 6= 0, то его корни вычисляются по формуле x
1,2
=
−b +

b
2
− 4ac
2a
(5)
Знак минус перед корнем из дискриминанта можно не ставить, так как здесь подразумевается комплексный корень, имеющий два значения, а не арифметическое значение действительного корня. В математике известны формулы для нахождения комплексных корней многочленов третьей и четвертой степени, но они громоздки и неудобны для практического применения, и потому мы не будем их приводить.
Б.М.Верников
Лекция 2: Многочлены

Рациональные корни многочленов с целыми коэффициентами (1)
При n > 5 единой формулы для нахождения корней произвольного многочлена степени n не существует (этот факт доказан в конце XVIII —
начале XIX века итальянским математиком Руффини и норвежским математиком Абелем). На практике при нахождении корней многочленов степени > 2 используются приближенные методы, но их изложение выходит за рамки нашего курса. Если все коэффициенты многочлена являются целыми числами, то найти его рациональные корни (если они существуют) можно с помощью сдедующего утверждения.
Предложение 1
Пусть f (x) = a
0
x n
+ a
1
x n−1
+ · · · + a n−1
x + a n
— многочлен с целыми коэффициентами, а p
q
— рациональное число и несократимая дробь. Если p
q
— корень многочлена f (x), то p является делителем свободного члена многочлена f (x), а q — делителем его старшего коэффициента.
Доказательство.
По условию a
0
p q

n
+ a
1
p q

n−1
+ · · · + a n−1
·
p q
+ a n
= 0.
Умножив обе части этого равенства на q n
, получим a
0
p n
+ a
1
p n−1
q + · · · + a n−1
pq n−1
+ a n
q n
= 0.
(6)
Б.М.Верников
Лекция 2: Многочлены

Рациональные корни многочленов с целыми коэффициентами (2)
Отсюда a
n q
n
= −a
0
p n
− a
1
p n−1
q − · · · − a n−1
pq n−1
=
= (−a
0
p n−1
− a
1
p n−2
q − · · · − a n−1
q n−1
)p,
и потому p делит a n
q n
. Так как числа p и q взаимно просты, p делит a n
. С
другой стороны, из (6) вытекает, что a
0
p n
= −a
1
p n−1
q − · · · − a n−1
pq n−1
− a n
q n
=
= (−a
1
p n−1
− · · · − a n−1
pq n−2
− a n
q n−1
)q,
и потому q делит a
0
p n
. Вновь учитывая, что числа p и q взаимно просты,
получаем, что q делит a
0
Ясно, что существует лишь конечное число дробей вида p
q
, где p —
делитель a n
, а q — делитель a
0
. Вычислив значение многочлена f (x)
от каждой из таких дробей и отобрав те дроби, для которых это значение равно 0, мы найдем все рациональные корни этого многочлена.
Б.М.Верников
Лекция 2: Многочлены

Целые корни многочленов с целыми коэффициентами
Из предложения 1 непосредственно вытекает
Следствие 5
Пусть f (x) = x n
+ a
1
x n−1
+ · · · + a n−1
x + a n
— многочлен с целыми коэффициентами и старшим коэффициентом 1. Все рациональные корни многочлена f (x) являются целыми числами. Если при этом целое число p является корнем многочлена f (x), то p является делителем свободного члена многочлена f (x).
Б.М.Верников
Лекция 2: Многочлены

Корни многочленов с целыми коэффициентами — пример (1)
В некоторых случаях следствие 5 позволяет находить все комплексные корни многочленов высоких степеней. Продемонстрируем это на следующем примере.
Задача 1.
Найти все корни многочлена f (x) = x
5
+ 3x
4
− 9x
3
− 52x
2
− 84x − 48.
Решение.
В силу следствия 5 все целые корни этого многочлена (если они существуют) находятся среди делителей числа −48. Это число имеет 20
делителей: 1, −1, 2, −2, 3, −3, 4, −4, 6, −6, 8, −8, 12, −12, 16, −16, 24,
−24, 48, −48. Вычисляя последовательно значение f (x) от этих чисел,
получаем, что если x ∈ {1, −1, 2}, то f (x) 6= 0, а f (−2) = 0. Итак, мы нашли первый корень многочлена f (x): x
1
= −2. Разделив столбиком f (x )
на x + 2, получаем, что f (x) = (x + 2)(x
4
+ x
3
− 11x
2
− 30x − 24).
Б.М.Верников
Лекция 2: Многочлены

Корни многочленов с целыми коэффициентами — пример (2)
Осталось найти корни многочлена g (x) = x
4
+ x
3
− 11x
2
− 30x − 24. В
силу следствия 5 его целые корни (если они существуют) являются делителями числа −24. Это число имеет 18 делителей: 1, −1, 2, −2, 3,
−3, 4, −4, 6, −6, 8, −8, 12, −12, 16, −16, 24, −24. Ясно, что если x ∈ {1, −1, 2}, то g (x) 6= 0, так как в этом случае f (x) 6= 0. Поэтому вычислять значения многочлена g (x) имеет смысл начиная с x = −2. Как показывают вычисления, g (−2) = 0. Мы нашли второй корень многочлена f (x): x
2
= −2. Он совпадает с первым корнем. Иными словами, −2 —
корень кратности не ниже 2 (как мы сейчас увидем, кратность этого корня равна 2). Разделив столбиком g (x) на x + 2, мы получаем, что g (x) = (x + 2)(x
3
− x
2
− 9x − 12).
Теперь надо найти корни многочлена h(x) = x
3
− x
2
− 9x − 12. Как и ранее, применяя следствие 5, получаем, что если этот многочлен имеет целые корни, то они находятся среди чисел −2, 3, −3, 4, −4, 6, −6, 12,
−12. Как показывают вычисления, если x ∈ {−2, 3, −3}, то h(x) 6= 0, а h(4) = 0. Таким образом, x
3
= 4. Разделив столбиком h(x ) на x − 4, мы получаем, что h(x) = (x − 4)(x
2
+ 3x + 3).
Б.М.Верников
Лекция 2: Многочлены

Корни многочленов с целыми коэффициентами — пример (3)
Осталось решить уравнение x
2
+ 3x + 3 = 0. По формуле (5) имеем x
4,5
=
−3+

−3 2
(напомним, что в данном случае

−3 — комплексный корень, принимающий два значения). По формуле (4) из лекции 1
находим, что

−3 = ±

3i . Таким образом, мы нашли еще два корня многочлена f (x): x
4
= −
3 2
+

3 2
i и x
5
= −
3 2


3 2
i . В силу следствия 4
других корней у многочлена f (x) нет.
Ответ.
x
1,2
= −2, x
3
= 4, x
4,5
= −
3 2
±

3 2
i .
Б.М.Верников
Лекция 2: Многочлены


написать администратору сайта