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
A=\begin{pmatrix} a_{11} & a_{12} \\\ a_{21} & a_{22} \end{pmatrix},
temos D=\begin{pmatrix} a_{11} & 0 \\\\ 0 & a_{22} \end{pmatrix}, L=\begin{pmatrix} 0 & 0 \\\ a_{21} & 0 \end{pmatrix}, U=\begin{pmatrix} 0 & a_{12} \\\\ 0 & 0 \end{pmatrix}.

Passo 3

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:
\beta_1 = \frac{1}{|a_{11}|}\sum_{j=2}^n |a_{1j}|,
e, para i=2,3,\dots,n,
\beta_i = \frac{1}{|a_{ii}|}\left(\sum_{j=1}^{i-1} |a_{ij}|\beta_j + \sum_{j=i+1}^n |a_{ij}|\right).
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 é
\sum_{j\ne i} \frac{|a_{ij}|}{|a_{ii}|} = \frac{1}{|a_{ii}|}\sum_{j\ne i}|a_{ij}|.
Se A é estritamente diagonalmente dominante, então essa soma é menor que 1 para cada i, e portanto
\|B_J\|_\infty = \max_i \frac{1}{|a_{ii}|}\sum_{j\ne i}|a_{ij}| < 1.
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.

Passo 8

Exemplo rápido (faça igual na prova): seja
A=\begin{pmatrix} 4 & -1 & 0\\\\ -2 & 5 & -1\\\\ 0 & -1 & 3 \end{pmatrix}.
Calcule \beta_1,\beta_2,\beta_3.
\beta_1=\frac{1}{|4|}\big(|-1|+|0|\big)=\frac{1}{4}\cdot 1 = \frac{1}{4}.
\beta_2=\frac{1}{|5|}\big(|-2|\beta_1 + | -1|\big)=\frac{1}{5}\big(2\cdot\frac{1}{4}+1\big)=\frac{1}{5}\cdot\frac{3}{2}=\frac{3}{10}.
\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).

Exercícios relacionados