Muhammad al xorazmiy nomidagi

Download 20.63 Kb.
Sana	13.04.2024
Hajmi	20.63 Kb.
	#194344

Bog'liq
iteratsion yechish
1. Anketa (talabalar), 3-mavzu, conference, 12 labaratoriya ishi, Маълумотлар тузилмаси ва алгоритмлар узб, Abduvositaka, Saralash algoritmlari, Akademik yozuv 2 Omonboyev Rashidbek 12, kontakt hodisalar, golosariy, Operatsion tizimlar uz, 1 - lesson (internet), 2-маруза мавзуси Симулятор, dars tahlili, 6666666666666666666666666666666666666

Qabul qildi: Xalilov D. A

RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL – XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
FARG‘ONA FILIALI

Komyuter injiniringi yo‘nalishi

711-21– guruh talabasi

Iqboljon Hamidovning

“Algoritmlarni loyihalash”

fanidan tayyorlagan
Mustaqil ishi

Topshirdi: Iqboljon Hamidov
Qabul qildi: Xalilov D. A

MAVZU: CHIZIKLI ALGEBRAIK TENGLAMALAR SISTEMASINI YECHISH.GAUSS METODI

REJA:

Asosiy qism:
Cizikli algebraik tenglamalar sistemasini yechishda iteratsion metodlar.Oddiy itaratsia metodi.
Chizikli algebraik tenglamalar sistemasini yechishda Gauss metodi.
Xulosa;
Foydalanilgan adabiyotlar.

Chizikli algebraik tenglamalar sistemasini yechishda iteratsion metodlar.Oddiy itaratsia metodi Iteratsion metodlarni qurishda vektor va matritsalaming norma- lari va limitlari tushunchalari qatnashadi. Shu sababli ular haqidagi ma'lumotlami keltiramiz. x vektorning normasi deb, quyidagi uch shartni qanoatlantiruvchi haqiqiy ‖𝑥‖ songa aytiladi. 1) ‖𝑥‖ ≤ 0 va x = 0 bo‘lgandagina ‖𝑥‖ = 0; 2) har qanday 𝛼 son uchun ‖𝛼𝑥‖ = |𝛼|‖𝑥‖ ; 3) |x+y| ≤ ||x|| + ||y|| uchburchak tengsizligi. x = (𝑥1, 𝑥2, 𝑥3, … 𝑥𝑛 ) 1vektoming yuqoridagi shartlami qanoatlantiruvchi va ko‘proq ishlatiladigan normalardan uchtasini keltiramiz. 1. Kubik norma: ‖𝑥‖1 = max 1≤𝑖≤𝑛 |𝑥𝑖 |. 2. Oktaedrik norma: ‖𝑥‖2=∑ |𝑥𝑖 | 𝑛 𝑖=1 . 3. Sferiknorma: ‖𝑥‖3 = √∑ |𝑥𝑖 | 𝑛 2 𝑖=1 Bu normalar uchun birinchi va ikkinchi shartlaming bajarilishi bevosita ko‘rinib turibdi. Uchinchi shartni tekshiramiz: Birinchi norma uchun: ‖𝑥 + 𝑦‖1 = max 1≤𝑖≤𝑛 |𝑥𝑖 + 𝑦𝑖 | ≤ max 1≤𝑖≤𝑛 |𝑥𝑖 | + max 1≤𝑖≤𝑛 |𝑦𝑖 | = ‖𝑥‖1 + ‖𝑦‖1. Ikkinchi norma uchun: ‖𝑥 + 𝑦‖2 = ∑|𝑥𝑖 + 𝑦𝑖 | ≤ ∑|𝑥𝑖 | +∑|𝑦𝑖 | = ‖𝑥‖2 + ‖𝑦‖2. 𝑛 𝑖=1 𝑛 𝑖=1 𝑛 𝑖=1 Uchinchi norma uchun Koshi-Bunyakovskiy tengsizligidan. ‖𝑥 + 𝑦‖3 = √∑|𝑥𝑖 + 𝑦𝑖 | 2 ≤ 𝑛 𝑖=1 √∑|𝑥𝑖 | 2 𝑛 𝑖=1 + √∑|𝑦𝑖 | 2 𝑛 𝑖=1 = ‖𝑥‖3 + ‖𝑦‖3. ga ega bo‘lamiz. A kvadrat matritsaning normasi deb, quyidagi shartlami qanoatlantiruvchi haqiqiy songa aytiladi: 1) ‖𝐴‖ ≥ 0 va A = 0 bolganida ‖𝐴‖=0; 2) ixtiyoriy 𝛼 soni uchun ‖𝛼𝐴‖ = |𝛼|‖𝐴‖; 3) ‖𝐴 + 𝐵‖ ≤ ‖𝐴‖ + ‖𝐵‖; 4) ‖𝐴 ∙ 𝐵‖ ≤ ‖𝐴‖ ∙ ‖𝐵‖, xususan ‖𝐴 𝑝‖ ≤ ‖𝐵 𝑝‖, p- natural son, Agar har qanday kvadrat matritsa A uchun va oichami matritsa tartibiga teng bolgan ixtiyoriy x vektor uchun ‖𝐴𝑥‖ ≤ ‖𝐴‖ ∙ ‖𝑥‖ (1) tengsizlik bajarilsa, u holda matritsa normasi vektoming berilgan normasi bilan moslashgan deyiladi. Har qanday A matritsa uchun Ax vektor normasining uzluksizligiga ko‘ra [7] ‖𝐴‖ = max ‖𝑥‖=1 ‖𝐴𝑥‖ (2) tenglikda maksimumga erishiladi, ya’ni shunday 𝑥 (0)vektor topiladiki, ‖𝑥 (0)‖ = 1 va ‖𝐴𝑥(0)‖ = ‖𝐴‖ tenglik bajariladi. (2) tenglik bilan kiritilgan matritsa normasi vektoming berilgan normasiga bo‘ysungan deyiladi. Quyidagi teorema o'rinli bo‘ladi [7]. Teorema. Matritsaning bo‘ysungan normasi: 1) norma ta’rifining to‘rtta shartini qanoatlantiradi; 2) vektoming berilgan normasiga moslashgan; 3) vektoming berilgan normasiga moslangan boshqa har qanday normasidan katta emas. Vektorlarning yuqorida kiritilgan normalariga bo‘ysungan matritsa normalari mos ravishda quyidagilardan iborat: ‖𝐴‖1 = max 1≤𝑖≤𝑛 ∑ |𝑎𝑖𝑘| 𝑛 𝑖=1 −kubik norma, (3) ‖𝐴‖2 = max 1≤𝑘≤𝑛 ∑ |𝑎𝑖𝑘| − 𝑛 𝑖=1 oktaedrik norma, (4) ‖𝐴‖3 = √𝜆1 − sferik norma, (5) bu yerda 𝜆1, A'A matritsaning eng katta xos soni. Faraz qilaylik, 𝑥 𝑘 = (𝑥1 (𝑘) , 𝑥2 (𝑘) , ⋯ 𝑥𝑛 (𝑘) ) 1 (𝑘 = 1,2, ⋯ ) vektorlar ketma-ketligi berilgan bo‘lsin. Agar n ta chekli 𝑥𝑖 = lim 𝑘→∞ 𝑥𝑖 (𝑘) (𝑖 = 1,2, ⋯ , 𝑛) limitlar mavjud bo‘lsa, u holda 𝑥 = (𝑥1, 𝑥2, ⋯ 𝑥𝑛 ) vektor {𝑥 (𝑘) } vektorlar ketma-ketligining limiti deyiladi va bu ketma-ketlikning o‘zi x vektorga yaqinlashadi deyiladi. Shu kabi 𝐴 (𝑘) = [𝑎𝑖𝑗 (𝑘) ] (𝑖,𝑗 = 1,2, … , 𝑛; 𝑘 = 1,2, … ) matritsalar ketma-ketligi berilgan bo‘iib, 𝑛 2 ta chekli 𝑎𝑖𝑗 = lim 𝑘→∞ 𝑎𝑖𝑗 (𝑘) limitlar mavjud bo‘lsa, u holda 𝐴 = [𝑎𝑖𝑗] matritsa {𝐴 (𝑘) } matritsalar ketmaketligining limiti deyiladi. Bu ta’rifga ko‘ra, agar matritsalardan tuzilgan cheksiz qator qismiy yig‘indilari ketma-ketligining limiti mavjud bo‘lsa, u holda qator yaqinlashuvchi deyiladi. Bu limit qatoming yig‘indisi deyiladi. Vektor normasi tushunchasiga asosan vektorlar ketma-ketligining yaqinlashishini quydagicha ta'riflash mumkin.
Oddiy iteratsiya metodi Faraz qilaylik, Ax = b (1) chiziqli algebraik tenglamalar sistemasi biror usul bilan x = Bx + c (2) ko'rinishiga keltirilgan bolsin. Ixtiyoriy 𝑥 (0) vektor olib uni boshlang‘ich yaqinlashish deylik. Agar keyingi yaqinlashishlar 𝑥 (𝑘) = 𝐵𝑥 𝑘 + 𝑐 , 𝑘 = 0,1, … (3) rekurrent formulalar yordamida aniqlansa, bunday metod oddiy iteratsiya metodi deyiladi. Agar (3) ketma-ketlikning limiti x* mavjud bo‘lsa, bu limit (2) sistemaning (shu bilan (1) sistemaning ham) yechimi bo‘ladi. Haqiqatan ham (3) da limitga o‘tsak, 𝑥 ∗ = 𝐵𝑥 ∗ kelib chiqadi. Oddiy iteratsiya metodining yaqinlashishini quyidagi teorema ko‘rsatadi. Teorema . (3) oddiy iteratsion jarayon ixtiyoriy boshlang‘ich 𝑥 (0) da yaqinlashuvchi bo‘lishi uchun B matritsaning barcha xos sonlarining modullari birdan kichik bo‘lishi zarur va yetarli Isboti. Zarurligi. Faraz qilaylik, lim 𝑘→∞ 𝑥 (𝑘) = 𝑥 ∗ mavjud bo‘lsin. U holda 𝑥 ∗ = 𝐵𝑥 ∗ . Bundan (3)ni ayirsak, quyidagilarga ega bo‘lamiz: 𝑥 ∗ − 𝑥 (𝑘) = 𝐵(𝑥 ∗ − 𝑥 𝑘−1 ) = 𝐵 2 (𝑥 ∗ − 𝑥 (𝑘−2) ) = ⋯ = 𝐵 𝑘 (𝑥 ∗ − 𝑥 (0) ) Endi 𝑥 ∗ − 𝑥 (𝑘) vektor k ga bog‘liq bolmaganligi uchun 𝑥 ∗ − 𝑥 (𝑘) = 𝐵 𝑘 (𝑥 ∗ − 𝑥 (0) tenglikda 𝑘 → ∞ limitga o‘tsak, lim 𝑘→∞ 𝐵 𝑘 = 0 kelib chiqadi, bundan 1-lemmaga asosan B matritsaning barcha xos sonlarining modullari birdan kichikligi kehb chiqadi. Yetarliligi. (3) orqali aniqlangan barcha yaqinlashishlami boshlan- g‘ich yaqinlashish 𝑥 (0) va c vektorlar orqali ifodalaymiz: 𝑥 (𝑘) = 𝐵𝑥 (𝑘−1) + 𝑐 = 𝐵(𝐵𝑥 (𝑘−2) + 𝑐) + 𝑐 = 𝐵 2𝑥 (𝑘−2) + (𝐸 + 𝐵)𝑐 = ⋯ = 𝐵 𝑘𝑥 (0) + (𝐸 + 𝐵 + 𝐵 2 + ⋯ + 𝐵 𝑘−1 )𝑐 Endi, faraz qilaylik B ning xos sonlarining moduli birdan kichik boTsin. U holda 1-lemmaga ko‘ra, lim 𝑘→∞ 𝐵 𝑘 = 0, 2-teoremaga asosan lim 𝑘→∞ (𝐸 + 𝐵 + 𝐵 2 + ⋯ + 𝐵 𝑘−1 ) = (𝐸 − 𝐵) −1 tengliklar o‘rinli boladi. Demak, 𝑥 (0) qanday bolishidan qat’iy nazar 𝑥 (𝑘) yaqinlashuvchi ketma-ketlik ekan. Bu teorema nazariy jihatdan foydali, lekin amaliyot uchun yaramaydi. Quyidagi teorema B matritsaning elementlari orqali iteratsion jarayon yaqinlashishining yetarli shartini ko‘rsatadi.
Chizikli algebraik tenglamalar sistemasini yechishda Gauss metodi Bu metod bir necha hisoblash sxemalariga ega. Biz Gaussning kompakt sxemasigina bilan tanishamiz. Quyidagi sistema berilgan bo‘lsin: { 𝑎11𝑥1 + 𝑎12𝑥2 + … + 𝑎1𝑛𝑥𝑛 = 𝑎1,𝑛+1 𝑎21𝑥1 + 𝑎22𝑥2 + … + 𝑎2𝑛𝑥𝑛 = 𝑎2,𝑛+1 … … … … … … … … … … … … … … … … … … . . 𝑎𝑛1𝑥1 + 𝑎𝑛2𝑥2 + … + 𝑎𝑛𝑛𝑥𝑛 = 𝑎𝑛,𝑛+1 (1) Faraz qilaylik, 𝑎11 ≠ 0 (yetakchi element) bo‘lsin deb, sistemaning birinchi tenglamasidan 𝑥1 + 𝑏12 (1) 𝑥2 + 𝑏13 (1) 𝑥3 + ⋯ + 𝑏1𝑛 (1) 𝑥𝑛 = 𝑏1,𝑛+1 (1) (2) ni hosil qilamiz, bu yerda 𝑏 (1) 1𝑗 = 𝑎𝑖𝑗 𝑎11 ⁄ (2) dan foydalanib, (1) sistemaning qolgan tenglamalaridan x\ noma’lumni yo‘qotish mumkin, ya’ni (2)ni ketma-ket 𝑎21, 𝑎31, … . , 𝑎𝑛1 larga ko‘paytirib, mos ravishda, ikkinchi, uchinchi va h.k. tenglamalridan ayirsak, natijada quyidagi sistema hosil bo‘ladi: { 𝑎22 (1)𝑥2 + 𝑎23 (1)𝑥3 + ⋯ + 𝑎2𝑛 (1)𝑥𝑛 = 𝑎2,𝑛+1 (1) … … … … … … … … … … … … … … … … … … … … 𝑎𝑛2 (1)𝑥2 + 𝑎𝑛3 (1)𝑥3 + ⋯ + 𝑎𝑛𝑛 (1)𝑥𝑛 = 𝑎𝑛,𝑛+1 (1) (3) bu yerda 𝑎𝑖𝑗 (1) = 𝑎𝑖𝑗 − 𝑎𝑖1𝑏1𝑗 (1) (𝑖,𝑗 ≥ 2). (3) tenglamalar sistemasida 𝑎22 (1) ≠ 0deb, yuqoridagidek jarayonni bajarsak, { 𝑎33 (2)𝑥3 + ⋯ + 𝑎3𝑛 (2)𝑥𝑛 = 𝑎3,𝑛+1 (2) … … … … … … … … … … … … … … … … 𝑎𝑛3 (2)𝑥3 + ⋯+ 𝑎𝑛𝑛 (2)𝑥𝑛 = 𝑎𝑛,𝑛+1 (2) sistemaga kelamiz, bu yerda 𝑎𝑖𝑗 (2) = 𝑎𝑖𝑗 − 𝑎𝑖2𝑏2𝑗 (2) (𝑖,𝑗 ≥ 3). Shu jarayonni n marta bajarish mumkin bo‘lgan bo‘lsa, (1) tenglamalar sistemasi { 𝑥1 + 𝑏12 (1) 𝑥2 + 𝑏13 (1) 𝑥3 + ⋯ + 𝑏1𝑛 (1) 𝑥𝑛 = 𝑏1,𝑛+1 (1) 𝑥2 + 𝑏23 (2) 𝑥3 + ⋯ + 𝑏2𝑛 (2) 𝑥𝑛 = 𝑏2,𝑛+1 (2) … … … … … … … … … … … … … … … … … … … … … 𝑥𝑛 = 𝑏𝑛,𝑛+1 (𝑛) (4) ko'rinishga keladi. Bu tenglamalar sistemasidan ketma-ket 𝑥𝑛, 𝑥𝑛−1, … , 𝑥1 lar aniqlanadi. (1) dan qadamma-qadam (4) ko‘rinishga kelish Gauss metodining to‘g‘ri yo‘li, (4) dan ketma-ket 𝑥𝑛, 𝑥𝑛−1, … , 𝑥1larni aniqlash Gauss metodining teskari yo‘li deyiladi. Faraz qilaylik, Gauss metodida to‘g‘ri yo‘lning m(m< n) ta qadami bajarilishi mumkin bo‘lgan bo‘lsin, u holda quyidagiga ega bo‘lamiz: { 𝑥𝑚 + 𝑏𝑚,𝑚+1 (𝑚) 𝑥𝑚+1 + ⋯ + 𝑏𝑚𝑛 (𝑚) 𝑥𝑛 = 𝑏𝑚,𝑛+1 (𝑚) 𝑎𝑚+1,𝑚+1 (𝑚)𝑥𝑚+1 + ⋯ + 𝑎𝑚+1,𝑛 (𝑚)𝑥𝑛 = 𝑎𝑚+1,𝑛+1 (𝑚) … … … … … … … … … … … … … … … … … … … … … 𝑎𝑛,𝑚+1 (𝑚)𝑥𝑚+1 + ⋯ + 𝑎𝑛,𝑛 (𝑚)𝑥𝑛 = 𝑎𝑛,𝑛+1 (𝑚) (5) Bu yerda 𝑏 (𝑚) 𝑚𝑗 = 𝑎 (𝑚) 𝑚𝑗 𝑎 (𝑚) 𝑚𝑚 , 𝑎 (𝑚) 𝑖𝑗 = 𝑎 (𝑚−1) 𝑖𝑗 − 𝑎 (𝑚−1) 𝑖𝑚𝑏 (𝑚) 𝑚𝑗, (𝑖,𝑗 ≥ 𝑚 + 1) Gauss metodida bajarilishi mumkin bo'lgan qadamlaming soni m ga teng bo'lgan bo‘lsa, bu shuni anglatadiki, (5) sistemaning ikkinchi tenglamasidan boshlab yetakchi elementni ajratish mumkin emas, chunki barcha 𝑎 (𝑚) 𝑖𝑗(𝑖,𝑗 = 𝑚 + 1, … , 𝑛) lar nolga teng. Agar (5) da 𝑎 (𝑚) 𝑖𝑛+1 (𝑖,𝑗 = 𝑚 + 1, … , 𝑛) nolga teng bo‘lsa, (5) bitta tenglamadan iborat bo‘ladi. Endi barcha qadamdagi birinchi tenglamalami birlashtirib { 𝑥1 + 𝑏12 (1) 𝑥2 + 𝑏13 (1) 𝑥3 + ⋯ + 𝑏1𝑛 (1) 𝑥𝑛 = 𝑏1,𝑛+1 (1) 𝑥2 + 𝑏23 (2) 𝑥3 + ⋯ + 𝑏2𝑛 (2) 𝑥𝑛 = 𝑏2,𝑛+1 (2) … … … … … … … … … … … … … … … … … … … … … 𝑥𝑚 + 𝑏𝑚,𝑚+1 (𝑚) 𝑥𝑚+1 + ⋯ + 𝑏𝑚𝑛 (𝑚) 𝑥𝑛 = 𝑏𝑚,𝑛+1 (𝑚) sistemani hosil qilamiz. Bundan 𝑥1, 𝑥2, … , 𝑥𝑚 larni 𝑥𝑚+1, 𝑥𝑚+2, … , 𝑥𝑛 lar orqali ifodalab olishimiz mumkin. Bu holda (1) cheksiz ko‘p yecliim- ga ega bo‘ladi. Agar (5) da 𝑎 (𝑚) 𝑖,𝑚+1 (𝑚 + 1 ≤ 𝑖 ≤ 𝑛) laming hech bo‘lmaganda birortasi noldan farqli bo‘lsa, u holda yechimga ega emas bo‘ladi.

Xulosa;
Chiziqli tenglamalar sistemasi fanning juda ko'p tarmoqlarida qo'llaniladi. Chizikli tenglamalar echishni ko'p usullari bor, lekin Gauss usuli universal usul хisoblanadi, chunki kengaytirilgan matritsa satrlari ustida elementar almashtirishlar bajarib, istalgan tenglama uchun uning echimi haqida ijobiy javob olish mumkin.

FOYDALANILGAN ADABIYOTLAR. 1. Isroilov M. “Hisoblash metodlari”, T., “O’zbekiston”, 2003 2. Boyzoqov A., Qayumov Sh. “Hisoblash matematikasi asoslari”, O’quv qo’llanma. Toshkent 2000 3. Abduqodirov A.A. “Hisoblash matematikasi va programmalash”, Toshkent. “O’qituvchi” 1989 4. Shoxamidov Sh. Sh. “Amaliy matematika unsurlari”, T., “O’zbekiston”, 1997 5. Воробьева Г.Н., “Практикум по вычислительной математике”, Москва, «Высшая школа», 1990

Download 20.63 Kb.