Kirish Intervallardagi elementar amallar Kalit so'zlar

3.1.3 1-misol:
3 yordamida A X=B sistemasini yechish
Choleski parchalanishi
Machine Translated by Google

---

ÿ
b2,1 b2,2
2
2
bn,1 milliard,2 ··· bn,n
k=1
ÿ(b3,2)
b3.1 b3.2 b3.3
k=1
j ÿ1 j ÿ1 bi,k .bj,k agar ij va bj,j = aj,j ÿ (bj,k ) bo‘lsa
2
b1,1
2
b1,1 = a1,1
a2,1
b2,1 =
b1,1
b2,2 = a2,2 ÿ(b2,1)
2
0 b2,1 b2,2 ···
b3,3 = a3,3 ÿ(b3,1)
a3,1
b3,1 =
b1,1
a3,2 -b3,1 ×b2,1
b3,2 =
b2,2
b1,1
2
bj, j
2 tasi bajariladi
[ÿ6,38; 0.]
[ÿ6,40; 1.32]
T :
ÿ
ÿ
0
natija Ning va boshqalar tomonidan topilgan
ÿ
ÿ
Funktsiyaning murakkabligi, asosan, asosiy arifmetik amallarning (yig'indi,
ayirish, ko'paytirish...) murakkabligiga bog'liq.
[ÿ1,52;ÿ0,45]
[3,15; 4,64]
[ÿ1,56;ÿ0,42]
.
[ÿ1,776; 0,006]
ÿ
ÿ
va B=
ÿ
ÿ
0
AX = B tizimini yechish quyidagi bosqichlarni bajarishdan iborat: 1-bosqich :
Silvestr mezonidan
foydalanib, A ning musbat aniq simmetrik matritsa ekanligini tekshiring .
.
Ushbu operatsiyalar faqat kirish qiymatlariga bog'liq va kirishlar hajmiga
ko'ra operatsiyalarni takrorlaydigan tsikl yoki rekursiya yo'q, shuning uchun
ular O (1) bo'lgan doimiy murakkablikka ega. Aksincha, musbat intervalning
ildizini hisoblaydigan funksiya O(l og (n)) murakkablikka ega, chunki bu
funksiya sonning kvadrat ildizini hisoblash uchun < NumP y > kutubxonasidagi
"sqrt()" funksiyasidan foydalanadi.
[0;
0] [ÿ1,56;ÿ0,42]
[3,08; 4.67]
Oqibatlari
:
shunday:
ÿ
ÿ
X=
[ÿ9; 0]
[ÿ3; 0]
simmetrik matritsa A = [ÿ1,5;ÿ0,5] [3,7; 4,3] [ÿ1,5;ÿ0,5]
0
2-qadam : Cholesky decomposi yordamida A F × FT shaklida parchalang
.
0
.
Mohamed Khier Gauss eliminatsiyasi yordamida
=
aj, j -
FT X = Y , shuning uchun X =
1
0
[ÿ3,9; 0]
Xoleskiyning parchalanishini hisoblaydigan funksiyaning eng ichki tsikli n
marta bajariladi, bu erda n - A matritsasining o'lchami. Oraliq sikl n - 1 marta
bajariladi. Shunday qilib, er-xotin halqaning murakkabligi O (n
5-qadam : FT X = Y tizimini yeching.
ÿ
ÿ
ÿ
ÿ
ÿ
Gauss yordamida Ning va boshqalar tomonidan topilgan natija
X=
[ÿ6,54; 0]
A
fn, n =
ÿ
ÿ
4.2 Natijalarni solishtirish:
ÿ
Choleskiy parchalanishining murakkabligi
Biz [3.7; 4,3]
[ÿ1,5;ÿ0,5]
[0; 0]
[3,60; 4,27]
[ÿ1,52;ÿ0,45]
[0; 0]
). Davrning har bir iteratsiyasida asosiy arifmetik amallar
va musbat oraliqning ildizini hisoblovchi funksiya bir necha marta chaqiriladi,
lekin har doim bir xil o‘lchamdagi intervallar bilan, shuning uchun ularning
murakkabligi o‘zgarmaydi. Xulosa qilib aytganda, xoleskiy funktsiyasining
murakkabligi O(n
keling, FT X = Y ni qo'yamiz va biz FY = B tizimini yechamiz , topamiz:
[ÿ14; 0]
[ÿ6,38; 1.12]
.
.
A va B intervalli koeffitsientli ikkita matritsa bo'lsin .
natija karkar nora tomonidan topilgan - Ben
ÿ
.
ÿ
ÿ
Y=
ÿ
ÿ
F = ÿ
ÿ
ÿ
ÿ
ÿ
[ÿ3,40; 0]
bartaraf etish
3-qadam : Biz FT X = Y ni o'rnatamiz.
l og (n)), chunki tsikllar marta va
musbat oraliqning ildizini hisoblaydigan funktsiya
o'lchami n ga teng bo'lgan raqam bilan tsiklning har bir iteratsiyasida
chaqiriladi .
ÿ
ÿ
ÿ
ÿ
F×FT ÿ
ÿ
ÿ
A X=B sistemasini yechish