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
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
para
. A ideia é usar somente valores de
para obter
.
Passo 3
Dentro de cada iteração, para cada componente
temos:
- Cálculo da soma
: exige multiplicações e somas. - Subtração de
de : operação de subtração (contabilizada como soma). - Divisão por
: divisão.
Logo, por componente
:
multiplicações ,
somas ,
divisões .
multiplicações
somas
divisões
Passo 4
Para todo o vetor
em uma iteração temos:
multiplicações totais ,
somas totais ,
divisões totais .
multiplicações totais
somas totais
divisões totais
Em notação de flops isso dá
flops de multiplicaçã
dição mais
divisões por iteração.
Passo 5
Esboço de pseudocódigo com contadores de operações:
a) Guarda
b) Para
-
- Para
* se
-
-
c) Se
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
tal que chega à tolerância):
- Multiplicações por iteração:
. - Somase/subtrações por iteração:
. - Divisões por iteração:
.
Ou seja, em cada iteração o método realiza exatamente
operações aritméticas.