RELATORIO PROJETO Numerico 2011.2 s

Prévia do material em texto

Equações Lineares
Neste texto é discutido à cerca da utilização dos chamados métodos iterativos para aproximar o vetor-solução (nx1) de um sistema de equações lineares, apesar de ter o método de Gauss-Jordan como direto para uma comparação com os iterativos (Jacobi e Gauss-Seidel, afim de mostrar que estes últimos são mais precisos e menos trabalhosos. Dado um determinado sistema de n equações lineares, com n variáveis, o programa irá encontrar o vetor-solução n x 1 do sistema. 
Para isto, detalhamos um exemplo a fim de deixar claro nossos objetivos e a utilização do software. Ainda expusemos as limitações envolvidas na execução do programa.
Palavras-chaves: variáveis, aproximação inicial, iteração, método, vetor solução.
	Introdução
Desde o começo de nossa vida escolar nos familiarizamos a encontrar vetores-solução de equações lineares através de métodos diretos, como a Regra de Cramer, Eliminação de Gauss, Gauss-Jordan e decomposição LU. Contudo, para sistemas lineares com um número considerável de variáveis, encontraríamos dificuldades de encontrar o vetor-solução pelo número de operações necessárias, aumentando muito conforme aumenta o nº de variáveis, além de, apesar de chegar ao vetor-solução em alguns métodos, ocorrer problemas em termo de precisão. Por exemplo, um sistema linear com 5 equações, pelo método de Cramer seria necessárias 1.349 operações, por Eliminação de Gauss, 115, já utilizando o método de Gauss-jordan sem pivotação, apesar de ser necessário menos operações, seu vetor-solução possui um erro de precisão alto. No nosso caso específico a resolução de um sistema linear é dado por métodos computacionais e relacionam uma grande quantidade de variáveis, que caso tentássemos resolver “a mão” seria bastante trabalhoso, praticamente inviável. Contornamos estes problemas recorrentes através dos métodos iterativos.
Através dos chamados métodos iterativos (repetitivos) - os quais, partindo de uma aproximação inicial e utilizando um algoritmo de repetição, obtemos uma aproximação tão perto do valor real quanto quisermos, chegando a uma solução final através de métodos de parada. 
	Projeto 
	O problema proposto consiste em encontrar o vetor-solução de equações de um sistema linear. Chegando a essa solução através de 3 métodos iterativos: a saber, o de Gauss-Jordan (c/ pivotação e s/ pivotação), o de Jacobi e o de Gauss-Seidel. Para tanto, o usuário poderá escolher um vetor de aproximação inicial, um número máximo de iterações (M), e um valor máximo de erro absoluto (ε- épsilon) que lhe couber. Caso não deseje introduzir, o programa toma como aproximação inicial o vetor nulo, ε=10-6 e M=1.000.
	 Métodos Iterativos
	Método de Gauss-Jordan sem pivotação
	
	Método de Gauss-Jordan com pivotação
	
	Método de Jacobi
	
	Método de Gauss-Seidel 
	
	Qualquer número- Todos os Métodos anteriormente listados.
	
 Tabela 1
	
	A escolha dos métodos é feita de acordo com a Tabela 1. Ao ser iniciado, o programa pede para que o usuário digite o número de equações (ou variáveis), cada elemento xi e resultado bi de cada equação, para a montagem do sistema. O programa escreve o sistema e pergunta qual método deseja utilizar, assim como na Tabela Apresentada. Se o número, o qual corresponderá sua escolha, for maior ou igual a 3, ou seja, se escolher os Métodos de Jacobi, Gauss-Seidel, ou todos, o programa pergunta se você deseja introduzir uma aproximação inicial, e se deseja determinar M e ε. Além disso, na escolha desses métodos (quando nº>=3, referente à tabela1) é analisado se o a matriz resultante do sistema é estritamente dominante, caso contrário, ele faz uso da pivotação parcial, permutação de linhas ou colunas, para assim torná-la, se ainda assim não for possível, o sistema é dado como impossível de obter uma solução. O vetor solução apresentado após a aplicação dos métodos, é dado com 8 decimais e arredondamento padrão. 
	Limitações do Software
	
	Listamos abaixo as limitações do software:
A matriz resultante do sistema de equações lineares, deve ser ou poderá se tornar, estritamente diagonalmente dominante, caso contrário o sistema é dado como impossível.
O sistema deve ser tal que a matriz de seus coeficientes seja do tipo n x n, ou seja deve conter equações em mesmo número de variáveis. E com 0<n<=50.
	
	Conclusão
Apesar das limitações citadas, o programa é bastante útil, por através dos métodos iterativos encontrar o vetor-solução, de um sistema de equações lineares, com mais precisão, aproximação, e mais rápido (por ter menos quantidades de operações) que os métodos diretos( a exemplo,Gauss-Jordan). Tendo como o mais eficiente, com menor erro absoluto e número de operações, o método de Gauss-Seidel. 
	Bibliografia
[1] J. D. dos Santos, Z. C. da Silva, Métodos Numéricos, Ed. Universitária UFPE, 3ª edição, 2010.
Program CNRenato;
uses crt;
type tipoMatriz = array[1..50,1..50] of double;
var sistema: tipoMatriz;
var resultadoSistema: array[1..50] of double;
var resposta, inicio, passoAntigo: array[1..50] of double;
var epsilon: double;
var M: integer;
var N: integer;
var tipo: integer;
var sn,sn2: char;
{Escreve uma matriz na tela}
procedure EscreveMatriz(Matriz:tipoMatriz);
var i,j: integer;
begin
 writeln('');
 for i:=1 to N do
 begin
 write ('|');
 for j:=1 to N do
 write (Matriz[i,j]);
 writeln('| ',resultadoSistema[i],'|');
 end;
 writeln('');
end;
{Le o sistema inicial}
procedure LeitorSistema;
 var i,j:integer;
 begin
 for i:=1 to N do
 begin
 for j:=1 to N do
	begin
	write('Escolha a parametro de x',j,' na equacao ', i,': ');
	read( sistema[i,j] );
 end;
 end;
 for i:=1 to N do
 begin
 write('Escolha o resultado da equacao',i,': ');
 read(resultadoSistema[i]);
 end;
end;
{Escolhe o vetor inicial}
procedure LeEntrada;
 var i:integer;
 begin
 for i:=1 to N do
 begin
	write('Escolha a posicao inicial ',i,': ');
	read( inicio[i] );
 end;
end;
{Escreve o vetor resposta}
procedure EscreveResposta;
var i:integer;
begin
 write ('[');
 for i:=1 to N do
 write (resposta[i],' ');
 writeln(']');
end;
procedure Swap(var a:double; var b:double);
var c:double;
begin
c:=a;
a:=b;
b:=c;
end;
{Organiza o sistema para se tornar dominante}
procedure ArrumaSistema;
var L: array [1..50] of integer;
var respostaTemp: array[1..50] of double;
var i,j,maxIdx: integer;
var max,soma:double;
var temp:tipoMatriz;
begin
 for i:=1 to N do
 begin
 L[i]:=i;
 max:= abs(sistema[i,i]);
 soma:=0;
 for j:=1 to N do
 begin
 if (j<> i) then
	soma:= soma + abs(sistema[i,j]);
 if (sistema[i,j] > max) then
 begin
	max := sistema[i,j];
	maxIdx := j;
 end;
 end;
 if (soma > sistema[i,i]) then L[i] := maxIdx;
 end;
 for i:=1 to N do
 begin
 if (L[i] = 0) then
 begin
 writeln('Sistema Impossível!');
 end;
 end;
 for i:=1 to N do
 begin
 for j:=1 to N do
 temp[L[i],j] := sistema[i,j];
 respostaTemp[L[i]] := resultadoSistema[i];
 end;
 for i:=1 to N do
 begin
 for j:=1 to N do
 sistema[i,j] := temp[i,j];
 resultadoSistema[i]:=respostaTemp[i];
 end;
end;
{Testa se o sistema convergiu}
function TestaConvergencia: boolean;
var i:integer;
var max, temp:double;
begin
 max:=0;
 for i:=1 to N do
 begin
 temp := abs((resposta[i] - passoAntigo[i])/resposta[i]);
 if (temp > max) then max := temp;
 end;
 TestaConvergencia := max > epsilon;
end;
{As funções seguintes testam asdominancias}
function DominanciaPorLinha:boolean;
var soma: double;
var i,j: integer;
begin
 for i:=1 to N do
 begin
 soma := 0;
 for j:=1 to N do
 if (i <> j) then soma := soma + sistema[i,j];
 if (soma > sistema[i,i]) then DominanciaPorLinha := false;
 end;
 DominanciaPorLinha := true;
end;
function DominanciaPorColuna:boolean;
var soma: double;
var i,j: integer;
begin
 for i:=1 to N do
 begin
 soma := 0;
 for j:=1 to N do
 if (i <> j) then soma := soma + sistema[j,i];
 if (soma > sistema[i,i]) then DominanciaPorColuna := false;
 end;
 DominanciaPorColuna := true;
end;
function Dominancia:boolean;
begin
 Dominancia := (DominanciaPorColuna or DominanciaPorLinha);
end;
{Função para o método de Jacobi}
procedure Jacobi;
var soma: double;
var i,j,k,counter:integer;
begin
 counter:=0;
 for i:=1 to N do
 resposta[i] := inicio[i];
 repeat;
 counter:=counter+1;
 for i:=1 to N do
 passoAntigo[i]:= resposta[i];
 for i:=1 to N do
 begin
 soma:=resultadoSistema[i];
 for j:=1 to N do
 begin
	if (j<> i) then
	 soma := soma - passoAntigo[j]*sistema[i,j];
 end;
 resposta[i]:= soma/sistema[i,i];
 end;
 until ((not TestaConvergencia) and ( M > counter));
end;
{Função para o método de Gauss-Seidel}
procedure GaussSeidel;
var soma: double;
var i,j,k,counter:integer;
begin
 counter:=0;
 for i:=1 to N do
 resposta[i] := inicio[i];
 repeat;
 counter:=counter+1;
 for i:=1 to N do
 passoAntigo[i]:= resposta[i];
 for i:=1 to N do
 begin
 soma:=resultadoSistema[i];
 for j:=1 to N do
 begin
	if (j<> i) then
	 soma := soma - resposta[j]*sistema[i,j];
 end;
 resposta[i]:= soma/sistema[i,i];
 end;
 until ((not TestaConvergencia) and ( M > counter));
end;
{Função para o método de Jordan}
procedure Jordan;
var i,j,k: integer;
var divisor,multiplicador: double;
var sistemaTemp : tipoMatriz;
begin
	for i:=1 to N do
	begin
	 resposta[i] := resultadoSistema[i];
		for j:=1 to N do
			sistemaTemp[i,j] := sistema[i,j];
	end;
	for i:=1 to N do
	begin
		divisor := sistemaTemp[i,i];
		for j:=1 to N do
			sistemaTemp[i,j] := sistemaTemp[i,j] / divisor;
		resposta[i] := resposta[i]/divisor;
		for j:=1 to N do
		begin
			if (j <> i) then
			begin
				multiplicador := sistemaTemp[j,i];	
				resposta[j] := resposta[j] - resposta[i] * multiplicador;
				for k:=1 to N do
					sistemaTemp[j,k] := sistemaTemp[j,k] - sistemaTemp[i,k] * multiplicador;
			end;
		end;
	end;
end;
{Função para o método de Jordan com Pivotação Parcial}
procedure JordanPivotante;
var i,j,k: integer;
var divisor,multiplicador: double;
var sistemaTemp : tipoMatriz;
begin
	for i:=1 to N do
	begin
	 resposta[i] := resultadoSistema[i];
		for j:=1 to N do
			sistemaTemp[i,j] := sistema[i,j];
	end;
	{Aqui entra a pivotação parcial}
	for i:=1 to N do
	begin
		divisor := sistemaTemp[i,i];
		for j:=1 to N do
			sistemaTemp[i,j] := sistemaTemp[i,j] / divisor;
		resposta[i] := resposta[i]/divisor;
		for j:=1 to N do
		begin
			if (j <> i) then
			begin
				multiplicador := sistemaTemp[j,i];	
				resposta[j] := resposta[j] - resposta[i] * multiplicador;
				for k:=1 to N do
					sistemaTemp[j,k] := sistemaTemp[j,k] - sistemaTemp[i,k] * multiplicador;
			end;
		end;
	end;
end;	
procedure Inicializa;
var i:integer;
begin
 epsilon := 1e-6;
 M:= 1000;
 for i:=1 to N do
 begin
 inicio[i] := 0;
 resposta[i] :=0;
 end;
end;
procedure EscolheMetodo(metodo:integer);
begin
 case metodo of
 1: begin
	writeln('Utilizando o Gauss-Jordan');
	Jordan;
	EscreveResposta;
	end;
 2: begin
	writeln('GJ com PVT');
	JordanPivotante;
	EscreveResposta;
	end;
 3: begin
	writeln('Utilizando Jacobi');
	Jacobi;
	EscreveResposta;
	end;
 4: begin
	writeln('GaussSeidel');
	GaussSeidel;
	EscreveResposta;
	end;
 else
 EscolheMetodo(1);
 EscolheMetodo(2);
 EscolheMetodo(3);
 EscolheMetodo(4);
 end;
end;
begin
sn := 'k';
Inicializa;
{
sistema[1,1] := 3;
sistema[1,2] := 6;
sistema[1,3] := -2;
sistema[2,1] := 2;
sistema[2,2] := -4;
sistema[2,3] := 10;
sistema[3,1] := 5;
sistema[3,2] := 2;
sistema[3,3] := 1;
resultadoSistema[1] := 7;
resultadoSistema[2] := 8;
resultadoSistema[3] := 8;
inicio[1] :=0;
inicio[2] :=0;
inicio[3] :=0;
N := 3;
}
repeat
 write('Escolha o numero de variaveis: ');
 read (N);
until ((N < 50) and (N>0));
LeitorSistema;
EscreveMatriz(sistema);
writeln ('1 - Método de Gauss-Jordan sem pivotação');
writeln ('2 - Método de Gauss-Jordan com pivotação parcial');
writeln ('3 - Método de Jacobi');
writeln ('4 - Método de Gauss-Seidel');
writeln ('Outro número - Todos os métodos anteriormente listados');
repeat
 write ('Escolha algoritimo para resolver: ');
 read(tipo);
until (tipo >0);
if (tipo >= 3) then
 begin
 if ((Dominancia)) then
 begin
 writeln('Sistema não é dominante.');
 writeln('Arrumando o sistema');
 ArrumaSistema;
 writeln('Sistema Organizado: ');
 EscreveMatriz(sistema);
 end;
 write('Deseja escolher o vetor inicial? (s/n)');
 read (sn);
 if (sn = 's') then
 begin
 leEntrada;
 end;
 end;
write('Deseja escolher epsilon e M?');
read(sn2);
if (sn2 = 's') then
 begin
 write ('Escolhe epsilon: ');
 read (epsilon);
 write ('Escolha M: ');
 read (M);
 end;
EscolheMetodo(tipo);
readkey
end.