Metode iterative

In aceasta tema:

Prezentarea principalelor metode iterative de rezolvare a sistemelor de ecuatii liniare;

Metoda iterativa Jacobi;

Metoda iterativa Gauss-Seidel;

Metoda suprarelaxarii succesive (SOR);

1. Metode iterative de rezolvare a sistemelor de ecuatii liniare

1.1. Prezentarea teoretica

Rezolvarea sistemelor de ecuatii liniare se face prin algoritmi grupati in doua mari clase:

Algoritmi directi (Gauss, Gauss-Jordan);

Algoritmi iterativi (Jacobi, Gauss-Seidel, SOR).

Algoritmii directi sunt acei algoritmi care, prin calcule, incearca aducerea sistemului initial la un sistem de ecuatii rezolvabil mai usor. Daca erorile de rotunjire lipsesc, acesti algoritmi conduc la solutia exacta a sistemului.

Algoritmii iterativi pornesc de la o aproximatie initiala a solutiei sistemului x⁽⁰⁾ si se incearca imbunatatirea acestei aproximatii prin determinarea unui sir de solutii aproximative x^(k), k=1,2,3,.. convergent catre solutia exacta. Procesul iterativ se opreste atunci cand aproximatia la iteratia k se incadreaza in limitele unei precizii stabilite initial. Metodele iterative se impart la randul lor in metode iterative stationare si metode iterative nestationare.

De aceea, putem scrie matricial un proces iterativ pentru rezolvarea unui sistem de n ecuatii liniare ca fiind:

                      (1)

Se spune despre un proces iterativ ca este stationar daca in timpul iteratiilor, atat matricea R cat si vectorul S raman neschimbate.

2. Metode iterativa Jacobi

2.1. Prezentarea teoretica

Se considera sistemul liniar de n ecuatii cu n necunoscute scris sub forma matriciala

(2)

Presupunem ca elementele de pe diagonala principala sunt diferite de zero. a_i,i 0; i=1,2,3,,n. Se rezolva fiecare ecuatie i in raport cu x_i sistemul devenind:

(3)

Sau, scris matricial:

(4)

unde

(5)

Metoda Jacobi porneste de la aproximatia initiala x⁽⁰⁾=S si succesiv se determina vectorii:

x⁽¹⁾=Rx⁽⁰⁾+S

x⁽²⁾=Rx⁽¹⁾+S

si asa mai departe. La modul general se poate scrie

                                      (6)

sau, altfel scris, procesul iterativ este:

(7)

sau, scris altfel:

(8)

Daca metoda Jacobi converge, la limita, cand numarul iteratiilor tinde la infinit, solutia aproximativa tinde la solutia exacta.

Conditia necesara si suficienta pentru ca procesul iterativ Jacobi sa fie convergent este ca matricea sistemului sa fie diagonal dominanta adica elementul de pe diagonala principala a matricei in valoare absoluta sa fie mai mare sau egal cu suma valorilor absolute a celorlalte elemente de pe linia respectiva.

Conditia de oprire a procesului iterativ este ca norma canonica a vectorului diferenta intre doua aproximatii succesive sa fie mai mica decat o eroare admisibila impusa.

Metoda Jacobi este o metoda stationara deoarece in cursul procesului iterativ, atat matricea de iteratie R cat si vectorul S raman cu valori neschimbate.

2.2. Aplicatii rezolvate

Aplicatia 1.

Sa se realizeze programul in limbajul Pascal care rezolva un sistem de ecuatii prin metoda iterativa Jacobi.

Rezolvare

Fiind dat sistemul de ecuatii liniare :

algoritmul de rezolvare este destul de simplu deoarece trebuie calculata o singura suma in variabila s. Maxit reprezinta numarul maxim de iteratii dupa care procesul iterativ este declarat neconvergent. Conditia de oprire a procesului iterativ este calculata prin intermediul variabilei maxe ce reprezinta valoarea maxima a diferentei in valoare absoluta dintre doua solutii succesive. Variabila epsi reprezinta o data de intrare ce pastreaza toleranta admisa pentru solutia sistemului de ecuatii. Programul nu testeaza daca elementul de pe diagonala principala este in valoare absoluta mai mare sau egal cu suma celorlalte elemente de pe linia respectiva conditia care este de convergenta.

Programul pentru rezolvarea prin metoda Jacobi se numeste JacobiSEL si este prezentat in lista 1

2.3. Aplicatii propuse

Aplicatia P1.

Sa se realizeze programul in limbajul Pascal care determina solutia sistemului de ecuatii si numarul de iteratii pentru a obtine o solutie cu o eroare de 10 . Se va folosi metoda iterativa Jacobi.

3. Metoda iterativa Gauss-Seidel

3.1. Prezentarea teoretica

Presupunem ca elementele de pe diagonala principala sunt diferite de zero. a_i,i 0, i=1,2,3,,n. Procedand ca si la metoda Jacobi, se poate rescrie sistemul intr-o forma echivalenta:

(9)

Sau, scris matricial:

(10)

unde

(11)

Metoda Gauss-Seidel porneste la fel ca si metoda Jacobi cu o aproximatie initiala a solutiei, x⁽⁰⁾=S, dar spre deosebire de metoda Jacobi care foloseste in procesul iterativ doar valorile solutiei aproximative determinate la iteratia anterioara, metoda Gauss-Seidel foloseste si valorile deja determinate in iteratia curenta, astfel incat se mareste viteza de convergenta a procesului iterativ.

Astfel, aproximatia initiala poate fi aleasa ca fiind:

(12)

Presupunand ca solutia aproximativa la iteratia k este determinata, aproximatia la iteratia k+1 va fi calculata dupa urmatoarele relatii:

(13)

Deci, se poate scrie la modul general ca:

(14)

sau scris altfel:

Conditia de oprire a procesului iterativ Gauss-Seidel este ca norma canonica a vectorului diferenta intre doua aproximatii succesive sa fie mai mica decat o eroare admisibila impusa.

Se estimeaza ca metoda Gauss-Seidel, la acelasi nivel de precizie, este de doua ori mai rapida decat metoda Jacobi.

2.2. Aplicatie rezolvata

Aplicatia 2

Sa se realizeze in limbajul Pascal programul care rezolva un sistem de ecuatii liniar prin metoda iterativa Gauss-Seidel.

Rezolvare

Algoritmul de rezolvare prin metoda iterativa Gauss-Seidel este simplu constand in calcularea a doua sume s si s1, una pentru insumarea termenilor dati de produsul intre elementele matricei sistemului si valoarea necunoscutei la iteratia curenta, respectiv  suma termenilor dati de elementele matricei sistemului si necunoscutele la iteratia anterioara. Drept norma canonica a vectorului diferenta intre solutiile la doua iteratii succesive se va considera norma canonica:

Celelalte variabile au semnificatia de la metoda Jacobi.

Programul pentru rezolvarea sistemului liniar de ecuatii prin metoda iterativa Gauss-Seidel se numeste GaussSeidelSEL si este prezentat in lista 2

Lista 2. Programul GaussSeidelSEL (continuare)

3.3. Aplicatii propuse

Aplicatia P2.

Sa se realizeze programul in limbajul Pascal care determina solutia sistemului de ecuatii si numarul de iteratii pentru a obtine o solutie cu o eroare de 10 . Se va folosi metoda iterativa Gauss-Seidel.

4. Metoda iterativa a suprarelaxarii succesive

4.1. Prezentarea teoretica

Metoda suprarelaxarii succesive (succesive over-relaxation SOR) se aseamana cu metoda Gauss-Seidel prezentata anterior, dar spre deosebire de aceasta se adauga un factor de ponderare  astfel incat formula devine:

(15)

unde x^*(k+1) este solutia obtinuta prin relatia Gauss-Seidel. Prin urmare, pentru determinarea necunoscutei x^(k+1)_i din ecuatia i a sistemului de ecuatii, se va folosi relatia:

(16)

Factorul de ponderare care se numeste si factor de suprarelaxare se alege astfel incat sa se mareasca viteza de convergenta. Daca metoda suprarelaxarii devine metoda Gauss-Seidel. In general, factorul de suprarelaxare are valori intre zero si doi adica wI

Scrisa matricial metoda suprarelaxarii succesive este:

(17)

unde R este matricea de iteratie pentru metoda suprarelaxarii.

Se poate demonstra usor, la fel ca si pentru metodele Jacobi si Gauss-Seidel, aceeasi conditie de convergenta, si anume matricea sistemului trebuie sa fie diagonal dominanta.

Conditia de oprire a procesului iterativ este aceeasi ca si la metodele iterative stationare discutate anterior adica, norma canonica a vectorului diferenta intre doua aproximatii succesive a solutiei sistemului sa fie mai mica decat o eroare maxima admisibila e

Alegerea unui factor optim de suprarelaxare este foarte important deoarece, de acest factor, depinde viteza de convergenta a procesului iterativ.

Pentru a estima un factor optim de suprarelaxare, Varga et al demonstreaza urmatoarea formula:

(18)

unde r(J) este raza spectrala a matricei de iteratie Jacobi.

Deoarece este greu sa estimam cu aceasta formula factorul optim de suprarelaxare w, in practica aceasta se ia de obicei o valoare mai mare decat unu, dar mai mica decat doi.

Aplicatia 3.

Sa se realizeze programul in limbajul Pascal care rezolva sistemul de ecuatii liniare prin metoda suprarelaxarii succesive.

Rezolvare

Programul pentru rezolvarea acestei aplicatii se numeste SORSEL si este prezentat in lista 3

Lista 3. Programul SORSEL (continuare)

4.3. Aplicatii propuse

Sa se realizeze programul in limbajul Pascal care determina solutia sistemului de ecuatii si numarul de iteratii pentru a obtine o solutie cu o eroare de 10^-6. Se va folosi metoda iterativa a suprarelaxarii succesive.