Métodos Directos para a Resolução de Sistemas


Método de Eliminação de Gauss

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

O objectivo do método consiste em eliminar os elementos aij de forma a obter um sistema equivalente com uma matriz triangular superior. Tendo uma matriz triangular, basta aplicar 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)
mik = a(k)ik / a(k)kk
i = k+1,... ,n 
a(k+1)ij = a(k)ij - mik a(k)kj
i, j = k+1, ..., n 
b(k+1)i = b(k)i - mik b(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 obtemos

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 de b(n)

Em cada Passo k :

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 ( n - k )2 = n (n - 1) (2 n - 1) / 6 .

Obtemos a seguinte tabela :

Somas + Subtracções  Multipl. + Divisões 
Factorização 
n ( n - 1) ( 2 n -1) / 6 
n ( n2 - 1) / 3 
Cálculo de b(n)
n ( n - 1 ) / 2 
n ( n - 1 ) / 2 
Substituição 
n ( n + 1 ) / 2 
n ( n - 1 ) / 2 
TOTAL
~ n3 / 3 
~ n3 / 3 

é fácil ver que a sucessão do número total de operações, ao considerarmos uma dimensão da matriz elevada, é assimptoticamente equivalente a 2 n3 / 3. Normalmente, como tempo de cálculo é muito superior numa multiplicação ou divisão, considera-se apenas que
assimptoticamente o método de eliminação de Gauss envolve n3 / 3 operações (*, / ).

Este valor é bastante reduzido se comparado com o número de operações que seria necessário efectuar se resolvessemos o sistema pela Regra de Cramer (nesse caso teriamos ~ (n+1) ! operações, o que por exemplo, para n = 10 corresponderia a efectuar ~ 40 000 000 de operações ( * , / ) ao invés de ~ 430 pelo Método de Gauss ).



Pesquisa de Pivot

Tal como quando o pivot é nulo ( isto é a(k)kk=0 ) devemos efectuar uma troca de linhas, se o seu valor fôr próximo de zero, se não for efectuada uma troca de linhas ou colunas, os erros de arredondamento (surgidos na factorização da matriz) podem provocar grandes erros nos resultados. De forma equivalente, deve efectuar-se troca de linhas ou colunas, quando houver um grande desiquilibrio de grandezas nos elementos da matriz, se o pivot for pequeno face aos restantes elementos (porque, dividindo, será equivalente a que ele seja próximo de zero).

Para contornar este problema de estabilidade numérica, usam-se as seguintes estratégias:

PESQUISA PARCIAL DE PIVOT : (normalmente por linhas)
Em cada passo k da eliminação de Gauss, troca-se a linha k com a linha r, onde r é tal que :

|a(k)r k| = max { i = k ,..., n } | a(k)ik |

(apenas no caso de k ¹ r ).

PESQUISA TOTAL DE PIVOT :
Em cada passo k da eliminação de Gauss, troca-se a linha k com a linha r e a coluna k com a coluna s , onde r, s são tais que :

|a(k)r s| = max { i, j = k ,..., n } | a(k) i j |

(apenas no caso de k ¹ r ou k ¹ s ).


Métodos de Factorização

Vimos que, usando o método de eliminação de Gauss, no caso de não haver troca de linhas, podemos obter uma factorização da matriz A na forma A = L U , onde U seria a matriz triangular superior obtida no final da factorização e L a matriz triangular inferior com diagonal unitária, cujos elementos seriam os multiplicadores mik.
Vamos agora ver uma maneira alternativa de obter essa mesma factorização através do Método de Doolittle.
(Notamos que há um outro processo semelhante, denominado método de Crout, em que a factorização A = L U é feita de forma a que seja a matriz U a ter diagonal unitária).



Método de Doolittle

Pretendemos obter as matrizes L e U tais que A = L U

Logo, efectuando o produto, podemos obter as fórmulas correspondentes ao método de Doolittle:

PASSO 1 :

u1 j = a1 j
( j = 1, ..., n )
l i 1 = a i 1 / u11
( i = 2, ..., n )

PASSO k :

uk j = ak j lk r ur j
( j = k , ..., n )
l i k = ( a i k li r ur k) / uk k
( i = k+1 , ..., n )

Para factorizar a matriz, usando o método de Doolittle são necessárias o mesmo número de operações que no método de eliminação de Gauss. Há, no entanto, vantagens apreciáveis no que diz respeito ao armazenamento dos elementos da matriz, já que estes não são sucessivamente alterados, como acontecia no caso do método de Gauss.
(Para este método também se pode utilizar uma pesquisa de pivot (por colunas) antes de se efectuar a divisão correpondente ao cálculo dos elementos de L).


Vamos agora ver alguns métodos particulares para certo tipos de matrizes, em que podemos reduzir o números de operações. Começamos pelas matrizes simétricas e depois vamos ver o caso das matrizes tridiagonais.


Método de Cholesky

Este método é semelhante ao método de Doolittle e é aplicado a matrizes simétricas ( A = AT), com o objectivo de obter a factorização A = L LT, em que L é uma matriz triangular inferior.

Querendo manter a factorização nos números reais, o método só pode ser aplicado a matrizes definidas positivas. Com efeito, basta reparar que no caso mais simples possível, com matrizes 1x1, ou seja números reais, isto corresponderia a encontrar l tal que a = l2, o que implicaria encontrar a raiz de a. Para que a raiz de a seja um número real, é necessário que a não seja negativo, e de  forma semelhante, para evitar que L tenha valores complexos, exigimos que A seja definida positiva.
 

Relembramos que uma matriz é definida positiva
se xTA x > 0 , para todo o x ¹0.
Dois critérios equivalentes, para verificar que uma matriz é definida positiva:
i) se os seus valores próprios forem positivos
ou,
ii) se os menores principais forem positivos.

 

 

Note-se que, verificar que a matriz é definida positiva, calculando os valores próprios ou os menores principais, poderia ser mais moroso do que resolver o sistema... Normalmente, é provado teoricamente que certas matrizes são definidas positivas, não havendo necessidade de efectuar quaisquer cálculos.

Teorema: Se a matriz A for simétrica e definida positiva é válida a factorização: A = L LT, em que L é uma matriz triangular inferior.

O método de Cholesky para encontrar L consiste nos seguintes passos:

PASSO 1:

PASSO k:

Neste caso, o número de operações é :

~ n3 / 6  Somas + Subtracções
~ n3 / 6  Multiplicações + Divisões 
Raízes Quadradas 

Ou seja, metade do exigido pelo método de Gauss, havendo apenas ~ n3 / 6 operações (*, / ).


Factorização de Matrizes Tridiagonais

Este é o caso de matrizes em que, à excepção das três diagonais principais, todos os outros elementos são nulos.
Ou seja:

aij = 0, se | i - j | > 1

Estas matrizes aparecem em muitos problemas práticos (por exemplo, no caso dos splines, ou na resolução de equações diferenciais...) . Devido à sua estrutura simples, o número de operações necessário para resolver um sistema, pode ser consideravelmente reduzido, já que podemos escrever A = L U; onde L será uma matriz triangular inferior, bidiagonal, com diagonal unitária, e U uma matriz triangular superior, bidiagonal.

O método de factorização de Doolittle reduz-se então a:

Passo 1:
l11 = 1
l21 = a21
u11 = a11 
u12 = a12
Passo k
(k = 2, ..., n)
lkk=1
ukk = akk - lk, k-1 uk-1,k
lk+1, k = ak+1, k / ukk
uk, k+1 = ak, k+1

Podemos contabilizar o número de operações efectuado na factorização e na resolução dos sistemas triangulares (neste caso, a substituição ainda será mais simples):

Somas + Subtracções  Multipl. + Divisões 
Factorização 
n - 1 
2n - 2 
Resolver Lg = b
n - 1 
n - 1 
Resolver Ux = g
n - 1 
2 n - 1
TOTAL
3 n -3 
5 n - 4 

Correspondendo a um total de ~5n operações (*, / ).