Eliminação

Consideremos o sistema Ax=b em que A é uma matriz quadrada n x n.

Objectivo do Método: Eliminar os elementos aij de forma a obter um sistema equivalente com uma matriz triangular superior. Depois bastará usar substituições sucessivas para chegarmos à solução pretendida.

O método consiste em n-1 passos, onde construimos elementos a(k+1)ij a partir dos elementos a(k)ij considerando como [a(1)ij] a matriz inicial.

PASSO k

(para k=1,... n-1)
Se o pivot a(k)kk=0 então há que efectuar troca de linhas.
Se a(k)kk=/= 0 calculamos mik=a(k)ik / a(k)kk i = k+1,... ,n a(k+1)ij=a(k)ij - mika(k)kj i, j = k+1, ..., n b(k+1)i=b(k)i - mikb(k)k i = k+1, ..., n
No final dos n-1 passos obtemos o sistema triangular superior equivalente:

que se pode resolver facilmente por substituição ascendente: Armazenando os coeficientes mik podemos obter uma factorização da matriz A na forma:

caso não sejam efectuadas trocas de linhas.
Caso existam trocas de linhas, a factorização é da forma P A = L U em que P é uma matriz de permutação. Ao resolver o sistema obteriamos
L U x = P b
Teorema :
A factorização A = L U em que

L é uma matriz triangular inferior com diagonal principal unitária
U é uma matriz triangular superior é obtida de forma única se os pivots verificarem a(k)kk =/= 0.

Número de Operações

Analisemos agora qual o número de operações ( + - ou * / ) envolvido na resolução de um sistema:
FACTORIZAÇÃO da MATRIZ

Em cada Passo k :

Cálculo dos mik n-k divisões --- correspondentes a um total de ( n - k ) operações.
Cálculo dos aij
( n - k )2 multiplicações e subtracções--- correspondentes a um total de ( n - k )2 operações.
CÁLCULO de b(n)

Em cada Passo k :

n - k multiplicações e subtracções correspondentes a um total de ( n - k ) operações.
SUBSTITUIÇÃO

No total teremos : n + k = n (n + 1) / 2 multiplicações e divisões k = n(n - 1) / 2 subtracções

Como ( n - k ) = n (n - 1) / 2 e também