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
e comparar o custo computacional deste algoritmo com o do método de Jacobi (exercício
). 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
com todos os
.
Entrada:
,
,
(chute inicial), tol, maxIter
Enquanto faça
Para de
até
faça
Para de
até
faça
% usa
atualizado
Para de
até
faça
% usa valor da iteração anterior
FimPara
Se então
Pare e retorne
FimEnquanto
Retorne
Enquanto
Para
Para
Para
FimPara
Se
Pare e retorne
FimEnquanto
Retorne
Passo 3
Contagem de flops por iteração em Gauss–Seidel:
Para cada fazemos
Para cada
-
multiplicações e somas para a parte , -
multiplicações e somas para a parte , - mais uma subtração e uma divisão.
Somando sobre, o total é
portanto
flops por iteração.
Passo 4
No método de Jacobi (exercício
), para cada iteração e cada
também calculamos
-
multiplicações e somas, - mais uma subtração e uma divisão,
totalizando novamente cerca deflops por iteração, ou seja, também .
Passo 5
Comparação: ambos os métodos custam
flops por iteração. A diferença prática é que Gauss–Seidel faz as atualizações in-place (usa imediatamente os
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
flops por iteração, assim como o método de Jacobi. Ambos têm custo assintótico
por iteração, mas Gauss–Seidel usa atualizações in-place, economizando memória e acessos à memória.