МИНИСТЕРСТВООБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕАГЕНТСТВО ПО ОБРАЗОВАНИЮ
НАБЕРЕЖНОЧЕЛНИНСКИЙГОСУДАРСТВЕННЫЙ
ПЕДАГОГИЧЕСКИЙИНСТИТУТ
МАТЕМАТИЧЕСКИЙФАКУЛЬТЕТ
КАФЕДРАМАТЕМАТИКИ И МЕТОДИКИ ЕЕ ПРЕПОДАВАНИЯ
АЛГОРИТМЫС МГНОГОЧЛЕНАМИ
/дипломнаяработа/
НабережныеЧелны
2006 год
Содержание
Введение
1. Многочлены
2. Деление многочленов
2.1. Делимость многочленов. Свойства делимости
2.2. Деление многочленов с остатком
2.3. Наибольший общий делитель многочленов
2.4. Алгоритм Евклида
3. Кратные корни
4. Производная от многочлена
5. Кратные множители
5.1. Выделение кратных множителей
Заключение
Список использованной литературы
/>Введение
Тема моей дипломнойработы: «Алгоритмы с многочленами».
Целью данной работыявляется изучение многочленов, алгоритмов с ними, рассмотрение возможностейсоставления различных программ. Для достижения поставленной цели необходиморассмотреть следующие вопросы:
– делимость многочленов;
– деление многочленов состатком;
– наибольший общийделитель, алгоритм Евклида;
– кратные корни;
– кратные множители,выделение кратных множителей;
– производные отмногочленов.
Для выполнения дипломнойработы я поставила следующие задачи:
1. изучитьлитературу о многочленах;
2. применить теориювысшей алгебры в решении задач элементарной математики;
3. составитьпрограммы для нахождения частного и остатка при делении многочленов, наибольшегообщего делителя двух многочленов, производной многочлена; разложениямногочленов на кратные множители.
/>1.Многочлены
Общий вид уравнения n-ной степени (где n некоторое положительное число) есть
/>. (1.1)
Коэффициенты /> этого уравнения мы будемсчитать произвольными комплексными числами, причем старший коэффициент /> должен быть отличным отнуля.
Если написано уравнение(1.1), то всегда предполагается, что требуется его решить, найти такие числовыезначения для неизвестного x,которые удовлетворяют этому уравнению, то есть после подстановки вместонеизвестного и выполнения всех указанных операций обращают левую частьуравнения (1.1) в нуль.
Целесообразно заменитьзадачу решения уравнения (1.1) более общей задачей изучения левой части этогоуравнения
/>, (1.2)
называемой многочленомn-ной степени от неизвестного х. Многочленом называется лишьвыражение вида (1.2), то есть лишь сумма целых неотрицательных степенейнеизвестного x, взятых снекоторыми числовыми коэффициентами. В частности, мы не будем считатьмногочленами такие выражения, которые содержат неизвестное x с отрицательными или дробнымипоказателями. Для сокращенной записи многочленов употребляются символы f(x), g(x) и так далее.
2. Деление многочленов
Теория многочленов в определенном отношении похожа на теорию целых чисел,хотя внешне эти две теории не имеют ничего общего. Внутренняя же близость,схожесть этих теорий объясняется тем, что для многочленов, так же как и дляцелых чисел, можно определить деление и, что еще более важно, деление состатком./> 2.1. Делимость многочленов. Свойства делимости
Многочлен /> делитсяна многочлен />, если существует такоймногочлен />, что выполняется равенство
/> (2.1)
Например, из равенства /> следует, что />делится на многочлен />и на многочлен />.
Многочлен /> в равенстве (2.1)определяется однозначно. Если бы существовал многочлен />, удовлетворяющий равенству(2.1), то мы получили бы, что
/> (2.2)
откуда />
Но многочлен /> по условию ненулевой, и всилу утверждения />или /> нулевом является многочлен/>, т.е. многочлен />совпадает с />.
Многочлен /> в равенстве (2.1) называетсячастным от деления /> на />, а /> – делителем.
Укажем некоторые основныесвойства делимости многочленов.
1. Если /> делится/>, а /> делится на />, то /> будет делиться на />.
В самом деле, по условию /> и />, а поэтому />.
2. Если /> и/> делятся на />, то их сумма и разностьтакже делятся на />.
Из равенств/> и /> вытекает />.
3.Если /> делится на />, то произведение /> на любой многочлен /> также будет делиться на />.
Если />, то />.
Из 2. и 3. вытекаетследующее свойство:
4. Если каждый из многочленов /> делится на />, то на /> будет делиться и многочлен/>, где /> - произвольные многочлены.
5. Всякий многочлен /> делится на любой многочленнулевой степени.
Если />, а с — произвольноечисло, не равное нулю, то есть произвольный многочлен нулевой степени, то />.
6. Если /> делитсяна />, то /> делится и на с/>, где с –произвольное число отличное от нуля.
Из равенства /> следует равенство />.
7. Многочлены />, />, и только они будутделителями многочлена />, имеющими такуюже степень, что и />.
Действительно, />. То есть /> делится на />.
Если /> делится на />, причем степени /> и /> совпадают, то степеньчастного от деления /> на /> должна быть равной нулю,то есть />, />, откуда />.
Отсюда вытекает следующеесвойство:
8. Тогда и только тогда многочлены />, /> одновременно делятся другна друга, если />, />.
Из 1. и 8. вытекаетсвойство:
9. Всякий делитель одного из двухмногочленов />, />, где />, будет делителем и длядругого многочлена.
Свойства делимости многочленовмогут быть применены для изучения делимости в множестве целых чисел. Выясним,например, для каких целых чисел nчисло/>являетсяпростым.
Натуральное число,отличное от 1, называется простым, если оно делится только на 1 и на само себя;целое отрицательное число kназывается простым, если число –kпростое.
Для ответа напоставленный вопрос заметим, что справедливо равенство
/> (2.3)
и поэтому число />делится на /> и на /> Следовательно, оно можетбыть простым только в случае, когда один из этих делителей равен 1 или –1, т.е.выполняется хотя бы одно из равенств /> /> />
Остается проверитьследующие значения n:3, 1, 0, -3, -1 и –2. При этих значениях nрассматриваемое число равно соответственно 19, -5, 3,4, так что искомое множество чисел есть />
Может возникнуть вопрос:откуда взялось равенство (2.3)? Как мы догадались, что многочлен /> таким образомраскладывается на множители? Для нахождения разложений такого типанеобязательно прибегать к искусственным группировкам, это можно сделать спомощью теории, которая будет изложена ниже.
Из этого примера видно,что уже для решения задач, связанных с делимостью целых чисел, полезно уметьвыяснять, делится ли данный многочлен на некоторый другой многочлен(раскладывается ли на множители).Ответ на такой и многие другие вопросы можнонайти с помощью деления многочлена с остатком./> 2.2. Деление многочленов с остатком
Для многочленов, как идля целых чисел, существует алгоритм деления с остатком.
Теорема о делении состатком. Для любых двух многочленов f(x) и g(x) можно найти такие многочлены q(x) и r(x, что
f(x)=g(x)q(x)+r(x),
причем степень r(x) меньше степени g(x) или же r(x)=0. Многочлены q(x) и r(x), удовлетворяющие этому условию,определяются однозначно.
Если разности f(x)-r(x) и /> обе делятся на g(x), то их разность/> такжеделится наg(x). Если бы многочлен s(x) был ненулевым, то он имел бы степень меньшую, чем g(x), и не мог бы тогда делится наg(x). Следовательно, s(x)=0, так что />.
В практическойдеятельности для нахождения частного и остатка применяют способ вычисления,называемый «деление углом». Покажем его на примере.
Пример. Найти частный и остаток от деления /> на />.
1. /> и />
/> |/>
/> />
/>
/>
/>
/>/>
/>
Частным от деления /> на /> является многочлен />, остатком – />.
2. /> и />
/> │/>/>
/> />
/>
/>
/>
Частным от деления /> на /> является многочлен />, остатком – />.
Это правило в общем видеможно сформулировать так:
1) разделить старший членмногочлена f(x) на старший член g(x) и записать результат «под длинной стороной угла»;
2)умножить g(x) на результат действия 1) и записать произведение подмногочленомf(x);
3) вычесть из f(x) записанный под ним многочлен;
4) проверить имеет лирезультат действия 3) степень меньшую, чем степень g(x); если да (или результат нулевой), то он являетсяостатком, а под длинной стороной угла записано частное, если нет, то применитьк этому результату действие 1), рассматривая его как многочленf(x).
Я составила программу длянахождения частного и остатка.
unit Unit1;
interface
uses
Windows,Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs,StdCtrls, Grids;
type
TForm1 =class(TForm)
SGd1:TStringGrid;
Edit1:TEdit;
Edit2:TEdit;
Edit3:TEdit;
Edit4:TEdit;
Edit5:TEdit;
Edit6:TEdit;
Button1:TButton;
Label1:TLabel;
Label2:TLabel;
Label3:TLabel;
Label4:TLabel;
Label5:TLabel;
Label6:TLabel;
Label7:TLabel;
Label8:TLabel;
Label9:TLabel;
procedureButton1Click(Sender: TObject);
private
{ Privatedeclarations }
public
{ Publicdeclarations }
end;
var
Form1:TForm1;
i,n,m,step,j,f:integer;
d,l,s:string;
a,a2,b,b2,k:array[0..100] of integer;
implementation
{$R *.dfm}
procedureTForm1.Button1Click(Sender: TObject);
begin
n:=StrToInt(Edit1.Text);
m:=StrToInt(Edit2.Text);
for i:=n+1downto 1 do begin
a[i]:=StrToInt(SGd1.Cells[n-(i-1),0]);
end;
for i:=m+1downto 1 do begin
b[i]:=StrToInt(SGd1.Cells[m-(i-1),1]);
end;
s:='f1(x)=';
for i:=n+1downto 1 do begin
ifa[i]0 then begin if(a[i-1]
str(a[i],l);
str(i-1,d);
s:=s+l+'x^'+d;
end
else begin
str(a[i],l);
str(i-1,d);
s:=s+l+'x^'+d+'+';
end;
end;
end;
Edit3.Text:=s;
s:='f2(x)=';
for i:=m+1downto 1 do begin
ifb[i]0 then begin if(b[i-1]
str(b[i],l);
str(i-1,d);
s:=s+l+'x^'+d;
end
else begin
str(b[i],l);
str(i-1,d);
s:=s+l+'x^'+d+'+';
end;
end;
end;
Edit4.Text:=s;
for j:=N+1downto 1 do begin
a2[j]:=a[j];
b2[j]:=0;
end;
step:=n-m;
f:=n+2;
for i:=step+1downto 1do begin
f:=f-1;
k[i]:=a2[f];
for j:=m+1downto 1do begin
b2[j]:=k[i]*b[j];
end;
for j:=fdownto 1 do begin
a2[j]:=a2[j]*b[m+1];
end;
for j:=fdownto 1 do begin
a2[j]:=a2[j]-b2[j+1-i];
b2[j]:=0;
end;
end;
s:='h(x)=';
for i:=fdownto 1 do begin
ifk[i]0 then begin if(k[i-1]
str(k[i],l);
str(i-1,d);
s:=s+l+'x^'+d;
end
else begin
str(k[i],l);
str(i-1,d);
s:=s+l+'x^'+d+'+';
end;
end;
end;
Edit5.Text:=s;
s:='r(x)=';
for i:=ndownto 0 do begin
ifa2[i]0 then begin if(a2[i-1]
str(a2[i],l);
str(i-1,d);
s:=s+l+'x^'+d;
end
else begin
str(a2[i],l);
str(i-1,d);
s:=s+l+'x^'+d+'+';
end;
end;
end;
Edit6.Text:=s;
end;
end.
/>/> 2.3. Наибольший общий делитель многочленов
Пусть даны произвольныемногочлены /> и />. Многочлен будетназываться общим делителем для /> и/>, если он служит делителемдля каждого из этих многочленов. Свойство 5. показывает, что к числу общихделителей многочленов /> и /> принадлежат все многочленынулевой степени. Если других общих делителей эти два многочлена не имеют, тоони называются взаимно простыми.
В общем же случаемногочлены /> и /> могут обладать делителями,зависящими от />, и введемпонятие о наибольшем общем делителе этих многочленов.
Наибольшим общимделителем отличныхот нуля многочленов /> и /> называется такой многочлен/>, который является их общимделителем и, вместе с тем, сам делится на любой другой общий делитель этихмногочленов. Обозначается наибольший общий делитель многочленов /> и /> символом />.
Это определение оставляетоткрытым вопрос, существует ли наибольший общий делитель для любых многочленов /> и />. Ответ на этот вопросположительный. Существует метод для практического разыскания наибольшего общегоделителя данных многочленов, называемый алгоритмом последовательного деленияили алгоритмом Евклида. />/> 2.4. Алгоритм Евклида
Алгоритм Евклида – метод для нахождениянаибольшего общего делителя двух целых чисел, а также двух многочленов отодного переменного. Он первоначально был изложен в «Началах» Евклида вгеометрической форме как способ нахождения общей меры двух отрезков. АлгоритмЕвклида для нахождения наибольшего общего делителя, как в кольце целых чисел,так и в кольце многочленов от одного переменного является частным случаемнекого общего алгоритма в евклидовых кольцах.
Алгоритм Евклида длянахождения наибольшего общего делителя двух многочленов /> и /> состоит в последовательномделении с остатком /> на />, затем /> на первый остаток/>, затем /> на второй остаток /> и так далее. Таккак степени остатков все время понижаются, то в этой цепочке последовательныхделений мы дойдем до такого места, на котором деление совершится нацело ипроцесс остановится. Последний отличный от нуля остаток />, на который нацело делитсяпредыдущий остаток />, и являетсянаибольшим общим делителем многочленов /> и/>.
Для доказательствазапишем изложенное в виде следующей цепочки равенств:
/>
(2.4)
/>
Последнее равенствопоказывает, что /> служит делителемдля />. Отсюда следует, что обаслагаемых правой части предпоследнего равенства делятся на />, а поэтому /> будет делителем и для />. Далее, таким же путем,поднимаясь вверх, мы получим, что /> являетсяделителем и для />, …, />, />. Отсюда ввиду второгоравенства, будет следовать, что /> служитделителем для />, а поэтому, наосновании первого равенства, — и для />.
Возьмем теперьпроизвольный общий делитель /> многочленов/> и />. Так как левая часть ипервое слагаемое правой части первого из равенств делятся на />, то /> также будет делится на />. Переходя ко второму иследующему равенствам, таким же способом получим, что на /> делятся многочлены />, />, … Наконец, если уже будетдоказано, что /> и /> делятся на />, то из предпоследнегоравенства получим, что /> делится на />. Таким образом, /> на самом деле будетнаибольшим общим делителем для /> и />.
Мы доказали, что любыедва многочлена обладают наибольшим общим делителем, и получили способ еговычисления. Этот способ показывает, что если многочлены /> и /> имеют оба рациональныеили действительные коэффициенты, то и коэффициенты их наибольшего общегоделителя также будут рациональными или, соответственно, действительными,хотя у этих многочленов могут существовать и такие делители, не всекоэффициенты которых рациональны (действительны).
Если /> есть наибольший общийделитель многочленов /> и />, то, как показываютсвойства 8. и 9., в качестве наибольшего общего делителя этих многочленов можно былобы выбрать такжемногочлен />, где /> - произвольное число,отличное от нуля. Иными словами, их наибольший общий делитель двух многочленовопределен лишь с точностью до множителя нулевой степени. Ввиду этого можноусловиться, что старший коэффициент наибольшего общего делителя двухмногочленов будет всегда считаться равным единице. Используя это условие можносказать, что два многочлена тогда и только тогда взаимно просты, если ихнаибольший общий делитель равен единице. В самом деле, в качественаибольшего общего делителя двух взаимно простых многочленов можно взять любоечисло, отличное от нуля, но, умножая его на обратный элемент, получим единицу.
Применяя алгоритм Евклидак многочленам с целыми коэффициентами, можем, чтобы избежать дробныхкоэффициентов, умножить делимое или сократить делитель на любое не равное нулючисло, причем не только начиная какое-либо из последовательных делений, но и впроцессе самого этого деления. Это будет приводить к искажению частного, ноинтересующие нас остатки будут приобретать лишь некоторый множитель нулевойстепени, что при разыскании наибольшего общего делителя допускается.
Пример. Найти наибольший общий делительмногочленов /> и />.
1. /> и />
Совершим требуемыеделения с остатком:
/> | />
/> />
/>
/>
/>
/>
/>
/>
/> | />
/> />
/>
/>
/>
/>
/>
/>
/> | />
/> />
/>
/>
/>
Построениепоследовательности Евклида закончено. Ее последний член /> есть наибольший общий делительисходных многочленов.
2. /> и/>
Совершим требуемыеделения с остатком:
/> │/>
/> ||/>
/>
/>
/>
/> │/>
/> />
/>
/>
/>
/>
/>
/>
/> │/>
/> />
/>
/>
/>
Построениепоследовательности Евклида закончено. Ее последний член /> есть наибольший общийделитель исходных многочленов.
Я составила программу длянахождения наибольшего общего делителя двух многочленов:
unit Unit1;
interface
uses
Windows,Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs,StdCtrls, Grids;
type
TForm1 =class(TForm)
Label1:TLabel;
Label2:TLabel;
Edit1:TEdit;
Edit2:TEdit;
SGd1:TStringGrid;
Label3:TLabel;
Button1:TButton;
Label4:TLabel;
Edit4:TEdit;
Label5:TLabel;
Label6:TLabel;
procedureButton1Click(Sender: TObject);
private
{ Privatedeclarations }
public
{ Publicdeclarations }
end;
var
Form1:TForm1;
st1,st2:integer;
kof1,kof2,k1,k2:array[0..10] of integer;
implementation
{$R *.dfm}
procedureTForm1.Button1Click(Sender: TObject);
vari,j,k_1,st3,l:integer;
sokr:boolean;
k2_2,k1_1:array[0..10] of integer;
begin
st1:=StrToInt(Edit1.Text);
st2:=StrToInt(Edit2.Text);
for i:=0 tost1 do begin
kof1[i]:=StrToInt(SGd1.Cells[i,0]);
k1[i]:=StrToInt(SGd1.Cells[i,0]);
end;
for i:=0 tost2 do begin
kof2[i]:=StrToInt(SGd1.Cells[i,1]);
k2[i]:=StrToInt(SGd1.Cells[i,1]);
end;
whilekof2[0]0 do begin
repeat
Edit4.Text:='';
k_1:=k1[0];
if k1[0]kof2[0]then begin
if(k1[0] mod kof2[0])=0 then begin
forj:=0 to st2 do
k2[j]:=(k1[0] div kof2[0])*kof2[j];
end
elsebegin
ifk2[0]1 then
for j:=0 to st1 do
k1[j]:=kof2[0]*k1[j];
ifk_11 then begin
for j:=0 to st2 do
k2[j]:=k_1*kof2[j];
end;
end;
end;
for i:=1to st1 do begin
k1[i-1]:=k1[i]-k2[i];
end;
st1:=st1-1;
untilst1
if k1[0]0then begin //Сокращение
sokr:=true;
for i:=1to st1 do
ifk1[i]0 then begin
if(k1[i] mod k1[0])0 then sokr:=false;
end;
k_1:=k1[0];
ifsokr=true then
for i:=0to st1 do
k1[i]:=k1[i] div k_1;
end;
for i:=0 tost2 do //Замена многочленов
k2_2[i]:=kof2[i];
for i:=0 tost1 do
k1_1[i]:=k1[i];
for i:=0 to10 do begin
kof1[i]:=0;
k1[i]:=0;
kof2[i]:=0;
k2[i]:=0;
end;
for i:=0 tost2 do begin
k1[i]:=k2_2[i];
ifk1[i]0 then
Edit4.Text:=Edit4.Text+IntToStr(k1[i])+'x^'+IntToStr(st2-i);
if(k2_2[i+1]>0)and(i
end;
for i:=0 tost1 do begin
k2[i]:=k1_1[i];
kof2[i]:=k1_1[i];
end;
st3:=st1;
st1:=st2;
st2:=st3;
end;
end;
end.
/>
Используем алгоритмЕвклида для доказательства следующей теоремы:
Теорема. Если /> естьнаибольший общий делитель многочленов /> и/>, то можно найти такиемногочлены /> и />, что
/>. (2.5)
Можно считать при этом,если степени многочленов /> и /> больше нуля, что степень /> меньше степени />, а степень /> меньше степени />.
Доказательство основано на равенствах (2.4). Еслиучтем, что />, и положим />, />, то предпоследнее изравенств (2.4) даст:
/>
/>.
Подставляя сюда выражение/> через /> и /> из предшествующегоравенства (2.4), получим:
/>,
где />, />. Продолжая подниматьсявверх по равенствам (2.4), придем к доказываемому равенству (2.5).
Для доказательствавторого утверждения теоремы предположим, что многочлены /> и />, удовлетворяющие равенству(2.5), уже найдены, но, например, степень /> большеили равна степени />. Делим /> на />:
/>,
где степень /> меньше степени />, и подставляем этовыражение в (2). Получим равенство:
/>
/>.
Степень множителя,стоящего при />, уже меньше степени />. Степень многочлена,стоящего в квадратных скобках, будет в свою очередь меньше степени />, так как в противномслучае степень второго слагаемого левой части была бы не меньше степени />, а так как степень первогослагаемого меньше степени этого произведения, то вся левая часть имела быстепень, большую или равную степени />, тогдакак многочлен /> заведомо имеет,при наших предположениях, меньшую степень.
Теорема доказана.
Одновременно получаем,что если многочлены /> и /> имеют рациональные илидействительные коэффициенты, то и многочлены /> и/>, удовлетворяющие равенству(2.5), можно подобрать так, что их коэффициенты будут рациональными или,соответственно действительными.
Применяя доказаннуютеорему к взаимно простым многочленам, получаем такой результат:
Многочлены /> и /> тогдаи только тогда взаимно просты, если можно найти многочлены /> и />, удовлетворяющие равенству
/>. (2.6)
Опираясь на этотрезультат, можно доказать несколько простых, но важных теорем о взаимно простыхмногочленах:
Теорема 1. Если многочлен /> взаимно прост с каждым измногочленов /> и />, то он взаимно прост и сих произведением.
Доказательство. В самом деле, существуют, по (2.6),такие многочлены /> и />, что />.
Умножая это равенство на />, получаем:
/>,
откуда следует, чтовсякий общий делитель /> и /> был бы делителем и для />; однако по условию />.
Теорема 2. Если произведениемногочленов /> и /> делится на />, но /> и /> взаимно просты, то /> делится на />.
Доказательство. Умножая равенство /> на />, получим: />.
Оба слагаемых левой частиэтого равенства делятся на />; нанего делится, следовательно, и />.
Теорема 3. Если многочлен /> делится на каждый измногочленов /> и />, которые между собойвзаимно просты, то /> делится и на ихпроизведение.
Доказательство. Действительно, />, так что произведение,стоящее справа, делится на />.Поэтому, по теореме 2, /> делится на />, />, откуда />.
Определение наибольшегообщего делителя может быть распространен на случай любой конечной системымногочленов: наибольшим общим делителем многочленов /> называется такой общийделитель этих многочленов, который делится на любой другой общий делитель этихмногочленов. Существование наибольшего общего делителя для любой конечнойсистемы многочленов вытекает из следующей теоремы, дающей также способ еговычисления.
Теорема. Наибольший общий делительмногочленов /> равен наибольшему общемуделителю многочлена /> и наибольшегообщего делителя многочленов />.
Доказательство. В самом деле, при /> теорема очевидна. Примемпоэтому, что для случая /> онасправедлива, то есть, в частности, уже доказано существование наибольшегообщего делителя /> многочленов />. Обозначим через /> наибольший общий делительмногочленов /> и />. Он будет общим делителемдля всех заданных многочленов. С другой стороны, всякий другой общий делительэтих многочленов будет делителем также и для />,а поэтому и для />.
В частности, системамногочленов /> называется взаимнопростой, если общими делителями этих многочленов являются лишь многочленынулевой степени, то есть если их наибольший общий делитель равен 1. Если />, то попарно эти многочленымогут и не быть взаимно простыми.
/>3.Кратные корни
Теорема Безу. Многочлен f(x) делится на x-cтогда и только тогда, когда число cявляется его корнем.
Рассмотрим произвольныймногочлен f(x) и разделим его с остатком на двучлен x-c. Поскольку степень этого двучлена равна 1, то остатоклибо равен 0, либо имеет степень 0. И в том, и в другом случае остаток rесть число. Таким образом, многочлен f(x) представляется в виде:
f(x)= (x-c) q(x)+ r.
Положив в этом тождестве x= c, получим что f(c)=r. Мы доказали тем самым, что остаток от делениямногочлена на двучленx— cравен значениюмногочлена приx=c.
С помощью теоремы Безурешим несколько задач.
Пример 1. Решить уравнение />.
Многочлен f(x)= /> имееткорень 2. По теореме Безу f(x) делится на x-2, то есть имеет место равенство
/>.
/>| />
/> />
/>
/>
/>
/>
/>
Остается решитьквадратное уравнение />.
Это уравнение не имеетдействительных корней, так что x=2– единственный действительный корень исходного уравнения.
2. Решить уравнение />.
Многочлен f(x)= /> имееткорень -2. По теореме Безу f(x) делится на x+2, то есть имеет место равенство />.
/> | />
/> />
/>
/>
/>
0
Остается решитьквадратное уравнение />.
Это уравнение имееткорень 1. Так что x=-2 и x=1 – корни исходного уравнения.
Если c – корень многочлена f(x), то есть f(c)=0, то f(x) делится на x-c. Может оказаться, что многочлен f(x) делится не только на первую степень линейногодвучлена x-c, но и на более высокие его степени. Во всяком случае,найдется такое натуральное число k, что f(x) нацело делится на />,но не делится на />. Поэтому
/>,
где многочлен /> на x-c уже не делится, то есть число с своим корнем неимеет. Числоkназывается кратностью корня cв многочлене f(x), а сам корень c–k— кратным корнем этого многочлена. Если k=1, то говорят, что корень с – простой.
/>4.Производная от многочлена
Понятие кратного корнятесно связано с понятием производной от многочлена. Мы изучаем многочлены слюбыми комплексными коэффициентами и поэтому не можем просто воспользоватьсяпонятием производной, введенным в курсе математического анализа. То, что будетсказано ниже, следует рассматривать как независимое от курса анализа определениепроизводной многочлена.
Пусть дан многочлен n–ной степени
f(x)= />
с любыми комплекснымикоэффициентами. Его производной (первой производной) называется многочлен(n- 1)-й степени
/>
Производная от многочленанулевой степени и от нуля считается равной нулю. Производная от первойпроизводной называется второй производной от многочлена f(x) и обозначается через f“(x). Очевидно, что
/>
и по этому />, то есть (n+1)-я производная от многочлена n–й степени равна нулю.
Свойства, являющиесяформулами дифференцирования для суммы и произведения:
1. /> (4.1)
2. /> (4.2)
Эти формулы легкопроверить, впрочем, непосредственным подсчетом, беря в качестве и двапроизвольных многочлена и применяя данное выше определение производной.
Формула (4.2)распространяется на случай произведения любого конечногочисла множителей,а поэтому выводится формула для производной от степени:
3. /> (4.3)
Доказательство. Используем метод математическойиндукции.
/> />
/> />
/> />
/>.
Если число с является k–кратным корнем многочлена f(x), то при k>1 оно будет (k-1)–кратным корнем первой производнойэтого многочлена; если же k=1, то с не будет служить корнем для />.
В самом деле, пусть
/>, />, (4.4)
где /> уже не делится на х-с.Дифференцируя равенство (4.4), получаем:
/>.
Первое слагаемое суммыделится на х-с, а второе на х-с не делится; поэтому вся этасумма на х-с не может делиться. Учитывая, что частное от деления f(x) на /> определено однозначно, мы получаем, что /> является наибольшей степеньюдвучлена х-с, на которую делится многочлен />.
Применяя эту теоремунесколько раз, мы получаем, что k-кратный корень многочлена f(x) будет (k-s)-кратным в s-й производной этого многочлена /> и впервые не будет служитькорнем для k-йпроизводной от f(x).
Пример. Найти производную /> многочлена />.
/>
/>.
Я составила программу длянахождения первой производной многочлена.
unit Unit1;
interface
uses
Windows,Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs,StdCtrls, Grids;
type
TForm1 =class(TForm)
Edit1:TEdit;
Label1:TLabel;
SGd1:TStringGrid;
Label2:TLabel;
Button1:TButton;
Edit2:TEdit;
Edit3:TEdit;
Label3:TLabel;
Label4:TLabel;
procedureButton1Click(Sender: TObject);
private
{ Privatedeclarations }
public
{ Publicdeclarations }
end;
var
Form1:TForm1;
c,i,st:integer;
k,l,s:string;
kof:array[0..100] of integer;
implementation
{$R *.dfm}
procedureTForm1.Button1Click(Sender: TObject);
begin
st:=StrToInt(Edit1.Text);
for i:=0 tost do begin
ifSGd1.Cells[i,0]'' then
kof[st-i]:=StrToInt(SGd1.Cells[i,0])
else MessageDlg ('Внимание! Не введены значения коэффициентов!',mtWarning,[mbOK],0);
end;
s:='f(x)=';
for i:=stdownto 0 do begin
ifkof[i]0 then begin
if(kof[i-1]
str(kof[i],l);
str(i,k);
s:=s+l+'x^'+k;
end
elsebegin
str(kof[i],l);
str(i,k);
s:=s+l+'x^'+k+'+';
end;
end;
kof[i]:=kof[i]*i;
end;
Edit2.Text:=s;
s:='f1(x)=';
for i:=stdownto 0 do begin
ifkof[i]0 then begin
if(kof[i-1]
str(kof[i],l);
str(i-1,k);
s:=s+l+'x^'+k;
end
elsebegin
str(kof[i],l);
str(i-1,k);
s:=s+l+'x^'+k+'+';
end;
end;
Edit3.Text:=s;
end;
end;
end.
/>
/>5. Кратные множители
Существуют методы,позволяющие узнать, обладает ли данный многочлен кратными множителями, и вслучае положительного ответа дающие возможность свести изучение этогомногочлена к изучению многочленов, уже не содержащих кратных множителей.
Теорема. Если /> является/> - кратным неприводимыммножителем многочлена />, />, то он будет /> — кратным множителемпроизводной этого многочлена. В частности, простой множитель многочлена. Невходит в разложение производной.
В самом деле, пусть
/>, (5.1)
причем /> уже не делится на />. Дифференцируя равенство(5.1), получаем:
/>.
Второе из слагаемых,стоящих в скобках, не делится на />. Действительно,/> не делится />по условию, /> имеет меньшую степень,т.е. также не делится на />. Сдругой стороны, первое слагаемое суммы, стоящей в квадратных скобках, делитьсяна/>, т.е. множитель />, на самом деле входит в /> с кратностью />.
Из данной теоремы и изуказанного выше способа разыскания наибольшего общего делителя двух многочленовследует, что если дано разложение многочлена /> нанеприводимые множители:
/>, (5.2)
то наибольший общийделитель многочлена /> и егопроизводной обладает следующим разложением на неприводимые множители:
/>, (5.3)
где множитель /> следует при /> заменять единицей. Вчастности, многочлен /> тогда и толькотогда не содержит кратных множителей, если он взаимно прост со своейпроизводной./> 5.1. Выделение кратных множителей
Если дан многочлен /> с разложением (5.2) и есличерез /> мы обозначим наибольшийобщий делитель /> и егопроизводной /> то (5.3) будет разложениемдля />. Деля (5.2) на (5.3), мыполучим:
/>
т.е. получим многочлен,не содержащий кратных множителей, причем всякий неприводимый множитель для />, имеющего вообще говоря,меньшую степень и, во всяком случае, содержащего лишь простые множители. Еслиэта задача для /> будет решена, тоостанется определить лишь кратность найденных неприводимых множителей в />, что достигаетсяприменением алгоритма деления.
Усложняя изложенныйсейчас метод, можно сразу перейти к рассмотрению нескольких многочленов безкратных множителей, причем, найдя неприводимые множители этих многочленов, мыне только найдем все неприводимые множители для />,но и будем знать их кратность.
Пусть (5.2) будетразложением /> на неприводимые множители,причем наивысшая кратность множителей есть />,/>. Обозначим через /> произведение всеходнократных множителей многочлена />, через /> - произведение всехдвукратных множителей, но взятых лишь по одному разу, и т.д., наконец /> - произведение всех />-кратных множителей, такжевзятых лишь по одному разу; если при этом для некоторого /> в /> отсутствуют />-кратные множители, тополагаем />. Тогда /> будет делиться на /> — тую степень многочлена /> и разложение (5.2) приметвид
/>
а разложение (5.3) для /> перепишется в виде />
обозначая через /> наибольший общий делительмногочлена /> и его производной и вообщечерез /> наибольший общий делительмногочленов /> и />, таким путем получим:
/>
/>
……………………………
/>
/>.
Отсюда
/>,
/>
/>
……………………………
/>,
И поэтому, наконец,
/>, />, …, />
Таким образом, пользуясьлишь приемами, не требующими знания неприводимых множителей многочлена />, а именно взятиемпроизводной, алгоритмом Евклида и алгоритмом деления, мы можем найти многочлены/> без кратных множителей,причем всякий неприводимый множитель многочлена /> />, будет />-кратным для />.
Пример. Разложить многочлен /> на кратные множители.
/>
/>
/>
/> │ />
/> />
/>
/>
/> │ />
/> />
/>
/>
/>
/>
/>
/>
/> │ />
/> />
/>
/>
/>
/>
/>
/>
/>
/> │/>
/> />
/>
/>
/>
/>
/>
/>
/> │/>
/> />
/>
/>
/>
/>
/>
/>
/>
/>
/>│/>
/> />
/>
/>
/>
/>
/>
/>
/>
/>
/>│/>
/> />
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>│/>
/> />
/>
/>
/>
/>
/>
/>│/>
/> />
/>
/>
/>
/>
/>
/>
/>
Многочлен /> имеет разложение в виде />.
Я составила программу дляразложения многочлена на кратные множители.
unit Unit1;
interface
uses
Windows,Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs,StdCtrls, Grids;
type
TForm1 =class(TForm)
Edit1:TEdit;
Label1:TLabel;
SGd1:TStringGrid;
Label2:TLabel;
Button1:TButton;
Label3:TLabel;
SGd2:TStringGrid;
SGd3:TStringGrid;
SGd4:TStringGrid;
Edit6:TEdit;
procedureButton1Click(Sender: TObject);
private
{ Privatedeclarations }
public
{ Publicdeclarations }
end;
var
Form1:TForm1;
c,i,st1,st2,stiz,n_iz,n_nod,n,m,d_st,step,f:integer;
k,d,s:string;
kof1,kof2,k1,k2,izubst,a,b,a2,b2,buf,est,fxst:array[0..15] of integer;
izub,e,fx:array[0..50,0..50] of integer;
first:boolean;
implementation
{$R *.dfm}
procedureTForm1.Button1Click(Sender: TObject);
vari,j,k_1,st3,l:integer;
sokr:boolean;
k2_2,k1_1:array[0..10] of integer;
begin
st1:=StrToInt(Edit1.Text);
for i:=0 tost1 do begin
SGd4.Cells[i,0]:=SGd1.Cells[i,0];
end;
repeat
n_iz:=n_iz+1;
st2:=st1-1;
for i:=0to st1 do begin
ifSGd1.Cells[i,0]'' then
kof1[st1-i]:=StrToInt(SGd1.Cells[i,0])
else MessageDlg('Внимание! Не введены значениякоэффициентов!',mtWarning,[mbOK],0);
end;
s:='f(x)=';
for i:=st1downto 0 do begin
ifkof1[i]0 then begin
if(kof1[i-1]
str(kof1[i],d);
str(i,k);
s:=s+d+'x^'+k;
end
elsebegin
str(kof1[i],d);
str(i,k);
s:=s+d+'x^'+k+'+';
end;
end;
kof2[i-1]:=kof1[i]*i;
end;
//Edit2.Text:=s;
s:='f1(x)=';
for i:=st2downto 0 do begin
SGd2.Cells[st2-i,0]:=inttostr(kof2[i]);
ifkof2[i]0 then begin
if(kof2[i-1]
str(kof2[i],d);
str(i-1,k);
s:=s+d+'x^'+k;
end
elsebegin
str(kof2[i],d);
str(i-1,k);
s:=s+d+'x^'+k+'+';
end;
end;
//Edit3.Text:=s;
end;
for i:=0to st1 do begin
kof1[i]:=StrToInt(SGd1.Cells[i,0]);
k1[i]:=StrToInt(SGd1.Cells[i,0]);
end;
for i:=0to st2 do begin
kof2[i]:=StrToInt(SGd2.Cells[i,0]);
k2[i]:=StrToInt(SGd2.Cells[i,0]);
end;
whilekof2[0]0 do begin
repeat
//Edit4.Text:='';
stiz:=0;
k_1:=k1[0];
ifk1[0]kof2[0] then begin
if(k1[0] mod kof2[0])=0 then begin
for j:=0 to st2 do
k2[j]:=(k1[0] div kof2[0])*kof2[j];
end
elsebegin
ifk2[0]1 then
for j:=0 to st1 do
k1[j]:=kof2[0]*k1[j];
ifk_11 then begin
for j:=0 to st2 do
k2[j]:=k_1*kof2[j];
end;
end;
end;
fori:=1 to st1 do begin
k1[i-1]:=k1[i]-k2[i];
end;
st1:=st1-1;
untilst1
ifk1[0]0 then begin //Сокращение
sokr:=true;
for i:=1to st1 do
ifk1[i]0 then begin
if(k1[i] mod k1[0])0 then sokr:=false;
end;
k_1:=k1[0];
ifsokr=true then
fori:=0 to st1 do
k1[i]:=k1[i] div k_1;
end;
for i:=0to st2 do //Замена многочленов
k2_2[i]:=kof2[i];
for i:=0to st1 do
k1_1[i]:=k1[i];
for i:=0to 10 do begin
SGd3.Cells[i,0]:='';
SGd1.Cells[i,0]:='';
kof1[i]:=0;
k1[i]:=0;
kof2[i]:=0;
k2[i]:=0;
izub[n_iz,i]:=0;
end;
izubst[n_iz]:=st2;
for i:=0to st2 do begin
k1[i]:=k2_2[i];
SGd1.Cells[i,0]:=inttostr(k1[i]);
izub[n_iz,i]:=k1[i];
ifk1[i]0 then begin
//Edit4.Text:=Edit4.Text+IntToStr(k1[i])+'x^'+IntToStr(st2-i);
end;
if(k2_2[i+1]>0)and(i
end;
for i:=0to st1 do begin
k2[i]:=k1_1[i];
kof2[i]:=k1_1[i];
end;
st3:=st1;
st1:=st2;
st2:=st3;
end;
until(st1=0);
d_st:=StrToInt(Edit1.Text);
fori:=d_st+1 downto 1 do begin
kof1[i]:=StrToInt(SGd4.Cells[d_st-(i-1),0]);
end;
//НахождениеЕ
first:=true;
for n_nod:=1to n_iz do begin
n:=d_st;
m:=izubst[n_nod];
d_st:=m;
for i:=n+1downto 1 do begin
a[i]:=kof1[i];
end;
for i:=m+1downto 1 do begin
b[i]:=izub[n_nod,m-(i-1)];
kof1[i]:=b[i];
end;
s:='f1(x)=';
for i:=n+1downto 1 do begin
ifa[i]0 then begin
if(a[i-1]
str(a[i],d);
str(i-1,k);
s:=s+d+'x^'+k;
end
elsebegin
str(a[i],d);
str(i-1,k);
s:=s+d+'x^'+k+'+';
end;
end;
end;
//Edit3.Text:=s;
s:='f2(x)=';
for i:=m+1downto 1 do begin
ifb[i]0 then begin
if(b[i-1]
str(b[i],d);
str(i-1,k);
s:=s+d+'x^'+k;
end
elsebegin
str(b[i],d);
str(i-1,k);
s:=s+d+'x^'+k+'+';
end;
end;
end;
//Edit4.Text:=s;
for j:=n+1downto 1 do begin
a2[j]:=a[j];
b2[j]:=0;
end;
step:=n-m;
f:=n+2;
fori:=step+1 downto 1 do begin
f:=f-1;
buf[i]:=a2[f];
forj:=m+1 downto 1 do begin
b2[j]:=buf[i]*b[j];
end;
for j:=fdownto 1 do begin
a2[j]:=a2[j]*b[m+1];
end;
for j:=fdownto 1 do begin
a2[j]:=a2[j]-b2[j+1-i];
b2[j]:=0;
end;
end;
s:='h(x)=';
for i:=f+1downto 1 do begin
e[n_nod,i]:=buf[i];
ifbuf[i]0 then begin
if(buf[i-1]
str(buf[i],d);
str(i-1,k);
s:=s+d+'x^'+k;
end
elsebegin
str(buf[i],d);
str(i-1,k);
s:=s+d+'x^'+k+'+';
end;
buf[i]:=0;
end;
end;
est[n_nod]:=f;
//Edit5.Text:=s;
s:='r(x)=';
for i:=ndownto 0 do begin
ifa2[i]0 then begin
if(a2[i-1]
str(a2[i],d);
str(i-1,k);
s:=s+d+'x^'+k;
end
elsebegin
str(a2[i],d);
str(i-1,k);
s:=s+d+'x^'+k+'+';
end;
end;
end;
Edit6.Text:=s;
first:=false;
end;
for n_nod:=1to n_iz-1 do begin
n:=est[n_nod];
m:=est[n_nod+1];
d_st:=m;
for i:=n+1downto 1 do begin
a[i]:=e[n_nod,i];
end;
for i:=m+1downto 1 do begin
b[i]:=e[n_nod+1,i];
kof1[i]:=b[i];
ifn_nod=n_iz-1 then fx[n_iz,i]:=b[i];
end;
s:='f1(x)=';
for i:=n+1downto 1 do begin
ifa[i]0 then begin if(a[i-1]
str(a[i],d);
str(i-1,k);
s:=s+d+'x^'+k;
end
elsebegin
str(a[i],d);
str(i-1,k);
s:=s+d+'x^'+k+'+';
end;
end;
end;
//Edit3.Text:=s;
s:='f2(x)=';
for i:=m+1downto 1 do begin
ifb[i]0 then begin if(b[i-1]
str(b[i],d);
str(i-1,k);
s:=s+d+'x^'+k;
end
elsebegin
str(b[i],d);
str(i-1,k);
s:=s+d+'x^'+k+'+';
end;
end;
end;
//Edit4.Text:=s;
for j:=n+1downto 1 do begin
a2[j]:=a[j];
b2[j]:=0;
end;
step:=n-m;
f:=n+2;
fori:=step+1 downto 1 do begin
f:=f-1;
buf[i]:=a2[f];
for j:=m+1downto 1 do begin
b2[j]:=buf[i]*b[j];
end;
for j:=fdownto 1 do begin
a2[j]:=a2[j]*b[m+1];
end;
for j:=fdownto 1 do begin
a2[j]:=a2[j]-b2[j+1-i];
b2[j]:=0;
end;
end;
s:='h(x)=';
for i:=f+1downto 1 do begin
fx[n_nod,i]:=buf[i];
ifbuf[i]0 then begin if(buf[i-1]
str(buf[i],d);
str(i-1,k);
s:=s+d+'x^'+k;
end
elsebegin
str(buf[i],d);
str(i-1,k);
s:=s+d+'x^'+k+'+';
end;
buf[i]:=0;
end;
end;
//Edit5.Text:=s;
fxst[n_nod]:=f;
s:='r(x)=';
for i:=ndownto 0 do begin
ifa2[i]0 then begin if(a2[i-1]
str(a2[i],d);
str(i-1,k);
s:=s+d+'x^'+k;
end
elsebegin
str(a2[i],d);
str(i-1,k);
s:=s+d+'x^'+k+'+';
end;
end;
end;
Edit6.Text:=s;
end;
fxst[n_iz]:=est[n_iz]+1;
Edit6.Text:='';
s:='';
for i:=1 ton_iz do begin
s:=s+'(';
forj:=fxst[i] downto 0 do begin
iffx[i,j]0 then begin
if(fx[i,j-1]
str(fx[i,j],d);
str(j-1,k);
s:=s+d+'x^'+k;
end
elsebegin
str(fx[i,j],d);
str(j-1,k);
s:=s+d+'x^'+k+'+';
end;
end;
end;
s:=s+')^'+IntToStr(i)+' ';
Edit6.Text:=Edit6.Text+s;
s:='';
end;
for i:=0 to10 do begin
SGd1.Cells[i,0]:=SGd4.Cells[i,0];
end;
end;
end.
/>
Заключение
При выполнении дипломнойработы я рассмотрела следующие вопросы:
– делимость многочленов;
– деление многочленов состатком;
– наибольший общийделитель, алгоритм Евклида;
– кратные корни;
– кратные множители,выделение кратных множителей;
– производные отмногочленов.
Составила программы длянахождения частного и остатка при делении многочленов; наибольшего общегоделителя двух многочленов; производной многочлена.
/>/>Список использованной литературы
1. Алгебра и теориячисел. Под ред. Н. Я. Виленкина. Москва: Просвещение,1984.
2. Архангельский А.Я. Программирование в Delphi6. Москва: ЗАО Бином, 2003.
3. Архангельский А.Я. Delphi 7. Справочное пособие. Москва: ОООБином-Пресс, 2004.
4. Курош А. Г. Курсвысшей алгебры. Москва: Наука, 1971.
5. Ляпин Е. С.,Евсеев А. Е. Алгебра и теория чисел. Часть II. Линейная алгебра и полиномы. Москва: Просвещение, 1978.
6. Мантуров О. В. идр. Математика в понятиях, определениях и терминах. Часть 2. Москва:Просвещение, 1982.
7. Попов В.Б. Turbo Pascal. Москва: Финансы и статистика, 2000.
8. Потапов М. К.,Александров В. В., Пасиченко П. И. Алгебра и анализ элементарных функций.Москва: Наука, 1980.
9. Сабинина Л. В.Математика в понятиях, определениях и терминах. Часть I. Москва: Просвещение, 1978.
10. Сборник задач поалгебре. Под ред. А. И. Кострикина. Москва: Наука, 1987.
11. Смолин Ю. Н.Алгебра и теория чисел. Перемь:1996.
12. Солодовников А.С., Родина М. А. Задачник-практикум по алгебре. Часть IV. Москва: Просвещение, 1985.
13. Фадеев Д. К.Лекции по алгебре. Москва: Наука, 1984.
14. Фадеев Д. К.,Соминский И. С. Сборник задач по высшей алгебре. Москва: Наука, 1968.
15. Шварцбурд С. И.Избранные вопросы математики. Москва: Просвещение, 1980.