Algoritmul GPT#

Nu acel GPT...

O altă cale pe care se poate îmbunătăți algoritmul GPP este folosind o altfel de pivotare - numim acest algoritm GPT, sau Eliminare Gaussiană cu Pivotare Totală.

Diferența între GPP și GPT este evidentă - în loc să se caute elementul de modul maxim aflat pe o anumită coloană, se va căuta elementul maxim din întreaga matrice rămasă.

Prin "întreaga matrice" se înțelege, la un pas \(i\in\overline{1,n-1}\), submatricea definită de colțurile \(\overline{a}_{ii}\) și \(\overline{a}_{nn}\), adică:

\[ \begin{bmatrix} \overline{a}_{ii}&\overline{a}_{i,i+1}&\dots&\overline{a}_{in}\\ \overline{a}_{i+1,i}&\overline{a}_{i+1,i+1}&\dots&\overline{a}_{i+1,n}\\ \vdots&\vdots&\ddots&\dots\\ \overline{a}_{ni}&\overline{a}_{n,i+1}&\dots&\overline{a}_{nn}\\ \end{bmatrix} \]

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}=\begin{bmatrix}\bm{\overline{a_1}}&\dots&\bm{\overline{a_{n+1}}}\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\in\overline{1,n-1}\) cu excepția ultimei, se vor alege mai întâi două valori, \(p,q\in\overline{i,n}\), astfel încât \(|\overline{a}_{p,q}|=\max_{j,k\in\overline{i,n}}\{\left|\overline{a}_{j,k}\right|\}\), iar apoi se vor interschimba liniile \(i\) și \(p\), respectiv coloanele \(i\) și \(q\).

Ordinea operațiilor

Ordinea operațiilor de interschimbare este pur întâmplătoare. Algoritmul nu va fi afectat dacă o schimbați, interschimbând întâi coloanele \(i\) și \(q\), apoi liniile \(i\) și \(p\).

Apoi, în matricea proaspăt formată, se va transforma fiecare element găsit pe a \(i\)-a coloană sub diagonala principală (sub elementul \(\overline{a}_{ii}\)), adică \(\overline{a}_{ji}\), \(\forall j\in\overline{i+1,n}\), astfel încât acesta să devină zero prin scăderea celei de-a \(i\)-a linie scalată cu \(\frac{\overline{a}_{ji}}{\overline{a}_{ii}}\) din a \(j\)-a linie.

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

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

    \[ \exists\,p,q\in\overline{i,n}: |\overline{a}_{pq}|=\max_{j,k\in\overline{i,n}}\{\left|\overline{a}_{jk}\right|\}\Rightarrow\boxed{\begin{cases}\bm{L_i}(\overline{A})\leftrightarrow\bm{L_p}(\overline{A})&\text{și}\\\bm{\overline{a_i}}\leftrightarrow\bm{\overline{a_q}} \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 alt sistem de ecuații liniare, descris direct în forma: \(\overline{A}=\begin{bmatrix} 1 & -2 & -3 & | & 0\\ 3 & 5 & 2 & | & 0\\ 2 & 3 & -1 & | & -1 \end{bmatrix}\).

  • Pasul 1a. Dintre toate valorile aflate în matricea coeficienților, cea mai mare în modul se deosebește a fi \(|a_{22}|=5\). Facem interschimbările între linia \(1\) și linia \(2\), \(\bm{L_1}(\overline{A})\leftrightarrow\bm{L_2}(\overline{A})\), iar apoi între coloana \(1\) și coloana \(2\), adică \(\bm{\overline{a_1}}\leftrightarrow\bm{\overline{a_2}}\):

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

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

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

  • Pasul 2a. Deoarece \(|\overline{a}_{22}|=2.2=\max\{2.2,2.2,0.2,2.2\}\), nu este necesară nicio interschimbare (în teorie, se interschimbă linia \(2\) cu linia \(2\), respectiv coloana \(2\) cu coloana \(2\), dar aceste modificări nu au niciun efect).

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

    \[ \bm{L_3}(\overline{A})\rightarrow \bm{L_3}(\overline{A})-\frac{1}{11}\bm{L_2}(\overline{A}) \Rightarrow \overline{A}=\begin{bmatrix} 5 & 3 & 2 & | & 0\\ 0 & 2.2 & -2.2 & | & 0\\ 0 & 0 & -2 & | & -1 \end{bmatrix} \]

Concluzie. Se rezolvă sistemul, de jos în sus, și se obține: \( \begin{cases} x_3'=0.5\\ x_2'=0.5\\ x_1'=-0.5 \end{cases}\). Aceste valori însă nu verifică sistemul inițial, deoarece am interschimbat la Pasul 1a liniile \(1\) și \(2\). Sistemul corect este dat de valorile: \(\begin{cases} x_1=x_2'=0.5\\ x_2=x_1'=-0.5\\ x_3=x_3'=0.5 \end{cases}\).

Cod ilustrativ#

Vom implementa acum algoritmul GPT, sub forma funcției GPT, acceptând 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] = GPT(A, b)
    [m, n] = size(A);
    Ae = [A, b];
    for p = [1 : n-1]
        % Partea noua (GPT):
        [piv, l_piv] = max(abs(Ae(p:n, p)));
        [piv, c_piv] = max(piv);
        l_piv = l_piv + p - 1;
        l_piv = l_piv(c_piv);
        c_piv = c_piv + p - 1;
        temp = Ae(l_piv, :);
        Ae(l_piv, :) = Ae(p, :);
        Ae(p, :) = temp;
        temp = Ae(:, c_piv);
        Ae(:, c_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#

Fie \(TP'(n,m)\) complexitatea introdusă suplimentar de acest algoritm, fără să luăm în calcul \(GE(n,m)\). Atunci, pentru fiecare pas \(i\in\overline{1,\mu}\), unde \(\mu=\min\{n-1,m\}\), matricea delimitată de colțurile \(\overline{a}_{ii}\) și \(\overline{a}_{nm}\) trebuie parcursă pentru a se descoperi cea mai mare valoare absolută, așadar:

\[\begin{split} TP'_i(n,m)&=(n-i+1)(m-i+1)\\ &=(mn+m+n+1)-(m+n + 2)i+i^2 \end{split}\]

Însumând toate aceste complexități, se poate construi valoarea lui \(TP'(n,m)\):

\[\begin{split} TP'(n,m)&=\sum_{i=1}^\mu TP'_i(n,m)\\ &= \sum_{i=1}^\mu(mn+m+n+1)-\sum_{i=1}^\mu(m+n+2)i+\sum_{i=1}^\mu i^2\\ &=(mn+m+n+1)\mu-(m+n+2)\frac{\mu(\mu+1)}{2}+\frac{\mu(\mu+1)(2\mu+3)}{6}\\ & \Rightarrow TP'(n,m)\in O(mn\mu) \end{split}\]

Complexitatea finală, \(TP(n, m)\), poate fi calculată prin adăugarea complexității \(GE(n,m)\) la \(TP'(n,m)\), ceea ce ar însemna că \(TP(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