TRABALHO DE ALGORITMO I

Prévia do material em texto

UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO 
CENTRO TECNOLÓGICO 
CURSO DE ENGENHARIA CIVIL 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
RELATÓRIO ALGORITMOS NUMÉRICOS 
 
 
 
 
 
 
 
 
 
 
 
VITÓRIA 
2017 
 
 
 
 
 
 
 
 
 
 
RELATÓRIO DE ALGORITMOS NUMÉRICOS 
 
 
 
 
 
 
 
 
 
Relatório apresentado como requisito 
parcial para obtenção de aprovação na 
disciplina de Algoritmos numéricos I 
apresentada no curso de Engenharia Civil 
da Universidade Federal do Espírito 
Santo, ministrada pela professora. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
VITÓRIA 
2 
LISTA DE GRÁFICOS 
 
GRÁFICO 1: Número de operações para uma matriz com n =10. ............................. 8 
GRÁFICO 2: Número de operações Matriz com n = 50 ............................................. 9 
GRÁFICO 3: Número de operações Matriz com n=100 .............................................. 9 
GRÁFICO 4: Número de operações Matriz com n=200 e n=400 ............................. 10 
GRÁFICO 5: Número de operações Matriz com n=1000 .......................................... 10 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
SUMÁRIO 
 
1. INTRODUÇÃO .............................................................................................................................. 5 
2. MÉTODO NUMÉRICO ................................................................................................................ 6 
2.1. Método de eliminação de Gauss para sistema pentadiagonal .............................. 6 
3. EXPERIMENTOS NUMÉRICOS ................................................................................................ 7 
3.1. Situação A ............................................................................................................................ 7 
3.2. Analise dos dados.............................................................................................................. 9 
3.2.1. Teste 1: Matriz A com dimensão n = 50 ................................................................ 9 
3.2.2. Teste 2: Matriz A com dimensão n = 100 .............................................................. 9 
3.2.3. Teste 3: Matriz A com dimensão n = 200 e n = 400.......................................... 10 
3.2.4. Teste 4: Matriz A com dimensão n = 1000 ......................................................... 10 
3.2.5. Eficiência do Método pentadiagonal ................................................................... 11 
4. CÓDIGO ....................................................................................................................................... 11 
5. REFERÊNCIAS .......................................................................................................................... 17 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1. INTRODUÇÃO 
 
Este trabalho tem como objetivo comparar o esforço computacional para resolução de 
um sistema de equações lineares do tipo pentadiagonal utilizando método de Gauss 
tradicional e uma versão específica para o caso pentadiagonal. 
 
Um sistema linear pentadiagonal é caracterizado por seus elementos da diagonal 
principal e das diagonais superiores e inferiores à diagonal principal serem os únicos 
elementos não nulos do sistema. 
 
Diante disto, a proposta foi de construir um algoritmo para minimizar o esforço 
computacional, reduzindo o número de operações. Isto foi possível mediante 
operações com os elementos não nulos ao longo da triangularização. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2. MÉTODO NUMÉRICO 
 
2.1. Método de eliminação de Gauss para sistema pentadiagonal 
 
O método utilizado consiste em não acessar as posições onde há zeros. Sabendo que 
a matriz de entrada será uma pentadiagonal, é possível prever em que posições 
haverá zeros, de modo que não seja necessário realizar operações nessas posições. 
 
Percorrendo a matriz em busca do melhor pivô com a função pivoteamento, é possível 
encontrarmos posições de pivô desde pivo = 0 até pivo = (n – 2). Encontrado o melhor 
pivô e realizando as operações do tipo, trocas de linhas, quando necessárias, 
inicializamos a triangularização. É no processo de triangularização e no cálculo do 
vetor solução, que será possível otimizar o código não acessando posições 
desnecessárias, posições nulas. 
 
Para percorrer as linhas, utilizamos um for que vai de i = (pivo+1) até (i < pivo+4 && 
i < n), não é necessário percorrer as linhas depois de (pivo+3), pois seus coeficientes 
são zero. 
 
Para percorrer as colunas, utilizamos um for que vai de j = (pivo+1) até (j < pivo+6 && 
j < n), percorrendo até (pivo + 5) evita-se acessar posições desnecessárias. 
 
Embora este método não previna o acesso de algumas posições desnecessárias, o 
método projetado para tratar um sistema pentadiagonal é mais eficiente em relação 
ao método de Gauss tradicional quando estamos comparando o número de operações 
realizadas. 
 
 
 
 
 
 
 
 
 
3. EXPERIMENTOS NUMÉRICOS 
 
Neste trabalho computacional, trataremos de 2 situações que foram definidos pela 
professora da disciplina. 
 
Situação A: Apresentar um problema de dimensão 𝒏 = 10 , que já é conhecida as 
soluções. E comparar a quantidade de operações da versão utilizando eliminação de 
Gauss tradicional e utilizar a versão pentadiagonal. 
 
Situação B (Analise de Dados): Apresentar número de operações realizadas, por cada 
versão do algoritmo de eliminação de Gauss, para os cinco problemas lineares 
tratados , com dimensão 𝒏 = 50; 𝒏 = 100; 𝒏 = 200, 𝒏 = 400 e 𝒏 = 1000 . E 
analisar graficamente. 
 
3.1. Situação A 
 
Utilizando um sistema do 𝐴𝑥 = 𝑏 , com a seguinte formatação: 
Onde A é uma matriz de dimensão n = 10. 
 
































10120000000
11012000000
21101200000
02110120000
00211012000
00021101200
00002110120
00000211012
00000021101
00000002110
 . 
































10
9
8
7
6
5
4
3
2
1
X
X
X
X
X
X
X
X
X
X
 = 
































125
122
128
112
96
80
64
48
32
18
 
 
 
 
 
 
 
Temos como solução, utilizando como exemplo a linha L1: 
 
10𝑋1 + 1𝑋2 + 2𝑋3 + 0𝑋4 + ⋯ + 0𝑋10 = 18 
10(1) + 1(2) + 2(3) + 0(4) + ⋯ 0(10) = 18 
 
































10120000000
11012000000
21101200000
02110120000
00211012000
00021101200
00002110120
00000211012
00000021101
00000002110
 . 
































10
9
8
7
6
5
4
3
2
1
 = 
































125
122
128
112
96
80
64
48
32
18
 
 
Número de operações método Gauss pentadiagonal: 364 
Número de operações método Gauss tradicional: 815 
 
 
GRÁFICO 1: NÚMERO DE OPERAÇÕES PARA UMA MATRIZ COM N=10. 
 
815
364
0
100
200
300
400
500
600
700
800
900
10N
ú
m
er
o
 d
e 
o
p
er
aç
õ
es
Dimensão 
Gauss Tradicional
Metodo pentadiagonal
 
3.2. Analise dos dados 
 
Comparando o número de operações coletadas ao resolver matrizes de dimensões 
𝒏 = 50; 𝒏 = 100; 𝒏 = 200, 𝒏 = 400 e 𝒏 = 1000 
 
3.2.1. Teste 1: Matriz A com dimensão n = 50 
 
 
GRÁFICO 2: NUMERO DE OPERAÇÕES MATRIZ COM DIMENSÃO N=50 
 
3.2.2. Teste 2: Matriz A com dimensão n = 100 
 
GRÁFICO 3: NÚMERO DE OPERAÇÕES MATRIZ COM DIMENSÃO N=100 
87075
2404
0
20000
40000
60000
80000
100000
50
N
ú
m
e
ro
 d
e
 o
p
e
ra
çõ
e
s
Dimensões
Gauss Tradicional X Método Pentadiagonal
Gauss Tradicional Método pentadiagonal
681650
4954
0
100000
200000
300000
400000
500000
600000
700000
800000
100
N
ú
m
e
ro
 d
e
 o
p
e
ra
çõ
e
s
Dimensão (N)
Gauss Tradicional X Método Pentadiagonal
Gauss Tradicional Método pentadiagonal
3.2.3. Teste 3: Matriz A com dimensão n = 200 e n = 400 
 
 
GRÁFICO 4: NÚMERO DE OPERAÇÕES MATRIZ COM DIMENSÃO N=200 E N=400 
 
3.2.4. Teste 4: Matriz A com dimensão n = 1000 
 
GRÁFICO 5: MATRIZ COM DIMENSÃO N=1000 
 
 
 
 
 
200 400
Gauss Tradicional 5393300 42906600
Método pentadiagonal 10054 20254
5393300
42906600
10054 20254
0
10000000
20000000
30000000
40000000
50000000
N
ú
m
e
ro
 d
e
 o
p
e
ra
çõ
e
s
Dimensão (N)
Gauss Tradicional X Método Pentadiagonal
Gauss Tradicional Método pentadiagonal
1000
Gauss Tradicional 668166500
Método Pentadiagonal 50854
N
ú
m
e
ro
 d
e
 o
p
e
ra
çõ
e
s
Dimensão (N)
Gauss Tradicional X Método Pentadiagonal
Gauss Tradicional Método Pentadiagonal
 
3.2.5. Eficiência do Método pentadiagonal 
 
 
 
 
 
 
 
 
 
A eficiência mede quantas vezes a menos o método pentadiagonal faz operações em 
relação ao método de Gauss tradicional. 
 
𝐸 =
𝑁𝑢𝑚𝑒𝑟𝑜 𝑑𝑒 𝑜𝑝𝑒𝑟𝑎ç𝑜𝑒𝑠 𝑝𝑜𝑟 𝐺𝑎𝑢𝑠𝑠 𝑇𝑟𝑎𝑑𝑖𝑐𝑖𝑜𝑛𝑎𝑙 
𝑁𝑢𝑚𝑒𝑟𝑜 𝑑𝑒 𝑜𝑝𝑒𝑟𝑎ç𝑜𝑒𝑠 𝑑𝑜 𝑚é𝑡𝑜𝑑𝑜 𝑃𝑒𝑛𝑡𝑎𝑑𝑖𝑎𝑔𝑜𝑛𝑎𝑙 
 
 
Com isso observamos que, embora o método projetado para tratar um sistema 
pentadiagonal não preveniu os acessos a algumas posições desnecessárias, ele 
ainda é muito mais eficiente em relação ao método de Gauss tradicional, quando 
comparamos o número de operações realizadas. 
 
4. CÓDIGO 
 
#include <stdio.h> 
#include <math.h> 
#include <stdlib.h> 
#include <time.h> 
 
int gaussPentadiagonal(int n, double dA, double dB, double dP, double dC, double dD, 
double vetorB[], double vetorX[]); 
int gaussTradicional(int n, double dA, double dB, double dP, double dC, double dD, 
double vetorB[], double vetorX[]); 
void gerarMatriz(int n, double matriz[][n], double dA, double dB, double dP, double dC, 
double dD); 
void copiarVetor(int n, double destino[], double fonte[]); 
void definirB(int n, double vetorB[], int criarB); 
void trocarLinhas(int n, double matriz[][n], int linha1, int linha2); 
 
NÚMERO DE OPERAÇÕES 
Dimensões(n) 
Gauss 
Tradicional 
Método 
Pentadiagonal 
Eficiência 
50 87075 2404 36,22 
100 681650 4954 137,60 
200 5393300 10054 536,43 
400 42906600 20254 2118,43 
1000 668166500 50854 13138,92 
void pivoteamento(int n, double matriz[][n], double vetorB[], int pivo); 
void imprimirMatriz(int n, double matriz[][n]); 
void imprimirVetor(int n, double vetor[]); 
 
 
void main(){ 
 
 int n; 
 int contadorPentadiagonal, contadorTradicional; 
 int criarB, mostrarX; 
 double dA, dB, dP, dC, dD; 
 
 srand(time(NULL)); 
 
 printf("Forneca a dimensao da matriz.\n"); 
 scanf("%d", &n); 
 
 double vetorX[n]; 
 double vetorB[n]; 
 
 printf("Forneca os coeficientes da matriz (dA, dB, dP, dC e dD)\n"); 
 scanf("%lf %lf %lf %lf %lf", &dA, &dB, &dP, &dC, &dD); 
 
 do{ 
 printf("\nDeseja gerar ou fornecer o vetor b?\n"); 
 printf("(1) - Gerar\n(2) - Fornecer\n\n"); 
 scanf("%d", &criarB); 
 } 
 while(criarB != 1 && criarB != 2); 
 
 definirB(n, vetorB, criarB); 
 
 
 contadorPentadiagonal = gaussPentadiagonal(n, dA, dB, dP, dC, dD, vetorB, vetorX); 
 contadorTradicional = gaussTradicional(n, dA, dB, dP, dC, dD, vetorB, vetorX); 
 
 do{ 
 printf("\nDeseja mostrar o vetor solucao?\n"); 
 printf("(1) - Sim\n(2) - Nao\n\n"); 
 scanf("%d", &mostrarX); 
 } 
 while(mostrarX != 1 && mostrarX != 2); 
 
 if(mostrarX == 1){ 
 printf("Vetor solucao: "); 
 imprimirVetor(n, vetorX); 
 } 
 
 printf("Numero de operacoes metodo Gauss pentadiagonal: %d\n", 
contadorPentadiagonal); 
 printf("Numero de operacoes metodo Gauss tradicional: %d\n\n", 
contadorTradicional); 
 
}//parentese da main 
 
 
//Método de eliminação de Gauss para resolver um sistema linear pentadiagonal 
int gaussPentadiagonal(int n, double dA, double dB, double dP, double dC, double dD, 
double vetorB[], double vetorX[]){ 
 
 double matriz[n][n]; 
 double copiaVetorB[n]; 
 int contador; 
 
 contador = 0; 
 
 gerarMatriz(n, matriz, dA, dB, dP, dC, dD); 
 copiarVetor(n, copiaVetorB, vetorB); 
 
 //Escalonamento. 
 int i, j, pivo; 
 double m; 
 for(pivo=0; pivo<n-1; pivo++){ 
 pivoteamento(n, matriz, copiaVetorB, pivo); 
 for(i=pivo+1; i<pivo+4 && i<n; i++){ 
 m = matriz[i][pivo]/matriz[pivo][pivo]; 
 contador += 1; 
 for(j=pivo+1; j<pivo+6 && j<n; j++){ 
 matriz[i][j] = matriz[i][j] - m*matriz[pivo][j]; 
 contador += 2; 
 } 
 copiaVetorB[i] = copiaVetorB[i] - m*copiaVetorB[pivo]; 
 contador += 2; 
 } 
 } 
 
 //Solução. 
 double soma; 
 for(i=n-1; i>=0; i--){ 
 soma = 0; 
 for(j=i+1; j<i+6 && j<n; j++){ 
 soma = soma + matriz[i][j]*vetorX[j]; 
 contador += 2; 
 } 
 vetorX[i] = (copiaVetorB[i] - soma)/matriz[i][i]; 
 contador += 2; 
 } 
 
 return contador; 
} 
 
//Método de eliminação de Gauss para resolver um sistema com o algoritmo tradicional 
int gaussTradicional(int n, double dA, double dB, double dP, double dC, double dD, 
double vetorB[], double vetorX[]){ 
 
 double matriz[n][n]; 
 double copiaVetorB[n]; 
 int contador; 
 
 contador = 0; 
 
 gerarMatriz(n, matriz, dA, dB, dP, dC, dD); 
 copiarVetor(n, copiaVetorB, vetorB); 
 
 //Escalonamento. 
 int i, j, pivo; 
 double m; 
 for(pivo=0; pivo<n-1; pivo++){ 
 pivoteamento(n, matriz, copiaVetorB, pivo); 
 for(i=pivo+1; i<n; i++){ 
 m = matriz[i][pivo]/matriz[pivo][pivo]; 
 contador += 1; 
 matriz[i][pivo] = 0;//APAGAR 
 for(j=pivo+1; j<n; j++){ 
 matriz[i][j] = matriz[i][j] - m*matriz[pivo][j]; 
 contador += 2; 
 } 
 copiaVetorB[i] = copiaVetorB[i] - m*copiaVetorB[pivo]; 
 contador += 2; 
 } 
 } 
 
 //Solução. 
 double soma; 
 for(i=n-1; i>=0; i--){ 
 soma = 0; 
 for(j=i+1; j<n; j++){ 
 soma = soma + matriz[i][j]*vetorX[j]; 
 contador += 2; 
 } 
 vetorX[i] = (copiaVetorB[i] - soma)/matriz[i][i]; 
 contador += 2; 
 } 
 
 return contador; 
} 
 
void gerarMatriz(int n, double matriz[][n], double dA, double dB, double dP, double dC, 
double dD){ 
 
 int i, j; 
 for(i=0; i<n; i++){ 
 
 for(j=0; j<n; j++){ 
 
 if(i == j + 2) {matriz[i][j] = dA;} 
 else if(i == j + 1) {matriz[i][j] = dB;} 
 else if(i == j) {matriz[i][j] = dP;} 
 else if(i == j - 1) {matriz[i][j] = dC;} 
 else if(i == j - 2) {matriz[i][j] = dD;} 
 else {matriz[i][j] = 0;} 
 } 
 } 
} 
 
void copiarVetor(int n, double destino[], double fonte[]){ 
 
 int i; 
 for(i=0; i<n; i++){ 
 destino[i] = fonte [i]; 
 } 
} 
 
void definirB(intn, double vetorB[], int criarB){ 
 
 if(criarB == 1){ 
 int i; 
 for(i=0; i<n; i++){ 
 vetorB[i] = ((rand()%2000)-1000)/100; //Gera numeros de -9.99 até 9.99 para 
facilitar os testes. 
 } 
 } 
 else{ 
 int i; 
 for(i=0; i<n; i++){ 
 scanf("%lf", &vetorB[i]); 
 } 
 } 
} 
 
void trocarLinhas(int n, double matriz[][n], int linha1, int linha2){ 
 
 int j; 
 double aux; 
 for(j=0; j<n; j++){ 
 aux = matriz[linha1][j]; 
 matriz[linha1][j] = matriz[linha2][j]; 
 matriz[linha2][j] = aux; 
 } 
} 
 
void pivoteamento(int n, double matriz[][n], double vetorB[], int pivo){ 
 
 int i, linhaMaior; 
 linhaMaior = pivo; 
 for(i=pivo+1; i<n; i++){ 
 if(fabs(matriz[linhaMaior][pivo]) < fabs(matriz[i][pivo])){ 
 linhaMaior = i; 
 } 
 } 
 trocarLinhas(n, matriz, linhaMaior, pivo); 
 
 //Troca dois elementos de B. 
 double aux; 
 aux = vetorB[pivo]; 
 vetorB[pivo] = vetorB[linhaMaior]; 
 vetorB[linhaMaior] = aux; 
} 
 
void imprimirMatriz(int n, double matriz[][n]){ 
 
 int i, j; 
 for(i=0; i<n; i++){ 
 for(j=0; j<n; j++){ 
 printf("%12f ", matriz[i][j]); 
 } 
 printf("\n"); 
 } 
 printf("\n\n"); 
} 
 
void imprimirVetor(int n, double vetor[]){ 
 
 int i; 
 for(i=0; i<n; i++){ 
 printf("%f ", vetor[i]); 
 } 
 printf("\n\n"); 
} 
 
 
 
 
 
 
 
 
 
5. REFERÊNCIAS 
 
CAMPOS, F. F. Algoritmos Numéricos. 2ª ed. Belo Horizonte : LTC, 2007. 
CANALE, R. P.; CHAPRA, S. C. Métodos Numéricos para Engenharia. 5ª ed. Porto Alegre 
: AMGH, 2011.