4-tajriba ishi mavzu: Algoritmlarni loyihalash. Funksiyalarning qiymatini xisoblashning Gorner algoritmi. Kvadrat va kubik tenglama ildizlarini aniqlash Ishdan maqsad

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)=a₀xⁿ+a₁x^n-1+...+a_n-1x+a_n(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) x<sup>5</sup>+x+20 ni x+2 ga bo`lishdan chiqadigan qoldiq r=(-2)⁵+(-2)+20=-14; 2) x⁵+x+34 ni x+2 ga bo`lishdan chiqadigan qoldiq r=(-2)<sup>5</sup>+(-2)+34=0.
Demak, x=-2 soni shu ko`phadning ildizi.
Natijalar. n€N bo`lganda:

1. 
   xⁿ-aⁿ ikkihad x-a ga bo`linadi. Haqiqatan, P(a)=aⁿ-aⁿ=0;
   
2. 
   xⁿ+aⁿ ikkihad x-a ga bo`linmaydi. Haqiqatan, P(a)=aⁿ+aⁿ=2xⁿ≠0;
   
3. 
   x²ⁿ-a²ⁿ ikkihad x+a ga bo`linadi. Haqiqatan, P(-a)=(-a)²ⁿ-a²ⁿ=0;
   
4. 
   x²ⁿ⁺¹-a²ⁿ⁺¹ ikkihad x+a ga bo`linmaydi. Haqiqatan, P(-a)=(-a)²ⁿ⁺¹-a²ⁿ⁺¹=-2a²ⁿ⁺¹≠0;
   
5. 
   x²ⁿ⁺¹-a²ⁿ⁺¹ ikkihad x+a ga bo`linadi. Haqiqatan, P(-a)=(-a)²ⁿ⁺¹+a²ⁿ⁺¹=0;
   
6. 
   x²ⁿ+a²ⁿ ikkihad x+a ga bo`linmaydi. Haqiqatan, P(- a)=a²ⁿ+a²ⁿ=2a²ⁿ≠0;
   

Bo`lish bajariladigan hollarda bo`linmalarning ko`rinishini aniqlaymiz:
x<sup>5</sup>-a<sup>5</sup>=(x-a)(x<sup>4</sup>+ax<sup>3</sup>+a<sup>2</sup>x<sup>2</sup>+a<sup>3</sup>x+a<sup>4</sup>);
x<sup>5</sup>+a<sup>5</sup>=(x+a)(x<sup>4</sup>-ax<sup>3</sup>+a<sup>2</sup>x<sup>2</sup>-a<sup>3</sup>x+a<sup>4);</sup>
x<sup>6</sup>-a<sup>6</sup>=(x-a)(x<sup>5</sup>+ax<sup>4</sup>+a<sup>2</sup>x<sup>3</sup>+a<sup>3</sup>x<sup>2</sup>+a<sup>4</sup>x+a<sup>5</sup>);
x<sup>6</sup>-a<sup>6</sup>=(x+a)(x<sup>5</sup>-ax<sup>4</sup>+a<sup>2</sup>x<sup>3</sup>-a<sup>3</sup>x<sup>2</sup>+a<sup>4</sup>x-a<sup>5</sup>).
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. x<sup>5</sup>-ax+4 ni x+3 ga bo`lishdagi qoldiq r=4 bo`lsa, a ni toping.
Yechish. (-3)<sup>5</sup>-a∙(-3)+4=4, bundan a=81.
P(x)=a<sub>0</sub>x<sup>n</sup>+a<sub>1</sub>x<sup>n-1</sup>+a<sub>2</sub>x<sup>n-2</sup>+...+a<sub>n</sub> 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)=b<sub>0</sub>x<sup>n-1</sup>+b<sub>1</sub>x<sup>n-2</sup>+b<sub>2</sub>x<sup>n-3</sup>+...+b<sub>n-1</sub>.
(1) da x ning bir xil darajalari oldidagi koeffitsiyentlarni tenglashtirib quyidagiga ega bo`lamiz:
a₀=b₀
a₁=b₁-αb₀
a₂=b₂-αb₁
.......
a_n-1=b_n-1-αb_n-2
a_n=r-αb_n-1
Bundan ko`rinadiki, b<sub>0</sub>=a<sub>0</sub>, b<sub>k</sub>=αb<sub>k-1</sub>+a<sub>k</sub>, k=1,2,..., n-1, r=a<sub>n</sub>+αb<sub>n-1</sub>.
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. x³+4x²-3x+5 ko`phadni Gorner sxemasidan foydalanib, x-1 ga bo`lishni bajaramiz.

	1	4	-3	5
1	1	5	2	7

Demak, x³+4x²-3x+5=(x-1)(x²+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. P<sub>3</sub>(x)=x<sup>3</sup>-3x<sup>2</sup>+5x+7 ni 2x+1 ga bo`lishdan hosil bo`lgan qoldiqni toping.
Yechish. Qoldiq r=P<sub>3</sub>(-1/2)=(-1/3)<sup>3</sup>-3∙(-1/2)<sup>2</sup>+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 α<sub>1</sub>, ..., α<sub>n</sub> ildizlarga ega bo`lsa, u (x-α₁) ... (x-a_n) 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 α<sub>1</sub>, ..., α<sub>k+1</sub> ildizlarga ega bo`lganda, u n+1-darajalin (x-α₁)...(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 a<sub>i</sub> haqiqiy koeffitsiyentlari va α<sub>i</sub> ildizlari orasidagi munosabatni ifodalovchi formulalarni keltiramiz:
1) a<sub>2</sub>x<sup>2</sup>+a<sub>1</sub>x+a<sub>0</sub>=b(x-α<sub>1</sub>)(x-α<sub>2</sub>)=bx<sup>2</sup>-b(α<sub>1</sub>-α<sub>2</sub>)x++bα<sub>1</sub>α<sub>2</sub>. Agar x ning bir xil darajalari oldidagi koeffitsiyentlari tenglashtirilsa, b=a<sub>2</sub> bo`ladi. Natijada ushbu formulalar topiladi:
α₁+α₂=-a₁/a₂, α₁α₂=a₀/a₂;
2) shu tartibda P₃(x)=a₃x³+a₂x²+a₁x+a₀ uchun:
α₁+α₂+α₃=-a₂/a₃, α₁α₂+α₁α₃+α₂α₃=a₁/a₃, α₁α₂α₃=-a₀/a₃ formulalar topiladi.
Hosil qilingan tengliklarning bajarilishi α₁ ,..., α_n sonlarining P_n(x)=a_nxⁿ+...+a₀ 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= b²-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: x₁, x₁

Chiqarish: “Tenglama ildizga ega emas”




D<0

D=b²-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:
x³+a*x²+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(R²-Q³)]^1/3,
A!=0 bo’lsa B=Q/A yoki A=0 bo’lganda B=0 .
Haqiqiy ildiz quyidagicha bo'ladi:
x₁=(A+B)-a/3.
Kompleks ildizlar:
x_2,3=-(A+B)/2-a/3 + i*sqrt(3)*(A-B)/2
Agar A=B bo'lsa, unda kompleks ildizlar haqiqiyga aylanadi:
x₂=-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

1. 
   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.
   
2. 
   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.
   
3. 
   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.
   
4. 
   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.
   
5. 
   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.
   
6. 
   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.
   
7. 
   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.
   
8. 
   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.
   
9. 
   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.
   
10. 
    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.
    
11. 
    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.
    
12. 
    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.
    
13. 
    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.
    
14. 
    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.
    
15. 
    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: