16-ma’ruza. Sodda parallel algoritmlar

15-rasm. Gaussning toʻgʻridan-toʻgʻri iteratsiyasi 
 
doimiyga koʻpaytirish orqali nolga tenglashtiriladi. Bunday takrorlash (n-
1) amalga oshirilgandan soʻng, chiziqli tenglamalar tizimini aniqlovchi 
matritsa yuqori uchburchak koʻrinishga qisqaradi. 
Gauss usulining oldinga siljishini bajarishda noma’lumlarni chiqarib 
tashlash uchun foydalaniladigan chiziq yetakchi element, yetakchi 
chiziqning diagonal elementi esa yetakchi element deb ataladi. Koʻrib 
turganingizdek, hisoblash faqat yetakchi nolga teng boʻlmasa mumkin. 
Bundan tashqari, agar a
i
, i yetakchi elementi kichik qiymatga ega boʻlsa, 
u holda bu element bilan qatorlarni boʻlish va koʻpaytirish hisoblash 
xatosining toʻplanishiga va algoritmning hisoblash beqarorligiga olib 
kelishi mumkin. 
Bunday 
muammodan 
qochishning 
mumkin 
boʻlgan usuli 
quyidagicha boʻlishi mumkin: Gauss usulining oldinga siljishining har bir 
ketma-ket takrorlanishida, istisno qilingan noma’lumga mos keladigan 
ustundagi mutlaq qiymatdagi maksimal qiymat bilan koeffitsientni 
aniqlash kerak, ya’ni 
𝑦 = max |𝑎
𝑘𝑖
|
 
𝑖≤𝑘≤𝑛−1
 
va ushbu koeffitsient joylashgan etakchi chiziq sifatida tanlang (yetakchi 
qiymatni tanlash uchun ushbu sxema asosiy element usuli deb ataladi). 
Gauss algoritmining oldingi qatorni tanlash bilan oldinga siljishini 
hisoblash murakkabligi O (n
3
) tartibida.