Escreva um algoritmo para o método de Jacobi e conte o número de operações realizadas em cada iteração do método. Implemente seu algoritmo em Octave.

Passo 1

O enunciado pede para escrever o método de Jacobi para resolver o sistema linear
A x = b
contar quantas operações aritméticas (multiplicações, somas/subtrações e divisões) são realizadas em cada iteração e implementar tudo em Octave. O conteúdo aqui é métodos iterativos para sistemas lineares, mais especificamente o método de Jacobi, e precisamos também entender como contabilizar as operações dentro do laço de iteração.

Passo 2

O método de Jacobi calcula iterativamente
x_i^{(k+1)} \;=\;\frac{1}{a_{ii}}\Bigl(b_i \;-\;\sum_{\substack{j=1 \\\ j\neq i}}^{n}a_{ij}\,x_j^{(k)}\Bigr),
para i=1,2,\dots,n. A ideia é usar somente valores de x^{(k)} para obter x^{(k+1)}.

Passo 3

Dentro de cada iteração, para cada componente i temos:
  • Cálculo da soma \displaystyle S_i = \sum_{j\neq i}a_{ij}\,x_j^{(k)}: exige (n-1) multiplicações e (n-2) somas.
  • Subtração de S_i de b_i: 1 operação de subtração (contabilizada como soma).
  • Divisão por a_{ii}: 1 divisão.
Logo, por componente i:
multiplicações = n-1,
somas = (n-2)+1 = n-1,
divisões =1.

Passo 4

Para todo o vetor x\in\mathbb R^n em uma iteração temos:
multiplicações totais = n\,(n-1),
somas totais = n\,(n-1),
divisões totais = n.
Em notação de flops isso dá 2n(n-1) flops de multiplicaçã o+adição mais n divisões por iteração.

Passo 5

Esboço de pseudocódigo com contadores de operações:
1. Recebe A, b, chute inicial x^{(0)}, tolerância \text{tol}, máximo de iterações \text{maxit}.
2. Inicializa contadores: \text{countMult}=0, \text{countAdd}=0, \text{countDiv}=0.
3. Para k=0 até \text{maxit}-1:
a) Guarda x^{(k)} em x_{\text{old}}.
b) Para i=1 até n:
- S=0.
- Para j=1 até n:
* se j\neq i: S=S + A(i,j)*x_{\text{old}}(j). Incrementa \text{countMult}++ e \text{countAdd}++.
- S = b(i) - S. Incrementa \text{countAdd}++.
- x(i) = S / A(i,i). Incrementa \text{countDiv}++.
c) Se \|x - x_{\text{old}}\|_\infty < \text{tol}, sai do laço.

Resposta

function [x, iter, countMult, countAdd, countDiv] \(=\) jacobi(A, b, x\(0\), tol, maxit)
  % [x,iter,countMult,countAdd,countDiv] \(=\) jacobi(A,b,x\(0\),tol,maxit)
  % Resolve A*\(x=b\) pelo método de Jacobi, retorna contagem de operações.
  
  n \(=\) length(b);
  x \(=\) x\(0\)(:);
  countMult \(=0\);
  countAdd  \(=0\);
  countDiv  \(=0\);
  
  for k \(=1\):maxit
    \(x_old =\) x;
    for i \(=1\):n
      S \(=0\);
      for j \(=1\):n
        if j ~\(=\) i
          % soma parcial
          S \(=\) S \(+\) A(i,j) * \(x_old\)(j);
          countMult \(=\) countMult \(+1\);   % uma multiplicação
          countAdd  \(=\) countAdd  \(+1\);   % uma soma
        end
      end
      % b(i) - S
      S \(=\) b(i) - S;
      countAdd \(=\) countAdd \(+1\);        % subtração como soma
      % divisão por A(i,i)
      x(i) \(=\) S / A(i,i);
      countDiv \(=\) countDiv \(+1\);        % uma divisão
    end
    % Critério de parada
    if norm(x - \(x_old\), Inf) < tol
      break;
    end
  end
  iter \(=\) k;
end
Explicação dos contadores por iteração (supondo parada em k tal que chega à tolerância):
  • Multiplicações por iteração: n\,(n-1).
  • Somase/subtrações por iteração: n\,(n-1).
  • Divisões por iteração: n.
Ou seja, em cada iteração o método realiza exatamente
\underbrace{n(n-1)}_{\text{mult}} + \underbrace{n(n-1)}_{\text{somas}} + \underbrace{n}_{\text{divisões}}õ
operações aritméticas.

Exercícios relacionados