4-TAJRIBA ISHI
Mavzu: Algoritmlarni loyihalash. Funksiyalarning qiymatini xisoblashning Gorner algoritmi. Kvadrat va kubik tenglama ildizlarini aniqlash
Ishdan maqsad: Algoritmlarni samaradorligini baholash. Funksiyalarning qiymatini xisoblashning Gorner algoritmi. Kvadrat va kubik tenglama ildizlarini aniqlash algoritmini ishlab chiqish.
Nazariy qism
Gorner algoritmi. Ko`phadning ildizlari.
(Etyen Bezu (1730-1783) – fransuz matematigi). P(x) ko`phadni x-a ikkihadga bo`lganda bo`linmada Q(x), qoldiqda R(x) qolsin:
P(x)=(x-a)Q(x)+R(x)
Agar bu munosabatga x=a qo`yilsa, P(a)=0∙Q(a)+R(a)=R(a)=r hosil bo`ladi. Shu tariqa ushbu teorema isbotlanadi:
1-teorema (Bezu). P(x)=a0xn+a1xn-1+...+an-1x+an(a≠0) ko`phadni x-a ga bo`lishdan chiqadigan r qoldiq shu ko`phadning x=a dagi qiymatiga teng, r=P(a).
Masalan, 1) x5+x+20 ni x+2 ga bo`lishdan chiqadigan qoldiq r=(-2)5+(-2)+20=-14; 2) x5+x+34 ni x+2 ga bo`lishdan chiqadigan qoldiq r=(-2)5+(-2)+34=0.
Demak, x=-2 soni shu ko`phadning ildizi.
Natijalar. n€N bo`lganda:
xn-an ikkihad x-a ga bo`linadi. Haqiqatan, P(a)=an-an=0;
xn+an ikkihad x-a ga bo`linmaydi. Haqiqatan, P(a)=an+an=2xn≠0;
x2n-a2n ikkihad x+a ga bo`linadi. Haqiqatan, P(-a)=(-a)2n-a2n=0;
x2n+1-a2n+1 ikkihad x+a ga bo`linmaydi. Haqiqatan, P(-a)=(-a)2n+1-a2n+1=-2a2n+1≠0;
x2n+1-a2n+1 ikkihad x+a ga bo`linadi. Haqiqatan, P(-a)=(-a)2n+1+a2n+1=0;
x2n+a2n ikkihad x+a ga bo`linmaydi. Haqiqatan, P(- a)=a2n+a2n=2a2n≠0;
Bo`lish bajariladigan hollarda bo`linmalarning ko`rinishini aniqlaymiz:
x5-a5=(x-a)(x4+ax3+a2x2+a3x+a4);
x5+a5=(x+a)(x4-ax3+a2x2-a3x+a4);
x6-a6=(x-a)(x5+ax4+a2x3+a3x2+a4x+a5);
x6-a6=(x+a)(x5-ax4+a2x3-a3x2+a4x-a5).
Bulardan ko`rinadiki, bo`linma albatta bir jinsli ko`phad bo`lib, x ning darajalari kamayib, a ning darajalarida o`sish tartibida joylashgan va agar bo`luvchi a+x bo`lsa, koeffitsiyentlar +1 va -1 almashib keladi, agar bo`luvchi x-a bo`lsa, bo`linmada hosil bo`lgan ko`phadning koeffitsiyentlari 1 ga teng bo`ladi. Bu xulosalarni istagan darajali ko`phadlar uchun umumlashtirish mumkin.
1-misol. x5-ax+4 ni x+3 ga bo`lishdagi qoldiq r=4 bo`lsa, a ni toping.
Yechish. (-3)5-a∙(-3)+4=4, bundan a=81.
P(x)=a0xn+a1xn-1+a2xn-2+...+an ko`phadni x-a ikkihadga bo`lishdagi qoldiqni hisoblashning Gorner (Xorner Uilyam (1786-1837) – ingliz matematigi) sxemasi deb ataluvchi usulini ko`rsatamiz.
P(x)=Q(x)(x-a)+r
bo`lsin. Bunda
Q(x)=b0xn-1+b1xn-2+b2xn-3+...+bn-1.
(1) da x ning bir xil darajalari oldidagi koeffitsiyentlarni tenglashtirib quyidagiga ega bo`lamiz:
a0=b0
a1=b1-αb0
a2=b2-αb1
.......
an-1=bn-1-αbn-2
an=r-αbn-1
Bundan ko`rinadiki, b0=a0, bk=αbk-1+ak, k=1,2,..., n-1, r=an+αbn-1.
Bo`linma va qoldiqni hisoblash quyidagi jadval yordamida topiladi.
|
a0
|
a1
|
a2
|
...
|
an-1
|
an
|
α
|
|
αb0+a1
|
αb1+a2
|
...
|
αbn-2+an-1
|
αbn-1+an
|
|
b0=a0
|
b1
|
b2
|
...
|
bn-1
|
r
|
2-misol. x3+4x2-3x+5 ko`phadni Gorner sxemasidan foydalanib, x-1 ga bo`lishni bajaramiz.
Demak, x3+4x2-3x+5=(x-1)(x2+5x+2)+7.
Bezu teoremasidan P(x) ko`phadni ax+b ko`rinishdagi ikkihadga bo`lishda hosil bo`ladigan r qoldiq P(-b/a) ga teng bo`lishi kelib chiqadi.
3-misol. P3(x)=x3-3x2+5x+7 ni 2x+1 ga bo`lishdan hosil bo`lgan qoldiqni toping.
Yechish. Qoldiq r=P3(-1/2)=(-1/3)3-3∙(-1/2)2+5∙(-1/2)+7=29/8 ga teng.
2-teorema. Agar α soni P(x) ko`phadning ildizi bo`lsa, P(x) ko`phad x-a ikkihadgaqoldiqsiz bo`linadi.
Isbot. Bezu teoremasiga ko`ra, P(x) ni x-a ga bo`lishdan chiqadigan qoldiq P(α) ga teng, shart bo`yicha esa P(α)=0. Isbot bajarildi.
Bu teorema P(x)=0 tenglamani yechish masalasini P(x) ko`phadni chiziqli ko`paytuvchilarga ajratish masalasiga keltirish imkonini beradi.
1-natija. Agar P(x) ko`phad har xil α1, ..., αn ildizlarga ega bo`lsa, u (x-α1) ... (x-an) ko`paytmaga qoldiqsiz bo`linadi.
2-natija. n-darajali ko`phad n tadan ortiq har xil ildizga ega bo`la olmaydi.
Isbot. Agar n- darajali P(x) ko`phad n+1 ta har xil α1, ..., αk+1 ildizlarga ega bo`lganda, u n+1-darajalin (x-α1)...(x-αk+1) ko`paytmaga qoldiqsiz bo`linardi. Lekin bunday bo`lishi mumkin emas.
Yuqorida qaralgan teoremalardan foydalanib, Fransua Viyet (fransuz olimi, 1540-1603) tomonidan berilgan hamda P(x)=0 butun algebraik tenglamaning ai haqiqiy koeffitsiyentlari va αi ildizlari orasidagi munosabatni ifodalovchi formulalarni keltiramiz:
1) a2x2+a1x+a0=b(x-α1)(x-α2)=bx2-b(α1-α2)x++bα1α2. Agar x ning bir xil darajalari oldidagi koeffitsiyentlari tenglashtirilsa, b=a2 bo`ladi. Natijada ushbu formulalar topiladi:
α1+α2=-a1/a2, α1α2=a0/a2;
2) shu tartibda P3(x)=a3x3+a2x2+a1x+a0 uchun:
α1+α2+α3=-a2/a3, α1α2+α1α3+α2α3=a1/a3, α1α2α3=-a0/a3 formulalar topiladi.
Hosil qilingan tengliklarning bajarilishi α1 ,..., αn sonlarining Pn(x)=anxn+...+a0 ko`phad ildizlari
Kvadrat tenglama ildizlarini aniqlash
Kvadrat tenglamaning ildizlarini topish vazifasi, boshqa ko'plab vazifalar singari, oson vazifadir. Uni qog’oz va qalam yordamida juda oson yechish mumkin, ammo algoritmni to’gri tanlab dasturini tuzish va undan foydalanish orqali yechimni avtomatlashtirish mumkin. Ushbu laboratoriyada biz shunday dastur algoritmini ko’rib chiqamiz.
Bilamizki, ko’rinishidagi tenglama kvadrat tenglama deyiladi. Ushbu tenglamani yechishning bir necha usullari mavjud. Ammo biz, Diskriminantlar usulidan foydalanamiz. Chunki bu usul dasturlash uchun eng optimal usul hisoblanadi.
Diskriminant D harfi bilan belgilanadi. D= b2-4ac ekanligini esa, maktab kursidan bilamiz.
Diskriminant uchun bir nechta shartlar mavjud:
Agar D> 0 bo'lsa, unda tenglama 2 xil haqiqiy ildizga ega.
Agar D = 0 bo'lsa, unda yagona ildizga ega yoki, ikkala haqiqiy ildiz teng bo'ladi.
Agar D <0 bo'lsa, unda yechimga ega emas yoki, ikkala ildiz ham kompleks sonlardir.
Yechish algoritmi juda oddiy. Diskriminant hisoblanadi, agar u 0 dan katta yoki unga teng bo'lsa, u holda ildizlar quyidagi formula yordamida hisoblanadi:
yoki
Kvadrat tenglama ildizlarini topish algoritmining bloksxemasini quyida ko’rishimiz mumkin.
Yakunlash
Chiqarish: x1, x1
Chiqarish: “Tenglama ildizga ega emas”
D<0
D=b2-4ac
Kiritish: a,b,c
Boshlash
Yo’q ha
Kubik tenglama ildizlarini aniqlash
Kub tenglamaning yechimi:
Ushbu tajriba ishida kubik tenglamani Vieta-Kardano usuli yordamida yechish algoritmi keltirilgan. Dastur faol(0 dan farqli) koeffitsientlar holati uchun yozilgan (ildizlar murakkab bo'lishi mumkin).
Kub tenglamasi quyidagicha yoziladi:
x3+a*x2+b*x+c=0.
Haqiqiy koeffitsientlar bo'lsa, uning ildizlarini topish uchun birinchi navbatda quyidagilar hisoblanadi:
Q=(a2-3b)/9, R=(2a3-9ab+27c)/54.
Bundan tashqari, agar R2t=acos(R/sqrt(Q3))/3,
x1=-2*sqrt(Q)cos(t)-a/3,
x2=-2*sqrt(Q)cos(t+(2*pi/3))-a/3,
x3=-2*sqrt(Q)cos(t-(2*pi/3))-a/3.
R2>=Q3 bo'lgan holatda, bitta (umumiy holat) yoki ikkita (degenerativ holatlar) haqiqiy ildiz mavjud. Haqiqiy ildizdan tashqari, ikkita kompleks ildizi mavjud. Ularni topish uchun quyidagilar hisoblab chiqiladi (Kardano formulasi):
A=-sign(R)[|R|+sqrt(R2-Q3)]1/3,
A!=0 bo’lsa B=Q/A yoki A=0 bo’lganda B=0 .
Haqiqiy ildiz quyidagicha bo'ladi:
x1=(A+B)-a/3.
Kompleks ildizlar:
x2,3=-(A+B)/2-a/3 + i*sqrt(3)*(A-B)/2
Agar A=B bo'lsa, unda kompleks ildizlar haqiqiyga aylanadi:
x2=-A-a/3.
Cardano va Vieta formulalari maxsus funktsiyalardan foydalanishni talab qiladi va agar koeffitsientlari juda ko'p o'zgarmaydigan kub tenglamaning ildizlarini hisoblashning katta seriyasini amalga oshirish kerak bo'lsa, boshqa tez tezkor algoritmdan foydalanish kerak: (Kardano-Vyeta yordamida dastlabki yaqinlashuvni topish bilan) Nyuton usuli yoki boshqa iterativ usullar
Quyida haqiqiy koeffitsientli kub tenglamaning ildizlarini topish dasturi keltirilgan:
Avvalo tenglama koeffitsoentlari :
ko’rinishga keltiriladi.
#include /* for sqrt(), fabs(), pow(), cos(), acos(). */
#include
//#define M_PI (3.141592653589793)
#define M_2PI (2.*M_PI)
using namespace std;
int Cubic(double *x,double a,double b,double c) {
double q,r,r2,q3;
q=(a*a-3.*b)/9.; r=(a*(2.*a*a-9.*b)+27.*c)/54.;
r2=r*r; q3=q*q*q;
if(r2double t=acos(r/sqrt(q3));
a/=3.; q=-2.*sqrt(q);
x[0]=q*cos(t/3.)-a;
x[1]=q*cos((t+M_2PI)/3.)-a;
x[2]=q*cos((t-M_2PI)/3.)-a;
return(3);
}
else {
double aa,bb;
if(r<=0.) r=-r;
aa=-pow(r+sqrt(r2-q3),1./3.);
if(aa!=0.) bb=q/aa;
else bb=0.;
a/=3.; q=aa+bb; r=aa-bb;
x[0]=q-a;
x[1]=(-0.5)*q-a;
x[2]=(sqrt(3.)*0.5)*fabs(r);
if(x[2]==0.) return(2);
return(1);
}
}
int main(){
double a,b,c;
double x[3];
cin>>a>>b>>c;
int d = Cubic(x,a,b,c);
cout<<"Ildizlar soni: "< for(int i = 0; i cout<<"x"< //cout< }
}
Natija:
Laboratoriya topshiriqlari:
1.Kvadrat teglama
Koeffitsiyentlari a=3, b= -6, c=2 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=5, b=7, c=9 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=2, b= -5, c=2 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=6, b=8, c=9 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=-1, b= -6, c=3 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=2, b=9, c=7 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=2, b= 4, c=-5 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=9, b=8, c=13 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=1, b=5, c=3 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=5, b=7, c=9 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=4, b= 6, c=-2 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=8, b=16, c=9 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=2, b= -7, c=4 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=3, b=4, c=5 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=4, b= 6, c=1 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=6, b=8, c=10 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=1, b= 8, c=7 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=12, b=15, c=9 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=4, b= 10, c=4 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=6, b=7, c=10 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=3, b= 10, c=3 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=5, b=11, c=9 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=4, b= -6, c=-4 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=7, b=16, c=10 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=3, b= -8, c=-3 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=8, b=5, c=9 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=2, b= -5, c=2 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=7, b=12, c=9 bo’lgan uchburchak yuzi topilsin.
Koeffitsiyentlari a=2, b= 5, c=-3 bo’lgan kvadrat tenglama ildizlari topilsin; Tomonlari a=10, b=10, c=10 bo’lgan uchburchak yuzi topilsin.
2.Kubik tenglama
Quyidagi tenglamalarning yechimlarini toping:
0>0>
Do'stlaringiz bilan baham: |