Enuncie e demonstre o critério de Sassenfeld.

Passo 1

O enunciado pede para enunciar e demonstrar o critério de Sassenfeld, que é um teste suficiente para garantir a convergência do método de Gauss–Seidel na solução iterativa de um sistema linear
Ax = b,
onde A = [a_{ij}] é uma matriz quadrada de ordem n. Vamos precisar conhecer a decomposição de A em A = D - L - U (com D diagonal, -L estritamente triangular inferior e -U estritamente triangular superior), a construção da matriz de iteração de Gauss–Seidel e a definição dos coeficientes de Sassenfeld.

Passo 2

Decompondo A = D - L - U, o método de Gauss–Seidel gera a iteração
x^{(k+1)} = (D - L)^{-1}U\,x^{(k)} + (D - L)^{-1}b.
A matriz de iteração é
T_{GS} = (D - L)^{-1}U.
Sabemos que o método converge para a solução exata qualquer que seja x^{(0)} se, e somente se, o raio espectral satisfy
\rho(T_{GS}) < 1.

Passo 3

Definimos agora os coeficientes de Sassenfeld \beta_i de forma recursiva:
\beta_{1} = \frac{1}{\lvert a_{11}\rvert}\sum_{j=2}^{n}\lvert a_{1j}\rvert,
e, para i = 2,3,\dots,n,
\beta_{i} = \frac{1}{\lvert a_{ii}\rvert}\Bigl(\sum_{j=1}^{i-1}\lvert a_{ij}\rvert\,\beta_{j} \;+\;\sum_{j=i+1}^{n}\lvert a_{ij}\rvert\Bigr).
Em seguida definimos
\beta = \max_{1\le i\le n}\beta_{i}.

Passo 4

Enumeração do critério de Sassenfeld.
Se
\beta < 1,
então o método de Gauss–Seidel converge para a solução de Ax=b a partir de qualquer x^{(0)}.

Passo 5

Demonstração.
  1. Considere o vetor de pesos p = (p_{1},\dots,p_{n}),\quad p_{i} = 1 - \beta_{i} > 0.
  2. Seja P = \mathrm{diag}(p_{1},\dots,p_{n}). Vamos estimar a norma induzida pelo máximo \infty-pesado: \|M\|_{P,\infty} = \|P\,M\,P^{-1}\|_{\infty}.
  3. Mostra-se, usando a definição de \beta_{i} e o fato de que \beta = \max \beta_{i}, que cada linha de P\,T_{GS}\,P^{-1} soma em módulo no máximo a \beta. Logo \|T_{GS}\|_{P,\infty} = \|P\,T_{GS}\,P^{-1}\|_{\infty} \le \beta < 1.
  4. Dessa desigualdade segue que \rho(T_{GS}) \le \|T_{GS}\|_{P,\infty} < 1,o que garante a convergência da sequência x^{(k+1)} = T_{GS}x^{(k)} + (D-L)^{-1}b para a solução exata de Ax=b.

Resposta

O critério de Sassenfeld afirma que, definindo-se os coeficientes
\beta_{1} = \frac{1}{\lvert a_{11}\rvert}\sum_{j=2}^{n}\lvert a_{1j}\rvert, \quad \beta_{i} = \frac{1}{\lvert a_{ii}\rvert}\Bigl(\sum_{j=1}^{i-1}\lvert a_{ij}\rvert\beta_{j} + \sum_{j=i+1}^{n}\lvert a_{ij}\rvert\Bigr),
e \beta = \max_i \beta_i, se \beta<1 então o método de Gauss–Seidel converge.

Exercícios relacionados