75634-1 (612447), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Данное нами алгебраическое определение многочлена не содержит никакого упоминания о функциях. Тем не менее, с каждым многочленом над областью целостности K можно естественным образом связать функцию, которая определена на K и принимает значения в K.

Пусть - многочлен с коэффициентами из K. Для любого

положим

, (7)

где выражение в правой части понимается как результат операций в кольце K. Получаемый при этом элемент называется значением многочлена f(x) в точке x0. (Слово "точка" употребляется по аналогии со случаем

, когда x0 можно представлять как точку действительной оси.) Таким образом, каждому элементу x0 кольца K сопоставляется элемент f(x0) того же кольца и тем самым определяется функция на K со значениями в K.

Покажем, что сложение и умножение многочленов согласуются с обычными операциями, производимыми над функциями, когда складываются или, соответственно, перемножаются значения функций в каждой точке.

Рассмотрим два многочлена: ,

. Пусть h(x) = f(x) + g(x) - их сумма. Докажем, что h(x0)= =f(x0) + g(x0) для любого

. В соответствии с формулой (1)

=

, где

, что и требовалось доказать.

Пусть теперь - произведение многочленов f(x) и g(x). Докажем, что

для любого

. Перемножим равенства

,

. Пользуясь свойствами операций в кольце K (в частности, коммутативностью и ассоциативностью умножения), получим:

, где

. Сравнение полученного результата с формулой (2) позволяет сделать вывод, что

.

Таким образом, функция, определяемая суммой (соответственно произведением) двух многочленов, есть сумма (соответственно произведение) функций, определяемых этими многочленами.

Вообще говоря, соответствие между многочленами и определяемыми ими функциями не является взаимно однозначным. Однако, если кольцо K бесконечно, то различным многочленам из кольца K[x] всегда соответствуют различные функции.

4. Схема Горнера и теорема Безу.

В кольце многочленов деление в обычном смысле слова, как правило, невозможно. Например, в кольце многочлен x2 нельзя разделить на x + 1, т.е. не существует такого многочлена g(x), что x2 = g(x)(x + 1) (если бы такой многочлен существовал, то при x = -1 мы получили бы невозможное равенство

).

Если для полиномов f(x) и g(x) из K[x] существует такой полином , что f(x) = g(x)h(x), то говорят, что полином f(x) делится на полином g(x). Наша ближайшая задача заключается в выяснении вопроса о делимости

на линейный двучлен x - c при

.

Прежде всего установим, что всегда осуществимо так называемое деление с остатком: при

. Здесь полином h(x) называется неполным частным, а r - остатком.

Теорема 2. Пусть и

. Найдутся полином

и элемент

такие, что

. При этом

.

Доказательство. Естественно искать h(x) в форме . Сравнение коэффициентов многочлена в левой части равенства

= =

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

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

(8)

Равенство непосредственно следует из равенства

после подстановки в последнее вместо x элемент c.

Теорема доказана. Кроме того, получен очень удобный способ вычисления коэффициентов h(x) и остатка r. Этот способ носит название схемы Горнера. Вычисления удобно располагать в виде таблицы:

Элементы нижней строки вычисляются последовательно по формулам (8): b0 = a0, a каждый последующий элемент равен сумме элемента, находящегося над ним, и предыдущего элемента нижней строки, умноженного на x0.

Элемент c кольца K называется корнем полинома f(x), если .

Следствие (теорема Безу). Многочлен f(x) делится на в кольце K[x] тогда и только тогда, когда c - его корень.

Доказательство. Пусть f(x) делится на , т.е.

. Тогда

.

Пусть . Тогда в равенстве

будет

, т.е.

. Следствие полностью доказано.

Теорема 3. Число корней ненулевого многочлена не превосходит его степени.

Доказательство. Докажем это утверждение с помощью индукции по степени многочлена. Многочлен нулевой степени вообще не имеет корней, так что для него утверждение теоремы справедливо. Предположим теперь, что утверждение теоремы справедливо для всех многочленов степени , и докажем его для любого многочлена f(x) степени n. Предположим, рассуждая от противного, что x1, x2, ..., xm - корни многочлена f(x), причем

. По теореме Безу, f(x) делится на

, т.е.

, где g(x) - некоторый многочлен степени

. Элементы x2, ..., xm кольца K являются корнями многочлена g(x). В самом деле, при

имеем:

. Так как

, а кольцо K не имеет делителей нуля, то

. Таким образом, многочлен g(x) имеет не менее чем

корней, что противоречит предположению индукции, поскольку

. Теорема доказана.

Следствие. Многочлен степени не выше n однозначно определяется своими значениями в точках.

Иначе говоря, существует не более одного многочлена степени не выше n, принимающего в данных (различных) точках данные значения y1, y2, ..., yn+1.

Доказательство. Предположим, что f(x), g(x) - два многочлена степени не выше n, принимающие одинаковые значения в точках . Рассмотрим многочлен

. Степень этого многочлена также не выше, чем n. Так как

, то

при

, т.е.

- корни многочлена h(x). Согласно теореме 3 h(x) = 0, т.е. f(x) = g(x).

Теорема 4. Если кольцо K бесконечно, то равенство функций, определяемых двумя многочленами из кольца K[x], влечет за собой равенство самих многочленов.

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

для любого

. Обозначим через n наивысшую из степеней многочленов f(x), g(x). Так как кольцо K бесконечно, то в нем найдутся

различных элементов

. Согласно нашему предположению, многочлены f(x) и g(x) принимают одинаковые значения в каждой из точек

(как и вообще в любой точке). Следствие теоремы 3 позволяет сделать отсюда вывод, что

.

Для конечного кольца K утверждение теоремы 4 неверно. Однако при некоторых дополнительных предположениях и в этом случае оказывается возможным из равенства функций, определяемых двумя многочленами, сделать вывод о равенстве самих многочленов.

6. Вычисление наибольшего общего делителя.

Наибольший общий делитель двух многочленов f и g из кольца R[x] многочленов над полем R может быть найден при помощи алгоритма Евклида. Алгоритм Евклида нахождения наибольшего общего делителя состоит в следующем. Сначала делят с остатком многочлен f на многочлен g, затем многочлен g - на остаток от первого деления, затем остаток от первого деления - на остаток от второго деления и т.д., пока не получится нулевой остаток. Это дает следующую цепочку равенств:

(9)

причем , поэтому процесс деления конечен. Пусть

, т.е. f и g принадлежат одному и тому же главному идеалу

. Поэтому их разность

, т.е.

. Аналогично можно доказать, что

,

и т.д. Таким образом,

. Из последнего равенства (21) следует, что

, тогда

. Поэтому

. Следовательно, по теореме 14

, т.е.

. Таким образом, последний ненулевой остаток (т.е. rk) и есть наибольший общий делитель многочленов f и g.

Пример. В кольце многочленов с действительными коэффициентами найдем наибольший общий делитель многочленов

,

. Делим f на g:

Для удобства умножим полученный остаток на . При этом последующие остатки также умножатся на некоторые числа, отличные от нуля, что несущественно при нахождении наибольшего общего делителя, так как он находится с точностью до константы. Выполним второе деление:

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

0

Поскольку остаток равен нулю, то .

Наибольший общий делитель нескольких многочленов f1, f2, ..., fm может быть найден индуктивным способом на основании следующей формулы:

. (10)

Для того чтобы найти наибольший общий делитель многочленов , следует, согласно этой формуле, найти сначала

, затем

и т.д.;

и будет искомым наибольшим делителем.

Докажем формулу (10). Согласно определению наибольшего общего делителя, делители многочлена - это в точности общие делители многочленов

Характеристики

Список файлов курсовой работы