[3] Quantas operações são realizadas em cada iteração dos métodos de Jacobi. Gauss-Seidel e SOR quando:
(a)
é uma matriz
?
(b)
é uma matriz de banda
? Considere
o número de diagonais não nulas acima da diagonal principal e
o número de diagonais não nulas abaixo da diagonal principal.
(a)
(b)
Passo 1
O enunciado pede para contarmos o número de operações (multiplicações, somas e divisões) realizadas em cada iteração dos métodos de Jacobi, Gauss–Seidel e SOR, nos casos em que
é
- uma matriz densa de tamanho
, - uma matriz de banda com
diagonais não nulas (sendo acima da diagonal principal e abaixo).
Para isso, em cada método, vamos examinar quanto custa computar uma nova componentee depois somar esse custo para .
Passo 2
Jacobi com
densa:
Para cada computamos
Para cada
- o somatório
, que exige multiplicações e somas; - uma subtração do resultado em relação a
(mais 1 soma) e uma divisão por .
Logo, por componentetemos
- multiplicações:
, - somas:
, - divisões:
.
Somando para, o total por iteração é
Passo 3
Gauss–Seidel com
densa:
O procedimento é igual ao de Jacobi, salvo que usamos valores atualizados para as primeiras componentes, mas o número de flops não muda. Assim, também temos por iteração
O procedimento é igual ao de Jacobi, salvo que usamos valores atualizados para as primeiras componentes, mas o número de flops não muda. Assim, também temos por iteração
Passo 4
SOR com
densa:
Para cada fazemos
Para cada
- o somatório
: mult. e somas; - subtração em relação a
: 1 soma; - multiplicação por
: 1 mult. (ou 1 div. + 1 mult., mas contamos como 1 div. e 1 mult.); - atualização relaxada
: 1 mult. e 1 soma.
Total por:
- multiplicações:
, - somas:
, - divisões:
.
Multiplicando por, obtemos por iteração
Passo 5
Jacobi e Gauss–Seidel com
de banda
:
Em cada linha só existem
coeficientes fora da diagonal, logo
Em cada linha
- multiplicações para o somatório:
, - somas para acumular esses termos:
, - mais 1 soma para subtrair de
e 1 divisão por .
Isso dá por componente -
mult., -
somas, - 1 divisão.
Somando emcomponentes:
Passo 6
SOR com
de banda
:
Para cada repetimos o raciocínio do passo anterior, acrescido de 2 mult./somas extras da relaxação. Assim, por componente
Para cada
- mult.:
, - somas:
, - divisões:
.
Emcomponentes, por iteração:
Resposta
(a)
densa
:
- Jacobi:
mult., somas, divisões. - Gauss–Seidel: idem Jacobi.
- SOR:
mult., somas, divisões.
(b)
de banda
:
- Jacobi e Gauss–Seidel:
mult., somas, divisões. - SOR:
mult., somas, divisões.