Algoritmul GPP#

Am încheiat subcapitolul anterior justificând necesitatea căutării unei îmbunătățiri algoritmului G. Soluția este introducerea pivotării liniilor - vom explica acum cum funcționează, atât vizual, cât și formal, respectiv exemplificat.

Vizualizarea algoritmului#

Omul este o ființă vizuală, așadar...

Fie \(A\in\mathbb{R}^{3\times3}\), o matrice pătratică de coeficienți pentru sistemul de ecuații liniare \(A\bm{x}=\bm{b}\), unde \(x,b\in\mathbb{R}^3\). Totodată, să considerăm cunoscute valorile aflate pe prima coloană, de pildă \(0\), \(-8\) și \(4\). Atunci, sistemul ia forma:

\[ A\bm{x}=\bm{b}\Rightarrow\begin{bmatrix} 0 & \boxtimes & \boxtimes\\ -8 & \boxtimes & \boxtimes\\ 4 & \boxtimes & \boxtimes \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix} = \begin{bmatrix} b_1\\b_2\\b_3 \end{bmatrix} \]

Am stabilit deja că algoritmul G trebuie modificat astfel încât \(a_{0,0}=0\) să nu ne facă probleme. Așadar, interschimbarea primelor două linii ar putea rezolva problema:

\[ \begin{bmatrix} -8 & \boxtimes & \boxtimes\\ 0 & \boxtimes & \boxtimes\\ 4 & \boxtimes & \boxtimes \end{bmatrix}\begin{bmatrix} x_1\\x_2\\x_3 \end{bmatrix} = \begin{bmatrix} b_2\\b_1\\b_3 \end{bmatrix} \]

În această situație, am interschimbat linia \(1\) cu linia ce conține pe coloana întâi elementul de modul maxim. Vom generaliza în secțiunile următoare algoritmul pentru a funcționa pe fiecare linie \(i\in\overline{1,n-1}\).

Explicația algoritmică#

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}\).

Pentru fiecare linie \(i\) cu excepția ultimei (\(i\in\overline{1,n-1}\)), se va alege o valoare \(k\in\overline{i,n}\) astfel încât \(|\overline{a}_{k,i}|=\max_{j\in\overline{i,n}}\{\left|\overline{a}_{j,i}\right|\}\), iar apoi se vor interschimba liniile \(i\) și \(k\).

Apoi, în noua matrice formată, asemănător cu G clasic, se vor transforma toate elementele găsite pe a \(i\)-a coloană sub elementul de pe diagonala principală, \(\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 linie 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}: |\overline{a}_{k,i}|=\max_{j\in\overline{i,n}}\{\left|\overline{a}_{j,i}\right|\}\Rightarrow\boxed{\bm{L}_i(\overline{A})\leftrightarrow\bm{L}_k(\overline{A})} \]

  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 1a. Deoarece \(|\overline{a}_{31}|\geq|\overline{a}_{21}|\geq|\overline{a}_{11}\), facem interschimbarea \(\bm{L_1}(\overline{A})\leftrightarrow\bm{L_3}(\overline{A})\):

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

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

    \[\begin{cases} \bm{L_2}(\overline{A})\rightarrow \bm{L_2}(\overline{A})-\frac{1}{4}\bm{L_1}(\overline{A})\\ \bm{L_3}(\overline{A})\rightarrow \bm{L_3}(\overline{A})-\frac{1}{2}\bm{L_1}(\overline{A}) \end{cases}\Rightarrow \overline{A}=\begin{bmatrix} 4 & -7 & 1 & | & 1\\ 0 & -0.25 & 0.75 & | & -0.25\\ 0 & 4.5 & -3.5 & | & 4.5 \end{bmatrix} \]

  • Pasul 2a. Deoarece \(|\overline{a}_{32}|\geq|\overline{a}_{22}|\), facem interschimbarea \(\bm{L_2}(\overline{A})\leftrightarrow\bm{L_3}(\overline{A})\):

    \[ \overline{A}=\begin{bmatrix} 4 & -7 & 1 & | & 1\\ 0 & -0.25 & 0.75 & | & -0.25\\ 0 & 4.5 & -3.5 & | & 4.5 \end{bmatrix}\Rightarrow \overline{A}=\begin{bmatrix} 4 & -7 & 1 & | & 1\\ 0 & 4.5 & -3.5 & | & 4.5 \\ 0 & -0.25 & 0.75 & | & -0.25 \end{bmatrix} \]

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

    \[\bm{L_3}(\overline{A})\rightarrow \bm{L_3}(\overline{A})+\frac{1}{18}\bm{L_2}(\overline{A}) \Rightarrow \overline{A}=\begin{bmatrix} 4 & -7 & 1 & | & 1\\ 0 & 4.5 & -3.5 & | & 4.5 \\ 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#

Implementarea algoritmului GPP se va face în 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] = GPP(A, b)
    [m, n] = size(A);
    Ae = [A, b];
    for p = [1 : n-1]
        % Partea noua (GPP):
        [piv, l_piv] = max(abs(Ae(p:n, p)));
        l_piv = l_piv + p - 1;
        temp = Ae(l_piv, :);
        Ae(l_piv,:) = Ae(p, :);
        Ae(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

Analiza complexității#

Noua operație introdusă pentru fiecare pas \(i\in\overline{1,\mu}\), \(\mu=\min\{n-1,m\}\), poate fi spartă la rândul său în două operații mai mici: găsirea valorii lui \(k\) și interschimbarea liniilor.

Pentru a găsi valoarea lui \(k\in\overline{i,n}\), fiecare element \(A_{j,i}\) trebuie verificat, \(j\in\overline{i,n}\), așadar se execută \((n-i+1)\) operații pentru fiecare pas \(i\). Pe de altă parte, interschimbarea poate fi realizată în timp constant utilizând o structură de date suplimentară (un vector de mapare, de exemplu).

Notând cu \(PP'(n,m)\) costul suplimentar ce provine din utilizarea unui pivot, deducem:

\[ PP'(n,m)=\sum_{i=1}^\mu\left[(n-i+1)+1\right]=O(n\mu) \]

În acest context, complexitatea finală, \(PP(n,m)\), poate fi calculată adăugând \(PP'(n,m)\) la costul \(GE(n,m)\) calculat anterior, ceea ce înseamnă că \(PP(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