Mavzu: chiziqli algebraik tenglamalar sistemasini taqribiy yechish usullari va ularni kompyuterda bajarish reja
Chiziqli algebraik tenglamalar sistemasini taqribiy yechish usullari
Yüklə 27,17 Kb.
|
1 2
mustaqil ish 2|
Chiziqli algebraik tenglamalar sistemasini taqribiy yechish usullari
Haqiqiy o‘zgaruvchili uzluksiz f(x) funksiya berilgan bo‘lsin. f(x)=0 (1) tenglamaning ildizlari yoki y =f(x) funksiyaning nollarini topish talab qilingan bo‘lsin. Algebraik ko‘pxadlar holida tenglamaning, ildizlari kompleks bo‘lishini bilamiz. SHuning uchun masalani yana ham aniqroq qo‘yish lozim. (1) - tenglamaning kompleks tekislikning biror-bir sohasidagi ildizlarini toping degan masala qo‘yish, yana ham aniqrok bo‘ladi. Masalani echish ikki bosqichdan iboratdir. Birinchi bosqichda ildizlarning joylashish sohasi aniqlanadi va ular ajratiladi, ya’ni har birida birta ildizni o‘z ichida saqlovchi sohalar aniqlanadi. Bundan tashqari yana karrali ildizlar va ularning karrali soni aniqlanadi. SHuning bilan birga ildizlarga biror-bir boshlag‘ich yaqinlashish topiladi. Ikkinchi bosqichda boshlang‘ich berilganlardan foydalanib qidirilayotgan ildizni aniqlashtiruvchi iteratsion jarayon tanlanib uning yordamida ildizga etarlicha yaqin son topiladi. Ixtiyoriy tenglamaning ildizlari joylashgan sohani aniqlaydigan biror - bir yaxshi metod yo‘q. Algebraik tenglamalar ildizlarining joylashishini aniqlovchi usullar ancha yaxshi o‘rganilgan va bu metodlarning bir qanchasi algebra kursidan sizga ma’lum. CHiziqlimas tenglamalarni echish metodlari asosan iteratsion bo‘lib, ular qidirilayotgan echimga (ildizga) etarlicha yaqin bo‘lgan boshlang‘ich berilganning ma’lumligini (berilishini) talab qiladilar. Iteratsion metodlarni o‘rganishga o‘tishdan odin (1)-tenglama ildizlarini ajratishning ikkita sodda metodi bilan tanishamiz. Birinchi metod: f(x) funksiyaning xk[a,b], k=0,1,…,n, nuqtalardagi f(xk) qiymatlari topiladi. Agar k-ning biror-bir qiymatida f(xk)f(xk+1)<0 bo‘lsa, unda tenglamaning (xk,xk+1) intervalda tenglamaning eng kamida birta ildizi mavjudligi ma’lum bo‘ladi. Undan so‘ng bu oraliq yana ham kichikroq bo‘laklarga ajratilib ildizlarning joylashishlari aniqlashtiriladi. Haqiqiy ildizlarni ajratishning ancha sodda usullaridan biri biseksiya metodidir. Faraz qilamiz [a,b] oraliqda birta x* ildiz joylashgan bo‘lsin. f(a)>0 , f(b)<0 bo‘lsin. deb, f(x0) - ni hisoblaymiz. Agar f(x0)<0 bo‘lsa, ildiz (a,x0), oraliqda agar f(x0)>0 bo‘lsa ildiz (x0,b) da joylashgan bo‘ladi. Bundan so‘ng ikki intervaldan f(x) chegaralarida turli ishorali qiymatlarni qabul qiladigan intervalni qaraymiz. Bu interval o‘rtasi x1 - ni topamiz. f(x1) - ni hisoblab yuqoridagi jarayonni takrorlaymiz. Natijada o‘zlarida x* ildizni saqlovchi, uzunliklari har gal ikki barobar qisqaradigan intervallarni hosil qilamiz. Jarayon intervalning uzunligi >0 dan kichik bo‘lgandan so‘ng to‘xtatiladi va x* ildizning taqribiy qiymati qilib shu oxirgi intervalning o‘rtasi olinadi. Agar (a,b) intervalda bir qancha ildiz bo‘lsa, ularning qaysisiga yaqinlashishini bilmaymiz. Agar x* ildiz m- karrali bo‘lsa va topilgan bo‘lsa unda boshqa ildizni topish funksiya uchun qaytariladi. 1)Oddiy iteratsiya metodi. Bu metod (1)- tenglamani ekvivalent bo‘lgan x=S(x) (2) tenglamaga almashtirilib iteratsiyalar xk+1=S(xk), k=0,1,… (3) qoida bilan tashkil qilinadilar. Bunda x0 boshlang‘ich yaqinlashish beriladi. Iteratsion ketma-ketlikning yaqinlashishi uchun S(x) funksiya katta rol o‘ynaydi. Bu funksiyani turli usullar bilan aniqlash mumkin. Odatda bu funksiya S(x)=x+(x)f(x) (4) ko‘rinishda aniqlanadi, bunda (x) ildiz qidirilayotgan sohada o‘z ishorasini o‘zgartirmaydigan funksiya. Bu metodning bo‘lganda yaqinlashishni keyinroq ko‘rsatamiz. Xususiy holda (x)==const bo‘lganda (5) relaksatsiya metodi deb aytiladi. Optimal parametrni tanlash uchun relaksatsiya tenglamasida zk = xk – x almashirish bajarib = f(x*+zk) xatolik tenglamasini hosil qilamiz. O‘rta qiymat haqidagi teoremaga asosan f (x*+zk) = f (x*) + zkf (x*+zk) = zkf (x*+zk) tenglikka ega bo‘lamiz. Bu erda (0,1). SHunday qilib relaksatsiya metodining xatoligi uchun = f(x*+zk)zk tenglikka ega bo‘lamiz. 2)Nyuton metodi. Faraz qilamiz boshlang‘ich yaqinlashish x0 ma’lum bo‘lsin. f(x) funksiyani Teylor qatorining kesmasi bilan almashtiramiz. f(x) H1(x) = f(x0) +f (x0)(x-x0) va keyingi yaqinlashish sifatida H1(x) = 0 tenglama ildizini olamiz. Umuman, agar xk yaqinlashish ma’lum bo‘lsa, Nyuton metodi bo‘yicha xk+1 yaqinlashishi (7) kabi aniqlanadi. Nyuton metodi, boshqacha yana urinmalar metodi ham deb aytiladi, chunki xk+1 nuqta f(x) funksiya grafigining (xk,f(xk)) nuqtasida o‘tkazilgan urinmaning abssissa o‘qi bilan kesishgan nuqtasining abssissasidir. Bu metodning yaqinlashishi keyinroq ko‘rsatiladi. Hozir bu metodning o‘ziga xos xususiyatlarini bayon etamiz. Birinchidan metod kvadratik yaqinlashishga ega, ya’ni keyingi qadamdagi yaqilashish xatoligi oldingi qadamdagi xatolikning kvadratiga proporsional: xk+1 - x* = O((xk - x*)2). Ikkinchidan metodning bunday yaqinlashishiga, boshlang‘ich yaqinlashishning ildizga etarlicha yaqin bo‘lgandagina kafolat bersa bo‘ladi. Agar boshlang‘ich yaqinlashish noqulay tanlangan bo‘lsa, metod yo sekin yaqinlashadi, yo umuman yaqinlashmasligi mumkin. 3)O‘zgartirilgan Nyuton metodi. Agar f(x) hosilaning qiymatini ko‘p marta hisoblashdan qutilmoqchi bo‘lsalar, unda (8) formuladan foydalanadilar. Bu metod boshlang‘ich yaqinlashishga uncha ko‘p talab qo‘ymaydi, lekin u sekin, faqat birinchi tartibli yaqinlashadi. (10) – metod bo‘lganda nolga bo‘lish sodir bo‘lmasligiga kafolat beradi. 4)Kesuvchilar metodi Bu metod Nyuton metodidan f '(xk) ni chekli ayirma bilan almashtirishdan hosil bo‘ladi. Natijada (9) ikki qadamli iteratsion metod hosil bo‘ladi. (9) - metodda oldin ikkita boshlang‘ich x0 , x1 yaqinlashishlarni berishga to‘g‘ri keladi. Bu metodning geometrik talqini quyidagidan iborat: (xk-1,xk) oraliqda y=f(x) funksiya grafigi (xk-1 , f(xk-1)) va (xk, f(xk)) nuqtalardan o‘tuvchi to‘g‘ri chiziq bilan almashtirilib uning abssissa o‘qi bilan kesishgan nuqtasi keyingi yaqinlashish sifatida olinadi. 4)Interpolyasiya metodi. Interpolyasiya metodlarining asosiy g‘oyasi f(x) funksiyani bu funksiyaning interpolyasion ko‘phadi bilan almashtirib bu interpolyasion ko‘phad ildizlarini aniqlashdan iborat. Birinchi tartibli interpolyasion metod, bu kesuvchilar metodidan iborat. Ikkinchi tartibli interpolyasion metod parabolalar metodi deb aytiladi. Nyuton metodi ermit interpolyasion metodidan kelib chiqadi. Parabolalar metodining formulalarini keltirib chiqaramiz. Buning uchun xk-2,xk-1,xk yaqinlashishlarni aniqlab Nyutonning ikkinchi tartibli interpolyasion P2(x)=f(x)+(x-xk)f(xk,xk-1)+(x-xk)(x-xk-1)f(xk,xk-1,xk-2), ko‘phadini quramiz. zk = x-xk deb belgilab az2+bz+c=0, (10) bu erda a=f(xk,xk-1,xk-2), b=f(xk,xk-1)+(xk-xk-1)f(xk,xk-1,xk-2), c=f(xk) tenglamani hosil qilamiz. (10)- tenglamani z1 va z2 ildizlarini topib x(1)=xk+z1 , x(2)=xk+z2 qiymatlarini hosil qilamiz. Keyingi yaqinlashish sifatida x(1) , x(2) lardan xk ga yaqin bo‘lganini olamiz. Parabola metodi kompleks ildizlarni topish uchun qulaydir. 5)Teskari interpolyasiyadan foydalanish f(x) ga teskari bo‘lgan x=(y) funksiyani interpolyasiyalash bilan bir qancha iteratsion metodlarni hosil qilish mumkin.
6)Oddiy iteratsiya metodining yaqinlashishi. f(x)=0 (1) tenglamani ekvivalent x=S(x) (2) ko‘rinishda yozamiz va x0 dastlabki yaqinlashishni tanlab olib xk+1=S(xk), k=0,1,… (3) oddiy iteratsiyani qaraymiz. (3)-iteratsiya yaqinlashadi deb aytiladi, agar {xk} ketma-ketlik k, limitga ega bo‘lsa. Quyidagi teoremada (2)-tenglamaning echimi mavjudligi va yagonaligiga kafolat beruvchi shartlar bayon qilinadi. Agar to‘plamning ixtiyoriy x , x nuqtalari uchun (4) tengsizlik bajarilsa S(x) funksiya to‘plamda Lipщits shartini qanoatlantirdi deb aytiladi (yoki lipщits uzluksiz). Kelajakda x lar to‘plami sifatida Ur(a) = (5) markazi a- da bo‘lgan uzunligi 2r ga teng kesma qaraladi. Teorema. Agar S(x) Ur(a) kesmada q(0,1) o‘zgarmasli lipщits uzluksiz bo‘lib, (6) bajarilsa, unda (2)- tenglama Ur(a) da yagona x* echimga ega bo‘lib, (3)-iteratsion ketma-ketlik ixtiyoriy x0Ur(a) uchun x* ga yaqinlashadi. Xatolik uchun (7) (tengsizlik) baho o‘rinli bo‘ladi. Isbot. Eng avval xkUr(a) k=1,2,.. ekanligini isbot qilamiz. Faraz qilamiz xjUr(a) bo‘lsin, xj+1Ur(a) ekanligini isbot qilamiz. tenglikdan ekanligi ma’lum bo‘ladi. Bundan lipщits - uzluksizlikni, induksiya farazini va (6)- ni inobatga olib ya’ni xj+1Ur(a) ekanligini hosil qilamiz. Endi ikki qo‘shni xj+1 va xj yaqinlashishlar orasidagi farqni baholaymiz. va barcha xj lar Ur(a) dan bo‘lganligi uchun yoki
tengsizlik hosil bo‘ladi. (8)- baho {xk} ketma-ketlikni fundamental ekanligini ko‘rsatishga imkon beradi. Haqiqatdan ham p ixtieriy natural son bo‘lsin. Unda (8)- ga asosan ya’ni (9) bu tengsizlikdan k , o‘ng tomoni nolga intiladigan bo‘lganligi uchun va p- ga bog‘liq bo‘lmaganligi uchun {xk} ning fundamentalligi kelib chiqadi. Demak (3)- da limitga o‘tib va S(x) funksiyaning uzluksizligini hisobga olib x*=S(x*) ekanligiga, ya’ni x* ildiz ekanligiga ishonch hosil qilamiz. Faraz qilamiz x* (2)- ning Ur(a)- ga tegishli boshqa biror bir ildizi bo‘lsin. Unda |x*-x*'|=|S(x*)-S(x*')| va teoremaning shartiga ko‘ra |x*-x*'| q|x*-x*'|. Bunda q<1 bo‘lganligi uchun, oxirgi tengsizlik x* = x*' bo‘lgandagina bajariladi, ya’ni echim birdan-bir ekanligi kelib chiqadi. (7)- tengsizlikni isbot qilamiz. (3)- munosabatdan xk+1 - x* = S(xk) - S(x*) xk va x*Ur(a) bo‘lganligi uchun |xk+1-x*| q|xk-x*| hosil bo‘ladi. Bu tengsizlik barcha k=0,1,2,... uchun bajariladi. SHuning uchun 1-Izoh. Agar biror bir iteratsion metod uchun bajarilsa, bunda qM1 k-ga bog‘liqmas bo‘lsa, unda iteratsion metod chiziqli q maxrajli geometrik progressiya tezligida yaqinlashadi deb aytiladi. 2-Izoh. (9) - da k- ni tanlab olib p- ni cheksizga intiltiramiz, unda hosil bo‘ladi. Bu tengsizlikning o‘ng tomonida x1 va x0 yaqinlashishlar turadi, q-ma’lum son. SHu sababli bu tengsizlikdan iteratsiya jarayonini to‘xtatish uchun foydalanish qulaydir. 1-Natija: Agar barchaxUr(a) uchun (12) bajarilib, (6) -shart o‘rinli bo‘lsa va x0Ur(a) bo‘lsa, (2)- tenglama birdan bir x*Ur(a) echimga ega, (3)- metod yaqinlashadi va (7)- baho o‘rinlidir. Haqiqatdan ham ,(12)-dan 2- Natija. Faraz qilamiz (2)- tenglama x*- echimga ega bo‘lsin, S(x) funksiya Ur(x*) = {x : |x-x*| r} (13) kesmada uzluksiz differensiallanuvchi va |S'(x*)|<1 bo‘lsin. Unda shunday > 0 mavjudki Ur(x*) kesmada (2)- tenglama boshqa ildizga ega bo‘lmaydi va faqat x0Ur(x*) bo‘lganda (3)- metod yaqinlashadi. 8)Nyuton metodining yaqinlashishi. Oddiy haqiqiy ildiz. Faraz qilamiz f(x)=0 (1) tenglama oddiy haqiqiy x* ildizga ega bo‘lsin, f(x*)=0 va f'(x*) 0 bo‘lsin. Faraz qilamiz f(x) funksiya x* ildizning etarlicha yaqin atrofida ikki marta uzluksiz hosilalarga ega bo‘lsin. (2) Nyuton metodini tadqiq etamiz. Eng avval (2)- ni oddiy iteratsiya metodining xususiy holi sifatida qaraymiz: (3) (4) Oldin, biz (3)- metodning yaqinlashishi uchun ildizning etarlicha yaqin atrofida (5) tengsizlikning bajarilishi etarli ekanligini ko‘rsatgan edik. (4)- funksiya uchun munosabat o‘rinli. Agar x*, f(x) ning ildizi bo‘lsa, unda S(x*)=0 bo‘ladi. SHu sababli ildizning shunday atrofi borki (5) - tengsizlik bajariladi. Demak x0 boshlang‘ich yaqinlashishni shunday tanlab olish mumkinki Nyuton metodi yaqinlashadi. Bu yaqinlashish oddiy yaqinlashish bo‘lmasdan u aslida kvadratik yaqinlashishdir. Quyidagi teorema Nyuton metodining kvadratik yaqinlashuvchi ekanligini ko‘rsatadi. 1-teorema. Faraz qilamiz x* (1)-tenglamaning oddiy haqiqiy ildizi bo‘lib Ur(x*)={x : |x-x*| atrofda bo‘lsin. Faraz qilamiz f(x) , Ur(x*) atrofda uzluksiz va (6) bo‘lib , (7) bo‘lsin. Unda agar x0Ur(x*) bo‘lsa, (2)- Nyuton metodi yaqinlashadi va xatolik uchun (8) baho o‘rinli , bunda Yüklə 27,17 Kb. Dostları ilə paylaş:
|
1 2