Многочилен. Лекция 2 Многочлены
 Скачать 217.45 Kb.
|
|
Лекция 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: Многочлены |