Metode
numerice - Aplicatii
Lucrarea 6.
Rezolvarea sistemelor de ecuatii liniare cu metode iterative: metodele
Jacobi, Seidel-Gauss si suprarelaxarii succesive
Tema A - Metoda iterativa
Jacobi
Tema B - Metoda iterativa Seidel-Gauss
Tema C - Metoda suprarelaxarii succesive
Determinarea solutiei exacte a sistemului A * x = b cu ajutorul
unor metode de tip iterativ este posibila numai dupa efectuarea unui numar
nelimitat
- teoretic infinit - de iteratii sau pasi. Deoarece nici o metoda
practica nu poate cicla la infinit, rezulta ca metodele iterative determina
doar o solutie aproximativa, aproximare prin trunchiere, care se
abate mai mult sau mai putin fata de solutia exacta x*, in functie
de precizia de calcul dorita.
Mai concret, metodele iterative apeleaza la construirea unui sir de aproximatii
succesive x_0, x_1, ... , x_k care, in anumite conditii, tinde catre
solutia exacta x*. In cazul in care pentru sirul aproximatiilor
succesive nu este posibila definirea unei limite, se spune ca metoda respectiva
diverge.
In cazul in care sirul aproximatiilor succesive are o limita, se spune
ca metoda este convergenta. In acest caz se poate defini o relatie de recurenta
intre doua aproximatii succesive x_k si x_(k+1). Definirea
relatiei de recurenta intre aproximatiile succesive se face pornind de
la desfacerea matricei A in alte doua matrice:
A = N - P
Folosind aceasta desfacere in expresia
sistemului de ecuatii se obtine relatia:
N * x = P * x +
b
care permite ca, pornind de la o
aproximatie initiala
x_0, sa se construiasca un sir de aproximatii
succesive pe baza relatiei de recurenta:
N * x_(k+1) = P * x_k
+ b
In practica, alegerea desfacerii
A
= N - P se face astfel incat un sistem de forma
N * y = C, unde
y
si
C sunt vectori ai necunoscutelor si termenilor liberi, sa se
rezolve cat mai usor. Aceasta este totuna cu o forma cat mai simpla a matricei
N,
diagonala sau triunghiulara.
In general, toate metodele iterative de rezolvare a sistemelor de ecuatii
liniare, definesc matricele
N si
P din desfacerea
A =
N - P pornind de la desfacerea standard a matricei
A:
A
= L + D + R
unde:
L este matricea strict
inferior triunghiulara ale carei elemente subdiagonale sunt elementele
matricei
A;
R este matricea strict superior triunghiulara
ale carei elemente supradiagonale sunt elementele matricei
A;
D
este matricea diagonala ale carei elemente nenule sunt tocmai elementele
diagonale din matricea
A.
Ca si in cazul metodelor directe, toate metodele iterative folosesc impartirea
la un element diagonal, numit
pivot. Din acest motiv, desfacerea
standard astfel definita trebuie sa se caracterizeze prin elemente nenule
pe diagonala matricei
D sau, ceea ce este totuna, pe diagonala matricei
A.
Daca exista cel putin un asemenea element nul este necesara permutarea
unor linii ale matricei
A (
pivotarea
partiala).
Tema
A - Metoda iterativa Jacobi
Metoda iterativa Jacobi, numita si metoda iteratiilor simultane,
foloseste o desfacere A = N - P, in care matricele N si P
se aleg conform relatiei:
N = D
P = - L - R
unde
D,
L si
R
sunt matricele din
desfacerea standard,
iar toate elementele diagonale
a_ii sunt nenule. Folosind aceasta
desfacere in relatia generala de recurenta, se obtine forma matriceala
a relatiei de recurenta pentru metoda Jacobi:
D * x_(k+1) = - ( L + R ) * x_k + b
Pentru un element
x_i al vectorului
necunoscutelor, la iteratia
k+1, relatia de recurenta capata forma:
care reprezinta formula de iterare
a metodei Jacobi. Inspectia sumara a acestei formule sugereaza imediat
motivul pentru care toate elementele diagonale
a_ii trebuie
sa fie nenule.
Metoda iterativa Jacobi este convergenta daca, pentru fiecare linie din
matricea
A, suma valorilor absolute ale termenilor din afara diagonalei
principale nu depaseste valoarea absoluta a termenului diagonal. Matricele
care satisfac aceasta proprietate se numesc
diagonal dominante.
O particularitate a metodei Jacobi se refera la modul cum este folosita
aproximatia anterioara
x_k pentru calculul noii aproximatii
x_(k+1).
Astfel, se constata ca noile aproximatii ale fiecarei necunoscute
se
determina în functie de aproximatiile anterioare ale tuturor celorlalte
necunoscute
(
j <> i ). Din acest motiv, noua aproximatie
nu
o poate inlocui pe cea anterioara în vectorul
x si, in consecinta,
aplicarea metodei Jacobi necesita folosirea a cel putin doi vectori : un
vector
x, care memoreaza aproximatia anterioara si un vector
y,
care memoreaza aproximatia nou calculata. La sfarsitul fiecarei iteratii
vectorul
x este actualizat, prin copierea in el a elementelor vectorului
y.
Algoritmul 1 - Sisteme de ecuatii liniare - Metoda iterativa Jacobi
- Definirea sistemului de ecuatii: rangul n, matricea coeficientilor A,
vectorul termenilor liberi b;
- Definirea parametrilor de iterare: abaterea relativa maxima admisa Emax
si numarul maxim de iteratii Nmax;
- Calcul iterativ:
- Stabilirea aproximatiei initiale, identica cu termenii liberi:
- Initializarea procesului iterativ: It <-- 0.
- Initializarea abaterii relative maxime in iteratia curenta cu
o valoare superioara lui Emax : Dx <-- Emax + 1.
- Daca s-a atins numarul maxim de iteratii (It=Nmax) sau
abaterea Dx a trecut sub valoarea admisa ( Dx <= Emax ),
se incheie procesul iterativ si se trece la pasul 4;
- Trecerea la o noua iteratie: It <-- It + 1.
- Calculul noii aproximatii in vectorul y:
- Calculul abaterii relative maxime in iteratia curenta:
- Actualizarea vectorului aproximatiilor din ultima iteratie:
- Se revine la pasul 3.iv.
- Stabilirea conditiilor de iesire din bucla iterativa:
- daca Dx <= Emax (metoda converge), se afiseaza solutia
aproximativasi
numarul de iteratii efectuate It;
- daca Dx>Emax, dar It=Nmax (metoda nu converge), se afiseaza
mesajul "Depasire numar maxim iteratii";
Tema
B - Metoda iterativa Seidel-Gauss
Metoda iterativa Seidel - Gauss, numita si metoda iteratiilor succesive,
foloseste o desfacere A = N - P, in care matricele N si P
se aleg conform relatiei:
N = L + D
P = - R
unde
D,
L si
R
sunt matricele din
desfacerea standard.
Folosind aceasta desfacere in relatia generala de recurenta, se obtine:
( L + D ) * x_(k+1) =
- R * x_k + b
care, particularizata pentru una
din necunoscutele
x_i, conduce la
formula de iterare a metodei
Seidel - Gauss:
Ca si in cazul metodei Jacobi, aparitia termenilor
a_ii la numitorul
acestei expresii reflecta necesitatea ca toate elementele diagonale ale
matricei
A sa fie nenule.
O comparatie intre formulele de iterare ale metodelor Jacobi si Seidel
- Gauss evidentiaza urmatoarea particularitate:
-
in cazul metodei Jacobi
noile aproximatii se determina folosind exclusiv aproximatiile
din iteratia anterioara;
-
prin contrast, metoda Seidel-Gauss
calculeaza noile aproximatii
folosind
si aproximatiile determinate deja in iteratia curenta
(,
j=1,...,i-1 ).
Consecinta imediata a acestei particularitati
o reprezinta posibilitatea utilizarii unui singur vector pentru memorarea
aproximatiilor succesive. Pe masura determinarii noilor aproximatii
,
acestea inlocuiesc in vectorul
x vechile aproximatii
,
care nu mai sunt folosite in iteratia curenta.
O alta consecinta a utilizarii aproximatiilor deja calculate pentru determinarea
celorlalte aproximatii se refera la convergenta metodei. De regula, metoda
Seidel - Gauss aduce un plus de viteza de convergenta fata de metoda Jacobi.
Astfel, este de asteptat ca, pornind de la o aceeasi aproximatie initiala,
metoda Seidel - Gauss sa asigure precizia impusa intr-un numar mai mic
de iteratii.
Ca si in cazul metodei Jacobi, conditia de convergenta a metodei Seidel
- Gauss o reprezinta forma diagonal dominanta a matricei coeficientilor
A.
Algoritmul 2 - Sisteme de
ecuatii liniare - Metoda iterativa Seidel-Gauss
- Definirea sistemului de ecuatii: rangul n, matricea coeficientilor A,
vectorul termenilor liberi b;
- Definirea parametrilor de iterare: abaterea relativa maxima admisa Emax
si numarul maxim de iteratii Nmax;
- Calcul iterativ:
- Stabilirea aproximatiei initiale, identica cu termenii liberi:
- Initializarea procesului iterativ: It <-- 0.
- Initializarea abaterii relative maxime in iteratia curenta cu
o valoare superioara lui Emax : Dx <-- Emax + 1.
- Daca s-a atins numarul maxim de iteratii (It=Nmax) sau
abaterea Dx a trecut sub valoarea admisa ( Dx <= Emax ), se
incheie procesul iterativ si se trece la pasul 4;
- Trecerea la o noua iteratie: It <-- It + 1.
- Initializarea abaterii relative maxime in iteratia curenta : Dx
<-- 0;
- Calculul noii aproximatii si al abaterii relative maxime folosind
o variabila tampon z:
- Se revine la pasul 3.iv.
- Stabilirea conditiilor de iesire din bucla iterativa:
- daca Dx <= Emax (metoda converge), se afiseaza solutia
aproximativasi
numarul de iteratii efectuate It;
- daca Dx>Emax, dar It=Nmax (metoda nu converge), se afiseaza
mesajul "Depasire numar maxim iteratii";
Tema
C - Metoda suprarelaxarii succesive
Metoda suprarelaxarii succesive este o varianta modificata a metodei
iterative Seidel - Gauss, care urmareste accelerarea suplimentara a convergentei
procesului iterativ. In acest scop, se utilizeaza o desfacere A = N
- P care depinde de un parametru real,
denumit parametru de accelerare (relaxare):
Matricele de desfacere
N()
si
P() se
pot alege arbitrar ca functii ale parametrului
.
Sa consideram insa cazul particular:
Alegerea judicioasa a parametrului
poate
determina cresterea ratei de convergenta. De fapt, pentru orice matrice
A
si pentru orice desfacere a acesteia de forma
se poate stabili o valoare optima a parametrului de accelerare
,
ca solutie a unei probleme de minimax (minimizarea unei valori maxime).
Un alt avantaj al metodei suprarelaxarii succesive consta in posibilitatea
transformarii unor procese divergente in procese convergente.
Introducerea matricelor
N()
si
P() astfel
definite in relatia de recurenta si particularizarea acesteia din
urma pentru una dintre necunoscutele
x_i, conduc la formula
de iterare a metodei suprarelaxarii succesive:
Comparand
formula de iterare a metodei Seidel-Gauss cu relatia de mai sus se constata ca metoda
suprarelaxarii succesive determina noua aproximatie prin aplicarea unei
corectii (ultimul termen din relatie) aproximatiei calculate dupa metoda
Seidel - Gauss. Aceasta corectie depinde de abaterile aproximatiilor in
doua iteratii succesive
-
si
de parametrul de accelerare
.
Pe de alta parte, se constata ca metoda suprarelaxarii succesive nu poate
folosi direct formula de iterare, deoarece aceasta determina aproximatia
in
functie de ea insasi. Din acest motiv, algoritmul de calcul determina mai
intai o solutie provizorie
cu
metoda Seidel-Gauss obisnuita, careia ii aplica apoi o corectie in functie
de abaterea
-
:
Pentru aceasta formula se pot stabili
doua expresii echivalente:
care introduc doi noi parametri de
accelerare:
Convergenta metodei Seidel - Gauss modificate, depinde in foarte mare masura
de alegerea parametrilor de accelerare
,
si
. Iata
doua cazuri particulare:
-
=1,
=0,
=1.
Aproximatiei nou calculate nu i se aplica nici o corectie. Se obtine metoda
Seidel - Gauss obisnuita;
-
=1/2,
=-1,
=0 .
Aproximatia nou calculata coincide cu aproximatia din iteratia anterioara.
Procesul este stationar, toate aproximatiile ramanand identice cu aproximatia
initiala.
In practica, factorul de relaxare
se alege de regula in intervalul ( 0 , 2
) . Daca
>2
procesul iterativ diverge in cele mai multe cazuri. In general, nu exista
un criteriu unic de determinare a valorii optime a parametrului de accelerare
,
aceasta valoare fiind influentata de structura particulara a fiecarui sistem
de ecuatii liniare analizat. Din acest motiv, se recomanda utilizarea cu
prudenta a metodei suprarelaxarii succesive, iar atunci cand aceasta se
aplica se recomanda folosirea unor parametri de accelerare cu valori in
intervalul 1.4 - 1.5.
In general, valori ale parametrului de accelerare 1 <
< 2 asigura accelerarea convergentei unor procese iterative deja convergente,
in timp ce valori ale aceluiasi parametru 0 <
< 1 permit deseori transformarea unor procese divergente in procese
convergente.
Algoritmul 3 - Sisteme de ecuatii liniare - Metoda suprarelaxarii succesive
- Definirea sistemului de ecuatii: rangul n, matricea coeficientilor A,
vectorul termenilor liberi b;
- Definirea parametrilor de iterare: abaterea relativa maxima admisa Emax
si numarul maxim de iteratii Nmax;
- Calcul iterativ:
- Stabilirea aproximatiei initiale, identica cu termenii liberi:
- Initializarea procesului iterativ: It <-- 0.
- Initializarea abaterii relative maxime in iteratia curenta cu
o valoare superioara lui Emax : Dx <-- Emax + 1.
- Daca s-a atins numarul maxim de iteratii (It=Nmax) sau
abaterea Dx a trecut sub valoarea admisa ( Dx <= Emax ), se
incheie procesul iterativ si se trece la pasul 4;
- Trecerea la o noua iteratie: It <-- It + 1.
- Initializarea abaterii relative maxime in iteratia curenta : Dx
<-- 0;
- Calculul noii aproximatii si al abaterii relative maxime folosind
o variabila tampon z:
- Se revine la pasul 3.iv.
- Stabilirea conditiilor de iesire din bucla iterativa:
- daca Dx <= Emax (metoda converge), se afiseaza solutia
aproximativasi
numarul de iteratii efectuate It;
- daca Dx>Emax, dar It=Nmax (metoda nu converge), se afiseaza
mesajul "Depasire numar maxim iteratii";
Pentru detalii suplimenatare privind
metodele iterative si convergenta procesului iterativ, se poate consulta
cartea
"Calcul numeric cu aplicatii in Turbo Pascal".
Aplicatii - Lista lucrarilor de laborator