Реферат: Метод наближеного обчислення коренів. Програма
Міністерствоосвіти і науки України
ФАКУЛЬТЕТ ІНФОРМАТИКИ
КАФЕДРАІНФОРМАЦІЙНИХ УПРАВЛЯЮЧИХ СИСТЕМ ТА ТЕХНОЛОГІЙ
Реєстраційний№________
Дата___________________
КУРСОВАРОБОТА
Тема:
Методнаближеного обчислення коренів. Програма.
Рекомендованадо захисту
“____”__________ 2008р.
Роботазахищена
“____”__________ 2008р.
зоцінкою
_____________________
Підписичленів комісії
Зміст
Вступ
Теоретична частина
1. Межі дійсних коренів
2. Число дійсних коренів
Практична частина
1. Опис програми
2. Текст програми
Контрольні приклади
Висновок
Література
Вступ
Не існує методудля пошуку точних значень многочленів з числовими коефіцієнтами. Адже, деякіпроблеми механіки, фізики і інших галузей техніки зводиться до питання прокорені многочленів, іноді досить високим степенем. Ця обставина з’явиласяприводом для численних досліджень, що мали метою навчитися робити ті чи іншівисловлення про корені многочлена з числовими коефіцієнтами, не знаючи цихкоренів. Для многочленів з дійсними коефіцієнтами розроблялися методивизначення числа їхніх дійсних коренів, шукалися границі, між якими ці кореніможуть знаходитися. Нарешті, багато досліджень було присвячено методамнаближеного обчислення коренів: у технічних додатках звичайно досить знати лишенаближені значення коренів з деякою заздалегідь точністю і якби, наприклад,корені многочлена записувалися в раидикалах, ці радикали все рівно були бзамінені їх наближеними значеннями.
Теоретичначастина
1.Межі дійсних коренів
Щоб знайти коренірівняння з достатнім степенем точності, треба знати, як ці корені розміщені накомплексній площині або на дійсній осі. Заважимо, що іноді навіть немаєпотреби знаходити числові значення коренів, а досить лише з‘ясувати їхрозміщення на площині (число дійсних, зокрема, додатних від‘ємних коренівтощо). Наприклад, одна з важливих проблем механіки – теорія стійкості –потребує з‘ясування умов, при яких усі корені даного алгебраїчного рівняннямають від‘ємні дійсні частини.
Зробимо двазауваження щодо комплексних коренів многочленів.
Зауваження 1. Усі корені многочлена /> лежать у середині круга зцентром у точці 0 і радіусом
/> (1)
Зауваження 2. Комплексні корені многочленаз дійсними коефіцієнтами розміщені симетрично відносно дійсної осі.
Переходячи тепердо розгляду дійсних коренів многочленів з дійсними коефіцієнтами, будемо зновупозначати змінне буквою x, а не z.
З наведеногозауваження 1 дістаємо таке твердження:
Теорема. Усі дійсні корені рівняння />міститься в інтервалі />, де
/>, />.
Справді, всікомплексні корені лежать у крузі />, атому, якщо серед них є дійсні корені, то вони повинні потрапити в зазначенийінтервал.
Теорему 1 частоназивають теоремою про межі коренів рівняння. Є чимало способів, які даютьзмогу з більшою точністю встановлювати межі дійних коренів алгебраїчнихрівнянь. Розглянемо один з них, так званий спосіб Ньютона.
Зробимо деякізауваження.
Число />, визначене за теоремою 1,дає одночасно верхню межу додатних коренів многочлена і нижню межу його від’ємнихкоренів, бо вказує інтервал />, вякому лежать усі дійсні корені, якщо вони існують. Один з шляхів уточнення,звуження меж, між якими слід шукати дійсні корені, полягає в тому, щоб окремознаходити нижню і верхню межі додатних коренів та нижню і верхню межі від’ємнихкоренів даного многочлена, тобто такі чотири числа /> ,що всі додатні корені многочлена лежать в інтервалі />,а всі від’ємні – />. Якщо многочленамоє корінь нуль, досить розглянути многочлена, утворений з даного ділення на x.
Завданняполегшується тим, що фактично досить знати спосіб знаходження лише одного з цихчотирьох чисел, наприклад />–верхньої межі додатних коренів. Знаходження інших трьох меж дійсних кореніврівняння /> легко звести дознаходження верхньої межі додатних коренів деяких допоміжних рівнянь.
Так, зробивши врівнянні /> заміну змінного />, дістанемо рівняння />, корені якого /> зв’язані з відповіднимикоренями /> заданого рівнянняспіввідношенням />. Якщо />– верхняя межа додатних коренів рівняння />, тобто />, то />, звідки видно, щ за нижнюдодатних коренів рівняння /> можнавзяти число />: />.
Аналогічно,заміна /> переводить рівняння /> в рівняння />, корені якого /> зв’язані з відповіднимикоренями /> рівняння /> рівністю />. Якщо />– всі додатні коренірівняння />, то />– всі від’ємні коренірівняння />. З нерівності /> видно, що />, тобто верхня і нижня межівід’ємних коренів рівняння /> виражаютьсячерез межі додатних коренів рівняння />: />.
Отже досить матиправило для знаходження верхньої межі додатних коренів многочлена.
2.Число дійсних коренів
Знання числа ірозміщення дійсних коренів многочленів є важливою передумовою застосуваннябагатьох методів чисельного розв’язування рівнянь. В окремих випадках деяківідомості про число дійсних коренів можна дістати за допомогою доситьповерхневого аналізу. Іноді при знаходженні меж коренів виявляється, щомногочлена не має додатних або від’ємних коренів. Однак для повної відповідіна питання про число дійсних коренів многочлена з дійсними коефіцієнтами (абонавіть про число таких коренів на довільному, наперед заданому інтервалідійсної осі) потрібні більш глибокі дослідження.
У багатьохвипадках число дійсних коренів рівняння з дійсними коефіцієнтами можнавизначити за простим правилом, яке дав Декарт. Перш ніж формулювати це правило,зробимо деякі зауваження.
Зауваження 1. Розглядатимемо кількість змінзнаків у даній упорядкованій скінченій послідовності дійсних чисел /> розуміючи під цимкількість пар сусідніх чисел цієї послідовності, які мають протилежні знаки. Наприклад,у послідовності –1,-2,6,3,-1,4 є 3 зміни знаків, а в послідовності–1,-2,-6,-3,-1,-4 є 0 змін знаків. Якщо які-небудь з чисел />дорівнюють нулю, то припідрахунку числа змін знаків їх до уваги не беруть. Зауважимо, що коли перше йостаннє числа /> і /> даної послідовності маютьоднакові знаки, то кількість змін знаків у послідовності парна; якщо ж /> і />мають протилежні знаки, токількість змін знаків – непарна. Справді, члени послідовності, якібезпосередньо йдуть за кожною зміною знаків, мають знак, протилежний знаку тихчленів, які передували зміні знаків. Отже, якщо остання зміна знаків маєнепарний номер, то числа послідовності, що йдуть за нею (і зокрема, />) матимуть знак,протилежний до />.
Зауваження 2. Припускатимемо, щорозглядуваний многочлена не має кратних коренів, оскільки завжди можнавідокремити кратні множники.
ПравилоДекарта. Числододатних коренів многочлена з дійсними коефіцієнтами
/>
дорівнює числузмін знаків у послідовності його коефіцієнтів або на парне число менше.
Зауваження 1. Правило Декарта можназастосувати і для оцінки числа від’ємних коренів з дійсними коефіцієнтами. Дляцього в рівнянні
/>
треба зробитизаміну змінного />. Зрозуміло, щочисло від’ємних коренів даного рівняння дорівнює числу додатних кореніврівняння />, яке можна оцінити заправилом Декарта.
Якщо данерівняння повне, тобто жодний коефіцієнт не дорівнює нулю, то число від’ємнихкоренів можна визначити і не виконуючи заміни />.Справді, в цьому випадку число /> змінзбережень знаків у ряді коефіцієнтів многочлена /> дорівнюєчислу /> збережень знаків у рядікоефіцієнтів многочлена />. Отже,число />від’ємних коренів повногорівняння дорівнює числу /> збережень знаківу ряді його коефіцієнтів або на парне число менше.
Зауваження 2. Коли наперед відомо, що всікорені даного рівняння /> дійсні,то правило Декарта дає точну відповідь на питання про число дійсних коренів, асаме: число додатних коренів дорівнює числу змін знаків у ряді коефіцієнтівмногочлена />, а число від’ємних коренів– числу змін знаків у ряді коефіцієнтів многочлена />.
Справді, нехай,як і вище, />і /> – число додатних івід’ємних коренів даного многочлена />, />-го степеня; /> і /> – число змін знаків у рядікоефіцієнтів многочлена /> імногочлена /> відповідно. З умови, щовсі корені дійсні, випливає: />. Якбирівняння були повними, то мали б також />.Якщо ж деякі з коефіцієнтів многочлена /> (атому й многочлена />) перетворюєтьсяв нуль, то числа /> і />можуть тільки зменшитися.Тому в загальному випадку />, звідки/>, або />. Але з правила Декартазнаємо, що />. Тому насправді />.
На жаль, убільшості випадків наперед невідомо, чи всі корені рівняння дійсні. У зв’язку зцим правило Декарта, хоч і зручне з точки зору простоти застосування, не даєповної відповіді на питання про число дійсних коренів рівнянь з дійснимикоефіцієнтами та їх розподіл між додатною і від’ємною півосями.
Практичначастина
1.Опис програми
Програмаскладається з двох файлів – polinom.pas і polinom.dat. У файлі polinom.datзаписується степень многочлена та його коефіціенти.
Описаняя процедурта функцій:
procedure znach –шукає межі додатніх та ві’ємних коренів;
functionznachenie – знаходить значення многочлена в точці;
procedure delenie– відокремлює корені многочлена;
procedure korni –уточнює корені многочлена методом поділу відрізка навпіл;
2.Текст програми
Uses crt;
typeff=array[0..10] of real;
var f0,f1,f2,f3:ff;
prom,kpol:array[0..100] of real;
fil:text;
i,nf,k,iprom:integer;
n0,n1,n2,n3,b:real;
procedureznach(a100:ff ;var a1:ff); {ищет промижутки}
var i1:byte;
begin
ifa100[0]<0 then
for i1:=0 tonf-1 do a100[i1]:=-1*a100[i1];
k:=0;
for i1:=0 tonf-1 do
ifa100[i1]<0 then begin k:=i1;break end;
b:=0;
for i1:=0 tonf-1 do
ifa100[i1]<0 then if b<abs(a100[i1]) then b:=abs(a100[i1]);
a1:=a100;
end;
proceduregran(k1:integer;b1,a5:real;var nk:real);{границы}
begin
if(k1<>0)and(b1<>0) then nk:=1+exp(1/k1*ln(b1/a5))
else nk:=0;
end;
functionznachenie(a100:ff;xx:real):real; {значение в тч ХХ}
var y:real;
i100:integer;
begin
y:=a100[0];
for i100:=1 tonf-1 do
y:=y*xx+a100[i100];
znachenie:=y;
end;
proceduredelenie(a,b:real);
const dx=0.1;
var z,z1,c:real;
begin
iprom:=0;
prom[0]:=a;
While b>ado begin
z:=znachenie(f0,a);
c:=a;
repeat
a:=a+dx;
z1:=znachenie(f0,a);
until(z*z1<0)or(b<a);
if z*z1<0then begin iprom:=iprom+1;
prom[iprom-1]:=c;
prom[iprom]:=a;
end;
end;
end;
procedurekorni(a8,b8:real);
const eps=0.0001;
var x0:real;
begin
x0:=(a8+b8)/2;
whileabs(b8-a8)>eps do begin
ifznachenie(f0,a8)*znachenie(f0,X0)<0 then begin b8:=x0;end;
ifznachenie(f0,x0)*znachenie(f0,b8)<0 then begin a8:=x0;end;
x0:=(a8+b8)/2 end;
kpol[i]:=x0;
end;
begin clrscr;
assign(fil,‘polinom.dat’);
reset(fil);
write(‘f=’);
readln(fil,nf);
{****************************************}
for i:=0 tonf-1 do {begin }
read(fil,f0[i]);write(f0[i],’ ‘)end;
writeln;
znach(f0,f0);
gran(k,b,f0[0],n0);
{*****************************************}
for i:=0 tonf-1 do f1[i]:=f0[nf-1-i];
znach(f1,f1);
gran(k,b,f1[0],n1);
{******************************************}
for i:=0 tonf-1 do
ifodd(nf-1-i)=true then f2[i]:=-1*f0[i]
elsef2[i]:=f0[i];
znach(f2,f2);
gran(k,b,f2[0],n2);
{************************************************}
for i:=0 tonf-1 do
ifodd(nf-1-i)=true then f3[i]:=-1*f0[nf-1-i]
elsef3[i]:=f0[nf-1-i];
znach(f3,f3);
gran(k,b,f3[0],n3);
if n0<>0then begin
writeln(‘відрізок додатних коренів [‘,1/n1:1:3,’; ‘,n0:1:3,’]’);
delenie(1/n1,n0);
fori:=0 to iprom-1 do begin
korni(prom[i],prom[i+1]);
writeln(kpol[i]:1:2{,’ ‘,znachenie(f0,kpol[i]):1:2}); end; end
elsewriteln('немає додатніх коренів');
ifn3<>0 then begin
writeln('Відрізок від’ємних коренів [',-1*n2:1:3,'; ',-1/n3:1:3,']');
delenie(-1*n2,-1/n3);
fori:=0 to iprom-1 do begin
korni(prom[i],prom[i+1]);
writeln(kpol[i]:1:2,’ ‘,znachenie(f0,kpol[i]):1:2); end; end
elsewriteln('немає від’ємних коренів');
readkey;
end.
3.Контрольні приклади
x3-4x2-7x+10=0
відрізок додатнихкоренів [0,588;8,000]
1,00
5,00
відрізоквід’ємних коренів [-4,162;-0,163]
-2,00
x5+2x4-5x3+8x2-7x-3=0
відрізок додатнихкоренів [0,380;3,646]
1,31
відрізоквід’ємних коренів [-9,000;-0,273]
-3,91
-0,30
3x5+7x4-8x3+5x2-2x-1=0
відрізок додатнихкоренів [0,274;2,633]
0,77
відрізоквід’ємних коренів [-3,667;-0,111]
-3,31
-0,26
x3-2,8x2-0,35x+3,45-0
відрізок додатнихкоренів [0,552;3,800]
1,50
2,30
відрізоквід’ємних коренів [-9,000;-0,273]
-1,00
Висновок
В курсовій роботібули розглянуті методи наближеного пошуку меж та самих коренів многочлена здійсними коренями. Можна знайти багато інших методів наближеного знаходженнякоренів. Один з них найбільш вдосконалим є метод Лобачевського. Цей методдозволяє знаходити наближення значення всіх коренів відразу, у тому числі ікомплексних, причому не потребує відділення коренів; однако він зв’язан звеликими обчисленнями.
Література
1. А. Г. Курош «Курс высшей алгебры», «Наука», Москва1975
2. С. Т. Завало, В. М. Костарчук, Б. И. Хацет «Алгебраи теория чисел», Том 1,«Высшая школа», Киев 1974
3. С. Т. Завало, В. М. Костарчук, Б. И. Хацет «Алгебраи теория чисел», Том 2,«Высшая школа», Киев 1976