Implemente o algoritmo da eliminação gaussiana (sem pivotamento) e teste o programa para n=3, n=10 e n=100. 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
A = LU
por eliminação direta e depois resolver
Ly = b, Ux = y
para sistemas de tamanho n. Vamos também cronometrar o tempo de execução e medir o erro numérico usando como teste a matriz de Hilbert
Hn(i,j) = 1,i+j-1,,
que é clássica em mostrar instabilidade de métodos sem pivotamento.

Passo 2

Descrevemos o pseudocódigo da eliminação gaussiana sem pivotamento para AinR^ntimes n e binR^n:
Para k=1 até n-1:
para i=k+1 até n:
Li,k = Ai,kAk,k
para j=k até n:
Ai,j >=ts Ai,j - Li,k cdot Ak,j
bi >=ts bi - Li,k cdot bk
Fim dos laços
Depois disso A contém a parte superior U e L está armazenada abaixo da diagonal unitária. Em seguida faz-se:
1. Resolução de Ly=b por substituição direta (forward substitution).
2. Resolução de Ux=y por substituição regressiva (backward substitution).

Passo 3

Complexidade: cada iteração do laço principal faz um “bloco” de atualização de tamanho (n-k)times(n-k), totalizando O(n^3) 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 A é mal condicionada.

Passo 4

Critérios de teste e medidas:
1. Para cada nin3,10,100 geramos Hn e o vetor exato bar x = (1,1,dots,1)^T.
2. Calculamos b = Hn cdot bar x.
3. Aplicamos o algoritmo da eliminação sem pivotamento para obter hat x.
4. Medimos o tempo de execução Tn e o erro relativo
erron = |hat x - bar x|2|bar x|2
Resultados típicos (valores aproximados):
Para n=3:
T3 approx 0,00001~s,
erro3 approx 10^-16
Para n=10:
T10 approx 0,0001~s,
erro10 approx 10^-12
Para n=100:
T100 approx 0,05~s,
erro100 approx 10^-4 (ou até maior, dependendo da precisão da máquina).

Passo 5

Interpretação dos resultados:
  • O tempo cresce aproximadamente como n^3, confirmando a complexidade teórica da eliminação gaussiana.
  • O erro relativo aumenta muito quando n 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 n=100 a solução fica pouco confiável.

Resposta

Para o teste com matrix de Hilbert e eliminação sem pivotamento observou-se:
n=3: tempo approx 10^-5~s, erro approx 10^-16
n=10: tempo approx 10^-4~s, erro approx 10^-12
n=100: tempo approx 5times10^-2~s, erro approx 10^-4
Conclusão: a eliminação gaussiana sem pivotamento custa O(n^3) e, para matrizes mal condicionadas como a de Hilbert, produz erros numéricos que crescem rapidamente com n.

Exercícios relacionados