8/14/2019 Metoda Gauss Seidel Si Jacobi
1/13
Capitolul 2. METODE NUMERICE PENTRU REZOLVAREA SISTEMELDE ECUAII ALGEBRICE LINIARE.
2.1. Metode de rezolvare numeric a sistemelor algebrice liniare
Modelarea numerica a proceselor tehnologice de multe ori duce la obineresisteme de ecuaii liniare. Procedeul Krame r, care permite obinerea soluiei sistemulu prin raportul determinailor, devine inutil dac numarul de ecuaii si necunoscute( n >10 ), deoarece numarul necesar de operaii aritmetice are o valoare fantasticn!n.
n acest caz rezolvare sistemelor liniare se face folosind anumite metode speccare pot fi clasificate ca:
- metodedirecte ;- metodeindirecte (sauiterative ).
Metodeledirecte se utilizeaza pentru rezolvarea sistemelor liniare de ordinuln < 103.Metodeleindirecte se utilizeaza pentru rezolvarea sistemelor liniare de pn la ordn =
106
.NOT. Ca regula , pentru rezolvarea sistemelor de ecuatii liniare, se aplica metodeiterative.
2.1.1. Metoda eliminriiGauss
Metoda eliminariiGauss este cea mai simpl metoda direct, care cere circa
(2/3)n3 de operatii aritmetice. Metoda are la baza ideea transformrii matricei da Aintr-o matrice superior triunghiular prin eliminarea consecutiv a necunoscutelor srezolvarea ecuaiilor, folosind procedeul de substituire invers .
22
8/14/2019 Metoda Gauss Seidel Si Jacobi
2/13
Descrierea metodei
Se consider un sistem den ecuaii liniare, de forma:
=+++
=+++=+++
nnnnnn
nn
nn
b xa xa xa
b xa xa xa
b xa xa xa
.......
.........................................................
.......
.......
2211
22222121
11212111
(2.1)
care scris mai scurt va avea forma
i j
n
jij b xa =
=1, (2.2)
unde : i = 1,2,3,.....,n este numrul ecuaiei; j = 1,2,3, ...,n reprezint numrul necunoscutei
Acest sistem n forma matriceala se noteaz:
A x = b , (2.3)la care:
A
=
nnnn
n
n
aaa
aaa
aaa
.....
..........................
21
22221
11211
se numete matricea coeficienilor ,
x
=
n x
x
x
...2
1
- vectorul variabilelor necunoscute,
23
8/14/2019 Metoda Gauss Seidel Si Jacobi
3/13
b
=
3
2
1
...b
b
b
- vectorul termenelor liberi.
Dac matricea A este superior triunghiulara , adic toate elementele situate s
diagonala principal sunt nule :
nn
n
n
a
aa
aaa
.....00................ .....0
.....
222
11211
(coeficieniia ij = 0, lai > j ), atunci rezolvarea sistemului se poate face uor prin procedeul de eliminareinvers .
Dac toate elemente din matricea superior triunghiulara A de pe diagonala
principala sunt diferite de zero (a ii 0) atunci sistemul de ecuatii dat ( 2.1) va captaforma :
==+
=+++=++++
nnnn
nnnnnnn
nnnn
nnnn
b xa
b xa xa
b xa xa xa
b xa xa xa xa
,
1,111,1
2,211,2222
1,111,1212111
...........................................................
.......
.......
(2.4)
Se observ ca ultima ecuatie conine numai necunoscuta xn, atunci considernd
a n,n 0 , se obine xn = b n /a n,n (2.5)
Substituind aceasta valoare n penultima ecuatie rezult ecuaia :24
8/14/2019 Metoda Gauss Seidel Si Jacobi
4/13
a n-1 ,n-1 xn-1 + a n-1 ,n bn /a nn = b n-1 , (2.6)
din care vom avea necunoscuta xn-1 ( avnd n vedere caa n-1 ,n-1 0) :
1,1
,11
1
=
nn
nnn
nnn
n
a
ba
ab
x (2.7)
Introducnd valorile cunoscute pentru xn si xn-1 in ecuaia imediat anterioara rezunecunoscuta xn-2. Dac procedura se repet pn la prima ecuaia va rezult primanecunoscuta x1.
Problema care nu a fost deocamdata clarificat este de a gsi procedeul priun sistem de ecuaii liniare structurat arbitrar s fie transformat intr-o form cu msuperior triunghiular, pentru putea aplica procedeul de substituire invers examanterior.
Se consider un sistem cun ecuaii liniare (2.1) scris n forma (2.2). Notnd
termeni liberi 1, += nii ab se obine:
1,
1
, +
=
= ni jn
j
ji a xa , (2.8)
la care i = 1,2,3,.....,n este numrul ecuaiei; j = 1,2,3, ...,n reprezint numrulnecunoscutei.
Presupunem, ca n prima ecuaie
1,11
,1 +=
= n jn
j j a xa (2.9)
25
8/14/2019 Metoda Gauss Seidel Si Jacobi
5/13
primul coeficienta11 0 (in cazul contrar se face renumerarea necunoscutelor). Eldin aceasta ecuaie coeficientul din faa primei necunoscute x1 mprind-o cua11 .
Notnd)1(
111
1 j
j
aa
a= , iar
)1(1,1
11
1,1+
+
= nn
aa
ase obine:
=
+=+n
jn j j a xa x
2
)1(1,1
)1(11 , (2.10)
Multiplicnd ecuaia (2.10) consecutiv cua i1, unde i=2,...,n , i scaznd-o din
ecuaiai se elimin prima variabil x1 din toate ecuaiile sistemului (2.8) n afar de
ecuaie. Atunci aceste ecuaii vor capta forma :
=
+=n
ini jij a xa
2
)1(1,
)1( , i= 2,3, ..........,n (2.11)
unde :
11
11,
)1(, a
aaaa ml l ml m = , m= 2,3 ,....,n i l= 2,3 ,...., n+ 1 (2.12)
La fel se procedeaza cu sistemul obinut (2.11).Dupa eliminarea necunoscutei xk-1, restul ecuaiilor va forma sistemul :
=
+
=n
k j
k ni j
k ij a xa
)1(1,
)1( , (2.13)
unde: i= k , k+ 1 ,...,n; j=i+1.Eliminnd elemente ale coloaneik , se obine sistemul de ecuaii cu coeficienii
)1()1(
)1()1()(
= k kk
k
mk k kl
k ml
k ml a
aaaa , m=k+ 1 ,...,n ; l=k+ 1 ,...,n+ 1 (2.14)
Eliminarea necunoscutelor duce la sistemul (2.4) cu matricea superior triunghiulscris mai scurt are forma :
+=
+=+n
i j
ini j
iiji a xa x
1
)(1,
)( , (2.15)
26
8/14/2019 Metoda Gauss Seidel Si Jacobi
6/13
unde: i= 1,2,...,n.Cu aceast se ncheie eliminareaGauss i dup aceasta, pentru determinarea
necunoscutelor se aplic eliminarea invers. Pentru aceasta se utilizeaz formula
transcris n forma (2.16), considerndi= n , n 1 , n 2, ..., 2, 1 :
+=
+ =n
i j j
iij
inii xaa x
1
)()(1, (2.16)
NOT. Eliminarea Gauss prevede divizarea ecuaiilor pe elemente diagonale. Dac un
coeficient diagonal este nul sau foarte mic dup valoarea lui absolut, eroarea de calcul devine inadmisibil de mare. De aceea, nainte de aplicarea eliminrii, sistemul trebuie
rearanjat astfel nct elementele diagonale s fie dominante n valoarea absolut.
Aplicaia 2.1. Exemplu de folosirea eliminarii gaussiene i a eliminrei inverse
Se consider c analiza poceselui de amestecare a trei substane fluide cu trconcentraii volumice diferite a condus la urmtorul sistem de ecuaii :
=+
=+
=+
)(132-
(b)3344
)(532
321
321
321
c x x x
x x x
a x x x
Se cere deteminarea concentraiilor volumice iniiale x1, x2 i x3 . Rezolvare
S notm coeficienii :a11 =2, a12 =3, a13 =-1, a21 =4, a22 =4 , a23 =-3, a31
27
8/14/2019 Metoda Gauss Seidel Si Jacobi
7/13
=-2, a32 =3, a33 =-1 i termenii liberi cub1=5 , b2= 3 ,b3=1.1. Ca s eliminam pe x1 din ecuaia (b), nmulim ecuaia (a) cu coeficientul
- a21/a11 = - 4\2 i adunm rezultatul la ecuaia (b).
Se obtine ecuaia :-2 x2 - x3 = -7 (b' )
2.De asemenea, nmulim ecuaia (a) cu multiplicatorul -a31/a11= -(-2\2) i rezultatulobinut se adun la ecuaia (c).
Se obine o noua ecuaie :6 x2 - 2 x3 = 6 (c' )
3. Acum se va elimina necunoscuta x2 din ecuaia (c'). Pentru aceasta, se nmultesteecuaia (b') cu multiplicatorul -6\(-2) i rezultatul obinut se adun la ecuaia (c ) .Rezult :
- 5 3 x = - 15 (c")
Cu aceasta, noul sistem de ecuaii devine superior triunghiular :
=
==+
)(c" -155x-
)(b' 7-x-2x-
(a) 5 x-3x2x
3
32
321
,
sau in forma generalizat :
==+=++
3333
2323222
1313212111
bxa
bxaxa
bxaxaxa
28
8/14/2019 Metoda Gauss Seidel Si Jacobi
8/13
Rezolvarea sistemului transformat se face folosind procedeul de eliminarinvers :
x3 = b 2 /a 22 = -15/-5 = 3
x2 = (b 2 - a 23x3 ) /a 22 =(-7+13)/-2= 2
x1 = (b 1 - a 12x2 - a 13 x 3 )/a 11 =(5-32+13)/2= 1
2.1.2. Metoda iteraiilor simple Iacobi Se consider un sistem cu n ecuaii liniare :
=+++
=+++=+++
nnnnnn
nn
nn
b xa xa xa
b xa xa xa
b xa xa xa
.......
.........................................................
.......
.......
2211
22222121
11212111
Considernd ca sistemul examinat este astfel structurat inct elementele da i,i ( i=1,2,...,n) suntdominante n valoareaabsolut , rearanjam sistemul elimin
variabile xi din termeni care conin coeficieniia ii de la fiecare rand in felul urmator :
+++=
+++=
+++=
)......(1
.........................................................
)......(1
)......(1
11,2211,,
23231212222
22
13132121111
11
nnnnnnnnn
nn
nn
nn
xa xa xaaa
b x
xa xa xaaa
b x
xa xa xaaa
b x
(2.17)
29
8/14/2019 Metoda Gauss Seidel Si Jacobi
9/13
8/14/2019 Metoda Gauss Seidel Si Jacobi
10/13
1292
42788
321
321
321
=++=+
=+
x x x
x x x
x x x
Rezolvam fiecare ecuaie faa de necunoscut respectiv :
=++=
+=
213
312
321
111,0222,0333,1
286,0143,0571,0
125,0125,01
x x x
x x x
x x x
Alegem ca o soluie iniiala : 0)0(3)0(
2)0(
1 === x x x
Rezult prima soluie aproximativ:
===++=
=+=
333,10111,00222,0333,1
571,00286,00143,0571,0
10125,00125,01
)1(3
)1(2
)1(1
x
x
x
Introducem valorile obtinute pentru )1(3)1(2)1(1 ,, x x x in partea dreapta a sistemului,
rezultnd o noua solutie :
===++=
=+=
048,1571,0111,01222,0333,1
095,1333,1286,01143,0571,0
095,1333,1125,0571,0125,01
)2(3
)2(2
)2(1
x
x
x
Dupm nlocuirea )2(3)2(
2)2(
1 ,, x x x n partea dreapt a sistemului , rezult o
nou soluie, etc.
Din valorile numerice putem alctuiun tabel :
31
8/14/2019 Metoda Gauss Seidel Si Jacobi
11/13
Tabelul 2.1Soluii 0 1 2 3 4 5 6 7
x1 0 1,000 1,095 0,995 0,993 1,002 1,001 1,000
x2 0 0,571 1,045 1,026 0,990 0,998 1,001 1,000
x3 0 1,333 1,048 0,964 1,000 1,004 1,001 1,000
Din tabelul se vede ca dup a 7 iteraia soluii nu se mai schimb.
Rspuns : 000,1321 === x x x
2.1.3. Metoda iterativGauss Seidel
In acest caz, trecerea sistemului de ecuaii (2.17) de la iteraia(k ) spre (k+1 ) nu semai face simultan pentru toate ecuaiile,ci prin utiizarea soluiilor obinute din ec precedente. Pentru sistemul examinat iteraia (k+1 ) se realizeaz prin relaia:
)(
1
)1()1(
1
)1( k j
n
i j ii
ijk j
i
j ii
ij
ii
ik i xa
a xa
a
ab
x = +=+
=
+
(2.19)
NOT. Avantajul esenial al acestei metode l constituie creterea vitezei de condatorit reducerii numrului total de iteraii necesare.
Aplicaia 2.3. Utilizarea metodei iterativeGauss-Seidel .
Vom rezolva acelai sistem din Aplicatia 2.2 , pentru a arta rapiditateaconvergenei soluiei numerice la utilizarea metodeiGauss-Seidel . Deci , avem :
32
8/14/2019 Metoda Gauss Seidel Si Jacobi
12/13
=++=
+=
213
312
321
111,0222,0333,1
286,0143,0571,0
125,0125,01
x x x
x x x
x x x
Rezolvare
Considernd soluia iniiala 0)0(3)0(2)0(1 === x x x n prima ecuaie i se obine soluia)1(
1 x :
10125,00125,01)1(1 =+= x
Dup aceasta se rezolv a dou ecuaie introducnd 1)1(1 = x i 0)1(3 = x :
714,00286,01143,0571,0)1(1 =++= x
Considernd noile solutii: 1)1(1 = x i 714,0)1(2 = x , se rezolv a treia ecuaia:032,1714,0111,01222,0333,1)1(3 == x
A doua iteraie se incepe prin introducerea soluiilor 714,0)1(2 = x si 032,1)1(3 = x in prima
ecuatie , rezult : 039,1032,1125,0714,0125,01)2(1 =+= x
Introducnd 039,1)2(1 = x i 032,1)1(3 = x rezult :
014,1032,1286,0039,1143,0571,0)2(2 =++= x
n fine, cu noi soluii 039,1)2(1 = x i 014,1)2(2 = x se obine :
990,0014,1111,0039,1222,0333,1)2(3 == x
Procednd n mod asemntor se obin rezultatele prezentate mai jos in tabelul
33
8/14/2019 Metoda Gauss Seidel Si Jacobi
13/13
Tabelul 2.2Soluia Numr de iteraii
)1( +k i x 0 1 2 3 4 5
x1 0 1.000 1.039 0.997 1.001 1.000 x2 0 0.714 1.014 0.996 1.000 1.000 x3 0 1.032 0.990 1.002 1.000 1.000
Din tabelul se vede ca dup a 5- a iteraie soluii nu se mai schimb.
Rspuns: 000,1321 === x x x
34