1. Chiziqli tenglamalar tizimini echish Gauss Algoritmi Ketma-ket algoritm

Chiziqli algebraik tenglamalar sistemasini yechisda bajariladigan amallar soni

Reja:
1.Chiziqli tenglamalar tizimini echish
2. Gauss Algoritmi
3.Ketma-ket algoritm
Chiziqli tenglamalar tizimlari differentsial, integral yoki chiziqli bo'lmagan ( transsendent) tenglamalar tizimlari bilan tavsiflangan bir qator amaliy muammolarni echishda paydo bo'ladi . Ular matematik dasturlash, statistik ma'lumotlarni qayta ishlash, funktsiyalarni yaqinlashtirish, chekka differentsial muammolarni cheklangan farqlar usuli yoki cheklangan elementlar usuli bilan namuna olishda va hokazolarda ham paydo bo'lishi mumkin.
Chiziqli tenglamalar tizimining koeffitsient matritsalari turli xil tuzilish va xususiyatlarga ega bo'lishi mumkin. Yechilgan tizimlarning matritsalari zich bo'lishi mumkin va ularning tartibi bir necha ming qator va ustunlarga yetishi mumkin. Ko'pgina muammolarni hal qilishda o'n minglab tartibli va bir necha ming elementli lenta kengligi bo'lgan nosimmetrik musbat aniqlangan lenta matritsalariga ega tizimlar paydo bo'lishi mumkin. Va nihoyat, ko'p sonli muammolarni ko'rib chiqishda millionlab qatorlar va ustunlar tartibiga ega bo'lgan siyrak matritsali chiziqli tenglamalar tizimlari paydo bo'lishi mumkin.
N noma'lum x0, x1, s, xn-1 bo'lgan chiziqli tenglamani ifoda yordamida aniqlash mumkin

( 8.1)

N chiziqli tenglamalar to'plami

( 8.2)

bu erda A=(a _i,j) haqiqiy NxN o'lchamdagi matritsa va b va x vektorlari n elementlardan iborat.
Berilgan a matritsa va b vektor uchun chiziqli tenglamalar tizimini echish muammosi odatda noma'lum x vektorining qiymatini topishni anglatadi , bunda tizimning barcha tenglamalari bajariladi.
Gauss usuli-koeffitsient matritsalari zich bo'lgan chiziqli tenglamalar tizimini echishning keng tarqalgan to'g'ridan-to'g'ri algoritmi. Agar chiziqli tenglamalar tizimi degenerativ bo'lmasa, Gauss usuli mashina hisoblashining aniqligi bilan belgilanadigan xato bilan echimni topishni kafolatlaydi. Usulning asosiy g'oyasi a matritsasini ekvivalent transformatsiyalar orqali (tizim echimini o'zgartirmasdan (8.2)) uchburchak shaklga keltirishdir, shundan so'ng kerakli noma'lumlarning qiymatlari to'g'ridan-to'g'ri aniq shaklda olinishi mumkin.
Kichik bo'limda algoritmni dastlabki tushunish uchun etarli bo'lgan va chiziqli tenglamalar tizimini echishda parallel hisoblashning mumkin bo'lgan usullarini ko'rib chiqishga imkon beradigan Gauss usulining umumiy tavsifi berilgan . Olingan echimlarning aniqligi masalalarini qat'iy muhokama qilish bilan algoritmning to'liqroq taqdimotini, masalan, asarlarda olish mumkin[ [ 6 ] , [ 22 ] , [ 47 ] ] va boshqalar.
Gauss usuli ko'rib chiqilayotgan tizimning echimlarini o'zgartirmaydigan chiziqli tenglamalarning o'zgarishini amalga oshirish imkoniyatiga asoslanadi (bunday transformatsiyalar ekvivalent deb ataladi ). Bunday o'zgarishlarga quyidagilar kiradi:

• 
  tenglamalardan birini nolga teng bo'lmagan doimiyga ko'paytirish;
  
• 
  tenglamalarni almashtirish;
  
• 
  tenglamaga tizimning boshqa har qanday tenglamasini qo'shish.
  

Gauss usuli ikki bosqichni ketma-ket bajarishni o'z ichiga oladi. Birinchi bosqichda-Gauss usulining to'g'ridan-to'g'ri yo'nalishi-noma'lumlarni ketma-ket chiqarib tashlash yordamida chiziqli tenglamalarning dastlabki tizimi yuqori uchburchak shaklga keltiriladi
bu erda hosil bo'lgan tizimning koeffitsientlari matritsasi shaklga ega

Gauss usulining teskari yo'nalishi bo'yicha (algoritmning ikkinchi bosqichi) noma'lum qiymatlar aniqlanadi. O'zgartirilgan tizimning oxirgi tenglamasidan x _n-1 o'zgaruvchining qiymatini hisoblash mumkin, shundan so'ng x _n-2 o'zgaruvchisini aniqlash oxirgi tenglamadan mumkin bo'ladi va hokazo.
Gauss usulining to'g'ridan-to'g'ri yo'nalishi chiziqli tenglamalar tizimining tenglamalarida noma'lumlarni ketma-ket chiqarib tashlashdan iborat . I, 0 , usulning takrorlanishida , i (ya'ni i) dan katta bo'lgan k raqamlari bo'lgan barcha tenglamalar uchun noma'lum i chiqarib tashlanadi. Buning uchun ushbu tenglamalardan _i qatorni doimiy ( a _ki/a _ii) ga ko'paytiriladi , natijada noma'lum x i uchun koeffitsient nolga teng bo'ladi-barcha kerakli hisob-kitoblarni nisbatlar yordamida aniqlash mumkin:

Shaklning chiziqli tenglamalari tizimi misolida Gauss usulining to'g'ridan-to'g'ri harakatini tushuntiramiz:

Birinchi iteratsiyada noma'lum x0 ikkinchi va uchinchi qatorlardan chiqarib tashlanadi. Buning uchun ushbu satrlardan mos ravishda 2 va 1 ga ko'paytiriladigan birinchi qatorni olib tashlashingiz kerak. Ushbu o'zgarishlardan so'ng tenglamalar tizimi shaklni oladi:

Natijada, oxirgi iteratsiyani bajarish va noma'lum x ₁ ni uchinchi tenglamadan chiqarib tashlash qoladi. Buning uchun siz ikkinchi qatorni olib tashlashingiz kerak va oxirgi shaklda tizim quyidagi shaklga ega:

Shaklda 8.1 Gauss algoritmining to'g'ridan-to'g'ri harakatining birinchi iteratsiyasida ma'lumotlar holatining umumiy sxemasi keltirilgan . Asosiy diagonaldan pastda va i ustunning chap tomonida joylashgan noma'lumlar uchun barcha koeffitsientlar allaqachon nolga teng. Gauss usulining to'g'ridan-to'g'ri harakatining i-chi iteratsiyasida asosiy diagonaldan pastda joylashgan i ustun koeffitsiyentlari i qatorni kerakli nolga teng bo'lmagan konstantaga ko'paytirib olib tashlash orqali nolga tenglashtiriladi. (N-1) shunga o'xshash iteratsiyani amalga oshirgandan so'ng, chiziqli tenglamalar tizimini belgilaydigan matritsa yuqori uchburchak shaklga keltiriladi.

Gauss usulining to'g'ridan-to'g'ri harakatini amalga oshirayotganda, noma'lumlarni istisno qilish uchun ishlatiladigan chiziq etakchi deb nomlanadi va etakchi chiziqning diagonal elementi etakchi element deb ataladi. Ko'rib turganingizdek, hisob-kitoblarni amalga oshirish faqat etakchi element nolga teng bo'lmagan qiymatga ega bo'lsa mumkin bo'ladi. Bundan tashqari,agar a _{i, i} ning etakchi elementi kichik qiymatga ega bo'lsa, unda satrlarni ushbu elementga bo'lish va ko'paytirish hisoblash xatosining to'planishiga va algoritmning hisoblash beqarorligiga olib kelishi mumkin.
Bunday muammoning oldini olishning mumkin bo'lgan usuli quyidagicha bo'lishi mumkin: Gauss usulining oldinga siljishining har bir keyingi takrorlanishini amalga oshirayotganda, istisno qilingan noma'lumga mos keladigan ustundagi mutlaq qiymat bo'yicha maksimal qiymatga ega bo'lgan koeffitsientni aniqlash kerak, ya'ni.

Gauss algoritmining etakchi qatorni tanlash bilan oldinga siljishining hisoblash murakkabligi o(n 3) tartibiga ega .