Parallel dasturlash

Gauss algoritmi. Gauss usuli - koeffitsient matritsalari zich boʻlgan chiziqli tenglamalar tizimlarini yechish uchun mashhur toʻgʻridan-toʻgʻri algoritm. Agar chiziqli tenglamalar tizimi degenerativ boʻlmasa, Gauss usuli mashina hisob-kitoblarining aniqligi bilan aniqlangan xato bilan yechim topishni kafolatlaydi. Usulning asosiy gʻoyasi A matritsasini ekvivalent transformatsiyalar yordamida uchburchak shaklga qisqartirishdir, shundan soʻng noma’lum noma’lumlarning qiymatlarini olish mumkin.
Ushbu kichik boʻlim Gauss usulining umumiy tavsifini beradi, bu algoritmni dastlabki tushunish uchun etarli va chiziqli tenglamalar tizimini yechishda parallel hisoblashning mumkin boʻlgan usullarini koʻrib chiqishga imkon beradi.
Algoritm ketma-ketligi. Gauss usuli koʻrib chiqilayotgan sistemaning yechimini oʻzgartirmaydigan chiziqli tenglamalarni oʻzgartirishni amalga oshirish imkoniyatiga asoslanadi (bunday oʻzgartirishlar ekvivalent deb ataladi). Ushbu oʻzgarishlarga quyidagilar kiradi:
• har qanday tenglamani nolga teng boʻlmagan doimiyga koʻpaytirish;
• tenglamalarni qayta tashkil etish;
• tenglamaga tizimdagi har qanday boshqa tenglamani qoʻshish.
Gauss usuli ikki bosqichning ketma-ket bajarilishini oʻz ichiga oladi. Birinchi bosqichda - Gauss usulining toʻgʻridan-toʻgʻri yoʻnalishi - chiziqli tenglamalarning dastlabki tizimi noma’lumlarni ketma-ket yoʻq qilish orqali yuqori uchburchak shaklga tushiriladi.
Ux = c,
bu yerda hosil boʻlgan tizimning koeffitsientlar matritsasi shaklga ega

Gauss usulining qaytish qadamida (algoritmning ikkinchi bosqichi) noma’lumlarning qiymatlari aniqlanadi. x_n-1 oʻzgaruvchisining qiymatini oʻzgartirilgan tizimning oxirgi tenglamasidan hisoblash mumkin, shundan soʻng oxirgidan oldingi tenglamadan x_n-2 oʻzgaruvchisini aniqlash mumkin boʻladi va hokazo.

Gauss algoritmining toʻgʻridan-toʻgʻri qadami. Gauss usulining toʻgʻridan-toʻgʻri yoʻnalishi yechilayotgan chiziqli tenglamalar tizimining tenglamalaridagi noma’lumlarni ketma-ket yoʻq qilishdan iborat. i, 0 <= i ki / a_ii) bilan koʻpaytiriladi, shunda qatorlardagi noma’lum x_i uchun natija koeffitsienti nolga teng boʻladi - barcha kerakli hisob-kitoblarni munosabatlar yordamida aniqlash mumkin:





(ta’kidlash kerakki, shunga oʻxshash hisoblar b vektorida amalga oshiriladi).
Keling, Gauss usulining toʻgʻridan-toʻgʻri yoʻnalishini shakldagi chiziqli tenglamalar tizimi misolida tushuntirib beraylik:
,
,

Birinchi iteratsiyada noma’lum x₀ ikkinchi va uchinchi qatorlardan oʻchiriladi. Buning uchun ushbu satrlardan 2 va 1 ga koʻpaytirilgan birinchi qatorni ayirish kerak. Ushbu oʻzgarishlardan soʻng tenglamalar tizimi quyidagi shaklni oladi:

,
,

Natijada, oxirgi iteratsiyani bajarish va uchinchi tenglamadan noma’lum x₁ ni yoʻq qilish qoladi. Buning uchun ikkinchi qatorni olib tashlang va oxirgi shaklda tizim quyidagicha koʻrinadi:

,
,



15-rasmda Gauss algoritmining oldinga siljishining i-iteratsiyasida ma’lumotlar holatining umumiy diagrammasini koʻrsatadi. Asosiy diagonal ostida va i ustunining chap tomonida joylashgan noma’lumlar uchun barcha koeffitsientlar allaqachon nolga teng. Gauss usulining oldinga siljishining i-iteratsiyasida asosiy diagonaldan pastda joylashgan i ustunining koeffitsientlari i qatorni kerakli nolga teng boʻlmagan