Metode iterative de solutionare a sistemelor de ecuatii liniare

Metode iterative de solutionare a sistemelor de ecuatii liniare

1. Aspecte generale

Determinarea solutiei exacte a sistemului liniar de forma [A] [X] = [b] cu ajutorul unor metode de tip iterativ este posibila numai dupa efectuarea unui numar, teoretic infinit, de iteratii. Deoarece nici o metoda practica nu poate cicla la infinit, rezulta ca metodele iterative determina doar o solutie aproximativa, aproximata prin trunchiere, care se abate mai mult sau mai putin fata de solutia exacta X , in functie de precizia dorita.

Metodele iterative apeleaza la construirea unui sir de aproximatii succesive X⁰, X¹, , 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 este divergenta. In cazul in care sirul aproximatiilor succesive are o limita, se spune ca metoda este convergenta. Convergenta sirului aproximatiilor succesive este echivalenta cu posibilitatea definirii unei relatii 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 doua matrice:

(1)

Utilizand aceasta desfacere in expresia sistemului initial de ecuatii se obtine relatia:

    (2)

care permite ca, pornind de la o aproximare initiala X⁰, sa se construiasca un sir de aproximatii succesive pe baza relatiei de recurenta:

    (3)

In general, toate metodele iterative de rezolvare a sistemelor de ecuatii liniare, definesc matricile [N] si [P] pornind de la desfacerea standard a matricei [A]:

    (4)

unde:

[L] este o matrice strict inferior triunghiulara ale carei elemente subdiagonale sunt elementele matricei [A];

[R] este o matrice strict superior triunghiulara ale carei elemente supradiagonale sunt elementele matricei [A];

[D] este o matrice diagonala ale carei elemente nenule sunt tocmai elementele diagonale din matricea [A].

Ca in cazul metodelor directe, toate metodele iterative folosesc impartirea la un element diagonal, numit pivot. Din acest motiv, desfacerea standard definita de relatia (4) trebuie sa se caracterizeze prin elemente nenule pe diagonala matricei [A]. Daca exista cel putin un asemenea element nul este necesara efectuarea pivotarii partiale.

Fiecare metoda iterativa poate sa aiba una dintre urmtoarele trei conditii de oprire a procesului iterativ:

1. trecerea abaterii maxime intre doua iteratii succesive sub o valoare prag impusa E_max. Abaterea maxima se defineste ca cea mai mare abatere, in valoare absoluta, intre necunoscute in doua iteratii succesive:

    (5)

2. trecerea reziduului maxim la o iteratie sub o valoare prag impusa R_max. Reziduul maxim este definit ca cea mai mare abatere, in valoare absoluta, intre vectorul termenilor liberi [b] si produsul matricei [A] cu vectorul aproximatiei curente [X^k]:

    (6)

3. trecerea valorii unei functii obiectiv care depinde de toate necunoscutele X_i (i = 1, , n) calculata la fiecare iteratie, sub o valoare prag impusa F_max:

    (7)

2. Metoda iterativa Seidel - Gauss

Metoda iterativa Seidel - Gauss foloseste o desfacere de forma:

    (8)

Folosind aceasta desfacere, relatia de recurenta (3) capata urmatoarea forma:

    (9)

Relatia (9) particularizata pentru una dintre necunsocutele X_i, conduce la formula de iterare a metodei Seidel - Gauss:

    (10)

Aparitia termenilor a_ii la numitorul expresiilor (7) reflecta necesitatea ca toate elementele diagonale ale matricei [A] sa fie nenule. Conditia de convergenta a metodei Seidel - Gauss o reprezinta forma diagonal dominanta a matricei coeficientilor din matricea [A].

Algoritmul asociat metodei Seidel - Gauss este prezentat in Fig. 1.

Mersul lucrarii

Se studiaza textul lucrarii si metoda de rezolvare numerica a sistemului de ecuatii liniare.

Se elaboreaza programul de calcul.

Se testeaza programul de calcul.

Se solutioneaza cateva aplicatii numerice semnificative, prezentandu-se rezultatele.