Métodos Iterativos Cálculo numerico

Prévia do material em texto

Métodos Iterativos 
Os métodos iterativos resolvem sistemas lineares com muitas variáveis e 
muitas equações e chega a uma aproximação do resultado. Por exemplo, para 
verificarmos as reações sob forças aplicadas em um corpo, utilizamos 
equações lineares com várias incógnitas. Os métodos iterativos chegam a um 
resultado muito próximo da realidade, essa diferença pode ser desconsiderada 
devido ao alto grau de complexidade para resolver esses problemas 
manualmente. 
 
Método Gauss-Seidel 
No método de Gauss-Seidel, um sistema de equações lineares Ax = b é 
escrito de forma equivalente x = Cx + g por separação da diagonal. Seja x (0) 
uma aproximação inicial, pelo processo iterativo queremos calcular x (1), x(2), . 
. . , x(k). Nesse método, quanto maior for o valor de k, maior a precisão do 
resultado. 
EX: Dado um sistema linear com três equações e três incógnitas, 
podemos chegar a um resultado o mais próximo que desejarmos através do 
método Gauss-Seidel. 
 
O primeiro passo para resolução é isolar uma incógnita em cada uma das 
linhas: 
 
Para começar a resolução deve-se criar um vetor inicial: 
 
Em seguida deve-se começar encontrando o x1 da etapa 1. Com o valor de x1 
deve-se substituir na linha do x2. Deve-se fazer isso n etapas que forem necessárias, 
pois quanto mais etapas serem realizadas um resultado mais aproximado vai ser 
encontrado, ou seja, os valores encontrados são usados na própria iteração: 
 
Continuando com a substituição temos: 
 
Para um resultado ainda mais próximo devemos ir criando matrizes, cada vez 
com números menores, e mais aproximados. 
 
 
Exemplo com algoritmo: Pascal. 
program GaussSeidel; 
{INE 5202 Calculo Numerico em 
Computadores} 
uses crt; 
var 
i,j,n,it,itmax,liminf,limsup:integer; 
prec,precmin,somapre,somapos:real; 
a:array[1..10,1..10] of real; 
c:array[1..10] of real; 
x:array[1..10,1..10] of real; 
begin 
{DADOS:} 
clrscr; 
writeln('Este programa resolve um sistema 
de equacoes lineares'); 
writeln('pelo metodo iterativo de GaussSeidel'); 
readkey; 
writeln('Digite a quantidade de equacoes'); 
readln(n); 
writeln('Digite os elementos da matriz 
aumentada A|C por linhas'); 
for i:=1 to n do begin 
 for j:=1 to n do begin 
 writeln('Digite a[',i,',',j,']'); 
 readln(a[i,j]); 
 end;{for} 
 writeln('Digite c[',i,']'); 
 readln(c[i]); 
end;{for} 
writeln('Digite a quantidade maxima de 
iteracoes:'); 
readln(itmax); 
writeln('Digite a precisao minima 
aceitavel:'); 
readln(precmin); 
{TESTE RELATIVO AOS DADOS:} 
for i:=1 to n do begin 
 if(abs(a[i,i])<0.1) then begin 
 writeln('Elemento da diagonal principal 
da matriz eh nulo'); 
 writeln('ou muito proximo de zero'); 
 writeln('A EXECUCAO DEVE SER 
INTERROMPIDA'); 
 readkey; 
 end;{if} 
end;{for} 
writeln('***************************** 
***************'); 
{PROCESSAMENTO} 
{INICIALIZACOES:} 
it:=1;prec:=1000.0; 
for i:=1 to n do begin x[i,it]:=c[i]/a[i,i]; 
end;{for} 
{ITERACOES} 
while((it<=itmax)and(prec>=precmin))do 
begin 
 writeln('Iteracao Numero ',it); 
 prec:=0.0; 
 for i:=1 to n do begin 
 somapre:=0.0; 
 if(i>1)then begin 
for j:=1 to i-1 do begin 
 somapre:=somapre+a[i,j]*x[j,it+1]; 
 end;{for} 
 end;{if} 
 somapos:=0.0; 
if(i<n)then begin 
 for j:=i+1 to n do begin 
 somapos:=somapos+a[i,j]*x[j,it]; 
 end;{for} 
 end;{if} 
 {CALCULO DE NOVA ESTIMATIVA 
DA SOLUCAO DO SISTEMA:} 
 x[i,it+1]:=(c[i]-somapre-somapos)/a[i,i]; 
 prec:=prec+abs(x[i,it+1]-x[i,it]); 
 writeln('x[',i,'] = ',x[i,it+1]); 
 end;{for} 
 writeln('prec := ',prec); 
 it:=it+1; 
 readkey; 
end;{while} 
{SAIDA DOS RESULTADOS} 
if(prec<precmin)then begin 
 writeln('Houve convergencia do processo 
iterativo'); 
 writeln('para a solucao do sistema'); 
 writeln('em ',it,' iteracoes, com prec = 
',prec); 
end;{if} 
if(prec>precmin)then begin 
 writeln('A precisao desejada nao foi 
obtida'); 
 writeln('Foram realizadas ',it,' iteracoes'); 
 writeln('com prec = ',prec); 
end;{if} 
writeln('ultimos valores obtidos:'); 
for i:=1 to n do begin 
 writeln('x[',i,'] = ',x[i,it]); 
 end;{for} 
writeln('prec = ',prec); 
readkey; 
end. 
Método Gauss-Jordan 
 
Como no método Gauss-Seidel, o método Gauss-Jordan tem como objetivo 
resolver equações lineares de n variáveis. Este método consiste em aplicar sucessivas 
operações elementares num sistema linear, para o transformar num sistema de mais 
fácil resolução, que apresenta exatamente as mesmas soluções que o original. Permite 
reduzir uma matriz qualquer a sua forma escalonada por linha. A eliminação de Gauss, 
ou método de escalonamento, é um algoritmo para se resolver sistemas de equações 
lineares. Este método consiste em aplicar sucessivas operações elementares num 
sistema linear, para o transformar num sistema de mais fácil resolução, que apresenta 
exatamente as mesmas soluções que o original. 
Considere o problema de, dada uma solução básica qualquer, obter uma 
solução básica alternativa de forma computacionalmente eficiente. Este problema 
pode ser abordado por meio do método de Gauss-Jordan para solução de sistemas de 
equações lineares do tipo Ax = b, sendo A uma matriz quadrada não singular. O 
método de Gauss-Jordan pode ser estendido a sistemas de equações lineares com m ≤ 
n e rank A = m. Uma operação particular do método, conhecida como pivoteamento, é 
ilustrada a seguir. 
Exemplo: Considere o seguinte sistema de equações lineares: 
 
O sistema de equações pode ser representado na forma de uma matriz de 
coeficientes como: 
 
Inicialmente soma-se as duas primeiras linhas de M e armazena-se o resultado 
na segunda linha. Obtém-se: 
 
 O elemento da matriz M indicado por (I) funcionou como elemento-pivot. A 
operação que resultou na primeira coluna de M1 ´e chamada de pivoteamento. O segundo 
elemento pivot encontra-se indicado na matriz M1. Inicialmente divide-se a segunda linha de 
M1 por 4. Multiplica-se a nova segunda linha por −2, soma-se o resultado a` primeira linha e 
armazena-se a soma na primeira linha; multiplica-se a nova segunda linha por −1, soma-se o 
resultado a` terceira linha e armazena-se a soma na terceira linha. Obtém-se: 
 
O terceiro elemento pivot encontra-se indicado na matriz M2. Multiplica-se a terceira 
linha de M2 por −1, soma-se o resultado à primeira linha e armazena-se a soma na primeira 
linha, para obter a matriz final: 
 
O sistema de equações original foi manipulado até atingir a forma: 
 
A solução básica indicada é: 
 
Suponha que as variáveis x3 e x4 devam ser transformadas em variáveis não-básica e 
básica, respectivamente. A transformação desejada pode ser obtida aplicando-se o método de 
Gauss-Jordan ao elemento pivot indicado na matriz M3. A ideia é transformar a quarta coluna 
de M3 numa coluna idêntica à terceira coluna, associada à x3. No processo, a terceira coluna 
de M3 transforma-se numa coluna não básica. Com o pivoteamento, obtém-se: 
 
correspondente ao sistema de equações: 
 
A nova solução básica é: 
 
 
Método de Jacobi 
É um algoritmo para resolver sistemas de equações lineares. Trata-se de uma versão 
simplificada do algoritmo de valores próprios de Jacobi. O método tem o nome 
do matemático Alemão Carl Gustav Jakob Jacobi. 
O método iterativo de Jacobi é um método clássico que data do final do século XVIII. 
Técnicas iterativas são raramente utilizadas para solucionar sistemas lineares de 
pequenas dimensões, já que o tempo requerido para obter um mínimo de precisão 
ultrapassa o requerido pelas técnicas diretas comoa eliminação gaussiana. Contudo, para 
sistemas grandes, com grande porcentagem de entradas de zero (sistemas esparsos), 
essas técnicas aparecem como alternativas mais eficientes. Sistemas esparsos de grande 
porte frequentemente surgem na análise de circuitos, na solução numérica de problemas 
de valor de limite e equações diferenciais parciais. 
 
Dada uma matriz quadrada de equações lineares: 
 
Ax=b 
 
em que: 
 
Então A pode ser decomposto num componente diagonal D e o resto R: 
 
 
 
 
 
 
O sistema de equações lineares pode ser reescrito como: 
 
Dx=b-Rx 
 
O método de Jacobi é um método iterativo que resolve o membro esquerdo da expressão 
em ordem a x ao usar o método resultante da iteração anterior no membro direito. 
Analiticamente, isto pode ser escrito como: 
 
 
 
 
 
ou, equivalentemente: 
 
 
Nota-se que a computação de é feita com base em todos os valores obtidos em 
iterações anteriores. Ao contrário do método de Gauss-Seidel, não se pode reescrever
 com , pois esse valor é necessário durante a continuação da computação. 
Esta é a diferença mais significativa entre o método de Jacobi e o método de Gauss-Seidel 
e é o motivo que o torna um algoritmo paralelo. 
 
Exemplo Resolvido: 
 
 
Abaixo é apresentado a resolução utilizando na linguagem javascript. 
function norm(Matrix) { 
 //Requer implementação ou inclusão de biblitecas de terceiros 
} 
/* 
* A = Matriz 
* b = Resultado da matriz 
*/ 
function gaussJacobi(A, b) { 
 var X = new Array(); 
 var x = new Array(); 
 for (var k = 0; k < b.length; k++) 
 { 
 X[k] = 0; //Math.floor((Math.random() * 10000) + 1); 
 } 
 
 var E = 0.00001;//Precisão 
 var m = 1000;//Numero máximo de iterações 
 var ni = 0;//Contador de iterações 
 var continuar = true; 
 
 while (continuar && ni < m) { 
 for (var i=0; i < b.length; i++) { 
 soma = 0; 
 for (var j = 0; j < b.length; j++) { 
 if (j != i) { 
 soma = soma + A[i][j]*X[j]/A[i][i]; 
 } 
 x[i] = (b[i]/A[i][i]) - soma; 
 } 
 } 
 if (Math.abs(norm(x) - norm(X)) < E) { 
 continuar = false; 
 } else { 
 X=x.slice(0); 
 } 
 ni = ni + 1; 
 } 
 return X; 
}