Método de Gauss-Seidel

O método de Gauss-Seidel é um método iterativo utilizado para resolver sistemas lineares do tipo:

$A x = b$

Ele é uma melhoria do método de Jacobi, pois utiliza os valores mais recentes disponíveis para acelerar a convergência.

Formulação

Dado um sistema com matriz A $\in R^{n \times n}$ , vetor b $\in R^{n}$ , e uma aproximação inicial $x^{(0)}$ , o método atualiza cada componente da solução x segundo a fórmula:

x_{i}^{(k + 1)} = \frac{1}{a_{i i}} (b_{i} - \sum_{j = 1}^{i - 1} a_{i j} x_{j}^{(k + 1)} - \sum_{j = i + 1}^{n} a_{i j} x_{j}^{(k)})

Critério da Norma Linha (Norma ∞)

Esse critério é matemático e envolve a matriz de iteração T do método. Por exemplo, no Gauss-Jacobi:

$T = D^{- 1} (L + U)$

Onde:

D: diagonal da matriz A
L: parte inferior de A (sem a diagonal)
U: parte superior de A (sem a diagonal)

A norma linha (ou norma infinita) de uma matriz T é o máximo das somas dos módulos dos elementos de cada linha:

∥ T ∥ \infty = max 1 \leq i \leq n \sum_{j = 1}^{n} | t_{i j} |

Convergência

Se $∥ T ∥_{\infty} < 1$ , o Método Converge

Exemplo (Critério da Norma Linha)

Considere o sistema:

\begin{aligned} 4 x_{1} + x_{2} + x_{3} & = 7 \\ x_{1} + 5 x_{2} + 2 x_{3} & = - 8 \\ 2 x_{1} + 3 x_{2} + 10 x_{3} & = 6 \end{aligned}

A matriz A é:

A = [\begin{matrix} 4 & 1 & 1 \\ 1 & 5 & 2 \\ 2 & 3 & 10 \end{matrix}]

Para o Jacobi, a matriz de iteração é $T = D^{- 1} (L + U)$ . Calculando isso (ou com código), você obterá algo como:

T = [\begin{matrix} 0 & - 0.25 & - 0.25 \\ - 0.2 & 0 & - 0.4 \\ - 0.2 & - 0.3 & 0 \end{matrix}]

Agora, calcule a soma dos módulos dos elementos de cada linha:

linha 1: $| 0 | + | - 0.25 | + | - 0.25 | = 0.5$
linha 2: $| - 0.2 | + | 0 | + | - 0.4 | = 0.6$
linha 3: $| - 0.2 | + | - 0.3 | + | 0 | = 0.5$

Maior valor: $∥ T ∥_{\infty} = 0.6 < 1$

O método de Jacobi (e provavelmente o de Gauss-Seidel) converge.

Critério de Sassenfeld

Esse critério é mais fácil de aplicar manualmente e muito útil, principalmente para o método de Gauss-Seidel.

Ele define uma sequência de valores $β_{i}$ , onde:

β_{i} = \frac{1}{| a_{i i} |} (\sum_{j = 1}^{i - 1} | a_{i j} | β_{j} + \sum_{j = i + 1}^{n} | a_{i j} |)

Você usa os $β$ ’s anteriores conforme vai calculando. É uma espécie de “feedback” para estimar o quanto cada linha depende das outras.

Convergência

Se $max (β_{1}, \dots, β_{n}) < 1$ , o Método Converge

Exemplo (Critério de Sassenfeld)

Use a mesma matriz A:

A = [\begin{matrix} 4 & 1 & 1 \\ 1 & 5 & 2 \\ 2 & 3 & 10 \end{matrix}]

Vamos calcular os $β_{i}$ :

$β_{1} = \frac{1}{4} (| 1 | + | 1 |) = \frac{2}{4} = 0.5$
$β_{2} = \frac{1}{5} (| 1 | \cdot 0.5 + | 2 |) = \frac{1}{5} (0.5 + 2) = 0.5$
$β_{3} = \frac{1}{10} (| 2 | \cdot 0.5 + | 3 | \cdot 0.5) = \frac{1}{10} (1 + 1.5) = 0.25$

Logo:

max (β_{1}, β_{2}, β_{3}) = 0.5 < 1

O método de Gauss-Seidel converge!