Considere o seguinte sistema de equações lineares
\left\{\begin{aligned} 4 x_{1}+3 x_{2} & =24 \\\\ 3 x_{1}+4 x_{2}-x_{3} & =30 \\\\ -x_{2}+4 x_{3} & =-24 \end{aligned}\right.
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).
Sistema linear:
\left\{\begin{aligned} 4 x_{1}+3 x_{2} & =24,\\\\ 3 x_{1}+4 x_{2}-x_{3} & =30,\\\\ - x_{2}+4 x_{3} & =-24, \end{aligned}\right.
Solução conhecida (fornecida): \,(3,4,-5).
O enunciado pede:
  • (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.
Informações relevantes extraídas do enunciado:
  • Matriz dos coeficientes A (lida das equações):
A=\begin{pmatrix} 4 & 3 & 0\\[4pt] 3 & 4 & -1\\[4pt] 0 & -1 & 4 \end{pmatrix},
vetor termo independente b=(24,30,-24)^T.
  • Solução exata (fornecida) \;x^\star=(3,4,-5)^T.
  • Métodos a comparar: Jacobi, Gauss–Seidel (GS) e SOR com \omega=1{,}25 e mais um \omega à escolha.]

Passo 2

O método de Gauss–Jacobi e de Gauss–Seidel — fórmula, iteração e critério de convergência (aula curta e didática).
  1. Decomposição padrão. Para qualquer sistema A x = b escrevemos
A=D+L+U,
onde:
  • D é a matriz diagonal com os elementos diagonais de A;
  • L é a parte estritamente inferior (elementos abaixo da diagonal);
  • U é a parte estritamente superior (elementos acima da diagonal).
Para o nosso A (mostrando D,L,U):
D=\begin{pmatrix}4&0&0\\[2pt]0&4&0\\[2pt]0&0&4\end{pmatrix},\quad L=\begin{pmatrix}0&0&0\\[2pt]3&0&0\\[2pt]0&-1&0\end{pmatrix},\quad U=\begin{pmatrix}0&3&0\\[2pt]0&0&-1\\[2pt]0&0&0\end{pmatrix}.
  1. Iteração de Jacobi. A fórmula iterativa (com x^{(k)} sendo a aproximação na iteração k) é
x^{(k+1)} = -D^{-1}(L+U)\,x^{(k)} + D^{-1} b.
Define-se a matriz de iteração de Jacobi
B_J = -D^{-1}(L+U).
O método converge para qualquer x^{(0)} se e só se \rho(B_J)<1, onde \rho(\cdot) é o raio espectral (maior valor absoluto das auto‑valores).
  1. Iteração de Gauss–Seidel. A fórmula é
x^{(k+1)} = -(D+L)^{-1} U\, x^{(k)} + (D+L)^{-1} b,
com matriz de iteração
B_{GS}=-(D+L)^{-1} U.
Novamente, converge para qualquer x^{(0)} se \rho(B_{GS})<1.
  1. Método SOR (Sucessive Over-Relaxation). Para um parâmetro \omega (relaxation factor), a iteração SOR é
x^{(k+1)} = (D+\omega L)^{-1}\big[(1-\omega)D - \omega U\big] x^{(k)} + (D+\omega L)^{-1} \omega b,
com matriz de iteração
B_{SOR}(\omega)=(D+\omega L)^{-1}\big[(1-\omega)D - \omega U\big].
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.
  1. 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).
  1. Matriz de iteração de Jacobi. Usando D=4I,
B_J = -D^{-1}(L+U) = -\frac{1}{4}\begin{pmatrix}0 & 3 & 0\\[2pt]3 & 0 & -1\\[2pt]0 & -1 & 0\end{pmatrix} = \begin{pmatrix} 0 & -\tfrac{3}{4} & 0\\[4pt] -\tfrac{3}{4} & 0 & \tfrac{1}{4}\\[4pt] 0 & \tfrac{1}{4} & 0 \end{pmatrix}.
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
-\lambda\big(\lambda^2-\tfrac{5}{8}\big)=0,
logo os autovalores são
\lambda=0,\qquad \lambda=\pm\sqrt{\tfrac{5}{8}}=\pm\sqrt{0,625}\approx\pm0{,}7905694.
Portanto
\rho(B_J)=\sqrt{\tfrac{5}{8}}\approx 0{,}79057<1,
ou seja: o método de Jacobi converge para este sistema.
  1. Matriz de iteração de Gauss–Seidel. Calculamos B_{GS}=-(D+L)^{-1}U. Passo a passo (resolver triangular inferior e multiplicar) dá
B_{GS}=\begin{pmatrix} 0 & -\tfrac{3}{4} & 0\\[4pt] 0 & \tfrac{9}{16} & \tfrac{1}{4}\\[4pt] 0 & \tfrac{9}{64} & \tfrac{1}{16} \end{pmatrix}.
(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 dado
import 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]

def gauss_seidel(A, b, x0, niter):
    x = x0[:]
    history = [x0[:]]
    for k in range(1, niter+1):
        for i in range(3):
            s1 = sum(A[i][j]*x[j] for j in range(i))             # usando x^{(k+1)} já atualizado
            s2 = sum(A[i][j]* (x0[j] if j>i else 0.0) for j in range(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 in range(3) if j!=i)
            xi = (b[i] - s_right) / A[i][i]
            x[i] = xi
        history.append(x[:])
    return history

def sor(A, b, x0, omega, niter):
    x = x0[:]
    history = [x0[:]]
    for k in range(1, niter+1):
        for i in range(3):
            s1 = sum(A[i][j]*x[j] for j in range(i))   # já atualizados
            s2 = sum(A[i][j]*x[j] for j in range(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ções
print("k |   GS x1      x2         x3    ||   SOR(1.25) x1      x2         x3    ||   SOR(1.5) x1      x2         x3")
for k in range(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 velocidade
def inf_norm_error_hist(history, x_exact):
    return [max(abs(history[k][i]-x_exact[i]) for i in range(3)) for k in range(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 in range(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á.
  1. 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).
  1. 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.
  1. 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).

Exercícios relacionados