Universitatea de tiine Agricole i Medicin Veterinar Ion Ionescu de la Brad Iai

Asist. dr. Ciprian Chiru

MATEMATIC

Curs pentru nvmnt la Distan

2010

Cu mulumiri domnului lector dr. Clin Marius

1

Elemente de matematic liniar

1.1 Matrice i determinani 1.2 Ecuaii liniare 1.3 Sisteme de ecuaii liniare 1.4 Inegaliti liniare i sisteme de inegaliti liniare

Obiectivele capitolului

Definirea noiunilor de matematic liniar care vor sta la baza dezvoltrilor din capitolele 2 i 3;

Discutarea interpretrilor geometrice care se pot face n legtur cu ecuaiile i inegalitile liniare n dou variabile;

Introducerea metodei eliminrii totale pentru rezolvarea unui sistem de ecuaii liniare;

Introducerea noiunilor legate de explicitarea sistemelor de ecuaii liniare n raport cu un grup dat de variabile.;

Aplicarea metodei eliminrii totale la calcularea inversei unei matrice.

Acest capitol este destinat introducerii unor noiuni de baz din matematica liniar. Matematica liniar este important din mai multe motive. Astfel, multe fenomene din lumea real care trebuie studiate matematic sunt liniare sau pot fi aproximate ca fiind liniare. Deci, matematica liniar se aplic n multe domenii. In plus, analiza i manipularea relaiilor liniare este mai uoar dect a relaiilor neliniare. Mai mult, unele dintre metodele utilizate n matematica neliniar sunt similare cu cele din matematica liniar sau sunt extensii ale acestora.

1.1 Matrice i determinani

n aceast seciune vor fi punctate cteva definiii i proprieti elementare din algebra matriceal. Ne vom limita doar la acele elemente care vor fi folosite n seciunile i capitolele urmtoare.

Definiia 1.1. Se numete matrice o mulime de m n numere (reale sau complexe) aranjate ntr-un tablou dreptunghiular avnd m linii i n coloane.

2

A

a a aa a a

a a a

n

n

m m mn

=

11 12 1

21 22 2

1 2

K KK K

K K K K KK K

(1.1.1)

Numerele aij, i=1,2 ..., m, j = 1,2, ... , n se mai numesc elementele matricei A. O matrice cu m linii i n coloane se numete matrice de tipul (m, n) sau matrice de ordinul m n.

Notaii: ( ) njmiaAaAaA ijijij ,,2,1,,2,1,,, KK ===== sau, pe scurt, Am,n.

Mulimea matricelor de tipul (m, n) avnd toate elementele din mulimea R a numerelor reale se noteaz Mm,n(R ). n acest curs vor fi folosite numai matrice care au ca elemente numere reale.

Tipuri speciale de matrice O matrice de tip (m, 1) se numete matrice coloan sau vector coloan:

A

aa

am

=

11

21

1

M

(1.1.2)

O matrice de tip (1, n) se numete matrice linie sau vector linie:

( )A a a a n= 11 12 1K (1.1.3) O matrice de tip (n, n) se numete matrice ptratic de ordinul n O

matrice de tip (1, n) se numete matrice linie sau vector linie:

A

a a aa a a

a a a

n

n

n n nn

=

11 12 1

21 22 2

1 2

K KK K

K K K K KK K

(1.1.4)

Elementele a11, a22, ..., ann formeaz diagonala principal a matricei ptratice. Matricea de tipul (m, n) avnd toate elementele egale cu zero se numete

matricea nul de tipul (m, n). Notaie: Om,n. O matrice ptratic ale crei elemente care nu se afl pe diagonala

principal sunt toate nule se numete matrice diagonal.

3

A

aa

ann

=

11

22

0 00 0

0 0

K KK K

K K K K KK K

(1.1.5)

Matricea diagonal pentru care a11 = a22 = ... = ann = 1 se numete matricea unitate de ordinul n. Matricea unitate se noteaz In sau En.

In =

1 0 00 1 0

0 0 1

K KK K

K K K K KK K

(1.1.6)

Egalitatea matricelor Dou matrice de acelai tip Am,n i Bm,n sunt considerate egale dac

elementele lor sunt, respectiv, egale:

a b i m j nij ij= = =1 2 1 2, , , , , ,K K (1.1.6)

Notaie: A = B.

Adunarea matricelor Dou matrice de acelai tip Am,n i Bm,n pot fi adunate. Se definete suma

matricelor A i B ca fiind matricea Cm,n obinut adunnd elementele corespunztoare din A i B.

( )C c c a b i m j nij ij ij ij= = + = =1 2 1 2, , , , , ,K K (1.1.7) Notaie: C = A + B. Adunarea matricelor are urmtoarele proprieti: 1. A + B = B + A (comutativitate) 2. (A + B) + C = A + (B + C) (asociativitate) 3. A + O = O + A = A (element neutru) 4. Pentru orice matrice A Mm,n(R ) exist o matrice - A Mm,n(R )

astfel nct

A + (-A) = (-A) + A = Om,n (1.1.8)

Matricea -A se numete matricea opus lui A i

( ) ( )A a A a i m j nij ij= = = =, , , , , , , ,1 2 1 2K K (1.1.9)

4

nmulirea matricelor Fie dou matrice A i B. Se poate defini produsul AB (n aceast ordine)

dac numrul de coloane ale lui A este egal cu numrul de linii ale lui B. Deci, dac Am,n i Bn,p, atunci se poate defini matricea produs Cm,p, de tip (m, p), ale crei elemente se calculeaz cu relaia:

c a b a b a b a b i m j pij i j i j in nj ik kjk

n

= + + + = = ==1 1 2 2

1

1 2 1 2K K K, , , , , , , (1.1.10)

Notaie: C = AB.

nmulirea matricelor are urmtoarele proprieti: 1. (AB)C = A(BC) (asociativitate) 2. A(B + C) = AB + AC (distributivitate la stnga fa de adunare)

dac Am,n, Bn,p, Cn,p 3. (A + B)C = AC + BC (distributivitate la dreapta fa de adunare)

dac Am,n, Bm,n, Cn,p 4. Dac A este o matrice ptratic de ordinul n, atunci AIn = InA = A,

unde In este matricea unitate de ordinul n. (element neutru la nmulire)

nmulirea unei matrice cu un scalar Produsul unei matrice Am,n = (aij), i = 1,2,..., m, j =1,2, ..., n cu un numr

(scalar) R este o matrice Bm,n = (bij), i = 1,2,..., m, j =1,2, ..., n ale crei elemente se obin astfel:

b a i m j nij ij= = = , , , , , , ,1 2 1 2K K (1.1.11)

Notaie: B = A = A. nmulirea cu scalar are urmtoarele proprieti: 1. 1A =A 2. ( + ) A = A + A 3. (A + B) = A + B 4. () A = (A) 5. (AB) = (A) B

Determinani

Definiia 1.1.2 Fie o matrice ptratic A de ordinul n. Se numete determinantul lui A, numrul detA definit prin relaia:

( )( )

det, , ,

A a a an nn

= 1 1 21 21 2

K

K (1.1.12)

unde 1 2, ,K n sunt toate elementele mulimii { }1 2, , ,K n , iar suma

cuprinde toate permutrile posibile ale acestora i

5

= 0 dac permutarea este par i = 1 dac permutarea este impar. Notaie:

det A

a a aa a a

a a a

n

n

n n nn

=11 12 1

21 22 2

1 2

K KK K

K K K K KK K

Definiia 1.1.3 O matrice ptratic A de ordinul n al crei determinant este diferit de zero (det A 0) se numete matrice nesingular. n caz contrar, ea se numete matrice singular.

Rangul unei matrice Fie A o matrice de tip (m, n). Dac n aceast matrice se aleg la ntmplare

k linii i k coloane (k min{m, n}), elementele aflate la intersecia acestora formeaz o matrice ptratic de ordinul k. Determinantul acestei matrice se numete minor de ordinul k al matricei A.

Definiia 1.1.4 Se spune c o matricea A are rangul r dac: A are un minor nenul de ordinul r i toi minorii de ordin mai mare de r sunt nuli. Notaie: rang A = r

Urmtoarea teorem este util pentru calcularea rangului unei matrice.

Teorema 1.1.1 Fie o matrice A Om,n. Numrul natural r este rangul matricei date dac: exist un minor nenul de ordinul r al matricei A i toi minorii de ordinul r + 1 (dac ei exist) sunt nuli.

Matrice inversabile Se poate vorbi de inversa unei matrice doar n cazul matricelor ptratice

Definiia 1.1.5 Fie o matricea A ptratic de ordinul n. Se spune c A este inversabil dac exist o matricea ptratic de ordinul n notat A-1 astfel nct:

AA A A In = =1 1 (1.1.13)

Urmtoarea teorem este util pentru a decide dac o matrice este inversabil.

Teorema 1.1.2 Fie o matricea A ptratic de ordinul n. Matricea A este inversabil dac i numai dac ea este nesingular, adic det A 0.

6

Exemple: a) adunarea matricelor

,209171

862263103421

826132

623041

=

+++++=

+

b) nmulirea matricelor

( )( ) ( ) ( ) ,610

81211422013412

231021033011

2013

21

142301

=

++++++++=

c)nmulirea unei matrice cu un scalar

( ) .02

3042

012130

421

012130

421

=

=

aaaaaaa

aaaaaa

aaaa

1.2 Ecuaii liniare

Ecuaiile liniare vor juca un rol foarte important n modelele matematice care vor fi abordate n capitolele urmtoare. De aceea este util punctarea, n aceast seciune, a elementelor necesare legate de acest subiect. Vor fi discutate aici i interpretrile geometrice care se pot face n legtur cu ecuaiile liniare n dou variabile. De aceea, aceast categorie de ecuaii liniare va fi scoas n eviden n mod deosebit.

Definiia 1.2.1 O ecuaie liniar n dou variabile, x i y, are forma general:

ax by c+ = (1.2.1)

unde a b c, , R , iar a i b nu pot fi ambele zero. Definiia 1.2.2 O ecuaie liniar n n variabile are forma general:

a x a x a x bn n1 1 2 2+ + + =K (1.2.2)

unde a a a bn1 2, , , ,K R , iar a a an1 2, , ,K nu pot fi toate zero. Se observ c ecuaiile liniare sunt ecuaii de gradul nti: fiecare variabil

de ecuaie este (implicit) la puterea nti. Definiia 1.2.2 generalizeaz definiia 1.2.1. Atunci cnd se lucreaz cu

ecuaii n dou variabile este posibil reprezentarea grafic a ecuaiilor.

7

Soluiile ecuaiei liniare

Definiia 1.2.3 Fie o ecuaie liniar n dou variabile ax by c+ = . Se numete mulimea soluiilor ecuaiei, mulimea perechilor ordonate (x, y) care satisfac ecuaia.

( ){ }S x y ax by c= + =, | (1.2.3) O observaie important este c, oricare ar fi o ecuaie liniar n dou

variabile, mulimea S a soluiilor are un numr infinit de elemente. Deci exist un numr infinit de perechi ordonate (x, y) care satisfac ecuaia.

Pentru a determina o soluie a ecuaiei, se ia o valoare oarecare pentru una dintre variabile, se substituie aceast valoare n ecuaie, dup care rezult cealalt component.

Definiia 1.2.4 Fie ecuaia liniar n n variabile (1.2.2). Se numete mulimea soluiilor ecuaiei, mulimea n-uplelor ordonate (x1,..., xn) care satisfac ecuaia.

( ){ }S x x x a x a x a x bn n n= + + + =1 2 1 1 2 2, , , |K K (1.2.4) Ca i n cazul ecuaiilor n dou variabile, mulimea S este infinit.

Reper cartezian

Definiia 1.2.5 O dreapt d pe care s-au luat: un punct O numit origine, un sens de parcurgere (pozitiv) i o unitate de msur exprimat printr-un segment (considerat de lungime 1) se numete ax de coordonate. Notaie: Ox

Definiia 1.2.6 Fie (Ox, Oy) o pereche ordonat de axe de coordonate cu originea comun O. Acest ansamblu se numete reper cartezian. Dac cele dou axe de coordonate sunt perpendiculare, atunci reperul cartezian se numete drept sau rectangular. Axa Ox se numete abscis, iar axa Oy se numete ordonat. Notaie: xOy Folosind un reper rectangular, fiecare punct din plan poate fi identificat

unic printr-o pereche ordonat unic de numere numite coordonatele punctului. Invers, fiecrei perechi ordonate de numere (x, y) i corespunde un punct unic n plan.

n figura 1.2.1 este figurat un punct M(x1, y1) ntr-un reper ortogonal xOy.

8

Reprezentarea grafic a unei ecuaii liniare A reprezenta grafic o ecuaie liniar nseamn a reprezenta ntr-un reper

ortogonal mulimea S soluiilor sale. Fiecare soluie a ecuaiei (1.2.1) fiind o pereche ordonat de numere (x, y), ea poate fi reprezentat ca un punct n plan. De exemplu, dac x =1 i y = 3 satisfac o ecuaie liniar n dou variabile, atunci reprezentarea grafic a acestei soluii este punctul de coordonate (1, 3) din plan.

Teorema 1.2.1 Mulimea S a soluiilor unei ecuaii liniare n dou variabile reprezentat grafic ntr-un reper cartezian ortogonal este o dreapt. Rezult c, pentru a face reprezentarea grafic a ecuaiei, este suficient s

se determine dou soluii ale sale. Fiecare soluie va fi reprezentat printr-un punct n reperul cartezian bidimensional. Cele dou puncte determin dreapta care reprezint mulimea soluiilor ecuaiei.

Exemplu: S se reprezinte grafic ecuaia 2x + 4y = 16.

Trebuie gsite dou soluii ale ecuaiei pentru a determina dreapta care este reprezentarea tuturor soluiilor.

pentru x = 0 y = 4 (0, 4) este soluie pentru y = 0 x = 8 (8, 0) este soluie

Reprezentarea este ilustrat n figura 1.2.2.

Corespondena ntre mulimea soluiilor unei ecuaii de gradul nti n dou variabile i mulimea punctelor din plan care formeaz o dreapt, face util trecerea n revist a ctorva elemente privind geometria analitic a dreptei n plan.

Prima remarc n acest sens este c ecuaia liniar n dou variabile n form general (1.2.1) coincide cu ecuaia unei drepte n form general.

Fig. 1.2.1

Fig. 1.2.2

O x

y

A(0, 4)

B(8, 0)

M(x1, y1)

O x

y

x1

y1

9

Intersecii cu axele Atunci cnd se fac reprezentri grafice ale unei drepte ntr-un reper

cartezian, dou puncte de interes sunt interseciile cu axele de coordonate. Intersecia dreptei cu axa Ox este punctul care se obine fcnd y = 0. Intersecia dreptei cu axa Oy este punctul care se obine fcnd x = 0. n exemplul ilustrat n figura 1.2.2 aceste puncte au fost calculate i sunt

A(0,4) i B(8,0).

Ecuaia x = k O form particular a ecuaiei ax by c+ = se obine pentru b =0. Ecuaia

devine

ax c= sau x ca

=

Notnd ca

k= rezult o forma particular

x k= (1.2.5)

Aceast ecuaie liniar are un caracter special n sensul c x este egal cu k, indiferent ct este valoarea lui y. Consecina este c graficul unei astfel de ecuaii este o dreapt paralel cu axa Oy.

O astfel de dreapt este trasat n figura 1.2.3.

Ecuaia y = k O alt form particular a ecuaiei ax by c+ = se obine pentru a =0.

Ecuaia devine

by c= sau y cb

=

Notnd cb

k= rezult o forma particular

y k= (1.2.6)

Aceast ecuaie liniar are un caracter special n sensul c y este egal cu k, indiferent ct este valoarea lui x. Consecina este c graficul unei astfel de ecuaii este o dreapt paralel cu axa Ox.

O astfel de dreapt este trasat n figura 1.2.4.

Fig. 1.2.3

O x

y

k

x = k

10

" Rezolvai exerciiile 1 pn la 8 de la pagina 35.

Panta Orice dreapt, cu excepia celor verticale, este caracterizat de pant.

Panta indic msura n care se modific valoarea lui y ca rspuns la o modificare a valorii lui x. Panta este exprimat printr-un numr real. Semnul acestuia indic tendina cresctoare sau descresctoare a dreptei.

Panta pozitiv indic un caracter cresctor al dreptei adic, pe msura

creterii valorilor lui x, cresc i valorile lui y (ca dreapta d1 din figura 1.2.5). Panta negativ indic un caracter descresctor al dreptei adic, pe msura

creterii valorilor lui x, valorile lui y descresc (ca dreapta d2 din figura 1.2.5). Valoarea zero a pantei arat c dreapta este paralel cu axa Ox (nu este

nici cresctoare nici descresctoare, ca dreapta d3 din figura 1.2.5). Se consider c pentru dreptele paralele cu Oy panta este nedefinit (ca

dreapta d4 din figura 1.2.5). Nu numai semnul pantei este important, ci i valoare absolut a acesteia.

Cu ct valoarea absolut a pantei este mai mare, cu att variaia lui y este mai mare n raport cu o aceeai cretere a lui x.

Fig. 1.2.4

Fig. 1.2.5

O x

y d4

d3 (0)

d1 (+)

d2 (-)

O x

y

k

y = k

11

n figura 1.2.6 sunt dou drepte care au pant pozitiv, dar panta lui d2 este mai mare dect panta lui d1. n figura 1.2.7 sunt dou drepte care au pant negativ, dar panta lui d2 este mai mare, n valoare absolut, dect panta lui d1.

Urmtoarea definiie sintetizeaz cele discutate mai sus i introduce o modalitate de calcul a pantei unei drepte determinate de dou puncte.

Definiia 1.2.7 Fie punctele M(x1, y1) i N(x2, y2) cu x1 x2. Se definete panta dreptei determinate de punctele M i N prin

m y yx x

= 2 1

2 1 (1.2.7)

Figura 1.2.8 ilustreaz calcularea pantei definite prin relaia 1.2.7.

O alt interpretare a pantei este dat de urmtoarea definiie

Definiia 1.2.8 Panta dreptei este variaia valorii lui y atunci cnd x crete cu o unitate. n conformitate cu definiia 1.2.8, dac o dreapt are panta 8 3 , aceasta

nseamn c, dac x crete cu o unitate, y va crete cu 8 3 uniti.

Fig. 1.2.6

Fig. 1.2.7

Fig. 1.2.8

O O x x

y y

d1 d1

d2 d2

x2 - x1

O x

y

M(x1, y1)

N(x2, y2)

y2 - y1

x1 x2

y1

y2

12

O alt interpretare a pantei rezult imediat din figura 1.2.8 n care se evideniaz faptul c dreapta face cu abscisa un unghi msurat de la Ox n sens trigonometric (sensul contrar rotirii acelor de ceasornic, aa cum indic sgeata).

Definiia 1.2.9 Panta dreptei este tangenta unghiului (msurat n sens trigonometric) pe care dreapta l face cu axa Ox.

m tg= (1.2.7')

n afar de ecuaia general (1.2.1), o dreapt mai poate avea i alte forme de ecuaii. Ele sunt enumerate n continuare.

Ecuaia prin pant i tietur Plecnd de la ecuaia general (1.2.1) se poate obine o nou form fcnd

transformrile de mai jos

ax by c by ax c y ab

x cb

+ = = + = +

Notnd =ab

m i cb

k= se obine

y mx k= + (1.2.8)

Relaia (1.2.8) se numete ecuaia dreptei prin pant i tietur. Notaiile

alese exprim tocmai faptul c m este panta dreptei, iar k este tietura acesteia cu axa Oy (figura 1.2.9). ntr-adevr:

- pentru x = 0 se obine y = k, deci punctul de coordonate (0, k) este intersecia dreptei cu Oy;

- pentru o cretere unitar x2 - x1 = 1 avem ( ) ( )y y mx k mx k m x x m2 1 2 1 2 1 = + + = = , iar relaia obinut arat c o cretere cu o unitate a lui x determin o variaie cu m a lui y. Conform definiiei 1.2.8 rezult c m din relaia (1.2.8) este chiar panta dreptei.

Fig. 1.2.9

O x

y

k

13

Ecuaia prin pant i un punct Un alt caz este acela n care se cunoate panta m a dreptei i un punct (x0,

y0) al acesteia. Coordonatele punctului vor verifica, deci, ecuaia (1.2.8). Avem:

y mx k k y mx0 0 0 0= + =

nlocuind expresia lui k n ecuaia prin pant i tietur (1.2.8), dup efectuarea calculelor rezult expresia

( )y y m x x = 0 0 (1.2.9) care se numete ecuaia dreptei prin pant i un punct.

Ecuaia prin dou puncte Dac se cunosc (figura 1.2.10) coordonatele a dou puncte de pe dreapt

A(x1, y1) i B(x2, y2), se poate determina o nou form a ecuaiei plecnd de la faptul c A i B verific att ecuaia prin pant i tietur (1.2.8) ct definiia 1.2.7 a pantei. Astfel,

y mx k

m y yx x

y y yx x

x k k y y yx x

x1 1

2 1

2 1

12 1

2 11 1

2 1

2 11

= +=

= + =

nlocuind acum relaiile pentru m i k n ecuaia prin pant i tietur (1.2.8), rezult

y y yx x

x y y yx x

x= +

2 1

2 11

2 1

2 11

Prin prelucrarea relaiei de mai se sus se pot obine urmtoarele trei forme care reprezint variante pentru ecuaia dreptei prin dou puncte:

Fig. 1.2.10

A(x1, y1)

B(x2, y2)

O x

y

14

( )

( ) ( ) ( )

y y y yx x

x x y yy y

x xx x

x yx yx y

a b c

= =

=1

2 1

2 11

1

2 1

1

2 11 1

2 2

111

0

(1.2.10)

Ecuaia prin tieturi n cazul n care se cunosc interseciile dreptei cu axele, A(a, 0) i B(0, b),

acestea se pot nlocui ntr-una din formele ecuaiei prin dou puncte, de exemplu (1.2.10b). Dup prelucrri elementare rezult

xa

yb

+ =1 0

(1.2.11)

cunoscut ca ecuaia dreptei prin tieturi.

" Rezolvai exerciiile 9 pn la 18 de la pagina 35.

Poziiile relative a dou drepte Dou drepte d1 i d2 sunt:

paralele dac i numai dac intersecia lor este mulimea vid; coincidente dac i numai dac intersecia lor este o dreapt; secante dac i numai dac intersecia lor este un punct.

Fie, atunci, dou drepte n form explicit, d1: y1 = m1x + k1 i d1: y2 = m2x + k2. Acestea sunt:

paralele dac i numai dac m1 = m2 i k1 k2; coincidente dac i numai dac m1 = m2 i k1 = k2; secante dac i numai dac m1 m2; perpendiculare dac i numai dac m1m2 = -1.

Fie dou drepte n form general, d1: a1x + b1y = c1 i d2: a2x+ b2y = c2. Ele sunt:

Fig. 1.2.11

O x

y

B(0, b)

A(a, 0)

15

paralele dac i numai dac aa

bb

cc

1

2

1

2

1

2= ;

coincidente dac i numai dac aa

bb

cc

1

2

1

2

1

2= = ;

secante dac i numai dac aa

bb

1

2

1

2 ;

perpendiculare dac i numai dac a1a2 + b1b2 = 0.

Distane Fiind date punctele A(x1, y1) i B(x2, y2), se arat uor, aplicnd teorema

lui Pitagora n triunghiul ABP (figura 1.2.12) c distana ntre A i B este:

( ) ( )AB = + x x y y2 1 2 2 1 2

(1.2.12)

Dndu-se dreapta h: ax + by = c i punctul P(x0, y0) exterior acesteia

(figura 1.2.13), se poate arta c distana de la punctul P la dreapta h se calculeaz cu relaia:

( )d h ax by ca b

P; = + +

0 0

2 2

(1.2.13)

Fig. 1.2.12

Fig. 1.2.13

A(x1, y1)

B(x2, y2)

O x

y

P(x2, y1)

y2

y1

x2 x1

O x

y

P(x0, y0)

h

16

Reprezentri pentru ecuaii liniare n mai mult de dou variabile

Pentru ecuaii liniare n mai mult de dou variabile considerentele algebrice rmn aceleai dar, reprezentrile grafice se schimb sau nu mai sunt posibile.

Ecuaiile liniare n trei variabile, de forma general

a1x1 + a2x2 + a3x3 = b (1.2.14)

se reprezint grafic prin plane ntr-un reper cartezian tridimensional. Reprezentarea se face aflnd punctele de intersecie ale planului cu axele de coordonate Ox1, Ox2, Ox3.

Proprietate. O ecuaie de forma xj = k, j = 1, 2, 3 va avea ca grafic un plan perpendicular pe axa Oxj i care este situat la distana k de origine.

Pentru ecuaiile liniare n mai mult de trei variabile reprezentarea grafic nu este posibil. Se folosete, n acest caz, noiunea de hiperplan ca fiind o reprezentare geometric abstract a ecuaiei. Astfel, se spune c o ecuaie liniar n n variabile

a1x1 + a2x2 + ... + anxn = b, n > 3

este un hiperplan ntr-un spaiu cu n dimensiuni.

1.3 Sisteme de ecuaii liniare

Dup cum se va vedea n capitolul 2, multe fenomene din lumea real se pot modela cu ajutorul sistemelor de ecuaii liniare. Aceast seciune le este dedicat.

Definiia 1.3.1 Se numete sistem (liniar) de m ecuaii cu n necunoscute ansamblul de

ecuaii liniare

a x a x a x ba x a x a x b

a x a x a x b

n n

n n

m m mn n m

11 1 12 2 1 1

21 1 22 2 2 2

1 1 2 2

+ + + =+ + + =

+ + + =

KK

K...........................................

a b

i m j nij i

R R,

,1 1

(1.3.1)

Variabilele x1, x2, ..., xn R se numesc necunoscutele sistemului; aij 1 i m, 1 j n se numesc coeficienii sistemului; bi 1 i m se numesc termenii liberi.

17

Matricele

A

a a aa a a

a a a

n

n

m m mn

=

11 12 1

21 22 2

1 2

K KK K

K K K K KK K

i ~A

a a a ba a a b

a a a b

n

n

m m mn m

=

11 12 1 1

21 22 2 2

1 2

KK

K K K K KK

(1.3.2)

se numesc: A(m, n) - matricea coeficienilor sistemului sau, simplu, matricea

sistemului i (m, n+1) - matricea extins a sistemului. Dac pentru necunoscute i termenii liberi se folosesc vectorii coloan

X

xx

xn

=

1

2

M i B

bb

bm

=

1

2

M

(1.3.3)

atunci sistemul (1.3.1) se poate scrie sub forma matriceal

AX = B

(1.3.1')

Dimensiunea matricei sistemului fiind foarte important, adesea se folosesc expresiile sistem m n sau sistem m pe n.

Un sistem liniar se numete omogen dac bi = 0, 1 i m deci dac

termenii liberi sunt toi nuli; n caz contrar sistemul se numete neomogen.

Definiia 1.3.2 Se numete soluie a unui sistem liniar de forma (1.3.1) un n-uplu (x1, x2, ..., xn) care verific simultan toate cele m ecuaii ale acestuia. Sistemul (1.3.1) se numete compatibil dac are cel puin o soluie i incompatibil n caz contrar. Un sistem compatibil se numete compatibil determinat dac are o singur soluie i se numete compatibil nedeterminat dac are mai multe soluii. Dup cum se vede i din definiia 1.3.2, problema fundamental n

legtur cu un sistem liniar este determinarea mulimii S a soluiilor sale, adic a tuturor n-uplelor care verific simultan toate ecuaiile, precum i ncadrarea lui din acest punct de vedere. n legtur cu aceast problem urmtoarele rezultate sunt eseniale.

Teorema 1.3.1 (Kronecker-Capelli) Fie rangul matricei sistemului rang A = p i rangul matricei extinse rang = q. Atunci sistemul (1.3.1) este compatibil dac i numai dac p = q.

Consecina imediat a teoremei Kronecker-Capelli este c stabilete situaiile n care se poate afla un sistem liniar din punctul de vedere al numrului de soluii. Astfel, se poate demonstra c este valabil urmtoarea

18

Clasificare Fiind dat un sistem liniar de m ecuaii cu n necunoscute, exist urmtoarele trei posibiliti i numai acestea: I. sistemul este compatibil determinat (are soluie unic); aceasta se

ntmpl dac rangul matricei sistemului este egal cu rangul matricei extinse i egal cu numrul necunoscutelor:

rang A = rang = n

II. sistemul este compatibil nedeterminat (are o infinitate de soluii); aceasta se ntmpl dac rangul matricei sistemului este egal cu rangul matricei extinse, dar mai mic dect numrul necunoscutelor:

rang A = rang i rang A < n III. sistemul este incompatibil (nu are nici o soluie); aceasta se ntmpl

dac rangul matricei sistemului este mai mic dect rangul matricei extinse:

rang A < rang

Reprezentri grafice pentru sisteme de ecuaii cu dou necunoscute n cazul sistemelor cu dou necunoscute ecuaiile se pot reprezenta ca

drepte n plan, aa cum a fost artat n paragraful 1.2.2. Un sistem de dou ecuaii cu dou necunoscute

a x b y ca x b y c

1 1 1

2 2 2

+ =+ =

(1.3.4)

se reprezint ca dou drepte n plan, iar mulimea soluiilor

( ){ }S x y a x b y c a x b y c= + = + =, | 1 1 1 2 2 2 (1.3.5) va fi format din acele puncte care aparin simultan ambelor drepte care pot fi notate, respectiv, d1 i d2. Interpretarea grafic duce la situaiile ilustrate n figurile 1.3.1, a, b i c.

a)

b)

Fig. 1.3.1

c)

x O

y

d1 d2

x0

y0

x O

y

d2

d1

x O

y

d1

d2

19

n figura 1.3.1.a dreptele secante d1 i d2 sunt interpretarea geometric a unui sistem compatibil determinat; punctul lor de intersecie reprezint soluia unic, adic S = {(x0, y0). Dreptele paralele din figura 1.3.1.b sunt interpretarea geometric a unui sistem incompatibil; absena punctelor comune ilustreaz lipsa soluiilor, adic S = . Figura 1.3.1.b este reprezentarea grafic a unui sistem compatibil nedeterminat; dreptele d1 i d2 sunt coincidente, ceea ce ilustreaz faptul c mulimea S este format dintr-o infinitate de soluii.

Interpretri geometrice sunt posibile i pentru sisteme m 2. Figurile 1.3.2, a, b i c ilustreaz situaiile posibile pentru un sistem de 3 ecuaii cu dou necunoscute, respectiv sistem compatibil determinat, sistem incompatibil i sistem compatibil nedeterminat.

Reprezentrile grafice discutate mai sus sunt o ilustrare sugestiv a

clasificrii pentru sistemele liniare care este indus de teorema Kronecker-Capelli. Definiia urmtoare i cele trei transformri care vor fi enunate dup

aceasta sunt de mare importan pentru cele ce vor fi abordate n restul acestui capitol, precum i n urmtorul.

Definiia 1.3.3 Dou sisteme de ecuaii se numesc echivalente dac au aceeai mulime S a soluiilor.

Definiia 1.3.4 Se numete transformare elementar asupra unui sistem de ecuaii liniare, aplicarea uneia dintre urmtoarele operaii: T1. nmulirea unei ecuaii cu un numr diferit de zero; T2. Adunarea unei ecuaii la o alt ecuaie; T3. Schimbarea ordinii ecuaiilor.

Evident, aplicarea fiecreia dintre cele trei transformri elementare asupra sistemului determin o transformare a matricei extinse . De aceea se pot defini corespunztor transformrile elementare ale acesteia.

Definiia 1.3.4' Se numete transformare elementar asupra matricei extinse a unui sistem de ecuaii liniare, aplicarea uneia dintre urmtoarele operaii: T1. nmulirea unei linii cu un numr diferit de zero;

a)

b)

Fig. 1.3.2

c)

x O

y

d1

d2

x O

y

d1 d2

x0

y0

d3 d3

x O

y

d3

d1

d2

20

T2. Adunarea unei linii la o alt linie, element cu element; T3. Schimbarea ordinii liniilor. Aplicarea unei transformri elementare asupra sistemului nseamn

aplicarea transformrii elementare corespunztoare asupra matricei extinse i invers. De aceea, n definiiile 1.3.4 i 1.3.4', s-a folosit aceeai numerotare a transformrilor.

Teorema 1.3.2 Orice sistem liniar se transform ntr-un sistem echivalent prin aplicarea unei succesiuni arbitrare de transformri echivalente. Fie acum un sistem de m ecuaii cu n necunoscute de forma (1.3.1),

compatibil (determinat sau nedeterminat) i fie rang A = rang = p; evident, p min(m, n). Rezult, conform definiiei rangului, c exist cel puin un minor de ordinul p diferit de zero. Fie P(p,p) matricea corespunztoare acestui minor. Pentru simplitate, dar fr a afecta generalitatea, se poate presupune c P este format chiar din primele p linii i p coloane ale matricei A:

P

a a aa a a

a a a

p

p

p p pp

=

11 12 1

21 22 2

1 2

K KK K

K K K K KK K

(1.3.6)

Definiia 1.3.5 Determinantul matricei P, det(P) 0, se numete minor principal al sistemului (1.3.1). Ecuaiile sistemului care corespund liniilor lui P se numesc ecuaii principale, iar celelalte ecuaii se numesc ecuaii secundare. Sistemul format cu ecuaiile principale este deci, conform relaiei (1.3.6),

a x a x a x ba x a x a x b

a x a x a x b

n n

n n

p p pn p p

11 1 12 2 1 1

21 1 22 2 2 2

1 1 2 2

+ + + =+ + + =

+ + + =

KK

K...........................................

(1.3.7)

Teorema 1.3.3 Sistemul (1.3.1) i sistemul (1.3.7) format cu ecuaiile principale sunt sisteme echivalente. Din teorema 1.3.3 rezult c ecuaiile secundare ale unui sistem, dac

exist astfel de ecuaii, pot fi eliminate fr ca aceasta s modifice mulimea soluiilor. Se mai poate arta c ecuaiile secundare sunt combinaii liniare ale ecuaiilor principale.

Definiiile 1.3.4 i 1.3.4', precum i teorema 1.3.2 permit introducerea unei metode foarte convenabile de rezolvare a sistemelor de ecuaii liniare. Metoda

21

permite, de asemenea, eliminarea ecuaiilor secundare din cadrul sistemului astfel nct n final s se obin un sistem format numai din ecuaii principale.

Rezolvarea sistemelor de ecuaii prin metoda eliminrii complete Fie, pentru nceput, urmtorul exemplu de sistem de trei ecuaii cu trei

necunoscute:

4 2 93 2 7

2

1 2 3

1 2 3

1 2 3

x x xx x xx x x

= + =+ + =

(1.3.8)

Rezolvnd sistemul folosind, de exemplu, regula lui Cramer, se obine soluia x1 = 2, x2 = -1, x3 = 1. Cu alte cuvinte, sistemul (1.3.8) este echivalent cu sistemul

xx

x

1

2

3

211

== =

(1.3.9)

Se pune problema cum s-ar putea face trecerea sistemului dat de la forma (1.3.8) la forma final (1.3.9) aplicnd transformri elementare. Metoda eliminrii complete i propune tocmai ca, prin transformri elementare, s aduc un sistem de la forma sa iniial la o form care s permit citirea direct a soluiei. Deci, pentru un sistem 3 3,

a x a x a x ba x a x a x ba x a x a x b

11 1 12 2 13 3 1

12 1 22 2 23 3 2

31 1 32 2 33 3 3

+ + =+ + =+ + =

... x v

x vx v

1 1

2 2

3 2

===

forma iniial transformri soluie elementare

(1.3.10)

De fapt, metoda acioneaz asupra matricei extinse a sistemului, deci asupra liniilor acesteia se fac transformrile:

a a aa a aa a a

bbb

11 12 13

12 22 23

31 32 33

1

2

3

... 1 0 00 1 00 0 1

1

2

3

vvv

forma iniial transformri soluie elementare

(1.3.11)

Dup cum se observ din (1.3.11), soluia sistemului, x1 = v1, x2 = v2, x3 = v3, poate fi citit direct de pe matricea extins. Pentru sisteme de n ecuaii cu n necunoscute metoda este cunoscut i sub numele de metoda Gauss-Jordan i

22

const n transformarea unui sistem de ecuaii liniare care are o matrice a coeficienilor ptratic, ntr-un sistem echivalent care are ca matrice a coeficienilor, chiar matricea unitate.

Generalizarea pentru sisteme m n este simpl: ideea central a metodei eliminrii complete este de a aduce matricea extins a sistemului la o form care s conin n partea stng numrul maxim posibil de coloane ale matricei unitate.

Metoda se aplic iterativ, ncepnd cu coloana 1; la fiecare iteraie se obine o nou coloan a matricei unitate pstrnd, bineneles, coloanele obinute la etapele anterioare. Procesul de obinere a unei coloane a matricei unitate se numete pivotaj i se realizeaz efectund transformri elementare asupra liniilor. Pivotajul se desfoar n dou etape care sunt descrise n continuare.

Etapele pivotajului Fie j coloana asupra creia se execut pivotajul. Pivotul va fi elementul ajj. A. Se creeaz elementului egal cu 1 pe poziia (j, j). Pentru ca aceast lucru

s fie posibil trebuie ca ajj s fie nenul. A1. Dac ajj 0, atunci se mparte linia j la valoarea ajj (se aplic T1)

i se trece la etapa B. A2. Dac ajj = 0, se caut printre aj+1,j, ..., an,j (adic pe coloana j, sub

ajj), un element nenul; Dac printre aj+1,j, ..., an,j se gsete un element akj 0 (j < k

n), atunci se inverseaz ntre ele liniile j i k (se aplic T3), se obine astfel ajj 0, dup care se poate face 1 pe poziia (j, j) mprind linia j la valoarea ajj.

Dac printre aj+1,j, ..., an,j nu se gsete nici un element diferit de zero, atunci se ntrerupe pivotajul pe aceast coloan i se trece la urmtoarea.

B. Se transform n zerouri toate elementele de pe coloan n afara pivotului. Pentru aceasta se nmulete linia j, a pivotului, cu o valoare convenabil, adunnd-o apoi la linia n care trebuie s se obin zeroul (se aplic T1, apoi T2). Astfel, obinerea pe poziia (l, j) a unui zero n locul valorii alj, se face nmulind linia j (pe care se afl pivotul ajj =1) cu valoarea -alj i adunnd-o la linia l.

Dup pivotajul unei coloane se fac urmtoarele verificri: Verificarea 1. Se controleaz dac pe vreo linie s-au obinut zerouri n

zona coeficienilor sistemului i o valoare diferit de zero pe poziia termenului liber. n acest caz pivotajul se ntrerupe: sistemul este incompatibil. Urmtorul exemplu ilustreaz de ce. S presupunem c, pentru un sistem de trei ecuaii cu trei necunoscute se obine, la un moment dat, matricea extins

1 5 20 6 30 0 0

21

6

Aceasta nseamn c, prin transformri elementare, s-a ajuns de la sistemul iniial la sistemul echivalent

23

==+=+

60136225

32

321

xxxxx

Faptul c, n forma la care s-a ajuns, ultima ecuaie nu are sens denot c att acest sistem ct i cel iniial, cu care este echivalent, sunt incompatibile. Aceleai consideraii se pot face, evident, pentru orice alt sistem adus n aceast situaie.

Verificarea 2. Se controleaz dac pe vreo linie s-au obinut numai zerouri, inclusiv pe poziia termenului liber. Atunci linia respectiv poate fi eliminat pentru c ecuaia corespunztoare ei este o combinaie liniar a celorlalte ecuaii din sistem (este o ecuaie secundar). Se va continua rezolvarea sistemului rmas dup eliminarea ecuaiei secundare. De exemplu, dac pentru un sistem de trei ecuaii cu trei necunoscute se obine, dup primul pivotaj, matricea extins

1 5 20 0 00 3 8

206

atunci aceast matrice corespunde sistemului, echivalent cu cel iniial,

=+=

=+

68300

225

32

321

xx

xxx

Ecuaia a doua a sistemului iniial, fiind o combinaie liniar a celorlalte dou, a devenit identitatea 0 = 0 i poate fi eliminat. Rmne de rezolvat un sistem cu dou ecuaii.

Exemplul 1.3.1

S se rezolve sistemul (1.3.8):

=++=+=

2723924

321

321

321

xxxxxxxxx

24

Este convenabil, dar nu obligatorie, organizarea calculelor ntr-o form tabelar ca cea alturat.

Pentru fiecare coloan se observ cele dou etape ale pivotajului: A. Stabilirea pivotului i aducerea sa la valoarea 1; n aceast etap este notat

alturi de tabel valoarea convenabil cu care trebuie nmulit linia. B. Crearea de zerouri pe restul coloanei; pentru aceast etap sunt notate alturi

valorile convenabile cu care trebuie nmulit linia pivotului nainte de a fi adunat o alt linie, iar sgeile indic liniile la care se face adunarea.

Exemplul 1.3.2

S se rezolve sistemul:

4 2 93 2 7

7 10 8 342

1 2 3

1 2 3

1 2 3

1 2 3

x x xx x xx x xx x x

= + =+ =+ + =

Succesiunea de sisteme echivalente obinute prin aplicarea transformrilor elementare este ilustrat de matricele extinse corespunztoare:

4 -2 -1 9 ( ) 14 1 -3 2 7 1 1 1 2 1 12 14 9 4 (-1) (-1) 1 -3 2 7 1 1 1 2 1 12 14 9 4 0 52 9 4 19 4 ( ) 2 5 0 32 54 14 1 12 14 9 4 0 1 910 1910 12 32 0 32 54 14 1 0 710 1310 0 1 910 1910 0 0 135 135 ( )513 1 0 710 1310 0 1 910 1910 0 0 1 1 ( )910 ( )710 1 0 0 2 0 1 0 -1 0 0 1 1

25

2 1 11 4 27 10 81 2 2

2103410

11 4 27 10 81 2 2

1103410

1000

19

279

12

12

12

12

92

32

272

92

32

52

10 100

12279

1 00 1

0 0 2

22

12

12

12

13

272

92

32

52

23

13

0 0 0 0

S-a obinut o linie( a treia) format numai din zerouri,

inclusiv termenul liber; conform verificrii 2, ea va fi eliminat

1 00 10 0 1

226

1 0 00 1 00 0 1

646

23

13

Sistemul este compatibil determinat i are soluia:

x1 = 6; x2 = 4; x3 = 6

Exemplul 1.3.3

S se rezolve sistemul: + + =

+ + = =

2 3 122 5 10

6 3 9 24

1 2 3

1 2 3

1 2 3

x x xx x xx x x

Succesiunea de sisteme echivalente obinute prin aplicarea transformrilor elementare este ilustrat de matricele extinse corespunztoare:

2 1 31 2 56 3 9

121024

11 2 56 3 9

61024

10

616

12

32

12

32

52

132

0 0 0 60

Ultima linie a matricei extinse la care s-a ajuns a fost scoas n eviden pentru c arat c s-a ajuns la o situaia care, conform verificrii 1, semnaleaz un sistem incompatibil.

Exemplul 1.3.4

S se rezolve sistemul: x x x

x x xx x x

1 2 3

1 2 3

1 2 3

202 3 56 4 4 30

+ + = + = + =

Succesiunea de sisteme echivalente obinute prin aplicarea transformrilor elementare este ilustrat de matricele extinse corespunztoare:

1 1 12 3 16 4 4

205

30

1 1 10 5 10 10 2

204590

1 1 10 10 10 2

20990

1 00 1

11915

45

15

0 0 0 0

26

Dup eliminarea ecuaiei secundare reprezentate de linia a treia format doar din zerouri rmne un sistem compatibil nedeterminat care are necunoscutele principale x1 i x2, iar necunoscuta secundar este x3. Notnd x3 cu R rezult c soluiile se pot scrie:

==

,

5195411

2

1

x

x

Este clar c, aplicnd verificarea 2 dup fiecare pivotaj, se vor elimina pn n final toate ecuaiile secundare (dac au existat astfel de ecuaii), iar sistemul rmas va fi format numai din ecuaii principale, iar matricea unitate obinut va avea ordinul egal cu numrul de ecuaii.

" Rezolvai exerciiile 19 pn la 24 de la pagina 35. Definiia 1.3.6 Se spune c un sistem de ecuaii liniare este explicitat dac matricea sistemului conine toate coloanele matricei unitate de ordin egal cu numrul ecuaiilor sistemului. Conform definiiei 1.3.6, pentru un sistem compatibil, aplicarea metodei

eliminrii complete duce n final la o form explicit a acestuia. Se poate spune, deci, c rezolvarea sistemului este acelai lucru cu explicitarea sa.

Pe de alt parte, dei s-a enunat faptul c metoda eliminrii complete se aplic coloan cu coloan ncepnd cu prima, trebuie remarcat c definiia 1.3.6 presupune doar prezena tuturor coloanelor matricei unitate i nu oblig neaprat ca ea s formeze un bloc n cadrul matricei sistemului. Aceast observaie se va dovedi important ceva mai trziu.

Teorema urmtoare asigur c, folosind metoda eliminrii complete, se ajunge la o concluzie asupra naturii sistemului liniar studiat.

Teorema 1.3.4 Fie sistemul liniar (1.3.1) de m ecuaii cu n necunoscute. Printr-un numr finit de transformri elementare se obine fie rezultatul c sistemul (1.3.1) este incompatibil, fie o form explicit a unui sistem echivalent cu (1.3.1).

Definiia 1.3.7 Fie un sistem de ecuaii liniare adus la o form explicit. Variabilele care corespund coloanelor matricei unitate se numesc variabile principale sau variabile de baz, iar celelalte variabile se numesc variabile secundare sau variabile nebazice. Vom insista n continuare asupra sistemelor compatibile, n special asupra

celor compatibile nedeterminat.

27

innd cont de teorema 1.3.3 i de faptul c prin aplicarea verificrii 2 n metoda eliminrii complete se elimin ecuaiile secundare, vom considera pentru moment c un sistem compatibil nedeterminat are forma (1.3.1), dar ecuaiile secundare sunt eliminate de la nceput.

Aa cum se vede i din exemplul 1.3.1, un sistem compatibil determinat nu are dect variabile principale. Aducerea sa la forma explicit nseamn obinerea unui sistem echivalent care are n partea stng a matricei extinse doar matricea unitate i nimic altceva. n aceast form, soluia poate fi citit direct de pe ultima coloan, cea corespunztoare termenilor liberi. Reinnd i presupunerea c sistemul nu are ecuaii secundare, rezult c poate fi compatibil determinat doar un sistem n n.

De un interes deosebit pentru elementele de programare liniar care vor fi abordate n capitolul 2 sunt, ns, sistemele compatibile nedeterminat. Conform teoremei 1.3.3, un astfel de sistem are rangul egal cu numrul ecuaiilor, iar numrul ecuaiilor este mai mic dect numrul de necunoscute (m < n). El va avea m necunoscute principale i n-m necunoscute secundare. Orice form explicit a sistemului va conine, conform definiiei 1.3.6, toate coloanele matricei unitate de ordin egal cu numrul ecuaiilor. Un astfel de sistem a fost rezolvat n exemplul 1.3.4. Pentru forma explicit obinut, variabilele principale sunt x1, x2, iar variabila secundar este x3. Variabilele principale se exprim n funcie de variabilele secundare care pot primi orice valori reale; n acest fel se obine infinitatea de soluii care a fost enunat la punctul II al clasificrii induse de teorema Kronecker-Capelli. Dintre soluii, unele au o importan special i sunt definite n continuare.

Definiia 1.3.8 Se numete soluie de baz a sistemului liniar (1.3.1) de m ecuaii cu n necunoscute orice soluie a sistemului obinut n cadrul unei forme explicite prin egalarea cu zero a variabilelor secundare. Dac soluia de baz are exact m componente nenule ea se numete nedegenerat, iar dac are mai puin de m componente nenule ea se numete degenerat. Conform definiiei 1.3.8 rezult c soluia de baz a formei explicite la

care s-a ajuns poate fi citit direct din matricea extins a acesteia. Ea formeaz ultima coloan, cea corespunztoare termenilor liberi. Exerciiul din exemplul 1.3.4 este o ilustrare imediat.

Tot din definiia soluiei de baz rezult c, n cadrul acesteia, cel puin n - m variabile sunt nule, adic variabilele secundare. Este, ns, posibil ca, din explicitare, s rezulte i printre variabilele principale unele egale cu zero. Se poate face, din acest punct de vedere, urmtoarea clasificare a soluiilor de baz ale unui sisteme liniar.

Definiia 1.3.9 Dac o soluie de baz are exact m componente nenule, ea se numete

nedegenerat, iar dac are mai puin de m componente nenule se numete degenerat.

Explicitarea unui sistem liniar n raport cu un grup dat de m variabile Pn acum s-a pus problema de a explicita un sistem liniar fr a interesa

care vor fi variabilele principale al sistemului aflat sub form explicit; s-a considerat c ele sunt chiar primele, n ordine ncepnd cu x1. Mai mult, s-a

28

considerat c sistemele discutate nu au ecuaii secundare pentru c, aplicnd verificarea 2 la sfritul fiecrui pivotaj, acestea sunt oricum eliminate.

n continuare vom renuna la ideea simplificatoare c sistemul nu are ecuaii secundare i nici nu vom mai aplica verificarea 2, prin care se elimin aceste ecuaii, n cadrul metodei eliminrii complete. Aceasta deoarece sistemelor liniare despre care se discut n acest capitol i n urmtorul nu sunt simple exerciii. Ele trebuie privite ca modele ale unor situaii din lumea real: costuri sau profituri ntr-un fenomen economic, combinaii ale unor factori tehnologici ntr-un proces industrial sau agricol etc. Prin urmare, nu se poate renuna la vreuna dintre ecuaiile sistemului pe motiv c ea este combinaie liniar a celorlalte, pentru c astfel s-ar ignora fenomenul pe care aceasta l descrie n cadrul modelului.

Tot n acest context, al modelrii unui fenomen din lumea real, trebuie privit i situaia urmtoare: se pune problema de a explicita un sistem de m ecuaii cu n necunoscute n raport cu un grup dat de m variabile (principale). Acest lucru nu este ntotdeauna posibil. Astfel, innd cont de ceea ce s-a discutat pn acum, n cazul unui sistem compatibil care are ecuaii secundare (reductibile) nu se poate face explicitarea n raport cu nici un grup de m variabile. Ba chiar i n cazul unui sistem compatibil fr ecuaii secundare s-ar putea ca explicitarea n raport cu anumite grupuri de m variabile s nu fie posibil.

Deci, explicitarea n raport cu un grup dat de m variabile cere s se realizeze prin transformri elementare toate cele m coloane ale matricei unitate de ordinul m, dar acestea s apar n anumite coloane ale matricei extinse. Pentru aceasta, se stabilesc cele m coloane care vor fi supuse pivotajului (nu neaprat primele) i se ncepe procesul de la stnga spre dreapta. Presupunnd c s-a fcut pivotajul primelor r-1 coloane din cele m alese, la pasul r se procedeaz astfel:

Pe a r-a coloan aleas se stabilete poziia l (linia) unde se dorete s fie pivotul

Pivotajul se face n cele dou etape, uor modificate fa de varianta descris anterior.

A. Se creeaz elementului egal cu 1 pe poziia (l, r). Pentru ca acest lucru

s fie posibil trebuie ca alr s fie nenul. A1. Dac alr 0, atunci se mparte linia l la valoarea alr (se aplic T1)

i se trece la etapa B. A2. Dac alr = 0, se caut pe coloana r supus pivotajului un element

nenul care s poat fi adus pe poziia (l, r) prin schimbarea ordinii liniilor (transformarea T3). Elementul cutat trebuie s nu fie pe una din liniile pe care se afl deja pivoi egali cu 1 realizai n cele r-1 etape anterioare. Adic, prin aplicarea transformrii T3, coloanele din matricea unitate realizate pn atunci trebuie s nu fie distruse aj+1,j, ..., an,j (adic pe coloana j, sub ajj), un element nenul; Dac pe coloana r se gsete un element akr 0 care s poat

fi adus pe poziia (l, r) fr a afecta coloanele din matricea unitate deja construite, atunci se inverseaz ntre ele liniile k i l (se aplic T3); se obine astfel alr 0, dup care se poate face 1 pe poziia (l, r) mprind linia l la valoarea alr.

Dac pe coloana r nu se gsete nici un element diferit de zero care s poat fi adus pe poziia (l, r) fr a afecta coloanele din matricea unitate deja construite, atunci se

29

ntrerupe pivotajul i se trage concluzia c sistemul nu poate fi explicitat n raport cu grupul de m variabile cerut.

B. Se transform n zerouri toate elementele de pe coloan n afara pivotului (aa cum a fost artat deja).

Cele dou verificri care trebuiau fcute la varianta anterioar nu mai sunt necesare pentru c, pe de o parte, am presupus c ne plasm n situaia unor sisteme compatibile nedeterminat (singura interesant pentru scopurile noastre) i, pe de alt parte, eliminarea ecuaiilor secundare nu este de dorit pentru c ele fac parte din modelarea procesului studiat.

Din cele expuse pn aici, fiind dat un sistem liniar de m ecuaii cu n necunoscute avnd m < n, cu cele n variabile ale sistemului se pot forma Cnm grupuri diferite de m variabile. De aceea, pentru un astfel de sistem este valabil teorema urmtoare.

Teorema 1.3.5 Dac un sistem liniar de m ecuaii cu n necunoscute admite cel puin o form explicit, atunci el va admite cel mult Cnm forme explicite. Prin definiia 1.3.8 s-a introdus noiunea de soluie de baz i s-a stabilit c

fiecrei forme explicite a sistemului i corespunde o unic soluie de baz. Se poate ntmpla, desigur, ca la dou forme explicite s corespund o aceeai soluie de baz. innd cont i de teorema 1.3.5 rezult

Teorema 1.3.6 Dac un sistem liniar de m ecuaii cu n necunoscute are cel puin o soluie de baz, atunci el va admite cel mult Cnm soluii de baz. n definiia 1.3.9 s-a stabilit o clasificare a soluiilor de baz n

nedegenerate i degenerate. Se mai poate face o clasificare dup alt criteriu; ea va fi util n tratarea problemelor de programare liniar din capitolul urmtor.

Definiia 1.3.10 Dac ntr-o soluie de baz toate variabilele au valoare nenegativ, atunci soluia se numete admisibil sau fezabil. Dac n soluia de baz mcar o variabil ia valoare negativ, atunci ea se numete neadmisibil sau nefezabil. Din cele discutate pn acum rezult c, plecnd de la o form explicit,

printr-un pivotaj convenabil, se poate ajunge la una din urmtoarele situaii: o nou form explicit care difer de prima printr-o variabil

principal; se stabilete c noua form explicit la care se dorea s se ajung

nu exist. Orice form explicit a sistemului are m variabile principale i n-m

variabile secundare. Formele explicite difer ntre ele tocmai prin grupul de variabile principale. De aceea, atunci cnd se face trecerea de la o form explicit la alta prin pivotaj, una din variabilele secundare devine variabil principal (sau de baz), iar una din variabilele principale de pn atunci trebuie s devin secundar (sau nebazic) pentru ca numrul de m variabile principale s rmn constant. Se spune c, prin pivotaj, o variabil secundar intr n baz, iar o variabil principal iese din baz. O justificare mai riguroas a acestor expresii

30

este posibil dac se trateaz sistemele de ecuaii liniare prin prisma structurilor algebrice care se numesc spaii liniare (sau spaii vectoriale).

Corespunztor formelor explicite sunt soluiile de baz ale sistemului. n rezolvarea problemelor de programare liniar vor interesa soluiile de baz corespunztoare diferitelor forme explicite precum i trecerea de la una la alta dintre acestea.

Calcularea inversei unei matrice folosind metoda eliminrii complete Metoda eliminrii complete ofer o modalitate comod de calculare a

inversei unei matrice. Dup cum s-a vzut n seciunea 1.1, o matrice ptratic de ordinul n este inversabil dac se poate determina o matrice, notat A-1, astfel nct AA-1 = A-1A = In, unde In este matricea unitate de ordinul n.

Calcularea lui A-1, dac aceasta exist, se poate face cu metoda eliminrii complete. Vom ilustra acest lucru pe o matrice ptratic de ordinul 2, generalizarea la matrice de orice ordin n fiind imediat.

Fie, deci, matricea A(2,2) pe care o presupunem inversabil:

Aa aa a

=

11 12

21 22 (1.3.9)

Calcularea inversei lui A nseamn determinarea elementelor necunoscute ale matricei

Ax xx x

=

1 11 12

21 22 (1.3.10)

astfel nct AA-1 = A-1A = I2, adic

a aa a

x xx x

11 12

21 22

11 12

21 22

1 00 1

=

(1.3.11)

Dezvoltnd relaia (1.3.11) se obine succesiv

a x a x a x a xa x a x a x a x

11 11 12 21 11 12 12 22

21 11 22 21 21 12 22 22

1 00 1

+ ++ +

=

a x a xa x a x

a x a xa x a x

11 11 12 21

21 11 22 21

11 12 12 22

21 12 22 22

10

01

+ =+ =

+ =+ =

(1.3.12)

(1.3.13)

Cele dou sisteme au, respectiv, matricele extinse

a aa a

a aa a

11 12

21 22

11 12

21 22

10

01

(1.3.14)

31

Ambele sisteme se pot rezolva prin metoda eliminrii complete i, n cazul n care sunt compatibile determinat, duc la forme explicite pe care se pot citi direct soluiile

1 00 1

1 00 1

11

21

12

22

bb

bb

x bx b

x bx b

11 11

21 21

12 12

22 22

==

==

(1.3.15)

(1.3.16)

n acest fel s-au determinat elementele matricei A-1, adic

Ax xx x

b bb b

= =

1 11 12

21 22

11 12

21 22 (1.3.17)

Sistemele (1.3.13) au, ambele, aceeai matrice a coeficienilor, aa cum se vede i din matricele extinse (1.3.14). De aceea, ele pot fi rezolvate simultan scriind mpreun cele dou matrice extinse. n acest fel se poate calcula A-1 plecnd de la tabloul n care matricea A ocup partea stng, iar matricea unitate partea dreapt. Se aplic metoda eliminrii complete pn cnd se ajunge la tabloul care are n stnga matricea unitate, moment n care n partea dreapt apare matricea A-1.

Dac nu se poate obine un tablou final care s conin n partea stng matricea unitate, atunci se trage concluzia c matricea dat nu este inversabil.

Exemplul 1.3.5

S se determine inversa matricei A =

2 0 12 1 13 1 1

Aplicnd metoda descris se obin succesiv tablourile

2 0 12 1 13 1 1

1 0 00 1 00 0 1

1 02 1 13 1 1

0 00 1 00 0 1

1 00 1 20 1

0 01 1 0

0 1

12

12

12

52

12

32

1 00 1 20 0

0 01 1 0

1 1

1 00 1 20 0 1

0 01 1 0

1 2 2

1 0 00 1 00 0 1

0 1 11 5 41 2 2

12

12

12

12

12

12

S-a obinut matricea invers A =

1

0 1 11 5 41 2 2

32

Exemplul 1.3.6

S se determine inversa matricei A =

2 0 13 1 12 2 4

2 0 13 1 12 2 4

1 0 00 1 00 0 1

1 00 10 2 5

0 01 0

1 0 1

1 00 10 0 0

0 01 0

2 2 1

125

2

123

2

125

2

123

2

K

Ultima linie a tabloului final indic incompatibilitatea sistemelor care stau

la baza acestuia. Concluzia care trebuie tras este c matricea dat nu este inversabil.

" Rezolvai exerciiile 25 i 26 de la pagina 35. 1.4 Inegaliti liniare i sisteme de inegaliti liniare

n aplicaiile metodelor matematice n lumea real apar adesea situaii n care anumite laturi ale unui fenomen se modeleaz nu prin ecuaii liniare, ci prin inegaliti liniare. O inegalitate liniar se obine dac n expresia formei generale a unei ecuaii liniare se n locuiete semnul = cu unul din semnele , , . Vom ncepe cu discutarea inegalitilor i sistemelor de inegaliti n dou variabile deoarece acestea pot fi interpretate geometric.

Inegaliti i sisteme de inegaliti n dou variabile

Definiia 1.4.1 Se numete inegalitate liniar sau inecuaie liniar n dou variabile, x i y, expresia:

cbyax

> c. Un astfel de punct se vede n figura 1.4.1.

33

Dreapta d: ax + by = c mparte planul n dou regiuni care se numesc semiplane. n acest context ea este frontiera celor dou semiplane. n figura 1.4.1 cele dou semiplane sunt colorate cu nuane diferite. Atunci cnd vorbim de unul dintre semiplane putem s includem n el i frontiera, caz n care el se numete semiplan nchis. Dac frontiera nu este inclus, avem un semiplan deschis.

Cele dou semiplane determinate de

dreapta d au importan pentru c ele reprezint mulimile soluiilor pentru cele patru forme de inecuaii exprimate prin (1.4.1).

Astfel, se poate demonstra c: Mulimea soluiilor inecuaiei ax + by < c este unul din semiplanele

deschise determinate de dreapta ax + by = c; cellalt semiplan deschis reprezint mulimea soluiilor inecuaiei ax + by > c;

Pentru inecuaiile ax + by c i ax + by c mulimile soluiilor sunt reprezentate respectiv de semiplanele nchise aflate de o parte i de alta a dreptei ax + by = c.

Din cele de mai sus rezult c, pentru a rezolva o inecuaie linar: se traseaz dreapta corespunztoare ecuaiei ataate; se alege un punct din plan care nu aparine dreptei ataate i se

nlocuiesc coordonatele acestuia in expresia inecuaiei; dac expresia rezultat dup efectuarea calculelor este logic

corect, atunci soluia inecuaiei este reprezentat de ntregul semiplan n care se afl punctul testat, iar n caz contrar soluia este reprezentat de cellalt semiplan;

se ia ca soluie semiplanul determinat, deschis dac inegalitatea din enun este strict i nchis dac inegalitatea admite i posibilitatea de egal.

Un set de inegaliti liniare formeaz un sistem de inegaliti (sau inecuaii) liniare. Pentru sistemele n dou variabile este posibil rezolvarea grafic prin determinarea interseciei semiplanelor care reprezint soluiile inecuaiilor.

Exemplu. S se rezolve urmtorul sistem de inegaliti liniare n dou variabile:

4 81

2 2

x yx yx y

+

Fig. 1.4.1

M(x, y)

d

O x

y

34

Soluia grafic este reprezentat n figura 1.4.2 prin punctele din interiorul, precum i de pe laturile triunghiului ABC care reprezint intersecia semiplanelor determinate de cele trei inegaliti din enun. Vrfurile triunghiului au coordonatele A(0,1), B(2, 0), C(3, 4).

Un sistem de inegaliti liniare poate fi compatibil, dac are cel puin o soluie, deci exist mcar o pereche de valori (x, y) care s verifice toate inecuaiile, sau incompatibil, n caz contrar. De exemplu, n figura 1.4.3 este artat un sistem de dou inegaliti incompatibil. n legtur cu sistemele de inegaliti compatibile, are importan dac sistemul are soluie mrginit sau soluie nemrginit. O definire riguroas a mulimilor mrginite i nemrginite cere o tratare mult prea ampl pentru scopurile pe care ni le-am propus aici, dar reprezentri grafice intuitive sunt suficiente. Astfel, soluia sistemului din figura 1.4.2 este mrginit, n timp ce sistemul din figura 1.4.4 are soluie nemrginit.

Astfel, o inegalitatea liniar n n variabile are expresia

bxaxaxa nn

> .

Pentru o variabil aleatoare discret determinarea medianei se face astfel:

a) dac variabila aleatoare are un numr par de valori (n = 2p), atunci va exista un interval median [ ]x xp p, +1 i mediana poate fi orice numr din acest interval. De obicei se ia Me

x xp p= + +12

.

b) dac variabila aleatoare are un numr impar de valori (n = 2p+1), atunci Me x p= +1 .

82

Mod

Pentru variabila aleatoare discret X care ia valorile ( )xi i n=1 2, ,..., , aranjate n ordine cresctoare, cu probabilitile ( )pi i n=1 2, ,..., , punctul Mo = xm se numete mod dac sunt satisfcute inegalitile: p pm m> 1 i p pm m> +1 .

Media M(X), mediana Me i modul Mo se numesc caracteristici ale tendinei centrale de grupare a variabilei X. ntre ele nu exist, n general, relaii bine determinate.

Dispersie (varian) Media, mediana i modul exprim doar tendina central a valorilor

unei variabile aleatoare, dar nu ofer nici o informaie asupra mprtierii valorilor unei variabile aleatoare. De aceea, sunt necesare caracteristici care s indice n ce msur valorile se abat de la valoarea central de grupare. Una din aceste caracteristici este dispersia.

Fie, din nou, variabila aleatoare X cu media M(X):

Xx x xp p p

n

n: 1 2

1 2

KK

, ( )M X x pi ii

n

==

1

.

Atunci, variabila aleatoare X - M(X) se numete abaterea de la medie a variabilei X; ea are repartiia:

( ) ( ) ( )X x M X x M X x M Xp p p

n

n

: 1 21 2

KK

Problema este c abaterea de la medie nu poate furniza o msur a mprtierii valorilor variabilei deoarece media sa este zero. ntr-adevr, aplicnd proprietile mediei (notate n paranteze), rezult:

( )( ) ( ) ( ) ( )( ) ( ) ( ) ( )M X M X M X M M X M X M X = = =2 3 0 De aceea, se definete un alt indicator al mprtierii valorilor

variabilei aleatoare: dispersia. Prin definiie, dispersia (sau variana) variabilei aleatoare X este media ptratelor abaterilor de la medie.

( ) ( )( )D X M X M X2 2= (4.6.2) Notaii: D2(X), 2 Deci, pentru o variabil aleatoare simpl cu media m, dispersia va fi:

( ) ( ) ( ) ( )D X x m p x m p x m pn n2 1 2 1 2 2 2 2= + + + K Pe baza proprietilor mediei se obine:

( ) ( )( ) ( ) ( )( )( ) ( ) ( ) ( )( ) ( ) ( )( )

D X M X M X M X XM X M X

M X M X M X M X M X M X

2 2 2 2

2 2 2 2

2

2

= = + == + =

Deci, formula de calcul a dispersiei este:

83

( ) ( ) ( )( )D X M X M X2 2 2= (4.6.3) Exemplu

S se calculeze dispersiile variabilei aleatoare X:1 2 31

31

31

3

.

Trebuie calculat variabila aleatoare X2 pentru c media acesteia intervine n calcularea dispersiei.

X 21

31

31

3

1 4 9:

Avem ( )M X = + + =13

23

33

2 i ( )M X 2 13 43 93 143= + + = . Deci, ( ) ( ) ( )( )D X M X M X2 2 2 143 4 23= = =

Proprietile dispersiei

(1) ( )D X2 0 . Aceast proprietate rezult imediat din definiie. (2) ( )D a2 0= (dispersia unei constante este nul). (3) ( ) ( )D aX a D X2 2 2= (4) ( ) ( ) ( )D X Y D X D Y2 2 2+ = + . Proprietatea se verific imediat cu

relaia (4.6.3). (5) ( ) ( )D a X D X2 2+ =

Abaterea medie ptratic (deviaia standard) Abaterea medie ptratic (sau deviaia standard) este rdcina

ptrat a dispersiei. Se noteaz D(X) sau .

( ) ( )D X D X= = 2 (4.6.4) Abaterea medie ptratic are aceleai dimensiuni ca variabila

aleatoare X, de aceea este mai intuitiv pentru exprimarea mprtierii valorilor variabilei. De aceea, de regul, gradul de mprtiere a valorilor variabilei aleatoare X n jurul mediei se msoar prin abaterea medie ptratic i nu prin dispersie.

Pentru o variabil aleatoare simpl X care are media m, abaterea medie ptratic se calculeaz astfel:

( ) ( ) ( ) ( )D X x m p x m p x m pn n= = + + + 1 2 1 2 2 2 2K

84

Anex

Pentru a face posibil calcularea numrului de cazuri favorabile i a numrului de cazuri posibile, reamintim semnificaia noiunilor de permutri, aranjamente, combinri, precum i formulele pentru calcularea acestora. Permutri de n (notaie: n!) nseamn: n cte moduri se pot ordona n elemente? Formula de calcul: n n! = 1 2 3 K Aranjamente de n luate cte k (notaie: Ank ) nseamn: cte grupe de k elemente, ordonate, se pot face dintr-o mulime de n elemente? Formula de calcul: ( ) ( )A n n n knk = +1 1K Combinri de n luate cte k (notaie: Ank ) nseamn: cte grupe de k elemente, la care nu conteaz ordinea, se pot face dintr-o mulime de n elemente?

Formula de calcul: C Akn

k nk

=!

" Rezolvai exerciiile din seciunea "Variabile aleatoare" de la paginile 85 - 86.

Elementele de teoria probabilitilor din acest capitol sunt o baz

pentru definirea proceselor abordate n capitolul urmtor. De asemenea, ele constituie un punct de plecare pentru dezvoltarea ulterioar a unor elemente de statistic.

Exerciii

Evenimente Fie experimentul care const n aruncarea unui zar. Considerm

urmtoarele evenimente: A - apariia unui numr par de puncte B - apariia unui numr impar de puncte C - apariia unui numr mai mic sau egal cu 3 D - apariia uneia din feele 2 sau 3 L - apariia uneia din feele 1 sau 3 F - apariia unui nr. strict mai mare ca 4 G - apariia unui numr mai mic sau egal cu 4 H - apariia feei 4 I - apariia feei 5 J - apariia feei 6 K - apariia feei 3

1) Care perechi de evenimente sunt incompatibile? 2) Care evenimente implic alte evenimente? 3) Dai dou exemple de evenimente contrare. 4) Care sunt evenimentele elementare din cele de mai sus? De ce? 5) Care din evenimentele de mai sus sunt compuse? De ce?

85

6) Scriei evenimentele: R1: A sau C R2: A i C R3: A C, R4: B sau D R5: B i D R6: B-D

7) Mulimea de evenimente definite mai sus formeaz un cmp de evenimente?

8) Se pot forma sisteme complete de evenimente dintre cele de mai sus? Dac da, dai exemple.

Probabiliti 1) Un student face parte dintr-o grup de 26 studeni care, la rndul ei, face parte dintr-un an cu 76 studeni. Anul su face parte dintr-o facultate cu 601 studeni. Studentul se ntlnete pe strad cu un coleg. Care este probabilitatea ca: a). s fie un coleg de grup? b) s fie un coleg de an? 2) O urn conine 3 bile albe i 4 bile negre. Alt urn conine 4 bile albe i 5bile negre. S se determine probabilitile urmtoarelor evenimente: a). F1 - ambele bile extrase s fie albe. b) F2 - cel puin o bil extras s fie alb. b). F3 - bila extras din prima urn s fie alb, iar cealalt s fie neagr. 3) Trei trgtori trag simultan asupra unei inte. Probabilitile pentru fiecare trgtor s loveasc inta sunt, respectiv: p1 = 0.4, p2 =0.5, p3 = 0.7. S se afle probabilitatea ca inta s fie lovit exact o dat. 4) O urn conine 3 bile albe i 4 bile negre. Se extrag succesiv dou bile (fr a pune bila la loc). Fie evenimentele: A - prima bil extras este alb; B - a doua bil este alb. Care este probabilitatea ca a doua bil s fie alb dac prima a fost alb? 5) Dou urne, U1 i U2, au urmtoarea compoziie: U1 - 3 bile albe i 4 bile negre; U2 - 4 bile albe i 5 bile negre. Dintr-o urn, aleas la ntmplare, se extrage o bil. Care este probabilitatea ca bila extras s fie alb? 6) Fie 5 urne dintre care: dou au compoziia k1: 3 bile albe i 4 bile negre; una are compoziia k2: 4 bile negre; dou au compoziia k3: 10 bile albe i 2 bile negre. a). Care este probabilitatea ca, dintr-o urn luat la ntmplare, s se extrag o bil alb? b). tiind c s-a extras o bil care s-a nimerit s fie alb, care este probabilitatea ca bila extras s fie dintr-o urn cu compoziia k3?

Variabile aleatoare 1) Se arunc dou zaruri i se noteaz cu S numrul de puncte care apar. S se formeze tabloul de distribuie al variabilei S. 2) Se arunc dou zaruri. Se acord 12 puncte dac suma feelor care apar este 2 sau 12, 4 puncte dac suma feelor este 7 i 1punct n celelalte cazuri. S se scrie distribuia numrului N de puncte acordat. 3) n condiiile problemelor precedente s se calculeze variabilele aleatoare S+1 i 2N.

4) Fie variabila aleatoare Xp p

:1 2 3 4

74

13

16

.

a). ct este valoarea lui p? b). care este probabilitatea ca X s ia o valoare mai mic sau egal cu 3?

86

5) Fie X:. . .

1 0 10 3 0 3 0 4

i Y:. .

1 10 5 0 5

. Calculai X2, Y2, X2+Y2, Xn, Yn.

S se calculeze media i dispersia pentru fiecare dintre variabilele aleatoare din exerciiile precedente.

87

5

Lanuri Markov

5.1 Procese stochastice. Lanuri Markov 5.2 Proprieti de baz ale lanurilor Markov 5.3 Lanuri Markov regulate

Obiectivele capitolului

nelegerea noiunii de proces stochastic. Introducerea lanurilor Markov, o clas de procese stochastice. Ilustrarea tipurilor de situaii din lumea real care pot fi modelate i

manipulate folosind lanuri Markov. Discutarea proprietilor de baz ale lanurilor Markov. Studierea unei clase speciale, lanurile Markov regulate.

Multe fenomene din lumea real (management, structuri sociale, economie etc.) pot fi caracterizate ca avnd o evoluie n etape. Mai mult, trecerea de la o etap la alta comport schimbri care nu pot fi stabilite determinist, ci au un caracter aleator. Astfel de fenomene sunt modelate prin intermediul aa-numitelor procese stochastice.

O clas special de procese stochastice este reprezentat de lanurile Markov. Acestea s-au dovedit utile pentru modelarea unui numr mare de situaii din realitate, de aceea li s-a acordat o atenie special.

n acest capitol se face o introducere n domeniul proceselor stochastice, n special al lanurilor Markov. O clas important care va fi avut n vedere sunt lanurile Markov regulate. Se va face legtura direct cu tipuri de situai din lumea real care se preteaz a fi modelate n acest fel.

88

5.1. Procese stochastice. Lanuri Markov

Multe experimente aleatoare se desfoar n etape. De aceea, un astfel de experiment poate fi considerat ca fiind o secvena de subexperimente si fiecare rezultat al experimentului este determinat de rezultatele subexperimentelor (n ordine).

Un exemplu este urmtorul: se dau trei urne, fiecare coninnd bile albe si bile negre n cte o proporie. Se alege o urna la ntmplare si, din ea, se extrage o bila. Se cere probabilitatea apariiei unei bile albe din urna 2. Se observa ca experimentul are doua faze:

alegerea urnei (la ntmplare) extragerea bilei (tot la ntmplare). Definiia 5.1.1 Se numete proces stochastic un experiment aleator care consta dintr-o suita de subexperimente (tot aleatoare). Deci, un proces stochastic este o mulime indexata de variabile

aleatoare, {Xt}, unde t parcurge o mulime T. Adesea, T este mulimea indicilor pozitivi T = N, iar Xt reprezint o caracteristica, cantitativa sau calitativa, a sistemului fizic sau economic cercetat.

O modalitate grafica de a descrie un proces stochastic (atunci cnd numrul de cazuri nu este prea mare) este prin intermediul unei diagrame ca cea care urmeaz: Fie, din nou exemplul celor trei urne. Ele conin U1: 3a+4n, U2: 4a+5n, U3: 5a+6n (a - bile albe, b - bile negre). Se poate trasa o diagrama ca cea din figura 5.1.1

( )P a U = =1 3713

17

( )P n U = =1 1347

421

( )P a U = =2 1349

427

( )P n U = =2 1359

527

( )P a U = =3 135

11533

( )P n U = =3 136

11211

Fig. 5.1.1

U2

a

a

a

U1

n

n

U3

n

5/11

6/11

4/9

5/9

3/7

4/7

start 1/3

1/3

1/3

89

Observaie Pe aceasta diagrama se pot vedea uor si diferite probabiliti condiionate. De exemplu:

a). Probabilitatea de rezulta o bila alba care a fost extrasa din urna

U2 este 274

94

31 = .

b). Probabilitatea de a extrage bile albe, indiferent de urna este

335

274

71 ++ .

Fie acum o succesiune de experimente, fiecare avnd aceleai rezultate posibile. Prin urmare, se va considera ca t este un moment de timp care ia valorile 1, 2, 3, (aceasta da secvena de experimente). Pentru fiecare moment, rezultatele posibile vor fi notate 1, 2, , m (le consideram n numr finit). Cele m rezultate posibile vor fi numite strile n care se poate afla sistemul la un moment dat. Unitatea de msura pentru momentele de timp succesive t depinde de sistemul economic/fizic studiat.

Un tip de astfel de secvene este acela n care probabilitile rezultatelor la un moment dat sunt independente de rezultatele experimentelor precedente (de exemplu: aruncarea repetata a unui zar, sau extrageri ale bilei din urna cu revenire).

Un alt tip de secvena este acela n care probabilitile rezultatelor la un moment dat depind de rezultatele din experienele anterioare (ca, de exemplu extragerile succesive din urna fr repunerea bilei la loc). n cazul acestui din urma tip de experiment se pot distinge doua subcazuri extreme:

- o extrema e reprezentata de faptul ca probabilitile rezultatelor la un moment dat depind de rezultatele tuturor experimentelor precedente din secvena;

- cealalt extrema a nivelului de dependenta este atunci cnd probabilitile rezultatelor la un moment dat depind doar de rezultatele experimentului precedent. n aceasta situaie secvena de experimente se numete proces (lan) Markov.

Definiia 5.1.2 Un proces Markov sau lan Markov este o succesiune de experimente n care fiecare experiment are m rezultate posibile E1, E2, Em, iar probabilitatea fiecrui rezultat depinde doar de rezultatul experimentului precedent. Cele de mai sus pot fi formalizate astfel:

Definiia 5.1.3 Se spune ca un proces stochastic are proprietatea lui Markov daca este ndeplinita egalitatea:

P(Xt+1 = jX1 = k1, , Xt-1 = kt-1, Xt = i) = P(Xt+1 =jXt = i), (5.1.1)

pentru t =1, 2, si pentru orice succesiune k1, k2, kt-1, i, j de stri din mulimea celor m stri posibile ale sistemului.

90

Nota: n (5.1.1) se folosete notaia P(A/B) pentru probabilitatea

evenimentului A condiionat de evenimentul B (n loc de PB(A)). Proprietatea lui Markov arata tocmai faptul ca probabilitatea

condiionata a oricrui eveniment viitor (Xt+1 = j), date fiind evenimentele trecute X1 = k1, , Xt-1 = kt-1 si starea prezenta Xt = i este independenta de strile trecute si depinde doar de starea prezenta a procesului.

Exista o larga varietate de fenomene care sugereaz o comportare n maniera unui proces Markov.

Exemple

probabilitatea ca o persoana sa cumpere un produs de o anumita marca (detergent, bere etc.) poate depinde de marca aleasa la cumprtura precedenta;

probabilitatea ca o persoana sa aib cazier poate depinde de faptul ca prinii au avut sau nu cazier;

probabilitatea ca starea de sntate a unui pacient s se mbuntateasc, s se nruteasc sau sa rmn stabil ntr-o zi poate depinde de ceea ce s-a ntmplat n ziua precedenta.

Evoluia unui proces Markov poate fi descrisa prin intermediul unei matrice. Acest lucru este ilustrat prin definiia care urmeaz.

Definiia 5.1.4 Fie un proces Markov care are m rezultate posibile mutual exclusive E1, E2, , Em. Matricea P definita ca n relaia (5.1.2) se numete matrice de tranziie ntr-un pas sau, pe scurt, matricea de tranziie.

starea urmtoare (rezultatul viitor)

(5.1.2) 1 2 j m

starea precedenta (rezultatul

curent)

P

pppp

pppp

pppppppp

m

i

mmmjmm

imijii

mj

mj

=

LLLLLLLL

LLLLLLLLLLL

21

21

222221

111211

21

Un element pij al matricei P se numete probabilitatea de trecere ntr-un pas de la starea i la starea j

pij = P(Xt+1 = j / Xt = i) (5.1.3)

Dup cum se observa din (5.1.2) ca matricea de tranziie ntr-un pas a fost notata cu P. La un moment dat sistemul modelat este ntr-una din cele m stri posibile (curente). O stare corespunde uneia din rezultatele posibile ale experimentului. La sfritul efecturii experimentului se obine un nou rezultat care reprezint o noua stare n care a trecut sistemul.

91

Matricea de tranziie este formata din elementele pij care reprezint probabilitatea condiionata ca sistemul sa treac din starea curenta i n starea urmtoare j. Deci pij este probabilitatea sa apar rezultatul Ej n pasul urmtor daca s-a produs rezultatul Ei n pasul precedent. Se observa ca pij nu depinde de momentul t, ci doar de strile i si j. Deci pij(t) = pij, oricare ar fi t si de aceea pij se numesc probabiliti de trecere staionare. Ele sunt caracteristice lanurilor Markov.

Din cele de mai sus se poate formula urmtoarea definiie a lanului Markov, echivalenta cu definiia 5.1.2.

Definiia 5.1.5 Un proces stochastic {Xt}, t = 1, 2, se numete proces Marcov (lan Markov) daca ndeplinete urmtoarele condiii: are un numr finit de stri I = {1, 2, , m}, are proprietatea lui Markov, are probabilitile de trecere ntr-un pas staionare, are o mulime de probabiliti iniiale pentru orice stare i I

Observaii

1. Pij cu i = j reprezint probabilitatea ca sistemul sa rmn n aceeai stare dup efectuarea experimentului, iar Pij cu i j reprezint probabilitatea ca sistemul sa treac dintr-o stare n alta.

2. Matricea de tranziie este o matrice ptratica de ordin m.

Proprieti Elementele matricei de tranziie trebuie sa satisfac urmtoarele:

1. 0 pij 1, i,j = 1,,m (pentru ca este vorba de probabiliti), 2.

===

m

jij m,...,,i,p

1211 (suma pe linie trebuie sa dea 1 pentru ca

E1, E2, Em este un sistem complet de evenimente).

Proprietatea 2 asigura ca, data fiind o stare curenta i a sistemului, sistemul va trece cu sigurana ntr-o stare j din cele m posibile dup efectuarea experimentului.

Exemplu Comportamentul consumatorilor fata de un anumit produs, precum si

nclinaia lor de a schimba marca produsului pe care l cumpra a fost modelat ca proces Markov pe durata multor ani. Fie un eantion de 250 consumatori ai unui anumit tip de produs cumprat sptmnal. Ei au la dispoziie 3 mrci din produsul respectiv. Tabela de mai jos arata schimbrile produse n preferina de la sptmna a asea la sptmna a aptea.

92

Marca preferata n sptmna 7 Total 1 2 3

Marca preferata n sptmna 6

1 72 4 4 80

2 12 102 6 120 3 2 6 42 50

Total 86 112 52 250

Prima linie arata ca pentru M1: 9 72 cumprtori care au cumprat marca M1 n sptmna 6 au

rmas tot la ea n sptmna 7, 9 4 care au cumprat M1 n sptmna 6 au trecut la M2 n

sptmna 7, 9 4 care au cumprat M1 n sptmna 6 au trecut la M3 n

sptmna 7. Pe de alta parte, tot pentru M1,

9 12 care au cumprat M2 n sptmna 6 au trecut la M1 n sptmna 7,

9 2 care au cumprat M3 n sptmna 6 au trecut la M1 n sptmna 7.

Per total, de la o sptmna la alta, pentru M1: 9 72 au pstrat M1, 9 4 + 4 = 8 au prsit M1 pentru alte mrci, 9 12 + 2 = 14 au venit de la alte mrci la M1. Rezulta un ctig total

de 14 - 8 = 6 cumprtori pentru marca M1.

ntre sptmna 6 si sptmna 7 rezulta o cretere a procentului din "piaa" pentru marca M1 de la 32% (80/250100) la 34,4% (86/250100). Pe lng ilustrarea schimbrilor nete si a cotelor deinute pe piaa, tabelele ca cea de mai sus arata si sursa schimbrilor petrecute. De exemplu M1 a nregistrat un ctig net de 12 - 4 = 8 consumatori de la marca M2 si a pierdut 2 - 4 = -2 n favoarea lui M3.

n plus, astfel de tabele pot fi folosite pentru a construi matricea P de tranziie.

..........

P

=

=840120040050850100050050900

5042

506

502

1206

120102

12012

804

804

8072

Aceasta matrice este considerata a fi o buna estimare a matricei de tranziie "adevrate" deoarece se bazeaz pe evaluarea comportamentului a 250 de consumatori pe o perioada de doua sptmni.

93

Examinnd matricea P se constata ca: - elementele unei linii reflecta n ce msura este de ateptat ca o

marca sa i retina clienii sau sa-i piard n favoarea alteia. - elementele de pe o coloana sumarizeaz n ce msur e de ateptat

ca o marca sa-si pstreze consumatorii sau s mai atrag si alii de la alte mrci.

Fig. 5.1.2 Deci, p11, p22, p33 sunt masuri ale "puterii de pstrare" a fiecrei

mrci. n rest pij (ij) reflecta "puterea de atracie" a mrcii Mj n condiiile n care marca din sptmna precedenta a fost Mi.

Procesul Markov din exemplul precedent poate fi descris printr-o diagrama (tip arbore) asemntoare cu cea de la nceputul capitolului si care este ilustrata n figura 5.1.2.

Daca ne ntrebam care este probabilitatea ca peste doua sptmni sa se cumpere iar marca M1, rezulta: 81700400501000509090 ....... =++ .

Bineneles, aceasta diagrama este greu de trasat pentru a vedea predicii pe mai multe sptmni. Pentru a putea face o reprezentare convenabila, abstractizam problema si o consideram un sistem care are trei stri posibile, M1, M2, M3. Sistemul trece dintr-o stare n alta cu diferite probabiliti. Rezulta o reprezentare ca cea din figura 5.1.3: un aa-numit graf orientat care are vrfurile M1, M2, M3, unite prin arce orientate. Acest graf se numete diagrama de tranziie.

Fig. 5.1.3

" Rezolvai exerciiile 1 si 2 de la pagina 102

M2

M1

M1

M1

M1

M3

M3

M3

M3

0.04

0.84

0.10

0.05

0.90

0.05

M1 0.05

0.90

0.05

M20.12

M20.85

M20.05

M3

0.05

M2

0.05 M1

0.05

0.12 0.10

0.04 0.90

0.85

0.85

94

5.2 Proprieti de baza ale lanurilor Markov

S-a vzut ca informaiile despre tranziiile de la o stare la alta n cadrul unui lan Markov pot fi reprezentate prin diagrama de tranziie sau prin matricea de tranziie (ntr-un pas). Pentru scopuri de calcul, cea mai utila este matricea de tranziie ntr-un pas. Ea este formata din elementele pij - probabilitatea de trecere ntr-un pas de la starea i la starea j (i, j = 1, 2, , m).

Se poate vorbi, atunci, si de probabilitile de tranziie n exact k pai si de o matrice formata din acestea. Pentru aceasta, n continuare, se vor face urmtoarele notaii:

pij(k) - probabilitatea condiionata de efectuare a tranziiei din starea i n starea j n exact k pai.

P(k) - matricea de tranziie n k pai. Conform celor enunate rezulta ca

P(k) = (pij(k))i,j=1,..m.

Fie acum din nou exemplul anterior n care se modeleaz alegerea uneia din cele trei mrci de la o sptmna la alta. Pentru el avem definite: matricea de tranziie ntr-un pas, arborele de tranziie si diagrama de tranziie.

Se pune problema, de exemplu, care este probabilitatea ca, dup doua sptmni, cei care au cumprat marca M1 sa rmn la aceasta preferina; deci, intereseaz p11(2). Din arborele de tranziie rezulta: p11(2) =

81700400501000509090 ....... =++ . Metoda de calcul folosind arborele de tranziie este uor de aplicat doar n cazul unui numr mic de pai (n acest caz, doua sptmni) si al unui numr mic de stri (n exemplul dat, trei mrci). Se observa uor, ns, ca din matricea P rezulta: p11(2)= p11p12+ p12p21+ p13p31 iar p12(2)= p11p12+ p12p22+ p13p32, deci p11(2) este elementul de pe poziia (1,1) n matricea PP, iar p12(2) este elementul de pe poziia (1,2) din matricea PP.

Fig. 5.2.1

n general, pentru un proces cu m stri, trecerea n doi pai de la

starea i la starea j nseamn, aa cum arata si figura 5.2.1,

1

i

m

j

P1j

Pmj

Pi1

Pim

P2j 2

Pi2 . . .

95

=

=+++=m

kkjikmjimjijiij pppppppp)(p

122112 K

adic pij(2) este elementul (i,j) din PP. Deci se poate spune ca P(2) = PP = P2. Se poate face imediat urmtoarea generalizarea din teorema 5.2.1:

Teorema 5.2.1 Fie P matricea de tranziie ntr-un pas a unui lan Markov. Atunci, matricea P(k) de tranziie n k pai este

( ) korik

PPPPkP == 43421 K (5.2.1)

Relaia din teorema 5.2.1 exprima o proprietate de baza a lanurilor

Markov prin care acestea se deosebesc de alte procese stochastice. Conform proprietii 2 a matricei de tranziie P, suma

probabilitilor de pe fiecare linie a acesteia trebuie sa dea 1. Aceasta proprietate rmne valabila si n cazul matricei de tranziie n k pai P(k) = Pk.

Aa cum s-a definit n capitolul 1, un n-uplu ordonat (x1, x2, , xn) se numete vector n-dimensional. Un vector mai poate fi reprezentat ca o matrice linie (vector linie) sau ca o matrice coloana (vector coloana).

Definiia 5.2.1 Un vector linie (q1, q2, , qn) care are proprietile

1

10

1=

=

n

ii

i

q)b

q)a

(5.2.2)

(5.2.3)

se numete vector de probabilitate sau vector stochastic. O matrice ale crei linii sunt vectori stochastici se numete matrice stochastic. Rezult c fiecare linie a matricei de tranziie P este un vector de

probabilitate. Acelai lucru se poate spune si despre liniile matricei de tranziie n k pai P(k) = Pk. De asemenea, matricele P si Pk sunt matrice stochastice.

" Rezolvai exerciiile 3, 4, 5 de la pagina 102

96

5.3 Lanuri Markov regulate

n continuare vom aborda o categorie de lanuri Markov utile n aplicaii practice.

Deoarece lanurile Markov sunt procese stochastice, nu se poate sti cu exactitate ce se ntmpla n fiecare stare; de aceea, sistemul trebuie descris n termeni de probabilitate.

Definiia 5.3.1 Fie un lan Markov cu m stri . Un vector de stare pentru lanul Markov este un vector de probabilitate X = sx1 x2 xnt . Coordonatele xi ale vectorului de stare X trebuie interpretate ca probabilitatea ca sistemul sa se afle n starea i. Procesul Markov luat ca exemplu n seciunea precedenta are trei

stri. n aceasta situaie vectorul de stare [0.6 0.1 0.3] trebuie interpretat astfel: n sptmna curenta clienii aleg marfa M1 cu probabilitatea 0,6, marca M2 cu probabilitatea 0.1 si M3 cu 0.3.

Atunci cnd se tie cu sigurana ca sistemul este ntr-o anumita stare, vectorul de stare are o forma particulara. Astfel, daca se tie sigur ca sistemul este n starea a i-a, vectorul de stare va avea a i-a componenta egala cu 1, iar restul 0. X = [0 0 0 i 0] .

Comportamentul unui lan Markov poate fi descris printr-o secvena de vectori de stare. Starea iniiala a sistemului poate fi descrisa printr-un vector de stare notat X0 . Dup o tranziie sistemul poate fi descris printr-un vector X1, iar dup k tranziii, prin vectorul de stare Xk. Relaia dintre aceti vectori poate fi sumarizata prin urmtoarea teorema:

Teorema 5.3.1 Fie un proces Markov cu matricea de tranziie P. Daca Xk si Xk+1 sunt vectori de stare care descriu un procesul dup k si k+1 tranziii, respectiv, atunci

PXX kk =+1 (5.3.1)

n particular,

( )kPXPXXPXPPXPXX

PXX

kk ==

====

00

20012

01

M

(5.3.2)

Deci, vectorul de stare Xk care descrie sistemul dup k tranziii e produsul ntre vectorul strii iniiale X0 si matricea Pk.

Observaie. X0, X1, X2, Xk, sunt toi vectori linie 1 m.

97

Exemplul 5.3.1 Fie un proces Markov cu matricea de tranziie

=

106030306010104050

,,,,,,,,,

P

Daca vectorul strii iniiale este X0 = [0,7 0 0,3], sa se determine vectorul de stare dup o tranziie.

Rezolvare: Conform teoremei 5.3.1. avem

[ ] [ ]100460440106030306010104050

3007001 ,,,,,,,,,,,,

,,PXX =

==

Exemplul 5.3.2 Un lan Markov are matricea de tranziie

=0820

6040,

,,P

Daca sistemul si ncepe evolutia din starea a doua, sa se determine vectorul de stare dup doua tranziii.

Rezolvare: X0 = [0 1] (pentru ca sistemul este sigur n starea a doua). Atunci avem;

[ ] [ ]76024080206040

80206040

10202 ,,,,,,

,,,,

PXX =

==

Revenind la scopul iniial al acestei sectiuni, exista mai multe moduri de a clasifica lanurile Markov. Ne vom referi la clasificarea care mparte lanurile Markov pe baza comportamentului lor pe termen