Escreva um algoritmo para o método de Gauss-Seidel. Compare o custo computacional deste algoritmo com o custo do algoritmo para o método de Jacobi (exercício 11.1).

Passo 1

O enunciado pede para escrever o pseudocódigo do método iterativo de Gauss–Seidel para resolver \boldsymbol{A}\mathbf{x}=\mathbf{b} e comparar o custo computacional deste algoritmo com o do método de Jacobi (exercício 11.1). O conteúdo aqui é métodos de solução iterativa de sistemas lineares e a ferramenta que vamos usar é a contagem de operações (flops) por iteração.

Passo 2

Segue o algoritmo de Gauss–Seidel em pseudocódigo, supondo uma matriz n \times n com todos os a_{ii} \neq 0.
Entrada: A, b, x^{(0)} (chute inicial), tol, maxIter
k \leftarrow 0
Enquanto k < \text{maxIter} faça
Para i de 1 até n faça
\sigma \leftarrow 0
Para j de 1 até i-1 faça
\sigma \leftarrow \sigma + a_{ij} \cdot x_j % usa x_j atualizado
Para j de i+1 até n faça
\sigma \leftarrow \sigma + a_{ij} \cdot x_j^{(k)} % usa valor da iteração anterior
x_i \leftarrow \frac{b_i - \sigma}{a_{ii}}
FimPara
Se \| x - x^{(k)} \| < \text{tol} então
Pare e retorne x
x^{(k+1)} \leftarrow x
k \leftarrow k + 1
FimEnquanto
Retorne x

Passo 3

Contagem de flops por iteração em Gauss–Seidel:
Para cada i\in\{1,\dots,n\} fazemos
  • (i-1) multiplicações e (i-1) somas para a parte j<i,
  • (n-i) multiplicações e (n-i) somas para a parte j>i,
  • mais uma subtração e uma divisão.
    Somando sobre i, o total é
\sum_{i=1}^n\bigl[(i-1)+(n-i)\bigr]\text{ mults} + \sum_{i=1}^n\bigl[(i-1)+(n-i)\bigr]\text{ adds} + n\text{ subs} + n\text{ divs} \;=\;2n(n-1)+2n \;=\;2n^2\;(\text{aprox.})
portanto O(n^2) flops por iteração.

Passo 4

No método de Jacobi (exercício 11.1), para cada iteração e cada i também calculamos
  • (n-1) multiplicações e (n-1) somas,
  • mais uma subtração e uma divisão,
    totalizando novamente cerca de 2n^2 flops por iteração, ou seja, também O(n^2).

Passo 5

Comparação: ambos os métodos custam O(n^2) flops por iteração. A diferença prática é que Gauss–Seidel faz as atualizações in-place (usa imediatamente os x_j novos), evitando a necessidade de um vetor extra para os valores da próxima iteração, o que reduz ligeiramente o uso de memória e de cópias de vetor.

Resposta

O método de Gauss–Seidel requer aproximadamente 2n^2 flops por iteração, assim como o método de Jacobi. Ambos têm custo assintótico O(n^2) por iteração, mas Gauss–Seidel usa atualizações in-place, economizando memória e acessos à memória.

Exercícios relacionados