PCLP

1 Metode directe pentru sisteme de ecua.iil liniare

In aceast. sec.iune sunt descrise metode pentru rezolvarea unui sistem de ecua.ii

liniare de forma Ax = b , unde An~n = (aij ) , bn~1 = (b j ) , cu aij ,b j ¸ R , i, j =1,..., n ,

iar xn~1 = (x j ) este matricea coloan. a necunoscutelor. Se va lucra in ipoteza c.

determinantul lui A este nenul, adic. sistemul are solu.ie unic..

O metod. direct. pentru rezolvarea unui sistem de ecua.ii liniare este metoda care

dup. un num.r finit de pa.i d. solu.ia exact. (exceptand erorile de rotunjire). Aceste

metode sunt eficiente cand A este dens.. Dac. A este rar. atunci adesea este

preferabil s. se utilizeze metode iterative.

1.1 Sisteme triunghiulare

In situa.ia in care matricea sistemului este triunghiular., rezolvarea sistemului este

imediat.. Intr-adev.r, fie sistemul Ux = b , unde U este o matrice superior

triunghiular.:

Dac. xii ‚ 0 , i = 1,2,...,n atunci solu.ia sistemului se poate calcula cu recuren.ele

urm.toare:

Solu.ia sistemului se calculeaz. prin substitu.ie inapoi.

Dac. Lx = b .i Leste inferior triunghiular. .i lii ‚ 0 , i = 1,2,...,n atunci se aplic.

urm.toarele rela.ii de recuren..

realizandu-se cu substitu.ie inainte.

Algoritmii prezenta.i in continuare vizeaz. aducerea matricii A a sistemului la una

din formele triunghiulare anterioare.

1.2 Algoritmul lui Gauss

Ideea de lucru a algoritmului lui Gauss este de a face transform.ri sistematice care

aduc sistemul la forma triunghiular..

1.2.1 Aducerea la forma triunghiular.

Fie sistemul Ax = b , A = (aij )n~n , b = (bi )n~1 , aij ,bi ¸R , i, j =1,...,n , cu

det A ‚ 0 . Forma explicit. a sistemului este

unde ai,n+1 = bi , i =1,..., n .

Fie A = [A:b] matricea extins. a sistemului ob.inut. prin ad.ugarea lui b dup.

ultim. coloan. a lui A . Asupra lui A se execut. transform.ri elementare const.nd in

inmul.irea unei linii cu un scalar .i adunarea acesteia la alt. linie cu scopul de a anula

elementele aflate sub diagonala principal..

S. presupunem c. sub primele k .1 elemente de pe diagonala principal. s-au realizat

zerouri .i ac.ion.m in continuare cu linia k asupra unei linii i ( i = k +1,...,n ) pentru

a anula toate elementele de pe coloana k aflate sub akk . Matricea A inaintea ac.iunii

liniei k este prezentat. in fig. 1.

Fig. 1.

Pentru a anula elementul din pozi.ia (i,k) se inmul.e.te linia k cu ă , se adun. la

linia i , ă fiind ales astfel incat ăakk + aik = 0 , adic.

kk

ik

a

a ă = . , unde s-a presupus

c. akk ‚ 0 . A.adar dup. aceast. transformare aik se anuleaz. iar celelalte elemente

de pe linia i se schimb. conform rela.iei:

aij = aij +ă . akj , j = k +1,...,n +1.

Prin urmare algoritmul lui Gauss este:

. pentru fiecare k =1,2,...,n .1 se execut.:

 pentru fiecare i = k +1,...,n se execut.:

.

kk

ik

a

a ă = . ;

. aik = 0 ;

. pentru fiecare j = k +1,...,n +1 se execut.:

. aij = aij +ă . akj

In final rezult. un sistem echivalent cu cel ini.ial .i care este superior triunghiular: