Explique os principais passos dos métodos de Gauss-Jacobi e Gauss-Seidel. Apresente a principal diferença entre estes métodos. Apresente os critérios de convergência de ambos os métodos e uma relação entre estes critérios.
Passo 1
O que o enunciado pede:
Explicar, passo a passo, os métodos de Gauss-Jacobi e Gauss-Seidel.
Apresentar a principal diferença entre os dois métodos.
Apresentar os critérios de convergência de ambos os métodos.
Apresentar uma relação (comportamental/teórica) entre esses critérios.
Informações relevantes dadas (implícitas no enunciado):
Trabalhamos com um sistema linear genérico \:Ax=b\: onde A é uma matriz quadrada n\times n, x é o vetor de incógnitas e b é o vetor de termos independentes.
Os métodos são iterações estacionárias que geram aproximações x^{(0)},x^{(1)},x^{(2)},\dots.
Queremos tanto a fórmula das iterações quanto condições que garantam que as iterações realmente se aproximem da solução.
Passo 2
Definição útil e decomposição da matriz (pré-aula curta):
Para qualquer matriz quadrada A=(a_{ij}) separamos A em três partes:A = D + L + Uonde:D=\text{matriz diagonal com }d_{ii}=a_{ii},\quad L=\text{matriz estritamente triangular inferior},\quad U=\text{matriz estritamente triangular superior}.Ou seja, L tem entradas a_{ij} só para j<i e zeros na diagonal; U tem entradas a_{ij} só para j>i.
Essa decomposição é essencial porque os métodos iterativos se escrevem a partir dela. Não se assuste: é só separar a diagonal do resto.
Passo 3
Gauss-Jacobi — ideia e fórmula (aula passo-a-passo):
Ideia intuitiva: em cada iteração calculamos todos os componentes novos x_i^{(k+1)} usando apenas os valores antigos x_j^{(k)}. Ou seja, não usamos atualizações parciais dentro da mesma iteração.
Derivação componente-a-componente: da equação linha i do sistema \sum_{j=1}^n a_{ij} x_j = b_i, isolamos x_i:a_{ii} x_i = b_i - \sum_{\substack{j=1\\\ j\neq i}}^n a_{ij} x_jAssim a fórmula iterativa do método de Jacobi éx_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{\substack{j=1\\\ j\neq i}}^n a_{ij} x_j^{(k)}\right),\quad i=1,\dots,n.
Em forma matricial (mais compacta) definimos a matriz de iteraçãoT_J = D^{-1}(- (L+U)) = I - D^{-1}A,e o esquema itera comox^{(k+1)} = T_J x^{(k)} + D^{-1} b.
Implementação prática (passos a seguir numa prova ou código):
Verifique que todos os a_{ii}\neq 0.
Escolha um chute inicial x^{(0)}.
Para cada iteração k, calcule cada x_i^{(k+1)} pela fórmula acima usando apenas os x_j^{(k)}.
Pare quando \|x^{(k+1)}-x^{(k)}\| ou \|b-Ax^{(k+1)}\| for menor que a tolerância desejada.
Observação pedagógica: o método é fácil de implementar porque cada componente da nova aproximação usa apenas valores da iteração anterior — isso facilita paralelização.
Passo 4
Gauss-Seidel — ideia e fórmula (aula passo-a-passo):
Ideia intuitiva: assim que computamos um novo componente x_i^{(k+1)}, já usamos esse valor atualizado para calcular x_{i+1}^{(k+1)}. Ou seja, dentro da mesma iteração usamos valores mais recentes à medida que eles são obtidos.
Derivação componente-a-componente: da mesma linha i,x_i^{(k+1)} = \frac{1}{a_{ii}}\Bigl(b_i - \sum_{j=1}^{i-1} a_{ij} x_j^{(k+1)} - \sum_{j=i+1}^{n} a_{ij} x_j^{(k)}\Bigr).Repare a diferença: somatório com j<i usa os x_j^{(k+1)} (já atualizados), enquanto o somatório com j>i usa os x_j^{(k)} (ainda antigos).
Em forma matricial, usando a mesma decomposição A=D+L+U, a matriz de iteração éT_{GS} = -(D+L)^{-1} Ue a iteração éx^{(k+1)} = T_{GS} x^{(k)} + (D+L)^{-1} b.
Implementação prática:
Garanta a_{ii}\neq 0 para todo i.
Escolha x^{(0)}.
Para cada iteração k, atualize sequencialmente i=1 até n pela fórmula componente do Gauss-Seidel.
Pare com critérios de diferença ou resíduo como no Jacobi.
Observação pedagógica: por usar imediatamente as atualizações, Gauss-Seidel costuma convergir mais rápido (menos iterações) do que Jacobi na prática.
Passo 5
Erro, matriz de iteração e condição necessária e suficiente de convergência (explanação didática):
Definimos o erro e^{(k)} = x^{(k)} - x, onde x é a solução exata de Ax=b.
Para um método linear iterativo escrito como x^{(k+1)} = T x^{(k)} + c, temos a relação de propagação do erro:e^{(k+1)} = T e^{(k)}.Iterando,e^{(k)} = T^k e^{(0)}.
Teorema chave (ferramenta que você precisa saber para a prova): a iteração converge para a solução para todo chute inicial x^{(0)} se, e somente se, a matriz de iteração T satisfaz\rho(T) < 1,onde \rho(T) é a razão espectral (spectral radius): \rho(T)=\max\{|\lambda|:\lambda\text{ é autovalor de }T\}é.
Intuição sobre \rho(T): se as potências T^k tendem a zero, então as componentes do erro vão a zero. A condição \rho(T)<1 é a condição teórica e necessária — na prática usamos normas para obter condições suficientes verificáveis.
Passo 6
Critério prático simples baseado em norma (ferramenta que cai muito em prova):
Para o método de Jacobi a matriz de iteração é T_J = D^{-1}(- (L+U)). Usando a norma infinito (norma das linhas):\|T_J\|_\infty = \max_{1\le i\le n} \frac{1}{|a_{ii}|} \sum_{\substack{j=1\\\ j\neq i}}^n |a_{ij}|.Se \|T_J\|_\infty < 1, então \rho(T_J) \le \|T_J\|_\infty < 1, logo Jacobi converge.
Isso gera um critério muito utilizado em exercícios: se a matriz A é estritamente diagonalmente dominante por linhas, ou seja,|a_{ii}| > \sum_{\substack{j=1\\\ j\neq i}}^n |a_{ij}|\quad\text{para todo }i,então Jacobi converge (porque \|T_J\|_\infty<1).
Mesma ideia para Gauss-Seidel: embora a expressão de T_{GS} seja mais complexa, a diagonal dominante estrita de A também garante a convergência do método de Gauss-Seidel. Em resumo: diagonal dominante estrita é um critério simples e suficiente que garante convergência de ambos.
Passo 7
Outros critérios importantes (teorema útil para provas):
Para matrizes que são simétricas e definidas positivas (matriz A simétrica e x^\top A x >0 para todo x\neq 0):
O método de Gauss-Seidel sempre converge. (Teorema clássico: GS converge para qualquer A simétrica definida positiva.)
Já o Jacobi não tem garantia automática apenas por A ser SPD; Jacobi pode convergir ou não dependendo da distribuição dos elementos da diagonal e da escala. Portanto, em casos SPD prefira afirmar a convergência do Gauss-Seidel.
Para matrizes do tipo M-matrix ou matrizes irreducivelmente diagonalmente dominantes há garantias de convergência para ambos os métodos. Esses nomes aparecem em teoria linear numérica; na prática, a diagonal dominance estrita é o critério que você usa com mais frequência.
Passo 8
Relação entre os critérios e comparação prática (intuição e desigualdades úteis):
Relação qualitativa: quando as condições suficientes se aplicam (por exemplo, A estritamente diagonalmente dominante por linhas), ambos os métodos convergem; normalmente Gauss-Seidel converge mais rápido (menos iterações) do que Jacobi.
Relação matricial útil para comparar: com A=D+L+U,T_J = -D^{-1}(L+U),\qquad T_{GS} = -(D+L)^{-1}U.Assim, T_{GS} usa uma fatoração/parcela que “incorpora” o efeito de L nas iterações, o que costuma reduzir \rho(T_{GS}) em relação a \rho(T_J) para muitas classes de matrizes (por exemplo, SPD, diagonally dominant, M-matrices).
Em palavras diretas e seguras para a prova: se Jacobi converge então normalmente Gauss-Seidel também convergirá e, na prática, terá taxa de convergência igual ou melhor. Para matrizes SPD, Gauss-Seidel converge sempre; Jacobi nem sempre.
Passo 9
Critério prático de parada e dicas de implementação (como usar na prova e laboratório):
Critérios de parada comuns:
diferença entre iterações: \|x^{(k+1)}-x^{(k)}\| < \varepsilon;
resíduo: \|b-Ax^{(k+1)}\| < \varepsilon (preferível quando possível);
número máximo de iterações.
Dica: o resíduo dá uma medida direta de quão bem x^{(k)} satisfaz o sistema.
Dica de prova/cálculo: para verificar convergência por diagonal dominance, calcule \max_i \frac{1}{|a_{ii}|}\sum_{j\ne i}|a_{ij}|. Se for <1, Jacobi converge; então também conclua convergência do GS e comente que GS converge mais rápido.
Passo 10
Exemplo mínimo (para fixar a ideia — faça isso numa prova se pedirem ilustrar):
ConsidereA=\begin{pmatrix}4 & 1\\\\ 1 & 3\end{pmatrix},\qquad b=\begin{pmatrix}1\\\ 2\end{pmatrix}.Aqui A é estritamente diagonalmente dominante por linhas porque |4|>1 e |3|>1. Portanto:
Jacobi e Gauss-Seidel convergem.
Fórmulas:x_1^{(k+1)}=\frac{1}{4}\bigl(1 - 1\cdot x_2^{(k)}\bigr),\qquad x_2^{(k+1)}=\frac{1}{3}\bigl(2 - 1\cdot x_1^{(k)}\bigr)(Jacobi — ambos usam valores antigos).x_1^{(k+1)}=\frac{1}{4}\bigl(1 - 1\cdot x_2^{(k)}\bigr),\qquad x_2^{(k+1)}=\frac{1}{3}\bigl(2 - 1\cdot x_1^{(k+1)}\bigr)(Gauss-Seidel — x_2^{(k+1)} usa x_1^{(k+1)}). Você verá que Gauss-Seidel normalmente precisa de menos iterações para atingir a mesma precisão.
Resposta
Gauss-Jacobi: iterar pela fórmula \;x_i^{(k+1)}=\dfrac{1}{a_{ii}}\Bigl(b_i-\sum_{j\neq i}a_{ij}x_j^{(k)}\Bigr)\; ou matricialmente \;x^{(k+1)}=T_J x^{(k)}+D^{-1}b com T_J=-D^{-1}(L+U).\nGauss-Seidel: iterar pela fórmula \;x_i^{(k+1)}=\dfrac{1}{a_{ii}}\Bigl(b_i-\sum_{j< i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}\Bigr)\; ou matricialmente \;x^{(k+1)}=T_{GS}x^{(k)}+(D+L)^{-1}b com T_{GS}=-(D+L)^{-1}U.\nPrincipal diferença: Jacobi usa apenas valores da iteração anterior para calcular todos os componentes novos (atualizações em paralelo); Gauss-Seidel usa imediatamente os componentes já atualizados dentro da mesma iteração (atualizações sequenciais), o que normalmente acelera a convergência.\nCritério geral de convergência: um método linear converge para todo chute inicial iff a razão espectral da sua matriz de iteração satisfaz \rho(T)<1.\nCritérios práticos suficientes: se A é estritamente diagonalmente dominante por linhas (ou colunas) então tanto Jacobi quanto Gauss-Seidel convergem (verificando \max_i \frac{1}{|a_{ii}|}\sum_{j\ne i}|a_{ij}|<1 garante \rho(T_J)<1). Para A simétrica definida positiva, Gauss-Seidel converge; Jacobi pode não convergir só com a SPD — precisa-se verificar \rho(T_J)<1.\nRelação entre critérios: quando as condições suficientes (por ex. diagonal dominance ou classe de M-matrices) valem, ambos convergem, e normalmente \rho(T_{GS}) é menor que \rho(T_J) (Gauss-Seidel converge tão rápido ou mais rápido que Jacobi na prática).