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
mik = a(k)ik / a(k)kk |
|
a(k+1)ij = a(k)ij - mik a(k)kj |
|
b(k+1)i = b(k)i - mik b(k)k |
|
No final dos n-1 passos obtemos o sistema triangular superior equivalente:
Armazenando os coeficientes mik podemos obter uma factorização da matriz A na forma:
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
Teorema : A factorização A = L U em que
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 :
Em cada Passo k :
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 |
|
|
Cálculo de b(n) |
|
|
Substituição |
|
|
TOTAL |
|
|
é 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 ).
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).
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 |
|
l i 1 = a i 1 / u11 |
|
PASSO k :
uk j = ak j - lk r ur j |
|
l i k = ( a i k - li r ur k) / uk k |
|
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.
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 |
n | 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:
O método de factorização de Doolittle reduz-se então a:
Passo 1: |
|
Passo k
(k = 2, ..., n) |
|
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 |
|
|
Resolver Lg = b |
|
|
Resolver Ux = g |
|
|
TOTAL |
|
|
Correspondendo a um total de ~5n operações (*, / ).