Laborator Nr. 10 Tema: Metoda de eliminare a lui Gauss. Regulile lui Cramer Scop lucrare

Laborator Nr. 10
Tema: Metoda de eliminare a lui Gauss. Regulile lui Cramer
Scop lucrare:

• 
  Verificarea posibilităţii aplicării metodei în studiu, pentru ecuaţiile şi sistemele de ecuaţii liniare;
  
• 
  Analiza ecuaţiilor propuse, rezolvarea analitică, alcătuirea programelor în limbaje de programare, care realizează metodele în studiu;
  
• 
  Estimarea erorilor metodelor în studiu (opţional).
  

Consideraţii teoretice:

Metoda lui Gauss este una din metode tradiţionale directe de rezolvare a sistemelor de ecuaţii liniare. Ideea de bază a metodei constă în aducerea sistemului de ecuaţii prin transformări elementare la o formă echivalentă, având matrice superior sau inferior triunghiulară, urmată de rezolvarea sistemului rezultat prin procedee recurente specifice, foarte eficiente.

Transformarea sistemului iniţial într-un sistem de formă triunghiulară se realizează cu ajutorul a trei operaţii de elementare sau bază:

1. 
   interschimabrea a două ecuaţii între ele;
   
2. 
   înmulţirea unei ecuaţii cu o constantă nenulă;
   
3. 
   scăderea unei ecuaţii din alta şi înlocuirea celei de-a doua ecuaţie cu rezultatul scăderii
   

Transformarea sistemului este echivalentă cu eliminarea succesivă a necunoscutelor din ecuaţii şi se numeşte de aceea faza eliminării. Rezolvarea sistemului cu matrice triunghiulară constă în determinarea necunoscutelor şi substituţia lor în ecuaţiile sistemului în ordine inversă, fiind denumită din acest motiv faza substituţiei inverse.

Pentru exemplificare se consideră un sistem de trei ecuaţii cu trei necunoscute:

(4.1)

sub formă matriceală, vom avea:

adică, în formă restrânsă: A x = b

unde: A=[a_ij] reprezintă matricea sistemului, i, j = 1, n;

x=[x_i] – matricea coloană a necunoscutelor;

b=[b_i] – matricea coloană a termenilor liberi.

La primul pas al etapei eliminării urmărim eliminarea necunoscutei x₁ din toate ecuaţiile sistemului, cu excepţia primei ecuaţii. Pentru aceasta, împărţim mai întâi prima linie la elementul pivot a₁₁, presupus nenul, adică a₁₁0 (dacă nu este îndeplinită această condiţie, reordonăm şi numerotăm ecuaţiile):

Scădem apoi prima ecuaţie înmulţită cu primul coeficient al celei de-a doua ecuaţii din această ecuaţie şi, respectiv, înmulţită cu primul coeficient al celei de-a treia ecuaţii din aceasta din urmă. Obţinem astfel sistemul:

cu (4.2)

Matriceal, primul pas al metodei eliminării lui Gauss conduce la

(4.3)

La următorul pas, eliminăm necunoscuta x₂ din ultima ecuaţie. Pentru aceasta, împărţim mai întâi a doua ecuaţie la elementul pivot , diferit de zero (dacă nu este aşa, atunci realizăm interschimbarea ecuaţiilor a doua şi a treia) şi apoi scădem linia obţinută, înmulţită cu , din ecuaţia a treia. Matriceal, al doilea pas ne conduce la sistemul:

(4.4)

cu

(4.5)

Faza eliminării se încheie, împărţind cea de a treia ecuaţie la elementul pivot , care, pentru un sistem cu matrice nesingulară, trebuie să fie diferit de zero. Rezultă după acest pas sistemul:

cu (4.6)

sau matriceal, A⁽³⁾x = b⁽³⁾.

 

Din rezultatele obţinute, observăm matricea A⁽³⁾ este superior triunghiulară, iar sistemul este echivalent cu cel iniţial Ax = b, adică are soluţia (x₁, x₂, x₃).

 

Faza substituţiei inverse (mersul înapoi) presupune parcurgerea în sens invers a ecuaţiilor sistemului cu matrice triunghiulară (4.6), rezultat în faza eliminării, şi stabilirea soluţiei sistemului potrivit unui calcul recursiv:

(4.7)

După cum se observă, determinarea componentelor soluţiei are loc de la indici mari spre indici mici, fiecare nouă componentă depinzând în mod explicit numai de componentele determinate anterior.

 

Observaţie. Metoda de eliminare Gauss permite şi calcularea determinantului matricii sistemului. Se observă că, matricea A⁽³⁾ a sistemului (6) fiind triunghiulară, are determinantul egal cu produsul elementelor diagonale, adică

det A⁽³⁾=1

Având în vedere, însă, că prin împărţirea liniilor matricii sistemului la elementele pivot rezultă o matrice având determinantul egal cu determinantul matricii iniţiale împărţit la produsul elementelor pivot, rezultă

adică

Metoda descrisă mai sus poate fi generalizată şi aplicată la rezolvarea a m sisteme de n ecuaţii liniare cu n necunoscute

(4.8)

sau sub formă matriceală

Atunci putem spune că la fiecare pas k al fazei eliminării se efectuează împărţirea liniei pivot k la elementul diagonal . Deoarece este posibil ca un element pivot să fie egal cu zero (imposibilitate de continuare a fazei eliminării ) se procedează în practică astfel:

• 
  se determină elementul maxim al matricei A^(k–1) situat pe coloana k şi liniile l k (pe diagonala principală şi sub ea), adică elementul a_lk;
  
• 
  se aduce elementul maxim a_lk găsit pe diagonala principală, interschimbând între ele liniile l şi k.
  

Această metodă se numeşte pivotare parţială pe coloană.
Algoritmul eliminării lui Gauss.

Mod de lucru:

Descriem mai jos algoritmul eliminării lui Gauss cu pivotare parţială pe coloane:

Algoritm
Date de intrare:

n {dimensiunea matricei}

m

a_ij, i=1,2,..., n, j=1,2,..., n {matricea sistemului)

b_ij, i=1,2,..., m, j=1,2,..., m {matricea termenilor liberi}
Date de ieşire:

b_ij, i=1,2,..., n, j=1,2,..., m { soluţia sistemului }

Det { determinantul sistemului }
  

Faza eliminării

 

Pasul 1. Det=1;

Pasul 2. Pentru k=1,..., n execută Paşii 3-6

Pasul 3. t=0 {caută elementul pivot de pe coloana k}

Pentru i=k+1,..., n execută

Dacă t<|a_ik| Atunci t=|a_ik|; lin:=i;

Pasul 4. Dacă link {interschimbă liniile lin şi k pentru a pune pivotul pe diagonală}

Atunci

Det=–Det {la interschimbarea a două linii Det işi schimbă semnul}

Pentru j=k,...,n execută t=a_kj; a_kj=a_linj; a_linj=t;

Pentru j=1...,m execută t=b_kj; b_kj=b_linj; b_linj=t;

Pasul 5. Det=a_kk*Det {Înmulţeşte determinantul cu pivotul}

Pentru j=k+1,..., n execută a_kj=a_kj/a_kk {Împarte linia pivot la pivot)

Pentru j=1,..., m execută b_kj=b_kj/a_kk;

Pasul 6. Dacă kn Atunci

Pentru i=k+1,..., n execută

Pentru j=k+1,..., n execută a_ij=a_ij-a_ika_kj;

Pentru j=1,..., m execută b_ij=b_ij-a_ikb_kj;

 

Faza substituţiei inverse

 

Pasul 7. Pentru k=n-1,..., 1 execută

Pentru j=1,..., m execută

t=0;

Pentru i=k+1,..., n execută t=t+a_kib_ij;b_kj=b_kj-t
Regulile lui Cramer pentru sisteme de ecuaţii liniare:

a) Dacă determinantul sistemului este nenul ( d <> 0 ), atunci sistemul este compatibil determinat, adică are o singură soluţie, care se calculează astfel:

b) Dacă determinantul sistemului şi toţi determinanţii d₁, d₂, …, d_n sunt egali cu zero, atunci sistemul este compatibil nedeterminat, adică are o infinitate de soluţii.

3. 
   Dacă determinantul sistemului este egal cu zero, iar printre determinanţii d₁, d₂, …, d_n există cel puţin unul diferit de zero, atunci sistemul este incompatibil.
   

 

Dacă sistemul de ecuaţii liniare este omogen, atunci toţi determinanţii d₁, d₂, …, d_n sunt egali cu zero.

Regulile lui Cramer pentru sisteme de ecuaţii liniare este omogen:

1. 
   Dacă determinantul sistemului este egal cu zero, atunci sistemul este compatibil determinant, soluţia lui este:
   

x₁ = 0 _, x₂ = 0 _{, … ,} x_{n =} 0. 

b) Dacă determinantul sistemului este nenul, atunci sistemul este incompatibil.

Desfășurarea lucrării:

1. 
   Să se rezolve sistemul de ecuaţii algebrice liniare prin metoda inversării matriceale:
   

Soluţia: Identificarea matricelor este:

A=

Calculăm determinantul: det =55 , deci matricea este inversabilă.

Transpusa şi apoi conjugata matricei vor fi:

Inversa matricei va fi:

Şi astfel vom obţine soluţia sistemului:

Soluţiile sunt: x₁ = 2; x₂ = 4; x₃ = 3

2. 
   Să se scrie programul de realizare a metodei lui Gauss.
   

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

float a[10][10],b[10],x[10],temp;

int i,j,n,iv,t,k,l; /*in functia procedurala

void citire() /*se citesc matricea sistemului A si vectorul termenior liberiB. Matricea a este constituita din cei n coeficienti a celor n ecuatii. */ 

void citire()

{

printf (" Dati numarul de ecuatii");

scanf ("%d",&n);

printf (" Dati matricea A \n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

printf ("a[%d][%d]=",i,j);

scanf ("%f",&a[i][j]);

}

printf ("Dati cei %d termenii liberi:\n",n);

for(i=1;i<=n;i++)

{

printf ("b[%d]=",i);

scanf ("%f",&b[i]);

}

}

void gauss() /*se implementeaza algoritmul specific acestei metode. Primadata se verifica si se fac pivotari in cazul in care acest lucru se impune, apoi se calculeaza ceilaltitermeni conform relatiilor de mai sus.in acest algoritm nu se fac inlocuiri cu 0 pe coloanapivotilor deoarece cu ajutorul unor restrictii din algoritm partea triunghiolara a matricvei de subdiagonala principala nu este accesata. Un alt lucru care iese in evidenta este ca la primul pas,acela in care impartim linia la elementul pivot, algorimul face in acelasi timp si inlocuirea cumetoda dreptunghiului, castigand din punct de vedere al eficientei*/ 

{

for(j=1;j<=n-1;j++)

{

iv=j;

t=1;

while

((iv<=n) && (t==1))

if (a[iv][j] == 0) iv=iv+1;

else t=0;

if (t==1)

{

printf (" Determinantul pricipal este nul");

exit(0);

}

if (j!=iv)

{

for(k=j;k<=n;k++)

{

temp=a[j][k];

a[j][k]=a[iv][k];

a[iv][k]=temp;

}

temp=b[j];

b[j]=b[iv];

b[iv]=temp;

}

for(l=j+1;l<=n;l++)

{

for(k=j+1;k<=n;k++)

a[l][k]=a[l][k] - a[j][k] * a[l][j] / a[j][j];

b[l]=b[l] - b[j] * a[l][j] / a[j][j];

}

}

if (a[n][n]==0)

{

printf(" Deterninantul principal este nul");

exit(0);

}

}

1. 
   Să se rezolve sistemul de ecuaţii liniare:
   

 

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁

……………………………..

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁

Programului de rezolvare al sistemelor de ecuaţii liniare cu ajutorul regulilor lui Cramer conţine trei părţi componente:

1. 
   programul principal;
   
2. 
   funcţia recursivă det – calculează valoarea unui determinant;
   
3. 
   procedura det_aug – copie coloana termenilor liberi pe rând în locul coloanelor matricei coeficienţilor şi apelează funcţia det pentru calculul determinanţilor auxiliari.
   

Program Dev C++

#include

#include

#include

int n,k=0;

float c[4][4]={{0,0,0,0},

{0,1,1,2}, //matrice implicita

{0,2,-1,2},

{0,4,1,4}};

float l[4]={0,-1,-4,-2}; //col el liberi

float v[10]; //valorile determinantilor

float x[10][10]; //matricea de lucru

void afis(float x[][10]) //afiseaza o matrrice

{ for(int j=1;j<=n;j++)

{ for(int i=1;i<=n;i++)

printf("%2.3f ",x[i][j]);

printf("\n");

}

printf("\n");

}
float determinant(float b[][10],int nn) //calculeaza orice determinant

{float d,a[10][10];int i,j,k;

for(i=1;i<=nn;i++)

for(j=1;j<=nn;j++)

a[i][j]=b[i][j]; //creez o copie pe care lucru !!
for(i=1;i<=nn-1;i++)

{if (fabs(a[i][i])<=1e-15){return 0;break;}

for(j=i+1;j<=nn;j++)

{d=a[i][j]/a[i][i];

for(k=i;k<=nn;k++)

a[k][j]=a[k][j]-d*a[k][i];

}

}

d=1.0;

for(int i=1;i<=nn;i++) d=d*a[i][i];

return d;

} //sf determinant
float inversez(float xx[][10],int c) //inverseaza o anume col cu termenii liberi

{float t[10],d; //t este temporarul

for(int j=1;j<=n;j++)

{ t[j]=xx[c][j]; //salvez col initiala

xx[c][j]=l[j]; //scriu col elemntelor liberi

}

d=determinant(xx,n); //calculez determinant

afis(xx); //afisez matricea

for(int j=1;j<=n;j++)

{ xx[c][j]=t[j]; //repun col initiala

}

return d;

} //sf inversez
void introducere()

{ float t;

for(int j=1;j<=n;j++) //introducere date

for(int i=1;i<=n;i++)

{printf("a[%d][%d]=",i,j);

scanf("%f",&t);

x[i][j]=t;

} //sf for i

printf("\n Introduceti col termeni liberi ! \n");

for(int i=1;i<=n;i++) //citesc col termeni liberi

{ printf("liber[%d]=",i);scanf("%f",&l[i]);}

}

void cramer()

{ float q,t;

printf("Metoda Cramer de rezolvare a sistemelor de n ecuatii");

printf("Pentru valorile implicite dati 0 ! \n");

printf("Numarul de ecuatii n=");scanf("%d",&n);

if(n!=0) introducere();

else {n=3;for(int j=1;j<=n;j++)

for(int i=1;i<=n;i++){ t=c[j][i];x[i][j]=t;}

}

printf("Matricea initiala ! \n");

afis(x);

q=determinant(x,n);v[0]=q;

printf("Det 0 =%f \n",q);

for (int g=1;g<=n;g++)

{ q=inversez(x,g);printf("det %d=%f \n",g,q);v[g]=q;}

printf("\n Si valorile pentru x sunt : \n");

for (int g=1;g<=n;g++) printf("x%d=%f\n",g,v[g]/v[0]);

} //sf cramer

int main()

{

cramer();

getche();

}

Concluzii, observații:
Se vor prezenta rezultatele obținute de fiecare student.

Se vor consemna eventualele dificultăți și se vor face propuneri pentru evitarea erorilor.

Bibliografie:

1. 
   Anton Hadar, Marin, C., Petre C., Voicu A. –”Metode Numerice in Inginerie”, Politehnica Press, Bucresti, 2004
   

2. 
   Anghel C.V. - „Metode numerice. Algoritmi şi programe de calcul”, Ed. Orizonturi Universitare, Timişoara, 2005.
   

3. 
   Mihai Rebican, Gabriela Ciuprina, Daniel Ioan - Metode numerice in ingineria electrica. Indrumar de laborator, 2012.