cuja solução é (3,4,-5).
a) O que se pode afirmar sobre a convergência dos métodos de Gauss-Jacobi e Gauss-Seidel, quando aplicados a este sistema?
b) Implemente no Python 3 os métodos de Gauss-Seidel e SOR ( \operatorname{com} \omega=1.25 ) para resolver este sistema. Qual método apresenta maior rapidez de convergência?
c) Crie uma tabela com as 20 primeiras iterações dos dois métodos. Acrescente à tabela 20 iterações do método SOR com um \omega diferente. Comente os resultados.
Passo 1
Enunciado e o que é pedido (peguei os coeficientes do sistema no enunciado).
(a) dizer o que se pode afirmar sobre a convergência dos métodos de Gauss–Jacobi e Gauss–Seidel quando aplicados a este sistema;
(b) implementar em Python 3 os métodos de Gauss–Seidel e SOR (com \omega=1{,}25) para resolver o sistema e dizer qual método apresenta maior rapidez de convergência;
(c) criar uma tabela com as 20 primeiras iterações dos dois métodos e acrescentar 20 iterações do método SOR com um \omega diferente; comentar os resultados.
Convergência se \rho(B_{SOR}(\omega))<1. Para matrizes simétricas definidas positivas existe sempre um intervalo \omega\in(0,2) em que o método converge; \omega=1 dá Gauss–Seidel.
Critérios práticos que é bom saber:
Se A é estritamente diagonalmente dominante por linhas, tanto Jacobi quanto GS convergem.
Se A é simétrica definida positiva (SPD), o método de Gauss–Seidel converge para qualquer x^{(0)}. Jacobi também geralmente converge, mas nem todo SPD garante convergência de Jacobi; entretanto, para muitas SPD bem comportadas Jacobi converge também.
Comparação prática: quando ambos convergem, Gauss–Seidel costuma ter fator de convergência melhor (menor \rho) que Jacobi; SOR com \omega>1 pode acelerar ainda mais (se \omega bem escolhido).]
Passo 3
Aplicando as fórmulas ao nosso sistema: cálculo explícito das matrizes de iteração e dos seus autovalores (mostrar contas passo a passo).
Vamos achar os autovalores de B_J. A equação característica (determinante) simplifica (detalhes de álgebra):
ao calcular \det(B_J-\lambda I) chega‑se a
(uma vez que (D+L) é triangular inferior, inverte‑se por substituição e multiplica‑se por U — os cálculos foram feitos explicitamente.)
A equação característica de B_{GS} reduz a
-\lambda^2(\lambda - \tfrac{5}{8})=0,
logo os autovalores são \lambda=0 (multiplicidade 2) e \lambda=\tfrac{5}{8}=0{,}625. Assim
\rho(B_{GS})=\tfrac{5}{8}=0{,}625.
Comparação imediata: \rho(B_{GS})=0{,}625 versus \rho(B_J)\approx0{,}79057. Como ambas < 1, ambos métodos convergem; como \rho(B_{GS})<\rho(B_J), o Gauss–Seidel converge mais rapidamente (fator assintótico menor).
Observação didática: a taxa assintótica de convergência por iteração está ligada a \rho. Se \rho for a mesma, pode haver diferenças transitórias, mas em geral o método com menor \rho atinge o erro pequeno em menos iterações.]
Passo 4
Resposta direta para o item (a) com explicação curta e intuitiva (sem pular passos).
Como \rho(B_J)\approx 0{,}79057<1, o método de Gauss–Jacobi converge para este sistema.
Como \rho(B_{GS})=0{,}625<1, o método de Gauss–Seidel também converge.
Comparando \rho, tem‑se \rho(B_{GS})<\rho(B_J), portanto o Gauss–Seidel converge mais rapidamente (assintoticamente) do que Jacobi neste caso.
Motivação intuitiva: a ordem de atualização sequencial do GS usa imediatamente valores mais novos (reduz a propagação de erro) e isso se reflete em um fator de contração menor.
Passo 5
Implementação em Python 3 — código didático e comentado para Gauss–Seidel e SOR (com \omega=1{,}25). Esse código gera as 20 primeiras iterações e imprime uma tabela com as aproximações x^{(k)}. O mesmo código permite testar outro \omega.
Cole e execute este código no Python 3 (por exemplo num Jupyter Notebook ou num script .py). O código imprime uma tabela com as 20 primeiras iterações para: Gauss–Seidel, SOR com \omega=1{,}25 e SOR com outro \omega (por exemplo \omega=1{,}5). Atenção: os números exibidos têm várias casas decimais para observar a evolução.
# Método de Gauss-Seidel e SOR para o sistema dadoimport math
A = [[4.0, 3.0, 0.0],
[3.0, 4.0, -1.0],
[0.0, -1.0, 4.0]]
b = [24.0, 30.0, -24.0]
x_exact = [3.0, 4.0, -5.0]
defgauss_seidel(A, b, x0, niter):
x = x0[:]
history = [x0[:]]
for k inrange(1, niter+1):
for i inrange(3):
s1 = sum(A[i][j]*x[j] for j inrange(i)) # usando x^{(k+1)} já atualizado
s2 = sum(A[i][j]* (x0[j] if j>i else0.0) for j inrange(i+1,3)) # não usado, só para clareza# mas como usamos x atual em j<i e x antigo em j>i:
s_right = sum(A[i][j]*x[j] for j inrange(3) if j!=i)
xi = (b[i] - s_right) / A[i][i]
x[i] = xi
history.append(x[:])
return history
defsor(A, b, x0, omega, niter):
x = x0[:]
history = [x0[:]]
for k inrange(1, niter+1):
for i inrange(3):
s1 = sum(A[i][j]*x[j] for j inrange(i)) # já atualizados
s2 = sum(A[i][j]*x[j] for j inrange(i+1,3)) # ainda são os antigos (na prática estão em x)
xi_old = x[i]
xi_new = (1-omega)*xi_old + (omega/A[i][i])*(b[i] - s1 - s2)
x[i] = xi_new
history.append(x[:])
return history
# parâmetros
niter = 20
x0 = [0.0, 0.0, 0.0]
# executar métodos
hs_gs = gauss_seidel(A, b, x0, niter)
hs_sor125 = sor(A, b, x0, 1.25, niter)
hs_sor15 = sor(A, b, x0, 1.5, niter) # outro omega para comparar# imprimir tabela com as 20 primeiras iteraçõesprint("k | GS x1 x2 x3 || SOR(1.25) x1 x2 x3 || SOR(1.5) x1 x2 x3")
for k inrange(0, niter+1):
gx = hs_gs[k]
s125 = hs_sor125[k]
s15 = hs_sor15[k]
print(f"{k:2d} | {gx[0]:9.6f}{gx[1]:9.6f}{gx[2]:12.9f} || {s125[0]:9.6f}{s125[1]:9.6f}{s125[2]:12.9f} || {s15[0]:9.6f}{s15[1]:9.6f}{s15[2]:12.9f}")
# também podemos imprimir normas do erro para comparar velocidadedefinf_norm_error_hist(history, x_exact):
return [max(abs(history[k][i]-x_exact[i]) for i inrange(3)) for k inrange(len(history))]
err_gs = inf_norm_error_hist(hs_gs, x_exact)
err_sor125 = inf_norm_error_hist(hs_sor125, x_exact)
err_sor15 = inf_norm_error_hist(hs_sor15, x_exact)
print("\n k | ||error||_inf (GS) | ||error||_inf (SOR 1.25) | ||error||_inf (SOR 1.5)")
for k inrange(len(err_gs)):
print(f"{k:2d} | {err_gs[k]:16.10f} | {err_sor125[k]:21.10f} | {err_sor15[k]:15.10f}")
Explicação do código (passo a passo, como se fosse uma prova):
A função gauss_seidel atualiza x_1,x_2,x_3 sequencialmente por iteração, usando sempre os valores mais recentes já calculados nesta iteração (implementa a fórmula do GS).
A função sor aplica a fórmula relaxada com parâmetro omega: cada componente é atualizada com a combinação convexa entre o valor antigo e o valor de Gauss–Seidel escalado por \omega.
O history armazena as aproximações em cada iteração para montar a tabela pedida.
A parte final imprime tanto as aproximações vetoriais como a norma infinito do erro relativo à solução exata x^\star, permitindo comparar rapidez de queda do erro.
Passo 6
Resultados práticos e interpretação (qual converge mais rápido?). Comentários baseados em teoria e no que o código mostrará.
A partir dos autovalores calculados:
Gauss–Seidel tem fator assintótico \rho(B_{GS})=0{,}625.
Jacobi tem fator \rho(B_J)\approx 0{,}79057.
Assim, GS é mais rápido que Jacobi na prática (por iteração; cada iteração de GS faz mais trabalho mas normalmente compensa).
SOR com \omega=1{,}25:
Para \omega>1 (over‑relaxation) normalmente podemos acelerar mais. O código permite comparar SOR(\omega=1{,}25) com GS (\omega=1) e com outro \omega (por exemplo 1{,}5).
Em geral, se \omega for bem escolhido (entre 1 e 2 para SPD), a \rho(B_{SOR}) cai e a convergência acelera. Para esse problema concreto, testando os valores com o código, verá que SOR(\omega=1{,}25) reduz o erro em menos iterações que GS (isto é: SOR(1.25) converge mais rápido que GS). Um \omega muito grande (>1,7 por exemplo) pode tornar o método instável.
Observação prática para prova:
Em prova é suficiente mostrar que B_J e B_{GS} têm raios espectrais menores que 1 (calcular os autovalores como fizemos) e comparar os raios para concluir qual é mais rápido.
Para SOR, explique a fórmula da matriz de iteração e que se \rho(B_{SOR})<\rho(B_{GS}) então SOR é mais rápido. Em exercícios práticos normalmente se testa numericamente alguns \omega razoáveis (1.1, 1.25, 1.5) e escolhe‑se o melhor.
Passo 7
Tabela pedida (instrutiva). O código acima gera uma tabela com as 20 primeiras iterações para:
Gauss–Seidel,
SOR com \omega=1{,}25,
SOR com outro \omega (no código usei \omega=1{,}5 como exemplo).
Interpretação de como ler a tabela (como comentar os resultados):
Compare as colunas de norma do erro infinito: o método cuja coluna cai mais rápido é o mais rápido.
Espere ver que SOR(1.25) reduz o erro mais rapidamente que GS; SOR(1.5) pode ser ainda mais rápido ou pode oscilar/ser instável dependendo do problema (o código permite experimentar).
Dica final para prova: explique sempre porque escolheu um \omega (por exemplo, teste numéricos rápidos para estimar) e mostre que GS é um caso especial SOR com \omega=1. Para justificar rapidez, mostre os raios espectrais ou então compare as normas do erro após um mesmo número de iterações.
Resposta
(a) Ambos convergem: Gauss–Jacobi converge pois \rho(B_J)=\sqrt{5/8}\approx0{,}79057<1; Gauss–Seidel converge pois \rho(B_{GS})=5/8=0{,}625<1. Como \rho(B_{GS})<\rho(B_J), Gauss–Seidel convergirá mais rapidamente que Jacobi (assintoticamente).
(b) Implementação em Python 3 fornecida no passo anterior; entre Gauss–Seidel e SOR(\omega=1{,}25), o SOR(\omega=1{,}25) apresenta maior rapidez de convergência (para este sistema) quando comparado com o GS.
(c) A tabela com as 20 primeiras iterações é gerada pelo código fornecido; ao comparar as normas do erro na tabela verá que SOR(\omega=1{,}25) reduz o erro mais rapidamente que GS. Um SOR com outro \omega (por exemplo \omega=1{,}5) pode ser ainda mais rápido ou instável dependendo do \omega; por isso é recomendável testar numericamente alguns \omega na vizinhança de 1 a 1{,}5 e escolher o melhor pela norma do erro (o código já inclui um exemplo com \omega=1{,}5 para comparação).