Explique o conceito de critério de Sassenfeld para a convergência de métodos iterativos como Jacobi e Gauss-Seidel. Por que a diagonal dominante é uma condição importante?
Passo 1
O enunciado pede duas coisas claras: explicar o que é o critério de Sassenfeld para convergência de métodos iterativos (Jacobi e Gauss–Seidel) e explicar por que a dominância diagonal é uma condição importante. As informações relevantes que temos (implícitas no problema) são: estamos lidando com sistemas lineares do tipo Ax=b com A quadrada, e queremos saber quando as iterações de Jacobi e de Gauss–Seidel convergem para a solução verdadeira, a partir de qualquer chute inicial.
Passo 2
Primeiro, entenda a estrutura básica de um método iterativo para Ax=b. Escrevemos a matriz A como soma de três partes:
A = D + L + U,
onde D é a diagonal de A (matriz diagonal com a_{ii} na diagonal), L é a parte estritamente triangular inferior (entradas abaixo da diagonal) e U é a parte estritamente triangular superior (entradas acima da diagonal). Isso é só uma forma organizada de separar os termos. Exemplo: para
Agora veja as fórmulas das iterações (forma matricial):
Iteração de Jacobi:
x^{(k+1)} = -D^{-1}(L+U)\,x^{(k)} + D^{-1}b.
Definimos a matriz de iteração de Jacobi como
B_J = -D^{-1}(L+U).
Iteração de Gauss–Seidel:
x^{(k+1)} = -(D+L)^{-1}U\,x^{(k)} + (D+L)^{-1}b,
e a matriz de iteração de Gauss–Seidel é
B_{GS} = -(D+L)^{-1}U.
Convergência (para qualquer chute inicial) ocorre se e somente se o raio espectral da matriz de iteração for menor que 1:
\rho(B) < 1,
onde \rho(B) é o máximo dos valores absolutos dos autovalores de B. Na prática de prova não se costuma calcular autovalores; procuramos condições suficientes fáceis de verificar que garantem \rho(B)<1.
Passo 4
Agora o que é o critério de Sassenfeld? É um critério prático e recursivo que dá uma condição suficiente (mais fraca que dominância diagonal estrita em alguns casos) para garantir a convergência do método de Gauss–Seidel. Dado o sistema Ax=b com entradas a_{ij}, definimos números \beta_1,\beta_2,\dots,\beta_n recursivamente assim:
Interpretação passo a passo: para cada linha i você soma primeiro os coeficientes dos termos à esquerda da diagonal multiplicados pelas \beta já calculadas (essas \beta_j incorporam o efeito das dependências anteriores), e soma também os coeficientes à direita da diagonal sem multiplicar por \beta (porque esses serão tratados “mais tarde” na ordem). Depois divide tudo por |a_{ii}|. O procedimento é simples de aplicar na prova: vai calculando \beta_1, depois \beta_2, etc.
O critério afirma: se
\max_{1\le i\le n} \beta_i < 1,
então o método de Gauss–Seidel converge para a solução de Ax=b para qualquer vetor inicial x^{(0)}.
Passo 5
Por que esse critério garante convergência do Gauss–Seidel? Explicação intuitiva e um esqueleto da razão:
A recorrência que define as \beta_i é construída de forma a controlar as somas das colunas (ou linhas, dependendo da escrita) da matriz de iteração em norma supremo adaptada à ordem das equações. Pode-se mostrar que existe uma norma vetorial ponderada \|\cdot\|_w (uma norma infinito com pesos) tal que a norma da matriz de iteração satisfaz \|B_{GS}\|_w \le \max_i \beta_i.
Se \|B_{GS}\|_w < 1 então \rho(B_{GS}) \le \|B_{GS}\|_w < 1, logo \rho(B_{GS})<1 e o método converge.
Não é necessário decorar a prova técnica na íntegra para a prova de graduação, mas é importante entender: Sassenfeld constrói um “peso” linha a linha que permite mostrar contração da iteração. Assim \max \beta_i<1 é uma garantia efetiva de convergência do Gauss–Seidel.
Passo 6
Relação com Jacobi e com dominância diagonal. Primeiro, definimos dominância diagonal estrita por linhas: a matriz A é estritamente diagonalmente dominante por linhas se, para todo i,
|a_{ii}| > \sum_{j\ne i} |a_{ij}|.
Por que isso é importante?
Se A é estritamente diagonalmente dominante por linhas, então tanto o método de Jacobi quanto o de Gauss–Seidel convergem. Uma maneira simples de ver isso para Jacobi é usar a norma infinito: calcule \|B_J\|_\infty. Como B_J = -D^{-1}(L+U), a soma dos elementos absolutos na linha i de B_J é
Daí \rho(B_J)\le \|B_J\|_\infty<1, logo Jacobi converge. Para Gauss–Seidel, pode-se mostrar que dominância diagonal também implica \max\beta_i<1, então Sassenfeld é satisfeita e Gauss–Seidel converge também.
Em resumo: dominância diagonal é uma condição fácil de verificar que implica convergência dos dois métodos. É mais forte (mais fácil de checar) e garante que as iterações são contrações em normas simples.
Passo 7
Observações importantes sobre o que cada critério garante:
Sassenfeld é uma condição suficiente para a convergência de Gauss–Seidel. Se \max\beta_i<1 então Gauss–Seidel converge. O contrário nem sempre é verdadeiro: pode convergir sem que Sassenfeld seja satisfeita.
Dominância diagonal estrita garante convergência de ambos (Jacobi e Gauss–Seidel) e ainda dá um controle simples via normas matriciais.
Nem todos os sistemas convergentes satisfazem dominância diagonal; existem matrizes — por exemplo matrizes simétricas positivas definidas — que permitem convergência mesmo sem dominância. Para essas, outras teorias (p.ex. convergência por positividade definida) entram em cena. Mas para provas e aplicações rápidas, Sassenfeld e dominância são ferramentas muito úteis.
\beta_3=\frac{1}{|3|}\big(|0|\beta_1 + |-1|\beta_2\;+\;(\text{nada à direita})\big)=\frac{1}{3}\cdot 1\cdot\frac{3}{10}=\frac{1}{10}.à
Temos \max\beta_i=\frac{1}{4}<1, logo por Sassenfeld Gauss–Seidel converge. Além disso, verifique a dominância diagonal: linha 1: 4>1, linha 2: 5>2+1=3, linha 3: 3>1 — então há dominância diagonal estrita, e portanto Jacobi também converge. Esse tipo de conta é rapidinha na prova.
Passo 9
Dicas práticas para a prova (motivação amiga): sempre que der uma matriz 3×3 ou 4×4, calcule as \beta_i — é pouco trabalho e dá uma resposta direta sobre Gauss–Seidel. Se quiser afirmar convergência de Jacobi, cheque a dominância diagonal (norma infinito) — isso é imediato. Se a matriz for simétrica e definida positiva, lembre-se que Gauss–Seidel também converge (mas essa é outra teoria que você pode usar quando for permitido). Você está indo bem: aplicar Sassenfeld é mecânico — pratique 2 ou 3 exemplos e fica suave.
Resposta
Sassenfeld: Calcule \beta_1,\dots,\beta_n por \displaystyle \beta_1=\frac{1}{|a_{11}|}\sum_{j=2}^n|a_{1j}| e \displaystyle \beta_i=\frac{1}{|a_{ii}|}\bigg(\sum_{j=1}^{i-1}|a_{ij}|\beta_j+\sum_{j=i+1}^n|a_{ij}|\bigg) para i\ge2. Se \max_i\beta_i<1 então o método de Gauss–Seidel converge para a solução para qualquer chute inicial.
Dominância diagonal: Se A é estritamente diagonalmente dominante por linhas, isto é |a_{ii}|>\sum_{j\ne i}|a_{ij}| para todo i, então tanto Jacobi quanto Gauss–Seidel convergem; a dominância implica \|B_J\|_\infty<1 (logo Jacobi converge) e também implica o critério de Sassenfeld (logo Gauss–Seidel converge).