Algoritmul GPPS#

Am "reparat" algoritmul G trecând la algoritmul GPP, adică introducând pivotarea între linii în prealabil. Mergem un pas mai departe și evoluăm algoritmul GPP folosindu-ne de scalare.

Categorii de GPPS#

Diferența principală dintre GPP și GPPS este dată de crearea unui vector adițional, \(\bm{s}=\begin{bmatrix}s_1&\dots&s_n\end{bmatrix}\in\mathbb{R}^n\), denumit vector de scalare (sau factor de scalare). Acest vector se calculează o singură dată, la începutul rulării algoritmului GPPS.

Există multiple modalități de a defini acest vector, dat fiind un sistem de ecuații liniare descris prin matricea extinsă \(\overline{A}\in\mathbb{R}^{n\times(n+1)}\), însă cele mai comune sunt:

  1. În funcție de modulul maxim de pe linia \(i\in\overline{1,n}\), începând cu a \(i\)-a coloană:

    \[ \boxed{s_i=\max_{j\in\overline{i,n}}\Big\{\left|\overline{a}_{i,j}\right|\Big\}}\,,\,\,\forall i\in\overline{1,n} \]
    GPP vs GPPS

    Mare atenție însă - spre deosebire de valoarea folosită de GPP, se caută valoarea de modul maxim de pe linie, NU de pe coloană; confuzia aceasta poate da peste cap întregul algoritm.

  2. În funcție de suma modulelor de pe linia \(i\in\overline{1,n}\), adică:

    \[ s_i=\sum_{j=i}^n\left|\overline{a}_{i,j}\right|,\,\forall i\in\overline{1,n} \]

În explicațiile ce urmează, voi presupune că \(s_i\) se calculează în baza modulului maxim, \(\forall i\in\overline{1,n}\). Vectorul \(\bm{s}\) va fi utilizat în algoritm atunci când se decide care linii trebuie interschimbate. Informații suplimentare vor apărea în paragrafele de mai jos.

Notă importantă

Presupunându-se cunoscut vectorul \(\bm{s}\in\mathbb{R}^n\), dacă oricare dintre valorile \(s_i\) este nulă (\(\exists i\in\overline{1,n}\) a.î. \(s_i=0\)), atunci matricea \(A\in\mathbb{R}^{n\times n}\) este singulară, așadar nu poate fi calculată nicio soluție validă pentru \(\bm{x}\in\mathbb{R}^n\).

Explicație algoritmică#

Să vedem acum modul în care ne ajută de fapt vectorul \(\bm{s}\).

Fie \(A\bm{x}=\bm{b}\) un sistem de ecuații liniare, unde \(A\in\mathbb{R}^{n\times n}\) este o matrice pătratică și \(\bm{x},\bm{b}\in\mathbb{R}^n\) sunt vectori coloană. Notăm \(\overline{A}=\begin{bmatrix}A&\bm{b}\end{bmatrix}\) matricea extinsă ce conține elemente de forma \(\overline{a}_{ij}\) pe linia \(i\in\overline{1,n}\), coloana \(j\in\overline{1,n+1}\).

Înainte de orice, se va calcula vectorul \(\bm{s}\) folosind una din formulele prezentate anterior. În cazul de față, folosind modulul maxim, obținem:

\[ \boxed{s_i=\max_{j\in\overline{i,n}}\Big\{\left|\overline{a}_{i,j}\right|\Big\}}\,,\,\,\forall i\in\overline{1,n} \]

Pentru fiecare linie \(i\in\overline{1,n-1}\) cu excepția ultimei, se va alege mai întâi o valoare \(k\in\overline{i,n}\) astfel încât \(\left|\frac{\overline{a}_{ki}}{s_k}\right|=\max_{j\in\overline{i,n}}\left\{\left|\frac{\overline{a}_{ji}}{s_j}\right|\right\}\) și se vor interschimba liniile \(i\) și \(k\), respectiv valorile \(s_i\) și \(s_k\).

Apoi, în matricea proaspăt formată, se vor transforma toate elementele aflate pe a \(i\)-a coloană sub diagonala principală (sub \(\overline{a}_{ii}\)), adică elementele \(\overline{a}_{ji}\), \(\forall j\in\overline{i+1,n}\), în zerouri prin scăderea celei de-a \(i\)-a linii scalată cu \(\frac{\overline{a}_{ji}}{\overline{a}_{ii}}\) din cea de-a \(j\)-a linie.

Matematic, pasul \(i\) arată astfel:

  1. Interschimbarea celor două linii poate fi scrisă drept:

    \[ \exists\,k\in\overline{i,n}: \left|\frac{\overline{a}_{ki}}{s_k}\right|=\max_{j\in\overline{i,n}}\left\{\left|\frac{\overline{a}_{j,i}}{s_j}\right|\right\}\Rightarrow\boxed{\begin{cases}\bm{L_i}(\overline{A})\leftrightarrow\bm{L_k}(\overline{A})&\text{și}\\s_i\leftrightarrow s_j \end{cases}} \]

  2. Apoi, se poate aplica algoritmul G clasic:

    \[ \boxed{\bm{L_j}(\overline{A})\rightarrow \bm{L_j}(\overline{A})-\frac{\overline{a}_{ji}}{\overline{a}_{ii}}\cdot \bm{L_i}(\overline{A})}\,,\,\,\forall j\in\overline{i+1,n} \]

Exemplificarea algoritmului#

Să considerăm același sistem de ecuații liniare, descris direct în forma: \(\overline{A}=\begin{bmatrix} 1 & -2 & 1 & | & 0\\ 2 & 1 & -3 & | & 5\\ 4 & -7 & 1 & | & 1 \end{bmatrix}\).

Urmăm acum pașii descriși anterior:

  • Pasul 1. Calculăm coeficientul de scalare. După cum am discutat, există mai multe modalități de a efectua acest calcul, dar alegem modulul maxim:

    \[ S=\begin{bmatrix} 2 & 3 & 7 \end{bmatrix} \]

  • Pasul 2a. Deoarece \(\left|\frac{\overline{a}_{21}}{s_2}\right|=\frac{2}{3}\geq\left|\frac{\overline{a}_{31}}{s_3}\right|=\frac{4}{7}\geq\left|\frac{\overline{a}_{11}}{s_1}\right|=\frac{1}{2}\), facem interschimbările de linie și de coeficient de scalare, adică \(\bm{L_1}(\overline{A})\leftrightarrow\bm{L_2}(\overline{A})\) și \(s_1\leftrightarrow s_2\):

    \[ \overline{A}=\begin{bmatrix} 2 & 1 & -3 & | & 5\\ 1 & -2 & 1 & | & 0\\ 4 & -7 & 1 & | & 1\\ \end{bmatrix}\text{ și }S=\begin{bmatrix} 3 & 2 & 7 \end{bmatrix} \]

  • Pasul 2b. Golirea primei coloane. Se execută:

\[\begin{cases} \bm{L_2}(\overline{A})\rightarrow \bm{L_2}(\overline{A})-\frac{1}{2}\bm{L_1}(\overline{A})\\ \bm{L_3}(\overline{A})\rightarrow \bm{L_3}(\overline{A})-2\bm{L_1}(\overline{A}) \end{cases}\Rightarrow \overline{A}=\begin{bmatrix} 2 & 1 & -3 & | & 5\\ 0 & -2.5 & 2.5 & | & -2.5\\ 0 & -9 & 7 & | & -9 \end{bmatrix}\]

  • Pasul 3a. Deoarece \(\left|\frac{\overline{a}_{32}}{s_3}\right|=\frac{9}{7}\geq\left|\frac{\overline{a}_{22}}{s_2}\right|=\frac{5}{4}\), facem interschimbările de linie și de coeficient de scalare, adică \(\bm{L_2}(\overline{A})\leftrightarrow\bm{L_3}(\overline{A})\) și \(s_2\leftrightarrow s_3\):

    \[ \overline{A}=\begin{bmatrix} 2 & 1 & -3 & | & 5\\ 0 & -9 & 7 & | & -9\\ 0 & -2.5 & 2.5 & | & -2.5 \end{bmatrix}\text{ și }S=\begin{bmatrix} 3 & 7 & 2 \end{bmatrix} \]

  • Pasul 3b. Golirea celei de-a doua coloane. Se execută:

    \[\bm{L_3}(\overline{A})\rightarrow \bm{L_3}(\overline{A})+\frac{5}{18}\bm{L_2}(\overline{A}) \Rightarrow \overline{A}\approx\begin{bmatrix} 2 & 1 & -3 & | & 5\\ 0 & -9 & 7 & | & -9\\ 0 & 0 & 0.5556 & | & 0 \end{bmatrix}\]

Concluzie. Se rezolvă sistemul superior triunghiular (de jos în sus) și se obține: \(\begin{cases} x_3=0\\ x_2=1\\ x_1=2 \end{cases}\).

Cod ilustrativ#

Pentru a ajunge la algoritmul GPPS, folosim funcția GPP, primind parametrii reprezentativi sistemului \(A\bm{x}=\bm{b}\):

  • A - matricea coeficienților sistemului;

  • b - vectorul coloană din partea dreaptă a egalității.

Funcția returnează perechea [A, b], echivalentul unui sistem triunghiular de ecuații liniare pe care se poate aplica apoi SST-ul explicat anterior. 

function [A, b] = GPPS(A, b)
    [m, n] = size(A);
    Ae = [A, b];
    for p = [1 : n]
        S(p) = max(abs(A(p,:)));
    end
    for p = [1 : n-1]
        % Partea de GPPS:
        [piv, l_piv] = max(abs(Ae(p:n, p)) ./ S(:,p:n)');
        l_piv = l_piv + p - 1;
        temp = Ae(l_piv, :);
        Ae(l_piv,:) = Ae(p, :);
        Ae(p, :) = temp;
        temp = S(l_piv);
        S(l_piv) = S(p);
        S(p) = temp;

        % Algoritmul G:
        if (Ae(p ,p) == 0)
            continue;
        end
        for l = p+1 : n
            arg = Ae(l, p) / Ae(p, p);
            Ae(l, :) = Ae(l, :) - arg * Ae(p, :);
        end
    end
    A = Ae(:, 1:n);
    b = Ae(:, n+1);
end

Calcularea complexității#

Calcularea vectorului \(\bm{s}\) se reduce la \((n-i+1)\) operații pentru fiecare element \(s_i\), \(\forall i\in\overline{1,n}\). Așadar, complexitatea adițională \(SPP'(n,m)\) ia forma:

\[ SPP'(n,m)=\sum_{i=1}^n(n-i+1)=O(n^2) \]

Complexitatea finală (obținută prin însumarea lui \(SPP'\) la \(PP'+GE=PP\)) devine:

\[ SPP(n,m) = SPP'(n,m) + PP'(n,m) + GE(n,m) \]

Așadar, \(SPP(n,m)\in O(mn\mu)=O(mn\cdot\min\{m,n\})\).

Licență#

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

Results will appear as you type