Matrice.

Proceduri de triangularizare

Triangularizarea superioară a matricei A ∈ Rn×n se realizează ı̂ntr-un număr de etape ı̂n care se deter-
mină matricele A(1) = A, A(2) , . . . , A(n) de forma:
 (k) (k) (k) (k) (k) 
a11 a12 . . . a1k−1 a1k . . . a1n
 (k) 
 0 (k)
a22 . . .
(k)
a2k−1
(k)
a2k . . . a2n 
 
 . . . . . . . . . . . 
 
 . . . ak−1k−1 ak−1k . . . ak−1n   , 2 ≤ k ≤ n.
(k) (k) (k) (k)
A = 0 0
 
 0 0 . . . 0
(k)
akk . . . akn 
(k)
 
 . . . . . . . . . . . 
(k) (k)
0 0 . . . 0 ank . . . ann

Elementele matricei A(k+1) se calculează astfel:



 a
(k)
pentru 1 ≤ i ≤ k, i ≤ j ≤ n

 ij
(k+1)
aij = 0 pentru 1 ≤ j ≤ k, j + 1 ≤ i ≤ n (1)



(k) (k) (k) (k)
aij akk −aik akj
 a(k) (k)
ij − mik akj = (k) pentru k + 1 ≤ i, j ≤ n
akk

Aşadar, matricea A(k) se transformă ı̂n matricea A(k+1) după următoarele reguli:
R1 . Liniile 1, 2, ..., k şi coloanele 1, 2, ..., k − 1, (k > 1), nu se modifică.
R2 . Elementele subdiagonale din coloana k se anulează.
R3 . Elementele situate ı̂n liniile şi coloanele k + 1, k + 2, ..., n se transformă după regula dreptunghiului.
În Algoritmul 1 se realizează triangularizarea superioară a unei matrice A ∈ Rn×n folosind regulile
R1 − R3 . Calculele se fac ı̂n matricea A.
(k)
Să presupunem acum că ı̂n etapa k elementul akk = 0. În acest caz se folosesc aşa numitele proceduri
de pivotare parţială sau totală.
10 . Procedura de pivotare parţială.
(k)
Se caută ı̂n coloana k acel element aik k cu proprietatea:
(k) (k)
aik k = max aik .
k≤i≤n

În Algoritmul 2 se realizează triangularizarea superioară a unei matrice A ∈ Rn×n aplicând ı̂n fiecare
etapă procedura de pivotare parţială şi regulile R1 − R3 . Calculele se fac ı̂n matricea A.

20 . Procedura de pivotare totală.

(k)
În această procedură se determină elementul aik jk cu proprietatea:

(k) (k)
aik jk = max aij .
k≤i,j≤n

În Algoritmul 3 se realizează triangularizarea superioară a unei matrice A ∈ Rn×n aplicând ı̂n fiecare
etapă procedura de pivotare totală şi regulile R1 − R3 . Calculele se fac ı̂n matricea A.

1
Algoritmul 1 Procedură de triangularizare a unei matrice A (varianta 1).
Date de intrare:
- Matricea A = (aij )1≤i, j≤n .

Date de ieşire:

- Matricea superior triunghiulară obţinută ı̂n A

Pentru k = 1, 2, ..., n − 1 execută:
Dacă akk ̸= 0 atunci:
Pentru i = k + 1, k + 2, ..., n execută:
Pentru j = k + 1, k + 2, ..., n execută:
aik akj
aij = aij −
akk
Sfârşit Pentru
aik = 0
Sfârşit Pentru
altfel:
Matricea A nu poate fi triangularizată prin acest algoritm.
STOP
Sfârşit Dacă
Sfârşit Pentru

Algoritmul 2 Procedură de triangularizare a unei matrice A (varianta 2).

Date de intrare:
- Matricea A = (aij )1≤i, j≤n .

Date de ieşire:
- Matricea superior triunghiulară obţinută ı̂n A

Pentru k = 1, 2, ..., n − 1 execută:

|apk | = max |aik |
k≤i≤n
Dacă apk ̸= 0 atunci:
Dacă p ̸= k atunci:
Permută liniile p şi k
Sfârşit Dacă
Pentru i = k + 1, k + 2, ..., n execută:
Pentru j = k + 1, k + 2, ..., n execută:
aik akj
aij = aij −
akk
Sfârşit Pentru
aik = 0
Sfârşit Pentru
Sfârşit Dacă
Sfârşit Pentru

2
Algoritmul 3 Procedură de triangularizare a unei matrice A (varianta 3).
Date de intrare:

- Matricea A = (aij )1≤i, j≤n .

Date de ieşire:

- Matricea superior triunghiulară obţinută ı̂n A

Pentru k = 1, 2, ..., n − 1 execută:
|apq | = max |aij |
k≤i,j≤n
Dacă apq ̸= 0 atunci:
Dacă p ̸= k atunci:
Permută liniile p şi k
Sfârşit Dacă
Dacă q ̸= k atunci:
Permută coloanele q şi k
Sfârşit Dacă
Pentru i = k + 1, k + 2, ..., n execută:
Pentru j = k + 1, k + 2, ..., n execută:
aik akj
aij = aij −
akk
Sfârşit Pentru
aik = 0
Sfârşit Pentru
altfel:
Matricea A este superior triunghiulară
STOP
Sfârşit Dacă
Sfârşit Pentru

3
Exemplul 0.1 Să se triangularizeze matricea:
 
1 −1 2
A= 2 1 1 .
1 2 −3

Soluţii.
a) În cazul algoritmului obişnuit (metoda lui Gauss), fără pivotare parţială sau totală, se parcurg următoarele
etape:
Etapa 1.
(1)
A(1) = A, a11 = 1, m21 = 2, m31 = 1,
   
1 0 0 1 −1 2
M1 =  −2 1 0  , A(2) = M1 A(1) =  0 3 −3  .
−1 0 1 0 3 −5
Etapa 2.
(2)
a22 = 3, m32 = 1,
   
1 0 0 1 −1 2
M2 =  0 1 0  , A(3) = M2 A(2) =  0 3 −3  .
0 −1 1 0 0 −2
b) Pivotare parţială.
Etapa 1. Avem:
(1) (1)
A(1) = A, max ai1 = a21 .
1≤i≤3

Se permută ı̂n A(1) liniile 1, 2. Se obţine matricea:

   
2 1 1 0 1 0
P1 A(1) =  1 −1 2  , P1 =  1 0 0 .
1 2 −3 0 0 1
Se aplică regulile R1 − R3 matricei P1 A(1) . Rezultă:
   
2 1 1 1 0 0
 3 3   1 
   0 .
A(2) =  0 − 2 2  = M1 P1 A(1) , M1 =  − 2 1

 3 7   1 
0 − − 0 1
2 2 2
Etapa 2. Avem:
(2) (2)
max ai2 = a22 , P2 = I.
2≤i≤3

Nu sunt necesare permutări de linii. Se aplică regulile R1 − R3 matricei A(2) . Rezultă:

 
2 1 1  
 3 3  1 0 0
A(3) = 
 0 −2
 = M2 P2 A(2) = M2 A(2) , M2 =  0 1 0 .
2 
0 1 1
0 0 −2

c) Pivotare totală.
Etapa 1. Avem:
(1) (1)
A(1) = A, max aij = a33 .
1≤i,j≤3

4
Se permută ı̂n A(1) liniile 1, 3 şi coloanele 1, 3. Se obţine matricea:
   
−3 2 1 0 0 1
P1 A(1) S1 =  1 1 2  , P1 =  0 1 0  = S1 .
2 −1 1 1 0 0

Se aplică acum regulile R1 − R3 matricei P1 A(1) S1 . Rezultă:

   
−3 2 1 1 0 0
 5 7   1 
   0 .
A(2) =  0 3 3  = M1 P1 A(1) S1 , M1 =  3 1

 1 5   2 
0 0 1
3 3 3
Etapa 2. Avem:
(2) (2)
max aij = a23 .
2≤i,j≤3

Se permută ı̂n A(2) coloanele 2, 3. Se obţine matricea:

 
−3 1 2  
 7 5  1 0 0
 
P2 A(2) S2 =  0 3 3  , P2 = I, S2 =  0 0 1 .
 5 1  0 1 0
0
3 3
Se aplică acum regulile R1 − R3 matricei P2 A(2) S2 . Rezultă:
 
−3 1 2  
 7 5  1 0 0
 0   0 1 0 .
A =
(3)
3 3 
(2)
= M2 P2 A S2 , M2 =  
 6 
5
0 − 1
0 0 − 7
7