Rezolvarea sistemelor#

Motivul pentru care ne propunem să rezolvăm sisteme de ecuații liniare este simplu, acestea se regăsesc peste tot în jurul nostru, modelând orice, începând cu circuitele electrice și până la funcționalitatea din spatele inteligenței artificiale.

Vom aborda însă acest subiect dintr-o perspectivă mai timidă pentru moment, urmând să dezbatem pe larg metode de rezolvare a sistemelor de ecuații liniare și neliniare pe parcursul acestei cărți.

Implementarea naivă#

Matematica ne dă deja o soluție pentru a rezolva sistemele de ecuații liniare. Fie un sistem de ecuații liniare, scris sub forma matriceală \(A\bm{x}=\bm{b}\), unde \(A\in\mathbb{R}^{n\times n}\) și \(\bm{x},\bm{b}\in\mathbb{R}^n\). În această situație, rezolvarea sistemului se poate face folosind ecuația:

Deși această soluție este foarte corectă din punct de vedere matematic, inversarea unei matrice, așa cum va fi ea prezentată în capitolele următoare, este un proces instabil numeric și costisitor, executându-se într-o complexitate de \(O(n^3)\).

Totodată, în cazul inversării unei matrice rare (en. Sparse Matrix - matrice ce conține preponderent valori nule), se va obține o matrice densă (en. Dense Matrix - opusul unei matrice rare, adică o matrice care conține preponderent valori nenule). Acest lucru duce la ocuparea unei bucăți mari de memorie pentru a putea fi reținută.

O parte semnificativă din materia de Metode Numerice gravitează în jurul ideii conform căreia inversarea unei matrice este (adesea) nedorită! - dacă rămâneți cu ceva, rămâneți cu asta.

În paragrafele următoare, vom introduce o modalitate de a soluționa un sistem de ecuații liniare utilizând factorizarea LU învățată anterior.

Noțiuni matematice#

Vom încerca să explicăm întâi de ce unele sisteme de ecuații liniare sunt mai ușor de soluționat decât altele. Pentru aceasta, vom introduce două noțiuni noi, anume sistemele superiror triunghiulare și sistemele inferior triunghiulare.

Sisteme superior triunghiulare#

Fie un sistem de ecuații liniare, scris sub forma matriceală \(U\bm{x}=\bm{b}\), unde \(U\in\mathbb{R}^{n\times n}\) este o matrice superior triunghiulară și \(\bm{x},\bm{b}\in\mathbb{R}^n\):

Acesta poartă denumirea de sistem superior triunghiular (SST) și este mult mai ușor de rezolvat decât un sistem obișnuit.

Rescriem ecuația \(U\bm{x}=\bm{b}\):

Din ultima ecuație, se observă că este ușor de scos \(x_n\); cunoscându-l pe acesta, din penultima ecuație se poate afla rapid \(x_{n-1}\), apoi folosind \(x_n\) și \(x_{n-1}\) se extrage \(x_{n-2}\) ș.a.m.d. La modul general, dacă sunt cunoscute valorile pentru \(x_n, x_{n0},\dots,x_{i+1}\), atunci este ușor de aflat valoarea pentru \(x_i\), \(\forall i\in\overline{1,n}\), folosind formula:

Cod ilustrativ#

Pentru a rezolva sisteme superior triunghiulare, se poate utiliza funcția SST, care acceptă:

• A - o matrice superior triunghiulară;

• b - vectorul coloană din partea dreaptă a egalității \(A\bm{x}=\bm{b}\).

Funcția returnează x, vectorul coloană soluție a sistemului superior triunghiular.

function x = SST(A, B)
    n = length(B);
    x = zeros(n, 1);
    for i = [n : -1 : 1]
        S = 0;
        for j = [i+1 : n]
            S += A(i,j) * x(j);
        end
        x(i) = (B(i) - S) / A(i,i);
    end
end

Sisteme inferior triunghiulare#

Un concept foarte asemănător pornește de la matricele inferior triunghiulare.

Fie un sistem de ecuații liniare, scris sub forma matriceală \(L\bm{x}=\bm{b}\), unde \(L\in\mathbb{R}^{n\times n}\) este o matrice inferior triunghiulară și \(\bm{x},\bm{b}\in\mathbb{R}^n\).

Acesta poartă denumirea de sistem inferior triunghiular (SIT) și este mult mai ușor de rezolvat decât un sistem obișnuit.

Începem prin a rescrie ecuația \(L\bm{x}=\bm{b}\):

Din prima ecuație, se observă că este ușor de scos \(x_1\); cunoscându-l pe acesta, din a doua ecuație se poate afla rapid \(x_2\); aceste prime două valori conduc la aflarea lui \(x_3\) ș.a.m.d. La modul general, dacă sunt cunoscute valorile pentru \(x_1,x_2,\dots,x_{i-1}\), atunci este ușor de aflat valoarea pentru \(x_i\), \(\forall i\in\overline{1,n}\), folosind formula:

Cod ilustrativ#

Pentru a rezolva sisteme inferior triunghiulare, se poate utiliza funcția SIT, care acceptă:

• A - o matrice inferior triunghiulară;

• b - vectorul coloană din partea dreaptă a egalității \(A\bm{x}=\bm{b}\).

Funcția returnează x, vectorul coloană soluție a sistemului inferior triunghiular.

function x = SIT(A, b)
    n = length(b);
    x = zeros(n, 1);
    for i = [1 : n]
        S = 0;
        for j = [1 : i-1]
            S += A(i,j) * x(j);
        end
        x(i) = (b(i) - S) / A(i,i);
    end
end

Rezolvarea sistemelor cu LU#

Putem acum să concepem o modalitate prin care să soluționăm un sistem de ecuații liniare oarecare, nu doar unul triunghiular.

Fie un sistem de ecuații liniare, scris sub forma matriceală \(A\bm{x}=\bm{b}\), unde \(A\in\mathbb{R}^{n\times n}\) și \(\bm{x},\bm{b}\in\mathbb{R}^n\). Totodată, să considerăm factorizarea LU a matricei \(A\), anume \(A=LU\) (\(L,U\in\mathbb{R}^{n\times n}\)). Atunci, dacă notăm \(\bm{y}=U\bm{x}\in\mathbb{R}^n\), sistemul poate fi rescris drept:

Sistemul astfel obținut presupune rezolvarea mai întâi a unui SIT (\(L\bm{y}=\bm{b}\)), iar apoi a unui SST (\(U\bm{x}=\bm{y}\)), precum a fost explicat anterior. Așadar, întreg procesul a fost simplificat până s-a ajuns la ceva digerabil.

Cu toate că acest algoritm ar avea aceeași complexitate cu implementarea naivă, \(O(n^3)\), rezultatul obținut este mult mai stabil din punct de vedere numeric.

Cod ilustrativ#

Presupunând implementată o funcție LU ce calculează factorizarea LU a unei matrice, respectiv funcțiile de rezolvare a sistemelor inferior/superior triunghiulare (SIT / SST), considerăm:

• A - matricea coeficienților sistemului;

• b - vectorul coloană din partea dreaptă a egalității \(A\bm{x}=\bm{b}\).

Funcția returnează x, vectorul coloană soluție a sistemului de ecuații liniare.

function x = solutie_sistem(A, b)
    [L, U] = LU(A);
    y = SIT(L, b);
    x = SST(U, y);
end

Concluzii#

Factorizarea LU este una dintre cele mai importante descompuneri din lumea metodelor numerice, fiind (oarecum) ușor de înțeles și de implementat.

În capitolele următoare, vor fi descrise și altfel de descompuneri, acestea urmând să fie comparate cu factorizările LU.

Licență#

The book "Metode Numerice", written by Valentin-Ioan Vintilă, is licensed under CC BY-NC-SA 4.0