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ção T_J = D^{-1}(- (L+U)) = I - D^{-1}A,e o esquema itera como x^{(k+1)} = T_J x^{(k)} + D^{-1} b.
  • Implementação prática (passos a seguir numa prova ou código):
    1. Verifique que todos os a_{ii}\neq 0.
    2. Escolha um chute inicial x^{(0)}.
    3. Para cada iteração k, calcule cada x_i^{(k+1)} pela fórmula acima usando apenas os x_j^{(k)}.
    4. 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:
    1. Garanta a_{ii}\neq 0 para todo i.
    2. Escolha x^{(0)}.
    3. Para cada iteração k, atualize sequencialmente i=1 até n pela fórmula componente do Gauss-Seidel.
    4. 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:
    1. diferença entre iterações: \|x^{(k+1)}-x^{(k)}\| < \varepsilon;
    2. resíduo: \|b-Ax^{(k+1)}\| < \varepsilon (preferível quando possível);
    3. 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):
  • Considere A=\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).

Exercícios relacionados