МІНІСТЕРСТВО ОСВІТИ І НАУКИ РФ
МІНІСТЕРСТВО ОСВІТИ
Набережночелнінскій ДЕРЖАВНИЙ
ПЕДАГОГІЧНИЙ ІНСТИТУТ
МАТЕМАТИЧНИЙ ФАКУЛЬТЕТ
КАФЕДРА МАТЕМАТИКИ та методики її викладання
АЛГОРИТМИ З МГНОГОЧЛЕНАМІ
/ Дипломна робота /
Набережні Челни
2006
Зміст
Введення
1. Многочлени
2. Розподіл многочленів
2.1. Подільність многочленів. Властивості подільності
2.2. Розподіл многочленів із залишком
2.3. Найбільший спільний дільник многочленів
2.4. Алгоритм Евкліда
3. Кратні коріння
4. Похідна від многочлена
5. Кратні множники
5.1. Виділення кратних множників
Висновок
Список використаної літератури
Введення
Тема моєї дипломної роботи: «Алгоритми з многочленами».
Метою даної роботи є вивчення многочленів, алгоритмів з ними, розгляд можливостей складання різних програм. Для досягнення поставленої мети необхідно розглянути такі питання:
- Подільність многочленів;
- Розподіл многочленів із залишком;
- Найбільший спільний дільник, алгоритм Евкліда;
- Кратні корені;
- Кратні множники, виділення кратних множників;
- Похідні від многочленів.
Для виконання дипломної роботи я поставила такі завдання:
вивчити літературу про многочленів;
застосувати теорію вищої алгебри у вирішенні завдань елементарної математики;
скласти програми для знаходження приватного та залишку при діленні многочленів, найбільшого загального дільника двох многочленів, похідної многочлена; розкладання многочленів на множники кратні.
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;
procedure Button1Click (Sender: TObject);
private
{Private declarations}
public
{Public declarations}
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}
procedure TForm1.Button1Click (Sender: TObject);
begin
n: = StrToInt (Edit1.Text);
m: = StrToInt (Edit2.Text);
for i: = n +1 downto 1 do begin
a [i]: = StrToInt (SGd1.Cells [n-(i-1), 0]);
end;
for i: = m +1 downto 1 do begin
b [i]: = StrToInt (SGd1.Cells [m-(i-1), 1]);
end;
s: = 'f1 (x) =';
for i: = n +1 downto 1 do begin
if a [i] <> 0 then begin if (a [i-1] <0) or (i = 1) then begin
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 +1 downto 1 do begin
if b [i] <> 0 then begin if (b [i-1] <0) or (i = 1) then begin
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 +1 downto 1 do begin
a2 [j]: = a [j];
b2 [j]: = 0;
end;
step: = nm;
f: = n +2;
for i: = step +1 downto 1do begin
f: = f-1;
k [i]: = a2 [f];
for j: = m +1 downto 1do begin
b2 [j]: = k [i] * b [j];
end;
for j: = f downto 1 do begin
a2 [j]: = a2 [j] * b [m +1];
end;
for j: = f downto 1 do begin
a2 [j]: = a2 [j]-b2 [j +1- i];
b2 [j]: = 0;
end;
end;
s: = 'h (x) =';
for i: = f downto 1 do begin
if k [i] <> 0 then begin if (k [i-1] <0) or (i = 1) then begin
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: = n downto 0 do begin
if a2 [i] <> 0 then begin if (a2 [i-1] <0) or (i = 1) then begin
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;
procedure Button1Click (Sender: TObject);
private
{Private declarations}
public
{Public declarations}
end;
var
Form1: TForm1;
st1, st2: integer;
kof1, kof2, k1, k2: array [0 .. 10] of integer;
implementation
{$ R *. dfm}
procedure TForm1.Button1Click (Sender: TObject);
var i, 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 to st1 do begin
kof1 [i]: = StrToInt (SGd1.Cells [i, 0]);
k1 [i]: = StrToInt (SGd1.Cells [i, 0]);
end;
for i: = 0 to st2 do begin
kof2 [i]: = StrToInt (SGd1.Cells [i, 1]);
k2 [i]: = StrToInt (SGd1.Cells [i, 1]);
end;
while kof2 [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
for j: = 0 to st2 do
k2 [j]: = (k1 [0] div kof2 [0]) * kof2 [j];
end
else begin
if k2 [0] <> 1 then
for j: = 0 to st1 do
k1 [j]: = kof2 [0] * k1 [j];
if k_1 <> 1 then begin
for j: = 0 to st2 do
k2 [j]: = k_1 * kof2 [j];
end;
end;
end;
for i: = 1 to st1 do begin
k1 [i-1]: = k1 [i]-k2 [i];
end;
st1: = st1-1;
until st1 <st2;
if k1 [0] <> 0 then begin / / Скорочення
sokr: = true;
for i: = 1 to st1 do
if k1 [i] <> 0 then begin
if (k1 [i] mod k1 [0]) <> 0 then sokr: = false;
end;
k_1: = k1 [0];
if sokr = true then
for i: = 0 to st1 do
k1 [i]: = k1 [i] div k_1;
end;
for i: = 0 to st2 do / / Заміна многочленів
k2_2 [i]: = kof2 [i];
for i: = 0 to st1 do
k1_1 [i]: = k1 [i];
for i: = 0 to 10 do begin
kof1 [i]: = 0;
k1 [i]: = 0;
kof2 [i]: = 0;
k2 [i]: = 0;
end;
for i: = 0 to st2 do begin
k1 [i]: = k2_2 [i];
if k1 [i] <> 0 then
Edit4.Text: = Edit4.Text + IntToStr (k1 [i]) + 'x ^' + IntToStr (st2-i);
if (k2_2 [i +1]> 0) and (i <st2) then Edit4.Text: = Edit4.Text +'+';
end;
for i: = 0 to st1 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;
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;
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;
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;
procedure Button1Click (Sender: TObject);
private
{Private declarations}
public
{Public declarations}
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}
procedure TForm1.Button1Click (Sender: TObject);
var i, 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 to st1 do begin
SGd4.Cells [i, 0]: = SGd1.Cells [i, 0];
end;
repeat
n_iz: = n_iz +1;
st2: = st1-1;
for i: = 0 to st1 do begin
if SGd1.Cells [i, 0 ]<>'' then
kof1 [st1-i]: = StrToInt (SGd1.Cells [i, 0])
else MessageDlg ('Попередження: Не введені значення коефіцієнтів!', MtWarning, [mbOK], 0);
end;
s: = 'f (x) =';
for i: = st1 downto 0 do begin
if kof1 [i] <> 0 then begin
if (kof1 [i-1] <0) or (i = 0) then begin
str (kof1 [i], d);
str (i, k);
s: = s + d + 'x ^' + k;
end
else begin
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: = st2 downto 0 do begin
SGd2.Cells [st2-i, 0]: = inttostr (kof2 [i]);
if kof2 [i] <> 0 then begin
if (kof2 [i-1] <0) or (i = 1) then begin
str (kof2 [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k;
end
else begin
str (kof2 [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k +'+';
end;
end;
/ / Edit3.Text: = s;
end;
for i: = 0 to st1 do begin
kof1 [i]: = StrToInt (SGd1.Cells [i, 0]);
k1 [i]: = StrToInt (SGd1.Cells [i, 0]);
end;
for i: = 0 to st2 do begin
kof2 [i]: = StrToInt (SGd2.Cells [i, 0]);
k2 [i]: = StrToInt (SGd2.Cells [i, 0]);
end;
while kof2 [0] <> 0 do begin
repeat
/ / Edit4.Text :='';
stiz: = 0;
k_1: = k1 [0];
if k1 [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
else begin
if k2 [0] <> 1 then
for j: = 0 to st1 do
k1 [j]: = kof2 [0] * k1 [j];
if k_1 <> 1 then begin
for j: = 0 to st2 do
k2 [j]: = k_1 * kof2 [j];
end;
end;
end;
for i: = 1 to st1 do begin
k1 [i-1]: = k1 [i]-k2 [i];
end;
st1: = st1-1;
until st1 <st2;
if k1 [0] <> 0 then begin / / Скорочення
sokr: = true;
for i: = 1 to st1 do
if k1 [i] <> 0 then begin
if (k1 [i] mod k1 [0]) <> 0 then sokr: = false;
end;
k_1: = k1 [0];
if sokr = true then
for i: = 0 to st1 do
k1 [i]: = k1 [i] div k_1;
end;
for i: = 0 to st2 do / / Заміна многочленів
k2_2 [i]: = kof2 [i];
for i: = 0 to st1 do
k1_1 [i]: = k1 [i];
for i: = 0 to 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: = 0 to st2 do begin
k1 [i]: = k2_2 [i];
SGd1.Cells [i, 0]: = inttostr (k1 [i]);
izub [n_iz, i]: = k1 [i];
if k1 [i] <> 0 then begin
/ / Edit4.Text: = Edit4.Text + IntToStr (k1 [i]) + 'x ^' + IntToStr (st2-i);
end;
if (k2_2 [i +1]> 0) and (i <st2) then / / Edit4.Text: = Edit4.Text +'+';
end;
for i: = 0 to 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);
for i: = d_st +1 downto 1 do begin
kof1 [i]: = StrToInt (SGd4.Cells [d_st-(i-1), 0]);
end;
/ / Знаходження Е
first: = true;
for n_nod: = 1 to n_iz do begin
n: = d_st;
m: = izubst [n_nod];
d_st: = m;
for i: = n +1 downto 1 do begin
a [i]: = kof1 [i];
end;
for i: = m +1 downto 1 do begin
b [i]: = izub [n_nod, m-(i-1)];
kof1 [i]: = b [i];
end;
s: = 'f1 (x) =';
for i: = n +1 downto 1 do begin
if a [i] <> 0 then begin
if (a [i-1] <0) or (i = 1) then begin
str (a [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k;
end
else begin
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 +1 downto 1 do begin
if b [i] <> 0 then begin
if (b [i-1] <0) or (i = 1) then begin
str (b [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k;
end
else begin
str (b [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k +'+';
end;
end;
end;
/ / Edit4.Text: = s;
for j: = n +1 downto 1 do begin
a2 [j]: = a [j];
b2 [j]: = 0;
end;
step: = nm;
f: = n +2;
for i: = step +1 downto 1 do begin
f: = f-1;
buf [i]: = a2 [f];
for j: = m +1 downto 1 do begin
b2 [j]: = buf [i] * b [j];
end;
for j: = f downto 1 do begin
a2 [j]: = a2 [j] * b [m +1];
end;
for j: = f downto 1 do begin
a2 [j]: = a2 [j]-b2 [j +1- i];
b2 [j]: = 0;
end;
end;
s: = 'h (x) =';
for i: = f +1 downto 1 do begin
e [n_nod, i]: = buf [i];
if buf [i] <> 0 then begin
if (buf [i-1] <0) or (i = 1) then begin
str (buf [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k;
end
else begin
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: = n downto 0 do begin
if a2 [i] <> 0 then begin
if (a2 [i-1] <0) or (i = 1) then begin
str (a2 [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k;
end
else begin
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: = 1 to n_iz-1 do begin
n: = est [n_nod];
m: = est [n_nod +1];
d_st: = m;
for i: = n +1 downto 1 do begin
a [i]: = e [n_nod, i];
end;
for i: = m +1 downto 1 do begin
b [i]: = e [n_nod +1, i];
kof1 [i]: = b [i];
if n_nod = n_iz-1 then fx [n_iz, i]: = b [i];
end;
s: = 'f1 (x) =';
for i: = n +1 downto 1 do begin
if a [i] <> 0 then begin if (a [i-1] <0) or (i = 1) then begin
str (a [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k;
end
else begin
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 +1 downto 1 do begin
if b [i] <> 0 then begin if (b [i-1] <0) or (i = 1) then begin
str (b [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k;
end
else begin
str (b [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k +'+';
end;
end;
end;
/ / Edit4.Text: = s;
for j: = n +1 downto 1 do begin
a2 [j]: = a [j];
b2 [j]: = 0;
end;
step: = nm;
f: = n +2;
for i: = step +1 downto 1 do begin
f: = f-1;
buf [i]: = a2 [f];
for j: = m +1 downto 1 do begin
b2 [j]: = buf [i] * b [j];
end;
for j: = f downto 1 do begin
a2 [j]: = a2 [j] * b [m +1];
end;
for j: = f downto 1 do begin
a2 [j]: = a2 [j]-b2 [j +1- i];
b2 [j]: = 0;
end;
end;
s: = 'h (x) =';
for i: = f +1 downto 1 do begin
fx [n_nod, i]: = buf [i];
if buf [i] <> 0 then begin if (buf [i-1] <0) or (i = 1) then begin
str (buf [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k;
end
else begin
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: = n downto 0 do begin
if a2 [i] <> 0 then begin if (a2 [i-1] <0) or (i = 1) then begin
str (a2 [i], d);
str (i-1, k);
s: = s + d + 'x ^' + k;
end
else begin
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 to n_iz do begin
s: = s +'(';
for j: = fxst [i] downto 0 do begin
if fx [i, j] <> 0 then begin
if (fx [i, j-1] <0) or (j = 1) then begin
str (fx [i, j], d);
str (j-1, k);
s: = s + d + 'x ^' + k;
end
else begin
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 to 10 do begin
SGd1.Cells [i, 0]: = SGd4.Cells [i, 0];
end;
end;
end.
Висновок
При виконанні дипломної роботи я розглянула такі питання:
- Подільність многочленів;
- Розподіл многочленів із залишком;
- Найбільший спільний дільник, алгоритм Евкліда;
- Кратні корені;
- Кратні множники, виділення кратних множників;
- Похідні від многочленів.
Склала програми для знаходження приватного та залишку при діленні многочленів; найбільшого загального дільника двох многочленів; похідної многочлена.
Список використаної літератури
Алгебра і теорія чисел. Під ред. Н. Я. Виленкина. Москва: Просвещение, 1984.
Архангельський А. Я. Програмування в Delphi 6. Москва: ЗАТ Біном, 2003.
Архангельський А. Я. Delphi 7. Довідковий посібник. Москва: ТОВ Біном-Пресс, 2004.
Курош А. Г. Курс вищої алгебри. Москва: Наука, 1971.
Ляпін Є. С., Євсєєв А. Е. Алгебра і теорія чисел. Частина II. Лінійна алгебра і поліноми. Москва: Просвещение, 1978.
Мантуров О. В. та ін Математика в поняттях, визначеннях і термінах. Частина 2. Москва: Просвещение, 1982.
Попов В. Б. Turbo Pascal. Москва: Фінанси і статистика, 2000.
Потапов М. К., Александров В. В., Пасіченко П. І. Алгебра і аналіз елементарних функцій. Москва: Наука, 1980.
Сабініна Л. В. Математика в поняттях, визначеннях і термінах. Частина I. Москва: Просвещение, 1978.
Збірник завдань з алгебри. Під ред. А. І. Кострикін. Москва: Наука, 1987.
Смолін Ю. Н. Алгебра і теорія чисел. Змін: 1996.
Солодовников А. С., Батьківщина М. А. Задачник-практикум з алгебри. Частина IV. Москва: Просвещение, 1985.
Фадєєв Д. К. Лекції з алгебри. Москва: Наука, 1984.
Фадєєв Д. К., соминського І. С. Збірник задач з вищої алгебри. Москва: Наука, 1968.
Шварцбурд С. І. Вибрані питання математики. Москва: Просвещение, 1980.