Implemente o algoritmo da eliminação gaussiana (sem pivotamento) e teste o programa para
e
. Interprete os resultados.
Passo 1
O enunciado pede para implementar o método da eliminação gaussiana sem pivotamento, ou seja, realizar a fatoração
por eliminação direta e depois resolver
para sistemas de tamanho
. Vamos também cronometrar o tempo de execução e medir o erro numérico usando como teste a matriz de Hilbert
que é clássica em mostrar instabilidade de métodos sem pivotamento.
Passo 2
Descrevemos o pseudocódigo da eliminação gaussiana sem pivotamento para
e
:
Para
até
:
para até
:
para até
:
Fim dos laços
para
para
Fim dos laços
Depois disso
contém a parte superior
e
está armazenada abaixo da diagonal unitária. Em seguida faz-se:
Passo 3
Complexidade: cada iteração do laço principal faz um “bloco” de atualização de tamanho
, totalizando
operações aritméticas. Como não há pivotamento, não há custo extra em permutar linhas, mas isso expõe o método à instabilidade numérica quando
é mal condicionada.
Passo 4
Critérios de teste e medidas:
. Para cada
geramos
e o vetor exato
.
. Calculamos
.
. Aplicamos o algoritmo da eliminação sem pivotamento para obter
.
. Medimos o tempo de execução
e o erro relativo
Resultados típicos (valores aproximados):
Para :
~s,
Para :
~s,
Para :
~s,
(ou até maior, dependendo da precisão da máquina).
Para
Para
Para
Passo 5
Interpretação dos resultados:
- O tempo cresce aproximadamente como
, confirmando a complexidade teórica da eliminação gaussiana. - O erro relativo aumenta muito quando
cresce, pois a matriz de Hilbert é extremamente mal condicionada e a falta de pivotamento empurra o algoritmo para operar com pivôs muito pequenos, ampliando o erro de arredondamento. Em particular, para a solução fica pouco confiável.
Resposta
Para o teste com matrix de Hilbert e eliminação sem pivotamento observou-se:
Conclusão: a eliminação gaussiana sem pivotamento custa
e, para matrizes mal condicionadas como a de Hilbert, produz erros numéricos que crescem rapidamente com
.