Kurs jumisi tema: sanaq sistemalari,KÓplikler, gauss hám gauss-jordan usullari

Gauss-Jordan usılı

Algoritm xarakteristikası

Sheshiwde sızıqlı algebralıq teńlemeler sisteması keńeytirilgen matritsa formasında jazıladı, yaǵnıy erkin atamalar ústininde belgisizlerdiń koefficiyentleri menen bir matritsaga jaylastırıladı. Matritsaning taǵı bir qatarı menen qosıladı ). 1 / a[i][i] turaqlı retinde isletiledi.

Pútkil algoritm 10 punkt penen ańlatılıwı múmkin:
1. Maǵluwmat retinde birinshi qatardı saylań .
2 .Eger kórsetkish qatarınıń sanına teń bolǵan búklem qatarınıń elementi nolge teń bolsa, Ol halda pútkil búklem qatarın tómende keltirilgen birinshi qatarǵa ózgertiriń, onıń ústininde nol.
3. Malumot sızıǵınıń barlıq elementleri shep tárepten bul qatardıń birinshi nolǵa teń bolmaǵan elementine bólinedi.
4. Tómengi bólekten qalǵan sızıqlardan uyqas jazıwlar sızıǵın shıǵarıń jeńiliw indeks bolǵan elementke kóbeytiriledi uyqas jazıwlar liniyasi nomerine teń.
5. Biz uyqas jazıwlar liniyasi retinde keyingi 5 ni tańlaymiz.

6. Kórsetkish qatarınıń nomerine shekem biz 2 - 5 basqıshlardı tákirarlaymız sızıqlar qatarlar sanınan aspaydı.

7. Maǵluwmat retinde aqırǵı qatardı saylań.

8.Joqarıdaǵı hár bir sızıqtan búklem sızıǵın shıǵarıń, indeks penen bul qatar elementine kóbeytiriledi.

9. Joqarıdaǵı qatardı uyqas jazıwlar qatarı retinde saylań.

10. Kórsetkish qatarınıń nomeri bolaman degenge shekem 8-9 ni tákirarlań birinshi qatar sanınan kemrek boladı.

Esaplawǵa misal 1
Teńlemeler sisteması bolsın :

Sistemanıń keńeytirilgen matritsasini jazamız :

jáne onıń sımların elementar transformaciyaların atqarıń. Onıń ushın birinshi qatardı 1 ge ko'beytiriń hám ekinshi qatardan shıǵarıń ; keyin birinshi qatardı 2 ge kóbeytiriń

úshinshi qatardan shıǵarıń.

Nátiyjede x1 ózgeriwshisin birinshi teńlemeden tısqarı barlıq teńlemelerden shıǵarıp taslaymiz. Biz alamız :

Endi, 3-qatardan 2-qatardı 3 ke kóbeytirip alamız.


Keyin 2 ge kóbeytirilgen 2- qatardan 3- qatardı alıp taslaymız.

Endi biz birinshi qatardan 3 qatardı, keyninen 2-qatardı alıp taslaymız :

Transformaciyalardan keyin biz teńlemeler sistemasın alamız :

Bunnan kelip shıǵadı, teńlemeler sisteması tómendegi sheshimge iye:
x1 = 1, x2 = 3, x3 = -1
Esaplawǵa mısal 2

1. 
   Mısalı, Gauss-Jordan usılı járdeminde matritsa kórinisinde keltirilgen teńlemeler sistemasın (1-keste) shesheyik
   

3	4	3	1
1	7	2	6
6	2	3	7

Biz birinshi qatardı 3 ke bólemiz (tiykarǵı diogonalda da jaylasqan birinshi qatardıń elementi), biz tómendegilerdi alamız :

1	4/3	1	1/3
1	7	2	6
6	2	3	7

Birinshi qatardı birge kóbeytiriń hám 2- qatardan alıń.1- qatardı 6 ǵa kóbeytiń hám 3- qatardan alıń.

1	4/3	1	1/3
0	17/3	1	17/3
0	-6	-3	5

Birinshi baǵanada diogonaldan tısqarı barlıq elementler nolga teń, biz ekinshi baǵana menen islesemiz, onıń ushın ekinshi qatardı tańlaymiz. Ekinshi qatardı 17/3 ke bólemiz :

1	4/3	1	1/3
0	1	3/17	1
0	-6	-3	5

2-qatardı 6 ǵa kóbeytemiz hám 3-qatarǵa qosamız.

1	4/3	1	1/3
0	1	3/17	1
0	0	-33/17	11

Endi 3-qatardı -33 / 17 ge bólemiz:

1	4/3	1	1/3
0	1	3/17	1
0	0	1	-17/3

Úshinshi qatardı 1 ge ko'paytiriń hám onı birinshisinen alıń.

1	4/3	0	6
0	1	0	2
0	0	1	-17/3

Úshmúyeshlik matrica alınadı, algoritmdıń teris háreketi baslanadı. Ekinshi qatar búklemge aylanadı. Úshinshi qatardı 4/3 ke ko'beytiriń hám birinshisidan alıń :

1	0	0	10/3
0	1	0	2
0	0	1	-17/3

Matricanıń aqırǵı baǵanası teńlemeler sistemasınıń sheshimi boladı.

Sızıqlı teńlemeler sistemasın sheshiw ushın Gauss usılı
M belgisiz bolǵan n ólshemli sızıqlı algebralıq teńlemeler sisteması berilgen. Bul sistemanı sheshiw talap etiledi: onıń qansha sheshimin anıqlaw kerek (joq, bir, yamasa sheksiz kóp) hám eger ol keminde bir sheshimge iye bolsa, ol jaǵdayda olardan birin tabıń.
Rásmiy túrde, wazıypa tómendegishe qoyıladı : sistemanı sheshiw:


bul jerde hám koefficiyentleri málim hám

ózgeriwshiler - belgisizler

Bul sistemanıń qolay matricalı kórinisi:

bul jerde A matrica n x m ,   hám    -vektor koefficiyentlerinen ibarat

m ólshemli baǵanalar.

Sonı atap ótiw kerek,sızıqlı algebralıq teńlemeler sisteması haqıyqıy sanlar maydanı ústinde emes, maydan p modulı boyınsha bazı bir p sanlar ústinde bolıwı múmkin. olar:

- Gauss algoritmı bunday sistemalar ushın da isleydi (biraq bul jaǵday tómende bólek bólimde kórip shıǵıladı ).

Gauss algoritmı

Qısqasha aytqanda, tómende xarakteristikalanǵan usıl tuwrı túrde Gauss-Jordannıń teńlemeler sistemasın sheshiw usılı dep atalǵan, sebebi bul 1887 jılda geodezist Vilgelm Jordan tárepinen táriyp berilgen Gauss usılınıń ózgeriwi (sonı atap ótiw kerek, Vilgelm Jordan da Iordaniyanıń da avtorı emes) iymek sızıqlar haqqındaǵı teorema, Iordaniya algebrasi joq - bulardıń hámmesi birdey attaǵı úsh qıylı alım bolıp tabıladı; bunnan tısqarı, " Iordaniya" transkripsiyasi tuwrılaw, biraq " Iordaniya" jazıwı rus ádebiyatında aldınnan berli anıqlanǵan). Iordaniya menen bir waqıtta (hám birqansha dereklerge kóre odan da aldınlaw ) bul algoritmdı Klasen oylap tapqan depte aytıladı. (B.-I. Clasen).

Tiykarǵı sxema

Qısqasha aytqanda, algoritm hár bir teńlemede ózgeriwshini izbe-iz joq etiwden ibarat bolıp, hár bir teńlemede tek bir ózgeriwshi qaladı. Eger n = m bolsa, ol jaǵdayda siz ete alasız

Gauss-Jordan algoritmı sistema matricasın A matricasin identifikaciya matricasına aylandırıwǵa umtılıwın aytıladı - óytkeni matrica identifikatorǵa aynalǵannan keyin sistemanıń sheshimi anıq - sheshim kem ushraytuǵın hám nátiyjede berilgen Bul halda algoritm eki ápiwayı ekvivalentke tiykarlanadı .

Sistema transformaciyaları : birinshiden, siz eki teńlemeni almastırıwıńız múmkin

ekinshiden, hár qanday teńlemeni bul qatardıń sızıqlı birikpesi menen almastırıw múmkin (nolge teń bolmaǵan koefficiyent penen) hám basqa qatarlar (qálegen koefficiyentler menen).
Birinshi basqıshda Gauss-Jordan algoritmı birinshic qatardı koefficiyentine ajratadı. Keyin algoritm birinshi qatardı qalǵan qatarlarǵa sonday qosadı olardıń birinshi baǵanadaǵı koefficiyentleri nolge aylanıwı ushın koefficiyentler - onıń ushın, birinshi qatardı I birinshi qatarǵa qosqanda, ge ko'paytirilishi kerek. A matritsasi menen hár bir operatsiya ushın (sanǵa bóliniw, birin ekinshisine qosıw ) tiyisli ámeller atqarıladı hám b vektor menen, m + 1-baǵana sıyaqlı háreket etedi A matritsası.

Nátiyjede, birinshi basqısh aqırında matricanıń birinshi baǵanası birlikke aylanadı (yaǵnıy birinshi qatarda 1, qalǵan bóleginde nollar boladı ).

Tap sol tárzde, algoritmdıń ekinshi basqıshı ámelge asıriladı, endi tek ekinshi baǵana hám ekinshi qatar kórip shıǵıladı : birinshi náwbette, ekinshi qatar ge bólinedi, keyininen ol basqa barlıq qatarlardan alınadı.

Soǵan uqsas tárizde, biz A matricasınıń barlıq qatarların yamasa barlıq baǵanaların qayta islegenimizge deyin , eger n = m bolsa, onda algoritmdı dúziwde A matricasi anıq boladı.

Tiykarǵı elementti izlep tabıń
Álbette, joqarıdaǵı sxema tolıq emes. Tek ǵana hár bir birinshi qádemde element nolge teń bolsa isleydi - keri jaǵdayda biz olarǵa i-qatardı qosıp ámeldegi ústin degi qalǵan koefficiyentlerdiń nolleniwina erise almaymız.

Algoritmdı bunday jaǵdaylarda islewin támiyinlew ushın búklem elementin tańlaw procesi ámeldegi (anglichan tilinde sonday dep ataladı bir sóz menen " búklem"). Bul almastırıwdıń ámelge asırılıwınan ibarat matritsaning qatarları hám / yamasa ústinleri, kerekli elementte (ol shıqtı ) nolǵa teń bolmaǵan nomer.

Qatarlardı almastırıwdı kompyuterde baǵanalardı almastırıwdan kóre ańsatlaw ámelge asırılıwın umıtpań : óytkeni, eki baǵananı almastırǵanda, siz bul eki ózgeriwshiniń jaylar almaslıǵin eslewińiz kerek, sonda juwaptı qayta qayta tiklewde siz qaysı juwap qaysı ózgeriwshige tiyisli ekenligin tuwrı ayta alasız.

Jaqsı jeri, usıldıń tuwrılıǵı ushın tek bir qatardı almastırıw jetkilikli (eki qatar hám baǵanalar almastırilganda, " tolıq búklem" den ayrıqsha bolıp , " bólek búklem" dep ataladı ). Biraq qaysı qatardı almastırıwdı tańlawıńız kerek? hám tiykarǵı elementti qıdırıw tek ámeldegi element nolǵa teń bolǵanda ámelge asırılıwı kerekpe?

Bul sorawǵa ulıwma juwap joq. Hár qıylı evristika ámeldegi, biraq olardan eń nátiyjeli (ápiwayılıǵı hám sıylıq tárepinen) tómendegi evristika bolıp tabıladı: turaqlı baha daǵı eń úlken element tiykarǵı element retinde qabıl etiliwi kerek hám mudamı da búklem elementin izlew kerek hám ol menen almasınıw hám tekǵana kerek bolǵanda (yaǵnıy, ol = 0 bolǵanda emes)

Basqasha etip aytqanda, Gauss-Jordan algoritmınıń i-basqıshın bóleklengen búklem evristikasi menen orınlawdan aldın i-ústinde elementler arasında n den hám maksimal modulǵa shekem indeksli elementlerdi tabıw hám qatardı sol element menen almastırıw zárúr. i-qatar menen.

Birinshiden, bul evristik Sızıqlı teńlemeler sistemasın tarqatıp alıwǵa múmkinshilik beredi. Hátte sheshim waqtında = 0 elementi júz sonda da, ekinshiden, bul júdá zárúrli, bul evristik Gauss-Jordan algoritmınıń san turaqlılıǵındı jaqsılaydı.

Bul evristikasiz, hátte sistema hár i-basqıshda ga teń sonda da, Gauss-Jordan algoritmı isleydi, biraq tóplanǵan qáte oǵada úlken bolıwı múmkin, hátte 20 ǵa jaqın matricalar da qátelik asıp ketedi juwaptıń ózi.

Ámelge asırıw
Gauss-Jordan algoritmın bólek búklem evristikasi menen ámelge asırıw (búklem elementin baǵana tárepinen maximum retinde tańlaw arqalı ).

a matricasınıń ózi Gaus funkciyasına kiredi. a matricanıń aqırǵı baǵanası - bul biziń eski belgilewimizdegi baǵanadaǵı erikli b koefficiyentin bildiredi.(bul programmalastırıwdıń qolaylıǵı ushın ámelge asıriladı, sebebi algoritmdıń ózinde barlıq erkin koefficiyentler menen operatsiyalar b a matritsa menen tákirarlanatuǵın operatsiyalar ).

Funktsiya sistemanıń sheshimlerin qaytaradı (0, 1 yamasa ) (sheksizlik kodta hár qanday úlken bahaǵa ornatılıwı múmkin bolǵan arnawlı turaqlı INF menen belgilenedi). Eger keminde bir sheshim bolsa, ol ans vector kórinisinde qaytadı.
int gauss (vector < vector > a, vector & ans) {

int n = (int) a.size();

int m = (int) a[0].size() - 1;

 

vector where (m, -1);

for (int col=0, row=0; col

int sel = row;

for (int i=row; i

if (abs (a[i][col]) > abs (a[sel][col]))

sel = i;

if (abs (a[sel][col]) < EPS)

continue;

for (int i=col; i<=m; ++i)

swap (a[sel][i], a[row][i]);

where[col] = row;

 

for (int i=0; i

if (i != row) {

double c = a[i][col] / a[row][col];

for (int j=col; j<=m; ++j)

a[i][j] -= a[row][j] * c;

}

++row;

}

 

ans.assign (m, 0);

for (int i=0; i

if (where[i] != -1)

ans[i] = a[where[i]][m] / a[where[i]][i];

for (int i=0; i

double sum = 0;

for (int j=0; j

sum += ans[j] * a[i][j];

if (abs (sum - a[i][m]) > EPS)

return 0;

}

 

for (int i=0; i

if (where[i] == -1)

return INF;

return 1;

}

Funkciyada 2 kórsetkish paydalanıladı.Paydalanip atirgan baǵanaǵa col hám paydalanıp atırǵan qatarǵa row sózlerin paydalanamız. 0 den ózgeshe hár bir baǵanada Qatar sanı jazılatuǵın where vektorı paydalanıladı.Ayırım ózgeriwshiler sheshim barısında” anıq emeslik” ti belgilegendede kerek boladı. Partial pivoting texnikasın amelge asırıw,

Qatar elementlerin moduli boyinsha maximumın tabıw, keyin bul qatardı row pozitciyası kórinisine aylandiradı.

Ámeldegi qatar oporniy elementke bólinbeydi-Jumıstıń juwmaǵında matricanıń olgoritmi birlik kóriniste emes diagonal kóriniste boladı.

Sheshim tawip bolǵannan keyin ol keri matricaǵa qoyıladı-eń bolmaǵanda bir sheshimi bar joqlıǵı tekseriledi.Eger tekseriw tabıslı ótse bir ǵárezsiz ozgeriwshi bar joqliǵına qaramastan funkciya bir yamasa ke qaytadı.
Asimptotika

Alınǵan olgoritmnıń asimptotikasın bahalaymız.Asimptotika m faz dan turadı.

Olardıń hár birinde tómendegiler bolıp ótedi:

• 
  “Partial pivoting”(baǵanadaǵı maximumdı izlew)dı paydalanǵanda O(n+m)waqıtta
  

kórsetkish elementti izlew hám toqtatıwıwdı ámelge asıradı.

• 
  Eger islenip atırǵan baǵanadaǵı kórsetkish element tabılǵan jaǵdayda O(n*m)waqitta islenilip atırǵan teńlemeni basqa teńlemelerge alıp keledi.
  

Bunnan kórinip turipti ekinshi punkttegige qaraǵanda birinshi punktte kemirek asimptotikaǵa iye bolamız.

Bunnan kórinip turipti 2-punkt sızıqli teńlemeler sistemasındaǵı ózgeriwshilerge ǵárezli min(n,m) márte orınlanadı.

Solay etip juwmaqlawshı asimptotika olgaritmi O(min(n,m)*nm) kóriniske iye boladı.

n=m jaǵdayda bul bahalaw O( ) aylanadı.

Sızıqlı teńlemeler sisteması haqiyqiy sanlar kópliginen emes 2 modulli kóplikten alınsa

Sistemanı tezirek sheshiwge erisemiz.

Kóplikler
Biz ob'ektler toparın xarakteristikalaw ushın sózler kompleksinen paydalanamız. Mısalı, biz maymil kompleksin shaqıra alamız :


Tomengi koplikler. Basqa koplikte jaylasqan ob'ektler kompleksi

birdey kishi koplikler dep ataladı. Mısalı, pánjeler hám kózlerdi kórsetetuǵın maymillar kishi bólegin quraydı. -dagi barlıq maymillar S-de bar. Biz tómendegishe jazamız : S Biz maymillardi pánjeleri hám awi’zleri menen basqa kishi gruppaǵa toplawımız múmkin:

Birikpe. Qaysı maymillar . yamasa ga tiyisli,? Juwap : dagi maymillar. Jańa koplik - unifikaciya aldınǵı ekewi. Biz bunı bunday jazamız : .
Kesilispe. Qaysı maymillar tiyisli? Juwap : Jańa koplik aldınǵı ekewinin kesilispesinen alınadı. Biz sonday jazamız : .

JUWMAQLAW

Bul kurs jumısında informatikanıń tiykarǵı bólegi bolǵan sanaq sistemaları haqqinda aytılǵan.

Algoritmlestiriwde maselerdi sheshiwde sızıqlı algebralıq teńlemeler sisteması keńeytirilgen matritsa formasında jazıladı, yaǵnıy erkin atamalar ústininde belgisizlerdiń koefficiyentleri menen bir matricaǵa jaylastırıladı. Usılar haqqında maǵluwmatlar keltirilgen. Sızıqlı teńleóeler sistemasın sheshiw ushın Gauss usulınan paydalanıw múmkin hám qolaylı.Bunda sistema aǵzaları basqıshpa-basqısh azayıp barıw jolı menen sheshiledi.Bul kurs jumısında kóplikler haqqındada aytilǵan,yaǵnıy olardıń birikpesi kesilispesi haqqında maǵliwmatlar keltirilgen.

PAYDALANILG’AN ÁDEBIYATLAR DIZIMI

• 
  Теоритический_минимум_computer_science.
  
• 
  Н. Вирт .Алгоритмы и структуры данных
  
• 
  Internet materialları.