Многочлены. 1. Многочлены. Многочлены от одной переменной о пределен и е. Многочленом
 Скачать 309.13 Kb.
|
|
1. Многочлены. Многочлены от одной переменной О пределен и е. Многочленом f (x) от переменной x называется выражение+ где a 0 , a 1 , a 2 , . . . , a n−1 , a n – произвольные действительные числа, причем Числа a 0 , a 1 , a 2 , . . . , a n−1 , a n — это коэффициенты многочлена, его старший коэффициент, натуральное число n — степень многочлена. Степень многочлена f (x) будет обозначаться через deg f В многочлене степени n все коэффициенты, кроме старшего, могут обращаться в ноль такой многочлен иногда называют одночленом. Из определения видно, что многочлен имеет конечное число коэффициентов. Однако в дальнейшем удобно использовать следующее соглашение считать, что при i > n выполнено равенство a i = 0. Иными словами, мы договариваемся, что коэффициенты многочлена образуют бесконечную последовательность, в которой лишь конечное число элементов отлично от нуля. Определение многочлена требует, что в последовательности его коэффициентов хотя бы один был отличен от нуля. Мы откажемся от этого ограничения, и введем в рассмотрение нулевой многочлен, те. многочлену которого все коэффициенты равны нулю. Этот многочен будет обозначаться символом 0. Для обозначения степени нулевого многочлена вводится символ −∞. По определению будем считать, что если n — произвольное неотрицательное целое число, то < n и −∞ + n = n + −∞ = −∞. Никаких других операций с этим символом производить не будем. Из сказанного вытекает, что для многочленов) неравенство deg f < deg g выполнено в двух случаях) если f (x) = 0, g(x) 6= 0; 2) f (x), g(x) 6= 0 и их степени сравниваются соответствующим образом. Заметим, что степень многочлена может быть равна нулю. Многочлены нулевой степени представляются ненулевыми действительными числами. Многочлен (1) записан по возрастанию степеней. Часто многочлен будет удобней записывать по убыванию степеней, те. в виде+ a 1 x n−1 + a 2 x n−2 + . . . + a n−1 x + где a 0 6= 0. Следует обратить внимание на то, что по сравнению с (здесь нумерация коэффициентов изменена на обратную Множество всех многочленов от переменной x с действительными коэффициентами обозначается через R[x]. Договоримся, какие многочлены будут считаться равными. О пределен и е. Многочлены f (x) и g(x) называются равными, если они имеют одинаковые степени и, кроме того, их коэффициенты при одинаковых степенях переменной x равны между собой. На множестве R[x] можно определить операции сложения и умножения. Эти операции будут обозначаться также, как соответствующие операции на числовых множествах. Пусть даны произвольные многочлены (x) = a 0 + a 1 x + a 2 x 2 + . . . + a n−1 x n−1 + a n x n , g(x) = b 0 + b 1 x + b 2 x 2 + . . . + b m−1 x m−1 + Для каждого k > 0 определим число (c k ) при помощи равенства a k + Если p = max(m, n), то легко понять, что c k = 0, если k > Определение. Многочлен) = c 0 + c 1 x + c 2 x 2 + . . . + c k−1 x k−1 + где коэффициенты определены равенством (2), называется суммой многочленов f (x), Из определения вытекает следующее неравенство deg s 6 max(deg f, deg Это неравенство становится равенством, если либо deg f 6= deg g, либо deg f = deg g, нов противном случае неравенство становится строгим. О пределен и е. Многочлен (x) = −a 0 − a 1 x − a 2 x 2 − . . . − a n−1 x n−1 − a n x n назывется противоположным к многочлену (Используя свойства операции сложения на множестве R, нетрудно убедиться в том, что определенная нами операции сложения обладает свойствами ассоциативности и коммутативности, нулевой многочлен является нейтральным элементом относительно сложения и, кроме того (x) + (−f (x)) = 0. 4 Наличие этих свойству операции сложения означает, что множество относительно этой операции является абелевой группой. Чтобы ввести произведение двух многочленов, для каждого неотрицательного целого k определим число d k = X i+j=k a i b j . (3) Ясно, что d n+m = a n b m 6= 0 и d l = 0, если l > n + Определение. Многочлен) = d 0 + d 1 x + d 2 x 2 + . . . + d m+n−1 x m+n−1 + где коэффициенты определены равенством (3), называется произведением многочленов f (x), Какие из свойств операции умножения на R наследует операция умножения на R[x] ? Из определения сразу видно, что умножение на R[x] коммутативно. Можно убедиться (соответствующие проверки мы опускаем), что эта операция ассоциативна и дистрибутивна относительно сложения. Кроме того, многочлен 1 является нейтральным элементом относительно умножения. Таким образом, множество R[x] относительно введенных нами операций сложения и умножения является коммутативным кольцом с еди- ницей. Выше было отмечено, что старший коэффициент произведения двух ненулевых многочленов равен произведению их старших коэффициентов. Поэтому произведение двух ненулевых многочленов — всегда ненулевой многочлен. Отсюда немедленно вытекает, что кольцо R[x] не содержит делитетелей нуля. В заключение этого раздела сделаем следующее важное замечание. Наряду с полем R нам известны и другие поля например, поле C всех комплексных чисел, поле Q всех рациональных чисел или поле Z p , состоящее из вычетов по простому модулю p. Просматривая данные выше определения, мы видим, что многочлены и операции над ними можно определить для произвольного поля, а не только для поля R. Таким образом, можно рассматривать множество всех многочленов F [x] с коэффициентами из произвольного поля F . Нетрудно понять, что определения суммы и произведения многочленов в этом более общем случае не претерпевают никаких изменений более того, отмеченные выше свойства этих операций также сохранятся. Начиная с этого момента, мы будем рассматривать кольцо многочленов над произвольным полем F . 5 1.2. Теорема о делении с остатком Пусть f (x), g(x) — произвольные многочлены над полем F . Будем го- ворить,что g(x) делит f (x) (обозначение g(x) | f (x)), если f (x) = где u(x) — некоторый могочлен. Например, многочлен нулевой степени делит произвольный многочлен. Нетрудно понять, однако, что не всегда один многочлен делит другой. В связи с этим важное значение имеет следующее утверждение, называемое теоремой о делении с остатком. Читателю будет полезно сравнить эту теорему с теоремой 2.1 из Теорема 1.1. Пусть f (x), g(x) — произвольные многочлены над полем F , причем g(x) — ненулевой многочлен. Тогда существуют однозначно определенные многочлены u(x) и r(x) такие, что (x) = u(x)g(x) + r(x), deg r < deg Многочлены u(x) и r(x) называют соответственно частными остатком, полученными при делении f (x) на g(x). Заметим, что остаток может оказаться нулевым многочленом. Д ока за тел ь ст во теоремы 1.1. Степени многочленов f (x), g(x) обозначим через n и m соответственно. Докажем сначала, что требуемые многочлены u(x) и r(x) сущечтвуют. Удобно многочлен g(x) зафиксировать, а многочлену f (x) разрешить изменяться произвольным образом. Если n < m, то (x) = 0 · g(x) + f откуда видно, что u(x) = 0, r(x) = f Пусть n > m. Считая, что многочлены f (x) и g(x) записаны по убыванию степеней, обозначим через a 0 , их старшие коэффициенты. Применим для доказательства существования многочленов u(x) и) метод математической индукции. При n = m положим) = f (x) Поскольку степени многочленов f (x) и a 0 b −1 0 g(x) равны между собой, а их старшие коэффициенты совпадают, получаем, что deg r < deg Если из равенства (4) выразить многочлен f (x), то станет понятно, что частное равно a 0 b −1 0 , а остаток равен Пусть n > m. Предположим, что для любого многочлена степени, меньшей n, частное и остаток отделения на g(x) существуют. Рассмотрим многочлен) = f (x) − a 0 b 0 x n−m g(x). (5) 6 Нетрудно понять, что deg h < deg f = n; поэтому к многочлену h(x) применимо предположение индукции. Следовательно, найдутся такие многочлены) и r(x), что) = v(x)g(x) + r(x), deg r < deg Из равенств (5) и (6) легко получить, что (x) = (a 0 b −1 0 x n−m + v(x))g(x) + Таким образом, существование частного и остатка отделения) на) доказано. Проверим единственность частного и остатка. Предположим, что существуют многочлены u(x), v(x), r(x), s(x) такие, что (x) = u(x)g(x) + r(x), deg r < deg g, (7) f (x) = v(x)g(x) + s(x), deg s < deg Вычитая из равенства (7) равенство (8), после очевидных преобразований приходим к равенству) − s(x) = (v(x) − Допустим, что многочлены r(x) и s(x) различны. Тогда многочлен r(x)− s(x) ненулевой, откуда следует, что v(x) − u(x) также ненулевой многочлен. Так как при перемножении степени многочленов складываются, степень (v(x) − u(x))g(x) не меньше, чем степень g(x). С другой стороны, степени многочленов r(x) и s(x) строго меньше степени g(x); ясно, что такому же неравенству удовлетворяет и степень разности Отсюда следует, что равенство (9) невозможно. Таким образом, предположение о том, что r(x) и s(x) — различные многочлены, привело к противоречию. Тем самым доказано, r(x) = s(x). Поскольку кольцо многочленов не содержит делителей нуля и g(x) 6= 0, из равенства (следует, что многочлен v(x) − u(x) нулевой, те Рассмотрим конкретный пример. Предположим, что требуется многочлен (делимое) поделить поделить с остатком на многочлен g(x) = x 2 + x − 1 (делитель. Имеем+ x 2 + 3x − 5 = 2x(x 2 + x − 1) + (−x 2 + 5x − 5), −x 2 + 5x − 5 = −1(x 2 + x − 1) + (6x − Отсюда видно, что+ x 2 + 3x − 5 = (2x − 1)(x 2 + x − 1) + (6x − 6). 7 Следовательно, частное и остаток равны 2x − 1 и 6x − 6 соответственно. Эти вычисления удобно записывать следующим образом (вспомните деление уголком для натуральных чисел+ x 2 + 3x − 5 x 2 + x − 1 2x 3 + 2x 2 − 2x 2x − 1 − x 2 + 5x − 5 − x 2 − x + 1 6x − 6 1.3. Схема Горнера В этом разделе мы рассмотрим простой алгоритм, при помощи которого произвольный многочлен f (x) можно разделить с остатком на линейный двучлен x − Применяя теорему о делении с остатком, имеем (x) = g(x)(x − c) + где g(x) — частное, а r — остаток отделения. Ясно, что deg g = deg f − и r — некоторое число. Пусть f (x) = a 0 x n + a 1 x n−1 + . . . + a n−1 x + a n , g(x) = b 0 x n−1 + b 1 x n−2 + . . . + b n−2 x + Если многчлен g(x) подставить в правую часть равенства (10), раскрыть скобки и привести подобные члены, то получится равенство (x) = b 0 x n + (b 1 − cb 0 )x n−1 + . . . + (b n−1 − cb n−2 )x + (r − Сравнивая коэффициенты многочленов, стоящих в правой и левой частях равенства (11), получаем b 0 a 1 = b 1 − cb 0 . . . . . . . . . . a n−1 = b n−1 − cb n−2 a n = r − Отсюда при помощи очевидных преобразований имеем a 0 b 1 = a 1 + cb 0 . . . . . . . . . . b n−1 = a n−1 + cb n−2 r = a n + cb n−1 . (13) 8 Равенства (13) позволяют последовательно вычислить коэффициенты частного и остаток отделения. Алгоритм, основанный на применении равенств (13), часто называют схемой Горнера. Применим схему Горнера для деления остатком многочлена f (x) = x 4 +3x 2 −2x на двучлен x+2. Обозначим через g(x) = и r соответственно частное и остаток отделения. В силу равенств (имеем a 0 = 1 b 1 = a 1 + cb 0 = −2 b 2 = a 2 + cb 1 = 7 b 3 = a 3 + cb 2 = −16 r = a 4 + cb 3 = Эти вычисления более удобно организовать в виде следующей таблицы Способ заполнения этой таблицы состоит в следующем. Впервой строке записаны все коэффициенты многочлена f (x), вначале второй строки для удобства записывается число c, равное в этом случае Затем последовательно, начиная со второй клетки, заполняется вторая строка (см. равенства (14). 1.4. Отношение делимости В разд. 1.2 было определено отношение делимости на кольце F многочлен g(x) делит многочлен f (x) (g(x) | f (x)), если f (x) = для некоторого многочлена Свойства отношения делимости в кольце многочленов во многом аналогичны свойствам отношения делимости в кольце целых чисел (см. разд. 2.5 из [3]) . Перечислим эти свойства) f (x) | f (x); (D2) если f (x) | g(x), g(x) | f (x) и f (x), g(x) 6= 0, то f (x) = s · g(x) для некоторого отличного от нуля числа s; (D3) если f (x) | g(x) и s — отличное от нуля число, то s · f (x) | g(x); (D4) если f (x) | g(x) и g(x) | h(x), то f (x) | h(x); (D5) если f (x) | g(x) и f (x) | h(x), то f (x) | u(x)g(x) + v(x)h(x) каковы бы ни были многочлены u(x), v(x); (D6) если f (x) | g i (x), 1 6 i 6 k, то f (x) | P k i=1 u i (x)g i (x) каковы бы ни были многочлены u i (x), 1 6 i 6 k; (D7) если f (x) | g(x) и g(x) 6= 0, то deg f 6 deg g. 9 Отметим, что произвольный многочлен f (x) делит нулевой многочлен и если 0 | g(x), то g(x) = Введем понятие наибольшего общего делителя двух многочленов. О пределен и е. Многочлен d(x) называется наибольшим общим делителем многочленов f (x) и g(x), если выполнены свойства) d(x) | f (x) и d(x) | g(x); (b) если c(x) | f (x) и c(x) | g(x), то c(x) | Проверим, что любые два ненулевых многочлена |