[3] Quantas operações são realizadas em cada iteração dos métodos de Jacobi. Gauss-Seidel e SOR quando:
(a) A é uma matriz n times n ?
(b) A é uma matriz de banda p+q+1 ? Considere p o número de diagonais não nulas acima da diagonal principal e q o número de diagonais não nulas abaixo da diagonal principal.

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 A é
  1. uma matriz densa de tamanho ntimes n,
  2. uma matriz de banda com p+q+1 diagonais não nulas (sendo p acima da diagonal principal e q abaixo).
    Para isso, em cada método, vamos examinar quanto custa computar uma nova componente xi e depois somar esse custo para i=1,dots,n.

Passo 2

Jacobi com A densa:
Para cada i computamos
  1. o somatório sumjneq iaijxj, que exige (n-1) multiplicações e (n-2) somas;
  2. uma subtração do resultado em relação a bi (mais 1 soma) e uma divisão por aii.
    Logo, por componente i temos
  • multiplicações: (n-1),
  • somas: (n-2)+1=n-1,
  • divisões: 1.
    Somando para i=1,dots,n, o total por iteração é
l[n(n-1)r] mu<, l[n(n-1)r] somas, n divisões õ

Passo 3

Gauss–Seidel com A 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
n(n-1) mu<iplicações, n(n-1) somas, n divisões çõõ

Passo 4

SOR com A densa:
Para cada i fazemos
  1. o somatório sumjneq iaijxj: (n-1) mult. e (n-2) somas;
  2. subtração em relação a bi: 1 soma;
  3. multiplicação por omega/aii: 1 mult. (ou 1 div. + 1 mult., mas contamos como 1 div. e 1 mult.);
  4. atualização relaxada xi^new=(1-omega)xi^old+dots: 1 mult. e 1 soma.
    Total por i:
  • multiplicações: (n-1)+2 = n+1,
  • somas: (n-2)+1+1 = n,
  • divisões: 1.
    Multiplicando por n, obtemos por iteração
n(n+1) mu<, ncdot n somas, n divisões õ

Passo 5

Jacobi e Gauss–Seidel com A de banda p+q+1:
Em cada linha i só existem p+q coeficientes fora da diagonal, logo
  • multiplicações para o somatório: p+q,
  • somas para acumular esses termos: (p+q-1),
  • mais 1 soma para subtrair de bi e 1 divisão por aii.
    Isso dá por componente
  • (p+q) mult.,
  • (p+q-1)+1 = p+q somas,
  • 1 divisão.
    Somando em n componentes:
n(p+q) mu<, n(p+q) somas, n divisões õ

Passo 6

SOR com A de banda p+q+1:
Para cada i repetimos o raciocínio do passo anterior, acrescido de 2 mult./somas extras da relaxação. Assim, por componente
  • mult.: (p+q)+2,
  • somas: (p+q-1)+1+1 = p+q,
  • divisões: 1.
    Em n componentes, por iteração:
n(p+q+2) mu<, n(p+q) somas, n divisões õ

Resposta

(a) A densa ntimes n:
  • Jacobi: n(n-1) mult., n(n-1) somas, n divisões.
  • Gauss–Seidel: idem Jacobi.
  • SOR: n(n+1) mult., n^2 somas, n divisões.
(b) A de banda p+q+1:
  • Jacobi e Gauss–Seidel: n(p+q) mult., n(p+q) somas, n divisões.
  • SOR: n(p+q+2) mult., n(p+q) somas, n divisões.

Exercícios relacionados