Быстрый поиск

Дипломная работа: Алгоритмы с многочленами

Рассмотрим произвольный многочлен 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, то есть имеет место равенство .

Остается решить квадратное уравнение .

Это уравнение имеет корень 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;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

c,i,st:integer;

k,l,s:string;

kof:array[0..100] of integer;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

begin

st:=StrToInt(Edit1.Text);

for i:=0 to st do begin

if SGd1.Cells[i,0]<>'' then

kof[st-i]:=StrToInt(SGd1.Cells[i,0])

else MessageDlg ('Внимание! Не введены значения коэффициентов!',mtWarning,[mbOK],0);

end;

s:='f(x)=';

for i:=st downto 0 do begin

if kof[i]<>0 then begin

if(kof[i-1]<0)or(i=0) then begin

str(kof[i],l);

str(i,k);

s:=s+l+'x^'+k;

end

else begin

str(kof[i],l);

str(i,k);

s:=s+l+'x^'+k+'+';

end;

kof[i]:=kof[i]*i;

end;

Edit2.Text:=s;

s:='f1(x)=';

for i:=st downto 0 do begin

if kof[i]<>0 then begin

if(kof[i-1]<0)or(i=1) then begin

str(kof[i],l);

str(i-1,k);

s:=s+l+'x^'+k;

end

else begin

str(kof[i],l);

str(i-1,k);

s:=s+l+'x^'+k+'+';

end;

Edit3.Text:=s;

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) примет вид