UNIVERSIDADE FEDERAL RURAL DO SEMIÁRIDO - UFERSA ... · do método de Sobre Relaxação Sucessiva - SRS, ... exemplo, na análise de um circuito elétrico, no cálculo estrutural

UNIVERSIDADE FEDERAL RURAL DO SEMIÁRIDO - UFERSADEPARTAMENTO DE CIÊNCIAS EXATAS, TECNOLÓGICASE HUMANAS - DCETHCAMPUS ANGICOSBACHARELADO EM CIÊNCIA E TECNOLOGIA

ANDERSON REIS DA SILVA

ESTUDO DO MÉTODO DE SOBRE RELAXAÇÃO SUCESSIVA NA RESOLUÇÃO DESISTEMAS DE EQUAÇÕES LINEARES

ANGICOS-RN2013

ANDERSON REIS DA SILVA

ESTUDO DO MÉTODO DE SOBRE RELAXAÇÃO SUCESSIVA NA RESOLUÇÃO DESISTEMAS DE EQUAÇÕES LINEARES

Monografia apresentada a UniversidadeFederal Rural do Semi-Árido - UFERSA,Campus Angicos para a obtenção do titu-lo de Bacharelado em Ciência e Tecnolo-gia. Orientador: Prof. Ms. Matheus daSilva Menezes - UFERSA

ANGICOS-RN2013

A Francisco Ferreira da Silva [in memoriam] meu grande pai, cuja sabedoria me ensinou aefetuar as primeiras operações matemáticas e por ele que tenho uma grande paixão pornúmeros e cálculos, quando o vi partir me deixou com um grande vazio no peito.

A toda a minha família, minha mãe Lucia Reis da Silva e minha querida irmã Luciana Reisda Silva, que são pessoas que sempre me ajudaram para que eu nunca desistisse dos meus

objetivos.

AGRADECIMENTOS

Agradeço primeiramente a Deus por me proporcionar tamanho felicidade assim como colocarem meu caminho sempre pessoas boas que me ajudaram a seguir o meu caminho vencendotodos os obstáculos.

A minha família por sempre me apoiar, me incentivar e acreditar em meu destino, sem nuncapensar duas vezes quando o assunto é estudar e crescer na vida.

Ao meu orientador Matheus da Silva Menezes que mesmo com todas as dificuldades sempreacreditou e mostrou-se disposto a ajudar e a acrescentar com seu vasto conhecimento em meutrabalho assim como em toda a minha vida acadêmica.

A meu grande amigo Luiz Carlos Guimarães Filho e a toda a sua família por sempre meapoiarem e me darem à mão em momentos difícil deste o inicio da minha jornada, este é umamigo que considero um irmão e que guardo e sempre guardarei no lado esquerdo do peito.

A minha noiva Elisllayni Lopes Silva, que sempre esteve do meu lado me incentivando e acon-selhando na minha jornada, em momentos de raiva, tristeza, felicidades e conquistas. Obrigadomeu amor.

Ao meu querido sobrinho Gabriel Reis Lopes por nos momentos de raiva e tristeza sempreme fazer sorrir e brincar, mesmo não sabendo falar ou entender o que passamos na vida, ele éuma companhia que me faz ver o mundo com bons olhos.

A todos os professores que contribuíram para que eu conseguisse chegar até aqui, me pas-sando um pouco de seus conhecimentos e disciplinas, considero vocês como mestres, e semprevou lembrar os momentos de aprendizados que vocês proporcionaram nesta instituição.

Aos meus amigos de turma em que passei grande parte do tempo, muitas vezes até mais doque minha própria família, isso seja por que vocês se tornaram minha segunda família.

Ao meu amigo Emerson Talles Pessoa Adelino que nesta reta final está sendo muito impor-tante na elaboração desse trabalho.

A todos os meus amigos de longas datas que me auxiliaram direta ou indiretamente com meusestudos, a aqueles motoristas que sempre me guiaram com segurança todos os dias no percursode ida e vinda à universidade.

Fico muito grato a todos que acreditaram na minha luta buscando encontrar e alcançar umfuturo melhor, mesmo sabendo que o caminho não é fácil, acreditem se não tivesse vocês naminha vida nunca conseguiria chegar onde estou. Muito obrigado a todos.

RESUMO

É de suma importância o estudo de métodos numéricos de resolução de sistemas lineares, poisem uma grande quantidade de problemas no dia a dia encontram-se sistemas de equações line-ares de várias características. Por esse motivo, o presente trabalho é constituído de um estudodo método de Sobre Relaxação Sucessiva - SRS, realizando uma análise de seu funcionamento,de suas aplicações e de seus resultados em comparação com outros dois métodos iterativos jáconsagrados que são os métodos de Jacobi e Gauss-Seidel. Os testes são realizados com o auxi-lio computacional de um software denominado de Scilab. É importante destacar que o métodoteve sua convergência provada de acordo com os requisitos das condições de convergência paraesse método. Para a realização dos testes foram escolhidos sete problemas com característicasdistintas, sendo que em quatro problemas o método de SRS foi superior aos demais métodos.Dessa maneira provando que o método é uma ótima alternativa para utilização de métodos itera-tivos. A principal desvantagem do método em relação aos demais é a escolha de um valor deômega adequado para cada problema, sendo esse um parâmetro necessário e importante queinfluenciou em grande escala os resultados para cada problema.

Palavras chave: Métodos numéricos. Sistemas lineares. Sobre Relaxação Sucessiva. Con-vergência.

LISTA DE TABELAS

Tabela 1 - Tabela dos valores de omega utilizados nos testes . . . . . . . . . . . . . 27Tabela 2 - Dados referentes ao computador utilizado nos testes . . . . . . . . . . . 28Tabela 3 - Dados referentes ao sistema operacional utilizado nos testes . . . . . . . 28Tabela 4 - Algoritmo utilizado para o método de Jacobi . . . . . . . . . . . . . . . 29Tabela 5 - Algoritmo utilizado para o método de Gauss-Seidel . . . . . . . . . . . . 30Tabela 6 - Algoritmo utilizado para o método de Sobre Relaxação Sucessiva - SRS . 31Tabela 7 - Dados referentes ao problema m30 . . . . . . . . . . . . . . . . . . . . 32Tabela 8 - Dados referentes ao problema BCSSTRUC1 . . . . . . . . . . . . . . . 33Tabela 9 - Dados referentes ao problema pde225 . . . . . . . . . . . . . . . . . . . 33Tabela 10 - Dados referentes ao problema MCFE . . . . . . . . . . . . . . . . . . . 34Tabela 11 - Dados referentes ao problema GR3030 . . . . . . . . . . . . . . . . . . 35Tabela 12 - Dados referentes ao problema SHERMAN1 . . . . . . . . . . . . . . . . 36Tabela 13 - Dados referentes ao sétimo problema SHERMAN4 . . . . . . . . . . . . 36Tabela 14 - Resultados para os métodos de Jacobi e Gauss-Seidel para o problema m30 38Tabela 15 - Resultados para os métodos SRS para o problema m30 . . . . . . . . . . 38Tabela 16 - Resultados para os métodos de Jacobi e Gauss-Seidel para o problema

BCSSTRUC1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39Tabela 17 - Resultados para os métodos SRS para o problema BCSSTRUC1 . . . . . 40Tabela 18 - Resultados para os métodos de Jacobi e Gauss-Seidel para o problema

pde225 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41Tabela 19 - Resultados para os métodos SRS para o problema pde225 . . . . . . . . 41Tabela 20 - Resultados para os métodos de Jacobi e Gauss-Seidel para o problema

MCFE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42Tabela 21 - Resultados para os métodos SRS para o problema MCFE . . . . . . . . 42Tabela 22 - Resultados para os métodos de Jacobi e Gauss-Seidel para o problema

GR3030 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43Tabela 23 - Resultados para os métodos SRS para o problema GR3030 . . . . . . . . 43Tabela 24 - Resultados para os métodos de Jacobi e Gauss-Seidel para o problema

SHERMAN1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44Tabela 25 - Resultados para os métodos SRS para o problema SHERMAN1 . . . . . 44Tabela 26 - Resultados para os métodos de Jacobi e Gauss-Seidel para o problema

SHERMAN4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45Tabela 27 - Resultados para os métodos SRS para o problema SHERMAN4 . . . . . 46Tabela 28 - Quadro comparativo dos métodos . . . . . . . . . . . . . . . . . . . . . 47

LISTA DE FIGURAS

Figura 1 - Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz BC-SSTRUC1, MatrixMarket(2013) . . . . . . . . . . . . . . . . . . . . . . 33

Figura 2 - Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz pde225,MatrixMarket(2013) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Figura 3 - Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz MCFE,MatrixMarket(2013) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Figura 4 - Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz GR3030,MatrixMarket(2013) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

Figura 5 - Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz SHER-MAN1, MatrixMarket(2013) . . . . . . . . . . . . . . . . . . . . . . . . 36

Figura 6 - Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz SHER-MAN4, MatrixMarket(2013) . . . . . . . . . . . . . . . . . . . . . . . . 37

Figura 7 - Gráfico dos resultados da matriz m30, Fonte Própria(2013) . . . . . . . . 39Figura 8 - Gráfico dos resultados da matriz BCSSTRUC1, Fonte Própria(2013) . . 40Figura 9 - Gráfico dos resultados da matriz GR3030, Fonte Própria(2013) . . . . . 44Figura 10 - Gráfico dos resultados da matriz SHERMAN1, Fonte Própria(2013) . . . 45Figura 11 - Gráfico dos resultados da matriz SHERMAN4, Fonte Própria(2013) . . . 46Figura 12 - Gráfico comparativo entre o número de iterações para o problema m30,

Fonte Própria(2013) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48Figura 13 - Gráfico comparativo entre o número de iterações para os problemas de

grande porte, Fonte Própria(2013) . . . . . . . . . . . . . . . . . . . . . 48Figura 14 - Gráfico comparativo entre o tempo de convergência em segundos para o

problema m30, Fonte Própria(2013) . . . . . . . . . . . . . . . . . . . . 49Figura 15 - Gráfico comparativo entre o tempo de convergência em segundos para o

problema BCSSTRUC1, Fonte Própria(2013) . . . . . . . . . . . . . . . 49Figura 16 - Gráfico comparativo entre o tempo de convergência em segundos para os

problemas de grande porte, Fonte Própria(2013) . . . . . . . . . . . . . 50Figura 17 - Gráfico comparativo entre os métodos, Fonte Própria(2013) . . . . . . . 52Figura 18 - Gráfico demostrativo do melhor ω , Fonte Própria(2013) . . . . . . . . . 52

SUMÁRIO

1 INTRODUÇÃO 121.1 OBJETIVOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.1.1 Objetivo Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.1.2 Objetivos específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.2 JUSTIFICATIVA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.3 ORGANIZAÇÃO DO TRABALHO . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 REVISÃO DA LITERATURA 142.1 TEXTO INTRODUTÓRIO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2 CLASSIFICAÇÃO DE SISTEMAS DE EQUAÇÕES LINEARES . . . . . . . . . 152.2.1 Quanto ao número de soluções . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2.2 Quanto ao tamanho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.3 TIPOS DE SISTEMAS LINEARES . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.1 Sistemas lineares triangulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.2 Sistemas lineares equivalentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.4 CLASSIFICAÇÃO DA MATRIZ DOS COEFICIENTES . . . . . . . . . . . . . . 172.4.1 Matriz quadrada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.4.2 Matriz simétrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.4.3 Matriz esparsa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.4.4 Matriz definida positiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.4.5 Matriz diagonalmente dominante . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.4.6 Matriz tridiagonal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.5 SOLUÇÃO DE SISTEMA LINEARES . . . . . . . . . . . . . . . . . . . . . . . 182.6 ESTRATÉGIAS DE SOLUÇÕES . . . . . . . . . . . . . . . . . . . . . . . . . . 192.7 MÉTODOS ITERATIVOS PARA A SOLUÇÃO DE SISTEMAS LINEARES . . . 192.7.1 Condição de convergência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.7.2 Critérios de parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.7.3 Método de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.7.4 Método de Gauss-Seidel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.7.5 Método de Sobre Relaxação Sucessiva (SRS) . . . . . . . . . . . . . . . . . . . . 24

3 MATERIAL E MÉTODOS 273.1 METODOLOGIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2 ALGORITMOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.3 PROBLEMAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3.1 Problema m30 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3.2 Problema BCSSTRUC1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3.3 Problema pde225 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3.4 Problema MCFE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.3.5 Problema GR3030 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.3.6 Problema SHERMAN1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.3.7 Problema SHERMAN4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4 RESULTADOS E DISCUSSÕES 38

5 CONSIDERAÇÕES FINAIS 53

REFERÊNCIAS 54

12

1 INTRODUÇÃO

Sistemas de equações lineares estão associados a vários problemas práticos, como porexemplo, na análise de um circuito elétrico, no cálculo estrutural de uma treliça. Para Burdene Faires(2008) "[...] os sistemas de equações lineares estão associados a muitos problemas

no campo da engenharia e da ciência, bem como com aplicações da matemática às ciências

sociais e aos estudos quantitativos nos problemas de administração e economia".Os sistemas de equações lineares estão associados a muitos problemas nos campos da

engenharia e da ciência. Segundo Leon (2011, p.1), mais de 75% dos problemas matemáticosencontrados em aplicações científicas e industriais envolvem a resolução de sistemas linearesem algum estágio. Segundo Sperandio et al.(2003, p. 67) "[...] os sistemas de equações lineares

podem ser de grande porte. Por exemplo, a análise de estruturas de uma aeronave [...]"paraBurian(2011, p.38), sistemas de equações lineares podem ser encontrados em análises de cir-cuitos elétricos, análise de vibrações em sistemas mecânicos e na distribuição de força-peso emedifícios. E segundo Leon (2011, p.1), "sistemas lineares aparecem em aplicações em áreas

como administração, economia, sociologia, ecologia, demografia, genética, eletrônica, enge-

nharia e física."Na maioria dos problemas citados anteriormente é possível deparar-se com problemas

de grande porte, contudo, resolver sistemas de equações lineares de grande porte é uma tarefaárdua. Franco (2006, p.121), para problemas desse tipo os métodos iterativos se sobressaemem relação aos métodos diretos. Segundo Burden e Faires(2008), para grandes sistemas espar-sos, essas técnicas são eficientes em termos tanto de armazenamento no computador quanto decálculos. O método da Sobre Relaxação Sucessiva é um método iterativo que se encaixa nessepadrão.

1.1 OBJETIVOS

1.1.1 Objetivo Geral

Efetuar um estudo comparativo de resultados em alguns problemas de teste, comparandoos resultados obtidos no método de Sobre Relaxação Sucessiva com os métodos de Gauss-Jacobi e Gauss-Seidel;

1.1.2 Objetivos específicos

• Analisar os aspectos teóricos e práticos do método da Sobre Relaxação Sucessiva;

• Analisar a aplicabilidade do método de acordo com as suas pré-condições;

• Implementar o algoritmo do método proposto na plataforma computacional numéricaScilab;

• Analisar a convergência dos métodos nos problemas de teste;

13

1.2 JUSTIFICATIVA

A construção de um trabalho a respeito de métodos numéricos é de suma importân-cia para várias áreas de atuação e de estudos, pois existem inúmeros tipos de problemas queenvolvem sistemas de equações lineares, assim como também existem um grande número demétodos de resolução desses sistemas, e cada método possui bons resultados para um certo tipode problema e não tão bons para um outro tipo de problema. Para determinar qual métodoserá utilizado em cada problema é necessário um estudo prévio em conjunto do método e doproblema. Para que possamos tomar essa decisão dentro de indicadores que leve a ter bonsresultados e não perder tempo e investimentos, devemos conhecer a fundo o funcionamento decada método.

1.3 ORGANIZAÇÃO DO TRABALHO

O presente trabalho está organizado de acordo com a seguinte formação metodológica. Nocapítulo 2 apresenta a fundamentação teórica matemática que dará suporte aos métodos estuda-dos. Já no capítulo 3, é descrito os procedimentos para a realização dos testes, assim como osalgoritmos e problemas utilizados. No capítulo 4 é mostrado os resultados obtidos nos testes decada problema para cada método. E finalmente no capítulo 5 serão apresentadas as conclusõesdeste trabalho.

14

2 REVISÃO DA LITERATURA

2.1 TEXTO INTRODUTÓRIO

Os sistemas de equações lineares são um conjunto de n equações lineares que paraFranco (2011, p.118) "uma equação é linear se cada termo contém não mais do que uma vari-

ável e cada variável aparece na primeira potência", e as mesmas possuem sua forma geral

a1x1 +a2x2 + ...+amxn = b (1)

onde, ai são os coeficientes da equação, xi são as incógnitas e b é o termo independente daequação, considerando i = 1,2,3, ..,n. Assim, um sistema de equações lineares é constituídoem sua forma geral por (FRANCO, 2011):

a11x1 +a12x2 + ...+a1nxn = b1

a21x1 +a22x2 + ...+a2nxn = b2...am1x1 +am2x2 + ...+amnxn = bm

(2)

Assim, da mesma forma, ai j representa os coeficientes do sistema, xi representa as in-cógnitas do sistema e bi representa os termos independentes, considerando i = 1,2,3, ..,m ej = 1,2,3, ..,n.

Segundo Franco (2006, p.118) esse tipo de sistema possui uma resolução bem maissimplificada do que a de sistemas formados por equações não lineares. De acordo com Burian(2011, p.38) a modelagem de um problema com um sistema linear possui uma resolução bemmais simplificada assim como também possui vários métodos de resolução já consagrados.

Os sistemas de equações lineares possuem sua notação matricial na sua forma simplifi-cada

Ax = b (3)

onde A é a matriz formada pelos coeficientes do sistema, x é a matriz coluna formada pelasincógnitas do sistema e b é a matriz coluna formada pelos termos independentes. Dessa forma,um sistema de equações lineares, na sua forma geral, pode ser expresso na forma matricial aseguir:

A =

a11 a12 ... a1n

a21 a22 ... a2n...

am1 am2 ... amn

×

x1

x2...

xn

=

b1

b2...

bm

onde n = 1,2,3, .., p e m = 1,2,3, .., p.

15

Um sistema linear também pode ser expresso na sua forma de matriz aumentada. Sendoconstituído pela matriz A mais a última coluna formada pelas constantes ou termos indepen-dentes. tomando o exemplo anterior um sistema na forma geral pode-se expressa uma matrizaumentada em sua forma geral da seguinte forma:

a11 a12 ... a1n b1

a21 a22 ... a2n b2...

......

......

am1 am2 ... amn bm

onde n = 1,2,3, .., p e m = 1,2,3, .., p.

2.2 CLASSIFICAÇÃO DE SISTEMAS DE EQUAÇÕES LINEARES

Existem vários parâmetros que podem ser utilizados para a classificação de um sistemade equações lineares. Os mais comuns são os mostrados a seguir:

2.2.1 Quanto ao número de soluções

Uma das formas de se classificar um sistema de equações lineares é observando onúmero de soluções que o sistema admite, de acordo com Franco (2006, p. 119), "A classi-

ficação de um sistema linear é feita em função do número de soluções que ele admite [...]", logode acordo com o suprecitado autor os sistemas podem ser classificados como:

• Sistemas possíveis ou consistentes;

Um sistema é dito possível quando o sistema estudado admite pelo menos uma solução.Esses tipos de sistemas podem ser distribuídos em dois grupos: determinados, quandoadmitem apenas uma solução, ou indeterminados, quando admitem mais de uma solução.

• Sistemas impossíveis ou inconsistentes;

Um sistema linear é dito impossível ou inconsistente quando esse sistema não admitenenhuma solução.

Assim é possível identificar se um sistema de equações lineares admite solução única,antes de aplicar um método de resolução. Segundo Ferreira(2009, p. 47), para obtermos essainformação verificamos se a matriz A, formada pelos coeficientes das equações, é uma matriznão-singular, ou seja, se o det(A) ̸= 0. Neste caso, o sistema possui solução única.

2.2.2 Quanto ao tamanho

Outra maneira de classificar um sistema de equações lineares é em relação ao seutamanho, que nada mais é que o analise de quantas equações lineares compõem aquele sis-

16

tema estudado. Para Gavala (2011, p.42) considerando n o número de equações que compõemo sistema, é dito, um sistema grande quando n > 300 e pequeno quando n <= 300.

2.3 TIPOS DE SISTEMAS LINEARES

2.3.1 Sistemas lineares triangulares

Existem tipos de sistemas lineares que possuem solução que exige pouco esforço mecâni-co. Esses tipos de sistemas são encontrandos quando a matriz dos coeficientes gerada pelosistema é denominada uma matriz triangular. Segundo Burian (2011, p. 39), uma matriz édenominada triangular quando todos os coeficientes acima ou abaixo da diagonal principal sãozero, gerando triangulares inferiores ou superiores respectivamente. Já de acordo com Franco(2006, p.123), "Uma matriz triangular inferior é uma matriz quadrada C = (ci j) tal que ci j = 0para i < j. Do mesmo modo, se ci j = 0 para i > j, C é uma matriz triangular superior.". Assimtem-se como exemplo de sistemas lineares triangulares superiores e inferiores segundo, Franco(2006, p.122), os sistemas 4 e 5, respectivamente.

a11x1 + a12x2 + a13x3 + ... + a1nxn = b1

0x1 + a22x2 + a23x3 + ... + a2nxn = b2

0x1 + 0x2 + a33x3 + ... + a3nxn = bn... +

... +... + ... +

... =...

0x1 + 0x2 + 0x3 + ... + annxn = bn

(4)

a11x1 + 0x2 + 0x3 + ... + 0xn = b1

a21x1 + a22x2 + 0x3 + ... + 0xn = b2

a31x1 + a32x2 + a33x3 + ... + 0xn = bn... +

... +... + ... +

... =...

an1x1 + an2x2 + an3x3 + ... + annxn = bn

(5)

2.3.2 Sistemas lineares equivalentes

Dois sistemas de equações lineares são ditos equivalentes se possuírem a mesma solução.De acordo com Leon (2011, p.4), "Dois sistemas de equações envolvendo as mesmas variáveissão ditos equivalentes se têm o mesmo conjunto solução".

Para Boldrini et al.(1986, p. 33), "dois sistemas lineares são equivalentes se, e somente

se toda solução de qualquer um dos sistemas também é solução do outro". De acordo comRuggiero et al.(1996 , p. 4) um sistema equivalente é baseado no seguinte teorema:

Teorema 2.1. Seja S um sistema linear. Aplicando sobre as equações deste sistema ums se-

quência de operações elementares escolhidas entre:

(i) Permutar duas das equações do sistema. Assim sendo o sistema obtido por essa operação

possui a mesma solução do sistema original.

17

(ii) Multiplicar uma das equações do sistema por um número real diferente de zero. Assim o

sistema obtido possui a mesma solução que o sistema original.

(iii) Somar a uma das equações do sistema uma outra equação desse sistema multiplicada

por um número real.

obtemos um novo sistema S1, e os sistemas S e S1 são equivalentes.

Demostração: Ver em Rugierro(1996).

Dessa forma segundo Callioli et al.(1990, p. 5) é valida a seguinte definição:

Definição 2.1. Dado um sistema linear S, em qualquer uma das condições do teorema 2.1, re-

cebe o nome de operações elementares com S. Se um sistema linear S1 foi obtido de um sistema

linear S através de um número finito de operações elementares, dizemos que S1 é equivalente a

S.

Essas operações elementares são utilizadas para encontrar um sistema linear equivalentede fácil resolução. De acordo com Franco (2006, p. 122) "Em geral, nos métodos exatos,

transformamos o sistema original num sistema equivalente, cuja solução é obtida resolvendo-

se sistemas lineares triangulares".

2.4 CLASSIFICAÇÃO DA MATRIZ DOS COEFICIENTES

2.4.1 Matriz quadrada

Uma matriz A é classificada como uma matriz quadrada, quando possui o número delinhas igual ao número de colunas. Quando é trabalhado com um sistema que possui umamatriz desse tipo, é possível verificar que o número de equações igual ao número de incógnitas(SPERANDIO et al., 2003).

2.4.2 Matriz simétrica

Uma matriz é classificada como simétrica, quando os elementos possuem uma sime-tria em relação a diagonal principal da matriz, desse forma é valida as seguintes afirmações(SPERANDIO et al., 2003):

ai j = a ji.

Onde, i, j = 1,2,3, ...,n.Quando é trabalhado com uma matriz simétrica a transposta da matriz AT é igual a

matriz A. Se por acaso a transposta AT =−A, a matriz é classificada como anti-simétrica.

2.4.3 Matriz esparsa

Uma matriz é classificada como esparsa quando possui grande parte dos seus elementosnulos. Possui uma facilidade em executar operações envolvendo matrizes quando é trabalhadocom matrizes desse tipo (SPERANDIO et al., 2003).

18

2.4.4 Matriz definida positiva

Uma matriz é classificada como definida possitiva se os elementos da sua diagonal prin-cipal forem todos positivos (RUGGIERO et al., 1996).

Para se determinar uma matriz definida possitiva é utilizado o seguinte critério denomi-nado de critério de Sylvester (SPERANDIO et al., 2003):

detAk > 0.

Onde, k = 1,2,3, ...,n e Ak é uma matriz k× k formadas pela k primeiras linhas e colunas damatriz A.

2.4.5 Matriz diagonalmente dominante

Uma matriz é denominada de diagonalmente dominante quando a expressão a seguir éverdadeira para todas as linhas da matriz (SPERANDIO et al., 2003):

|aii|> ∑j ̸=i

|ai j| para todoi,

Caso essa afirmação seja válida para todas as colunas da matriz em estudo. A matriztambém é determidada de diagonalmente dominante.

2.4.6 Matriz tridiagonal

Uma matriz é denominanda de tridiagonal quando apenas os termos da diaginal principale os termos imediatamente acima e abaixo da diagonal principal são não mulos (SPERANDIOet al., 2003).

2.5 SOLUÇÃO DE SISTEMA LINEARES

Os métodos numéricos possuem o objetivo de encontrar uma solução satisfatória. Deacordo com Seymour Lipschutz e Marc Lipson (2004, p.60) "uma solução de um sistema linear

nas incógnitas x1,x2, ...,xn é uma sequência de n números s1,s2, ...,sn, tais que, sendo substituí-

dos nos lugares de x1,x2, ...,xn, respectivamente tornam verdadeira cada equação do sistema.".Assim, esses números podem ser ordenados em forma de vetores denominado de conjuntosolução de um sistema como por exemplo, o vetor (s1,s2, ...,sn)

t , com n = 1,2,3, ...,m.Com o propósito de encontrar um conjunto de soluções para um determinado sistema de

equações lineares, foram criados diversos métodos, denominados de métodos numéricos, cujametodologia básica será apresentada a seguir.

19

2.6 ESTRATÉGIAS DE SOLUÇÕES

Os tipos de métodos numéricos para a determinação de um sistema linear, segundoFranco (2006, p.121), são divididos em dois principais grupos.

• Métodos exatos ou diretos;

• Métodos iterativos.

Para Franco (2006, p.121) os métodos diretos ou exatos são aqueles que encontram asolução do sistema linear, se houver, em um número finito de operações desprezando os errosde arredondamento. Já os métodos iterativos requerem um número infinito de operações paraproduzirem a solução do sistema linear. Dessa forma o autor indica que os métodos iterativospossuem erro de truncamento e os exatos ou diretos, possuem erros de arredondamento.

Segundo Sperandio et al.(2003, p. 68) é importante a observação de dois aspectos bási-cos na escolha de um método numérico, que são:

• A propagação dos erros de arredondamento, e sua acumulação, e

• Se o armazenamento da matriz dos coeficientes está de acordo com a sua estrutura.

A seguir será realizado um estudo dos métodos numéricos iterativos.

2.7 MÉTODOS ITERATIVOS PARA A SOLUÇÃO DE SISTEMAS LINEARES

O segundo grupo de métodos elaborados para a resolução de sistemas lineares, é de-nominado de métodos iterativos. De acordo com Campos (2010, p.88) é possível resolver umsistema de equações lineares partindo de um vetor inicial x(0), encontrando uma seqüência devetores x1,x2, ...,xn que deve convergir para a resolução x̄ do sistema.

Segundo Campos (2010, p.88), tais métodos são denominados de iterativos pelo fato derealizarem a mesma série de operações repetidamente, até que o vetor xn converta na resoluçãodo sistema ou atinja os critérios de parada, sendo que a cada repetição dar-se o nome de iteração.De acordo com Arenales e Darezzo (2008, p.50) ao partir de um vetor inicial x(0), encontramosuma sequência de vetores que seja convergente a solução do sistema, assim,

limk→∝

x(k) = x̄

Segundo Franco (2006, p.168) os métodos iterativos podem ser divididos em processosestacionários e processos de relaxação. De acordo com o autor supracitado os processos sãodefinidos como:

(i) Processos estacionários são os que fornecem uma sequência de aproximantes da solução,cada uma das quais obtidas das anteriores pela repetição do mesmo tipo de processo.

20

(ii) Processos de relaxação são processos gerados inicialmente com um vetor solução v, ondeé selecionado uma direção p, sendo corrigido v na direção p com o objetivo de diminuiro vetor resíduo F(v), atingindo o seu ponto de mínimo que é a solução do sistema linear.Esse método tenta diminuir o resíduo na direção p.

Neste trabalho será trabalhado apenas com processos estacionários, com sistemas deacordo com a equação (3), do tipo Ax = b, que segundo Arenales e Darezzo (2008, p.50) sãotransformados para sua forma equivalente, por:

x(k+1) = Mxk + c (6)

Onde, M representa a matriz de iteração do sistema. De acordo com Campos (2010,p.88), quando a matriz M não for alterada durante o processo, esse processo é denominado deestacionário.

Como os métodos iterativos partem da execução de operações a partir de um x(0) inicial,para Campos (2010, p.91) possui diversas formas para a determinação desse vetor. Porémdeve-se atender a condição de convergência, que é importante para garantir que o sistema iráconvergir, por esse motivo é importante utilizar o método do quociente entre os elementos dovetor b e da diagonal principal da matriz A. Assim, o x(0) será determinado por:

x(0) =bi

aii(7)

2.7.1 Condição de convergência

Segundo Campos (2010, p.89) as condições de convergência são os fatores que garantemque os vetores (x1,x2, ...,xn) gerados pelas iterações dos métodos, irão convergir para a soluçãoaproximada do sistema. A seguir é mostrado algumas condições para os métodos estudadosneste trabalho.

Condição 01:

A primeira condição estudada diz respeito ao raio espectral que toma como base oseguinte teorema:

Teorema 2.2. O método iterativo expresso pela equação (27) converge com qualquer valor

inicial x(0) se, e somente se, ρ(M) < 1, sendo ρ(M) o raio espectral (maior autovalor em

módulo) da matriz de iteração M.

Demostração: Ver em Campos(2010).

Segundo Campos(2010, p. 89) "[...] a determinação do raio espectral da matriz de

iteração ρ(M) pode requerer maior esforço computacional que a própria solução do sistema

Ax = b".

21

Condição 02:

É usualmente utilizado para os métodos de Gauss-Seidel e Jacobi, o chamado crítériodas linhas e/ou colunas, que toma como base, segundo Ruggiero et al. (1996, p.160), o seguinteteorema:

Teorema 2.3. Seja o sistema linear de acordo com a equação (3) e seja:

αk =

(n∑

j=1e j ̸=k|ak j|

)|akk|

(8)

Se α = max1≤k≤n

αk < 1, então o método de Jacobi ou Gauss-Seidel gera uma sequência x(k) con-

vergente para a solução do sistema dado, independentemente da escolha da aproximação ini-

cial, x(0).

Demostração: Ver em Ruggiero et al.(1996).

Condição 03:

A condição (03) representa o critério de Sassenfeld, que segundo Ruggiero et al. (1996,p.170), garante a convergência do método de Gauss-Seidel. Esse critério é utilizado apenas parao método de Gauss-Seidel. De acordo com Arenales e Darezzo (2008, p.60), esse critério tomacomo base o seguinte teorema:

Teorema 2.4. Sejam as constantes β1 definidas pelas seguintes fórmulas de recorrência:

βi =

i−1∑j=1

|ai j|β j +n∑

j=i+1|ai j|

|aii|i, j = 1, ...,n

e seja

β = max1≤i≤n

βi

Então, se β < 1, a sequência x(0), gerada pelo método iterativo de Gauss-Seidel, converge para

a solução x̄ do sistema dado.

Demostração: Ver em Arenales e Darezzo(2008).

De acordo com Ruggiero et al.(1996, p. 173), quanto menor o valor de β mais rápidodará a convergência pelo método.

Condição 04:

A condição (04) segundo Arenales e Darezzo (2008, p.55), toma como base o seguinteteorema:

22

Teorema 2.5. Sejam uma norma matricial consistente com alguma norma vetorial e x(0) ∈Rn uma solução aproximada inicial qualquer. Se ||M|| < 1, então a sequência de soluções

aproximadas definidas pelo processo iterativo de acordo com a equação 27 converge para a

solução x̄ do sistema.

Demostração: Ver em Arenales e Darezzo (2008)

De acordo com esse teorema esse critério é utilizado para todos os métodos que utilizama equação (27). Segundo Arenales e Darezzo (2008, p.55), quanto menor o valor de ||M||, maisrapidamente o método converge para a solução aproximada do sistema.

2.7.2 Critérios de parada

Segundo Campos (2010, p.89), a cada iteração do método determinado pela equação(27) é obtido uma solução com exatidão crescente. Sendo assim é indicado critérios de paradaspara que o processo seja interrompido caso algum critério seja satisfeito.

É possível trabalhar com dois critérios de paradas, por número de iterações k, e peladistância relativa, no primeiro caso, é estipulado um valor máximo de iterações denominado dekmax, então o método realizara iterações até que:

kmx ≤ k (9)

Em relação à distância relativa que é levado em consideração, uma precisão desejada ε ,segundo Campos (2010, p.90), é realizado o seguinte procedimento:

dk+1 = max01≤i≤n|x

(k+1)i − x(k)i | (10)

Após dividir d(k) pelo máximo valor do módulo de x(k+1) que é o máximo valor dasolução atual, tendo como resultado da divisão a distância relativa dk+1

r , onde a distância relativadeve ser menor que a precisão ε . Assim:

dk+1r =

d(k+1)

max1≤i≤n|x(k+1)i |

< ε (11)

2.7.3 Método de Jacobi

O método iterativo de Jacobi, como todo método iterativo, parte de uma solução inicialx(0), e por meio de equações de iterações tende a convergir para uma solução aproximada dosistema. Segundo Sperandio et al. (2003, p.82), o primeiro passo para a aplicação desse métodoé encontrar o valor de x(0), que pode ser encontrado a partir da equação (28). Em seguidadevemos encontrar as equações de iterações sendo possível adotar um sistema de equaçõeslineares genérico representado de acordo com a equação (3). De acordo com Campos (2010,p.90) sendo possível facilmente decompor a matriz A em:

23

A = (D+ I +S) (12)

sendo que D é uma matriz diagonal formada pelos termos da diagonal principal da matriz A eD ̸= 0 , I é uma matriz triangular inferior formada pelos termos da matriz A e da mesma formaS é do tipo triangular superior. Logo o sistema será formado de acordo com as equações (33) e(3) por:

Dx =−(I +S)x+b (13)

Dessa forma, é possível encontrar a seguinte expressão:

x(k+1) =−(I +S)D

xki +

bD, sendo k = 1,2,3, ...,n e i = 1,2,3, ...,n (14)

De acordo com Franco (2008, p.171) a equação (35) é denominada de equação de iter-ação do método de Jacobi, sendo expressada na forma matricial por:

x(k+1)1 = 1

a11(b1 −a12x(k)2 −a13x(k)3 − ...−a1nx(k)n )

x(k+1)2 = 1

a22(b2 −a21x(k)1 −a23x(k)3 − ...−a2nx(k)n )

...

x(k+1)m = 1

amm(bm −am1x(k)1 −am2x(k)2 − ...−amnx(k)n )

(15)

2.7.4 Método de Gauss-Seidel

A fim de um melhoramento e uma maior velocidade de convergência, segundo Speran-dio et al. (2003, p.83) o método de Gauss-Seidel possui algumas modificações em relação aométodo de Jacobi. Partindo inicialmente do princípio que é trabalhado com uma sistema deequações linear, conforme a equação (3) um sistema do tipo:

Ax = b,

de acordo com a equação (33) a matriz A pode ser representada por A = (D+ I +S), ficando osistema formado por,

(D+ I +S)x = b,

e de acordo com Campos (2010, p.96), é possível realizar as seguintes relações matemáticas,

(D+ I)x =−Sx+b.

Como é tratado de uma equação a fim de encontrar um xk+1, é representa a equação da seguinteforma,

(D+ I)xk+1 =−Sxk +b,

24

e isolando o termo xk+1, é encontra a seguinte equação de iteração:

xk+1 = D−1(−Ixk+1 −Sxk +b) (16)

A equação acima é representada em sua forma matricial por:x(k+1)

1 = 1a11

(b1 −a12x(k)2 −a13x(k)3 − ...−a1nx(k)n )

x(k+1)2 = 1

a22(b2 −a21x(k+1)

1 −a23x(k)3 − ...−a2nx(k)n )...

x(k+1)m = 1

amm(bm −am1x(k+1)

1 −am2x(k+1)2 − ...−amnx(k)n )

(17)

Assim neste método na medida em que encontra-se os novos valores para o vetor xk+1,já é realizado a utilização desses novos valores na própria iteração. Essa é a grande modificaçãodo método de Gauss-Seidel para o método de Jacobi.

2.7.5 Método de Sobre Relaxação Sucessiva (SRS)

O terceiro método iterativo para a resolução de sistemas lineares é o método de sobrerelação sucessiva - SRS. O método SRS toma como base o método iterativo de Gauss-Seidel.De acordo com Sperandio et al. (2003, p.83), esse é um método derivado a partir do métodode Gauss-Seidel, onde essa modificação tem o objetivo de acelerar a convergência da soluçãoinicial x(0) para vetor solução.

Conforme Campos (2010, p.102), o método consiste em multiplicarmos o sistema porum parâmetro denominado de ω . O parâmetro ω é determinado um parametro de correção. Autilização do ω e a condição de convergência do método são vistos no seguinte teorema:

Teorema 2.6. Se A for uma matriz definida positiva e 0 < ω < 2, então o método de SRS

converge para qualquer escolha do vetor inicial x(0).

Demostração: Ver em Burden e Faires(2008).

O método de relaxação sucessiva pode ser dividido em três casos (BURDEN e FAIRES,2008):

• ω > 1, o método é denominado de sub relaxação sucessiva;

• ω > 1, o método é denominado de sobre relação sucessiva;

• ω = 1, o método é denominado de Gauss-Seidel.

Dessa forma, trabalhando com um sistema conforme a equação (3):

Ax = b.

25

De acordo com a equação (33), podemos representar o sistema por,

(D+ I +S)x = b.

Multiplicando pelo fator ω se tem,

ω(D+ I +S)x = ω .

E somando o vetor nulo (D−D)x ao primeiro termo tem-se,

(D−D)x+ω(D+ I +S)x = ωb.

Realizando a organização por meio de fator comum tem-se,

(D+ωI)x = [(1−ω)D−ωS]x+ωb.

como tentamos encontrar um xk+1, e trabalhando com base no método de Gauss-Seidel encon-tramos a seguinte equação de iteração:

(D+ωI)xk+1 = [(1−ω)D−ωS]xk +ωb (18)

Analisando a equação (37), é fácil isolar o termo xk+1, ficando da seguinte forma,

xk+1 = (D+ωI)−1[(1−ω)D−ωS]xk +ω(D+ωI)−1b,

e comparando com a equação de iteração geral que é data por,

xk+1 = Mxk + c,

onde M é denominada de matriz de iteração, é fácil notar que no caso estudado se tem,

M = (D+ωI)−1[(1−ω)D−ωS],

sendo que, para o método de SRS a matriz de iteração M é uma matriz fixa por isso, segundoCampos (2010, p.88) é denominado de um método estacionário.

A determinação das equações de iterações de forma geral ocorre a partir da equação(37), onde se tem,

(D+ωI)xk+1 = [(1−ω)D−ωS]xk +ωb.

Realizando o desmembramento do primeiro membro se tem,

Dxk+1 +ωIxk+1 = [(1−ω)D−ωS]xk +ωb,

26

e isolando Dxk+1 resulta-se em,

Dxk+1 = [(1−ω)D−ωS]xk +ωb−ωIxk+1.

Realiza-se a decomposição do segundo membro e o isolamento do ω assim,

Dxk+1 = ω(−Ixk+1 −Sxk +b)+(1−ω)Dxk.

Isolando xk+1 no primeiro membro se tem,

xk+1 = ωD−1(−Ixk+1 −Sxk +b)+(1−ω)xk (19)

A equação (40) pode ser representada em sua forma matricial geral da seguinte forma,

x(k+1)

1 = ωa11

(−a12xk2 −a13xk

3 − ...−a1nxkn +b1)+(1−ω)xk

1,

x(k+1)2 = ω

a22(−a21x(k+1)

1 −a23xk3 − ...−a2nxk

n +b2)+(1−ω)xk2,

...

x(k+1)n = ω

ann(−an1x(k+1)

1 −an2x(k+1)2 − ...−ann−1x(k+1)

n−1 +bn)+(1−ω)xkn,

(20)

Esse método numérico, é um método que assemelha-se ao método de Gauss-Seidel,porém esse método depende da escolha do ω apropriado. O seguinte teorema foca essa escolha.

Teorema 2.7. Se A for uma matriz definida positiva e tridiagonal, então ρ(Tg) = [ρ(Tj)]2 < 1,

e a escolha ótima de ω para o método SRS será

ω =2

1+√

21− [ρ(Tj)]2.

Demostração: Ver em Burden e Faires(2008).

Porém o método de obtenção do melhor parâmetro omega pelo método descrito no teo-rema 2.9, se restringe apenas para casos que trabalha-se com matrizes definidas positivas etridiagonal, diminuindo muito a sua aplicação.

27

3 MATERIAL E MÉTODOS

3.1 METODOLOGIA

Nesse trabalho foi apresentado uma grande quantidade de métodos numéricos onde to-dos eles possuem o mesmo objetivo, que é encontrar o vetor solução x de um sistema linear dotipo Ax = b. Cada método possui uma forma de encontrar esse vetor, seja ele um método diretoou iterativo. É importante destacar que os métodos possuem resultados variáveis em relaçãoa cada problema trabalhado. Desta forma, é de suma importância a realização de testes comvários métodos e realizar uma comparação entre eles, para poder saber qual método sobressaiem relação a outro, em um determinado problema.

É destacado nesse trabalho o método de Sobre Relaxação Sucessiva, como citado an-teriormente, é uma derivação do método de Gauss-Seidel. Segundo o teorema 2.4, quando ascondições exigidas de convergência são satisfeitas, o método SRS converge para qualquer valorde omega no intervalo 0 < ω < 2. Contudo nesse trabalho será trabalhado apenas com valoresde omega no intervalo 1 < ω < 2 que caracteriza o método como sobre relaxação. Os valoresde ω que foram testados podem ser encontrados na tabela a seguir:

Tabela 1: Tabela dos valores de omega utilizados nos testesValores de ω para testes

1.05 1.15 1.25 1.35 1.45 1.55 1.65 1.75 1.75 1.95

Fonte: Fonte Própria(2013)

O enfoque principal dos testes foi para métodos iterativos estacionários, que são osmétodos cuja matriz de iteração permanece fixa na execução do método. Foram testados nessetrabalho os métodos de Jacobi, Gauss-Seidel e Sobre Relaxação Sucessiva - SRS. Para issoforam selecionado sete sistemas lineares com características distintas, onde aplicamos os trêsmétodos a cada um desses problemas, lembrando que para o método SRS foram aplicadosdez valores diferentes para ω de acordo com a tabela acima. Com isso é possível fazer umacomparação entre os métodos e saber em qual ponto a utilização de um determinado métodotorna-se melhor que outro, assim como dentro do próprio método de SRS, é possível identificarqual é o melhor ω a ser utilizado em cada problema específico.

Para a realização dos testes foram estabelecidos dois critérios de parada. O primeiro équanto ao número de iterações k. Para esse critério adotou-se kMax = 5000, ou seja no máximosão executadas 5000 iterações. O segundo quanto a distância relativa expressada pela equação32, adotou-se uma precisão de ε = 10−5 para problemas com n < 1000 e de ε = 10−4 paraproblemas com n ≥ 1000, sendo n é um número real inteiro positivo que identifica a ordem damatriz. A seguir, segue informações dos computadores e sistemas utilizados nos testes.

28

Tabela 2: Dados referentes ao computador utilizado nos testesCaracterísticas gerais

Fabricante ItautecModelo InfoWay ST 4270

Processador Intel(R) Core(TM) i5 CPU 750 @ 2.67GHz 2.66GHzMemória RAM 4GB

HD 300GB

Fonte: Manual do fabricante(2013)

Tabela 3: Dados referentes ao sistema operacional utilizado nos testesCaracterísticas gerais

Fabricante MicrosoftModelo Windows 7 Profissional 32 Bits

Fonte: Manual do fabricante(2013)

O software utilizado para a resolução dos problemas foi o Scilab, que é um software livrepara computação numérica, o Scilab é encontrado para downloads no site do desenvolvedor peloendereço http://www.scilab.org/, onde é encontrada também todas as informações do software,manuais e características das versões. Para a implementação desse trabalho foi utilizado osoftware Scilab da versão 5.3.0, para Windows 32 bits.

3.2 ALGORITMOS

Para a realização dos testes numéricos foi realizado a implementação do algoritmo paraa resolução do método de Sobre Relaxação Sucessiva - SRS adaptado para o Scilab, com basenos algoritmos utilizados por Oliveira (2012), no qual o mesmo realizou testes semelhantes uti-lizando os métodos de Jacobi e Gauss-Seidel. Isso torna-se possível pelo fato dos três métodosserem semelhantes com apenas pequenas modificações. Dessa forma, os algoritmos utilizadosnos testes são mostrados de forma simplificada pelas tabelas a seguir.

29

Tabela 4: Algoritmo utilizado para o método de JacobiAlgoritmo: Método de Jacobi

declare

An×n, (matriz dos coeficientes, a ser lida)bn, (vetor dos termos independentes)xn, (vetor-solução )(xant)n, (vetor-solução obtido na iteração anterior )ε , (tolerância de cálculo )nmx, (quantidade máxima de iterações )i,k (variáveis auxiliares )

numérico

leia n,An×n,bn,(xant)n,ε,nmax

x → biaii

(Encontra o vetor inicial x(0))k → 1

enquanto (não satisfazer os critérios de paradas)

para i de 1 até n faça

x(i)→

[b(i)−

n∑

j=1e j ̸=iA(i, j)× xant( j)

]÷A(i,i)

fim para

xant → xk → k+1

fim enquanto

escreva x

Fonte: Adaptado de Junior(2007)

30

Tabela 5: Algoritmo utilizado para o método de Gauss-SeidelAlgoritmo: Método de Gauss-Seidel

declare

An×n, (matriz dos coeficientes, a ser lida)bn, (vetor dos termos independentes)xn, (vetor-solução )(xant)n, (vetor-solução obtido na iteração anterior )ε , (tolerância de cálculo )nmx, (quantidade máxima de iterações )i,k (variáveis auxiliares )

numérico

leia n,An×n,bn,(xant)n,ε,nmax

x → biaii

(Encontra o vetor inicial x(0))k → 1



x(i)→

[b(i)−

1−i∑j=1

A(i, j)× x( j)−n∑

j=i+1A(i, j)× xant( j)

]÷A(i,i)

fim para

xant → xk → k+1

fim enquanto

escreva x

Fonte:Adaptado de Junior(2007)

31

Tabela 6: Algoritmo utilizado para o método de Sobre Relaxação Sucessiva - SRSAlgoritmo: Método de Sobre Relaxação Sucessiva - SRS

declare

An×n, (matriz dos coeficientes, a ser lida)bn, (vetor dos termos independentes)xn, (vetor-solução )(xant)n, (vetor-solução obtido na iteração anterior )ε , (tolerância de cálculo )ω , (Fator ω para o método de SRS )nmx, (quantidade máxima de iterações )i,k (variáveis auxiliares )

numérico

leia n,An×n,bn,(xant)n,ε,nmax,ωx → bi

aii(Encontra o vetor inicial x(0))

k → 1



x(i)→

{ω

A(i,i)×

[b(i)−

1−i∑j=1

A(i, j)× x( j)−n∑

j=i+1A(i, j)× xant( j)

]}+(1−ω)× x(i)

fim para

xant → xk → k+1

fim enquanto

escreva x

Fonte: Fonte própria(2013)

32

3.3 PROBLEMAS

Para a realização dos testes foi realizado a escolha de sete diferentes problemas. Umproblema nada mais é que matrizes formadas por termos de um sistema linear, mais um vetor b

que é o vetor formado pelos termos independentes do sistema linear.Cada problema foi escolhido com características diferentes uns dos outros, essas carac-

terísticas são, por exemplo, tamanho e propriedades, porém todas as matrizes são quadradas,ou seja, possuem o número de linhas igual ao número de colunas. Foram selecionadas matrizespequenas com trinta colunas e linhas até matrizes de grande porte de quase mil e duzentas li-nhas e colunas. Foi realizada essa diversificação de problemas para poder estimar como será ocomportamento do método para tipos de problemas diferentes e assim poder identificar em quepontos a aplicação de um método é boa ou ruim.

Com exceção da matriz do primeiro problema, todas as matrizes dos problemas foramretiradas do banco de dados da Matrix Market (2013), que pode ser encontrada no site de en-dereço, http://math.nist.gov/MatrixMarket/. Nesse banco de dados é encontrado matrizes devários tipos e tamanhos, assim como também é possível realizar o download de matrizes noformato MatrixMarket(.mtx) que é facilmente integrado ao software utilizado no caso Scilab. Amatriz referente ao primeiro problema possui fonte do trabalho realizado por Oliveira(2012). Aseguir são mostrados detalhadamente todos os sete problemas utilizados nos testes realizados.

3.3.1 Problema m30

O problema m30 é um problema considerado pequeno quanto ao seu tamanho, pos-suindo as características relacionadas na tabela a seguir.

Tabela 7: Dados referentes ao problema m30Características geraisTamanho 30×30

Diagonalmente Dominante SimEsparso Não

Fonte: Oliveira(2012)

É importante destacar por ser uma matriz diagonalmente dominante, segundo o teorema2.3 pelos métodos iterativos de Jacobi e Gauss-Seidel é garantida a convergência para qualquervetor inicial x(0).

3.3.2 Problema BCSSTRUC1

O problema BCSSTRUC1 pertencente a coleção Harwell-Boeing que foi gerada do es-tudo de análises dinâmicas em engenharia estrutural, considerado um problema pequeno quantoao seu tamanho, possuindo as características relacionadas na tabela a seguir.

33

Tabela 8: Dados referentes ao problema BCSSTRUC1Características gerais Valores não zeros

Tamanho 48×48 (224 entradas) Total 400Tipo da Matriz Real, simétrica e positiva definida Diagonal 48

Diagonalmente Dominante Não Abaixo da diagonal 176Número de Condição (est.) 1.6×106 Acima da diagonal 176

Esparso Não A−A(−1) 0

Fonte: MatrixMarket(2013)

A seguir é mostrado o mapeamento 2D e 3D da matriz em estudo, onde o mapeamento2D mostra onde os valores não zeros estão localizados na matriz e o mapeamento 3D mostra avariação no módulo do valor dos termos não zeros da matriz.

Figura 1: Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz BCSSTRUC1,MatrixMarket(2013)

3.3.3 Problema pde225

O problema pde225 pertencente a coleção NEP, oriunda das equações diferenciais par-ciais. É considerado um problema pequeno quanto ao seu tamanho, possuindo as característicasrelacionadas na tabela a seguir.

Tabela 9: Dados referentes ao problema pde225Características gerais Valores não zeros

Tamanho 225×225 (1065 entradas) Total 1065Tipo da Matriz Real e assimétrico Diagonal 225

Diagonalmente Dominante Não Abaixo da diagonal 420Número de Condição (est.) 1×102 Acima da diagonal 420

Esparso Sim A−A(−1) 420



34

Figura 2: Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz pde225, Matrix-Market(2013)

3.3.4 Problema MCFE

O problema MCFE pertencente também a coleção Harwell-Boeing oriunda de proble-mas astrofísicos. É considerado um problema grande quanto ao seu tamanho, possuindo ascaracterísticas relacionadas na tabela a seguir.

Tabela 10: Dados referentes ao problema MCFECaracterísticas gerais Valores não zeros

Tamanho 765×765 24382 entradas Total 24382

Tipo da Matriz Real e assimétrico Diagonal 765

Diagonalmente Dominante Não Abaixo da diagonal 9289

Número de Condição (est.) 1.7×1014 Acima da diagonal 14328




Figura 3: Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz MCFE, Matrix-Market(2013)

35

3.3.5 Problema GR3030

O problema GR3030 pertence a coleção Harwell-Boeing, oriundo de problemas comequações parciais diferenciais. É considerado um problema grande quanto ao seu tamanho,possuindo as características relacionadas na tabela a seguir.

Tabela 11: Dados referentes ao problema GR3030Características gerais Valores não zeros

Tamanho 900×900 (4322 entradas) Total 7744Tipo da Matriz Real, simétrico Diagonal 900

definido positivo e tridiagonalDiagonalmente Dominante Fraco Abaixo da diagonal 3422Número de Condição (est.) 3.8×102 Acima da diagonal 3422




Figura 4: Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz GR3030, Matrix-Market(2013)

3.3.6 Problema SHERMAN1

O problema SHERMAN1 pertence a coleção Harwell-Boeing, oriundo de problemas demodelagem de reservatório de óleo. É considerado um problema grande quanto ao seu tamanho,possuindo as características relacionadas na tabela a seguir.

36

Tabela 12: Dados referentes ao problema SHERMAN1Características gerais Valores não zeros

Tamanho 1000×1000 (3750 entradas) Total 3750Tipo da Matriz Real e simétrico Diagonal 1000

Diagonalmente Dominante Não Abaixo da diagonal 1375Número de Condição (est.) 2.3×104 Acima da diagonal 1375




Figura 5: Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz SHERMAN1,MatrixMarket(2013)

3.3.7 Problema SHERMAN4

O problema SHERMAN4 pertence a coleção Harwell-Boeing, oriundo de problemas demodelagem de reservatório de óleo. É considerado um problema grande quanto ao seu tamanho,possuindo as características relacionadas na tabela a seguir.

Tabela 13: Dados referentes ao sétimo problema SHERMAN4Características gerais Valores não zeros

Tamanho 1104×1104 (3786 entradas) Total 3786Tipo da Matriz Real e assimétrico Diagonal 1104

Diagonalmente Dominante Sim Abaixo da diagonal 1341Número de Condição (est.) 7.2×103 Acima da diagonal 1341



37


Figura 6: Imagem do mapeamento em 2D(esquerda) e 3D(direira) da matriz SHERMAN4,MatrixMarket(2013)

38

4 RESULTADOS E DISCUSSÕES

Após a realização de todos os testes da forma como descritos no capitulo anterior serámostrado a seguir os resultados obtidos de cada método para cada problema. Em seguida umcomentário sobre os resultados obtidos, destacando a eficiência do método de Sobre RelaxaçãoSucessiva - SRS.

Os fatores que são levados em consideração para análise dos resultados, são o númerode iterações (k) e o tempo de execução (t).

Os resultados serão mostrados de forma separada, uma tabela mostrará os resultadospara os métodos de Jacobi e Gauss-Seidel, e outra tabela mostrará os resultados para o métodode SRS com diferentes ω , em seguida a discussão para cada problema realizando uma com-paração entre os três métodos.

Resultados do problema m30

Tabela 14: Resultados para os métodos de Jacobi e Gauss-Seidel para o problema m30Parâmetros Jacobi Gauss-SeidelResultado Convergiu Convergiu

Numero de iterações 7 5Tempo de execução (s) 0,071 0,047

Precisão 4.89×10−6 3.17×10−5


Tabela 15: Resultados para os métodos SRS para o problema m30Resultados para o método SRS - problema m30

Omega(ω) Resultado Iterações Tempo(s) Precisão1.05 Convergiu 6 0.062 0.00000261.15 Convergiu 8 0.078 5.3×10−6

1.25 Convergiu 11 0.094 4.0×10−6

1.35 Convergiu 14 0.109 8.2×10−6

1.45 Convergiu 21 0.171 6.6×10−6

1.55 Convergiu 33 0.265 9.8×10−6

1.65 Convergiu 66 0.484 9.5×10−6

1.75 Convergiu 364 2.637 9.0×10−6

1.85 Não Convergiu 5000 35.895 Não1.95 Não Convergiu 5000 36.083 Não


39

De acordo com os resultados obtidos nos testes realizados com o problema m30 é pos-sível realizar uma comparação entre os métodos. Dessa forma, comparando os métodos é pos-sível notar que o método de Gauss-Seidel obteve um menor número de iterações e um menortempo de execução para convergir do que o método de Jacobi. Já em relação ao método SRS,o melhor ω foi o menor, no caso ω = 1.05, sendo que na medida em que foi aumentado o ωo desempenho do método caia, até que nos dois últimos valores de ω e maiores, o método nãoconvergiu para o problema dado. Sendo assim, para o primeiro problema o método de melhordesempenho foi o método de Gauss-Seidel em número de iterações e tempo de execução. Emseguida o método de SRS, e por último o método de Jacobi que obteve um tempo maior do queos demais métodos para convergir. Abaixo é mostrado o gráfico relacionado o fator ω e o tempode convergência.

Figura 7: Gráfico dos resultados da matriz m30, Fonte Própria(2013)

Resultados do problema BCSSTRUC1

Tabela 16: Resultados para os métodos de Jacobi e Gauss-Seidel para o problema BCSSTRUC1Parâmetros Jacobi Gauss-SeidelResultado Não Convergiu Convergiu

Numero de iterações 5000 1866Tempo de execução (s) 173.067 75.707

Precisão 1.90789 9.97×10−7


40

Tabela 17: Resultados para os métodos SRS para o problema BCSSTRUC1Resultados para o método SRS - problema BCSSTRUC1

Omega(ω) Resultado Iterações Tempo(s) Precisão1.05 Convergiu 1717 72.072 1.0×10−5

1.15 Convergiu 1450 59.093 1.0×10−5

1.25 Convergiu 1217 49.577 1.0×10−5

1.35 Convergiu 1010 41.153 1.0×10−5

1.45 Convergiu 824 34.445 9.9×10−6

1.55 Convergiu 653 26.645 1.0×10−5

1.65 Convergiu 496 20.265 9.9×10−6

1.75 Convergiu 346 14.149 9.9×10−6

1.85 Convergiu 195 8.018 9.6×10−6

1.95 Convergiu 182 7.472 8.5×10−6


Realisando a análise dos resultados obtidos para o problema BCSSTRUC1 temos que ométodo de Jacobi atingiu o número máximo de iterações e não convergiu para o vetor soluçãoaproximado, levando em consideração que o problema não é diagonalmente dominante. Sendoassim, segundo o teorema 2.3, não garante a convergência do método. Já o método de Gauss-Seidel convergiu, porém com número de iterações e tempo elevados em relação ao método deSRS, que por sua vez obteve o seu melhor desempenho com ω = 1.95. Sendo que, diferentemen-te do primeiro problema a medida em que aumentou o omega, diminuiu o tempo de convergên-cia do método. Sendo assim, para o segundo problema o método SRS obteve um desempenhosuperior que os demais métodos comparados. Abaixo é mostrado o gráfico relacionado o fatorω e o tempo de convergência.

Figura 8: Gráfico dos resultados da matriz BCSSTRUC1, Fonte Própria(2013)

41

Resultados do problema pde225

Tabela 18: Resultados para os métodos de Jacobi e Gauss-Seidel para o problema pde225Parâmetros Jacobi Gauss-SeidelResultado Convergiu Convergiu


Precisão 9.887×10−6 9.796×10−6


Tabela 19: Resultados para os métodos SRS para o problema pde225Resultados para o método SRS - problema pde225Omega(ω) Resultado Iterações Precisão

1.05 Não Convergiu 5000 Não1.15 Não Convergiu 5000 Não1.25 Não Convergiu 5000 Não1.35 Não Convergiu 5000 Não1.45 Não Convergiu 5000 Não1.55 Não Convergiu 5000 Não1.65 Não Convergiu 5000 Não1.75 Não Convergiu 5000 Não1.85 Não Convergiu 5000 Não1.95 Não Convergiu 5000 Não


Em relação ao problema pde225, levando em consideração os resultados obtidos paraos dois primeiros métodos, obteve convergência nos dois casos. Porém o método de Gauss-Seidel teve um melhor desempenho tanto em número de iterações como em tempo de execução.Já o método SRS não obteve convergência em nenhum ω testado, lembrando que o problemanão é diagonalmente dominante bem como não é definido positivo. Sendo assim, de acordocom o teorema 2.4 o método poderia ou não convergir. No caso estudado não obteve nenhumaconvergência. Nesse problema o método de melhor desempenho foi o método de Gauss-Seidel.

42

Resultados do problema MCFE

Tabela 20: Resultados para os métodos de Jacobi e Gauss-Seidel para o problema MCFEParâmetros Jacobi Gauss-SeidelResultado Convergiu Convergiu


Precisão 0 0


Tabela 21: Resultados para os métodos SRS para o problema MCFEResultados para o método SRS - problema MCFEOmega(ω) Resultado Iterações Precisão

1.05 Não Convergiu 5000 Não1.15 Não Convergiu 5000 Não1.25 Não Convergiu 5000 Não1.35 Não Convergiu 5000 Não1.45 Não Convergiu 5000 Não1.55 Não Convergiu 5000 Não1.65 Não Convergiu 5000 Não1.75 Não Convergiu 5000 Não1.85 Não Convergiu 5000 Não1.95 Não Convergiu 5000 Não


Os resultados obtidos para o problema MCFE, mostram que da mesma forma que oproblema anterior, o método SRS não obteve convergência para nenhum dos dez ω utilizadonos testes. Da mesma forma, o problema estudado não é um caso de problema que gera umamatriz positiva definida. Sendo assim, de acordo com o teorema 2.4 o método de SRS podeou não convergir e nesse caso o método não obteve sucesso. Já analisando os demais métodos,o método de Gauss-Seidel obteve um melhor desempenho em relação ao número de iteração etempo de execução.

43

Resultados do problema GR3030

Tabela 22: Resultados para os métodos de Jacobi e Gauss-Seidel para o problema GR3030Parâmetros Jacobi Gauss-SeidelResultado Convergiu Convergiu


Precisão 9.93×10−6 9.86×10−6


Tabela 23: Resultados para os métodos SRS para o problema GR3030Resultados para o método SRS - problema GR3030


1.15 Convergiu 343 5132.424 1.0×10−5

1.25 Convergiu 287 4302.757 9.9×10−6

1.35 Convergiu 237 3535.029 9.8×10−6

1.45 Convergiu 192 2888.438 9.9×10−6

1.55 Convergiu 151 2262.004 9.8×10−6

1.65 Convergiu 113 1717.126 9.4×10−6

1.75 Convergiu 74 1124.947 9.6×10−6

1.85 Convergiu 72 1093.484 9.8×10−6

1.95 Convergiu 198 2934.830 1.0×10−5


Analisando os resultados obtidos com os testes do problema GR3030, é possível notarque todos os métodos convergiram. Esse fato acontece por que o problema se trata de umamatriz que é diagonalmente dominante e definida positiva e de acordo com os teoremas 2.3e 2.4, possui a garantia de convergência para todos os métodos. Nesse caso, o método SRSobteve o seu melhor desempenho com ω = 1.85. O que é importante destacar nesse problemaé que para todos os valores de ω testados no método SRS tiveram resultados superiores, tantoem número de iteração quanto em tempo de execução, melhores que os métodos de Jacobi eGauss-Seidel, neste caso o método SRS foi bastante superior que os demais métodos. Abaixo émostrado o gráfico relacionado o fator omega e o tempo de convergência.

44

Figura 9: Gráfico dos resultados da matriz GR3030, Fonte Própria(2013)

Resultados do problema SHERMAN1

Tabela 24: Resultados para os métodos de Jacobi e Gauss-Seidel para o problema SHERMAN1Parâmetros Jacobi Gauss-SeidelResultado Não Convergiu Convergiu


Precisão 1.19×10−4 9.99×10−5


Tabela 25: Resultados para os métodos SRS para o problema SHERMAN1Omega(ω) Resultado Iterações Tempo(s) Precisão

1.05 Não Convergiu 5000 92707.176 2.37×10−5

1.15 Convergiu 2703 49834.009 1.0×10−4

1.25 Convergiu 2376 44029.377 1.0×10−4

1.35 Convergiu 2064 38410.870 9.9×10−5

1.45 Convergiu 1762 32769.214 9.9×10−5

1.55 Convergiu 1467 27055.034 9.9×10−5

1.65 Convergiu 1174 21801.288 9.9×10−5

1.75 Convergiu 877 16325.741 9.9×10−5

1.85 Convergiu 565 10532.904 9.9×10−5

1.95 Convergiu 181 3370.495 8.5×10−5


45

Os resultados obtidos para o problema SHERMAN1 foram de certa forma favoráveispara o método SRS, tendo em vista que o método de SRS com ω = 1.05 não convergiu. Porém,a partir de ω = 1.15 o método convergiu já com um desempenho melhor em relação ao de-mais métodos, e a medida em que aumentou-se o ω o desempenho do método teve uma grandemelhora, atingindo o melhor desempenho com ω = 1.95, sendo que o método de Jacobi nãoobteve convergência. Já o método de Gauss-Seidel obteve convergência, porém com desem-penho inferior ao método SRS, tendo em vista que esse problema é formado por uma matrizque não é diagonalmente dominante e definida positiva. De acordo com os teoremas 2.3 e 2.4não é garantida a convergência do método assim como ocorreu com o método de Jacobi e com ométodo SRS para ω = 1.05. Abaixo é mostrado o gráfico relacionado o fator omega e o tempode convergência.

Figura 10: Gráfico dos resultados da matriz SHERMAN1, Fonte Própria(2013)

Resultados do problema SHERMAN4

Tabela 26: Resultados para os métodos de Jacobi e Gauss-Seidel para o problema SHERMAN4Parâmetros Jacobi Gauss-SeidelResultado Convergiu Convergiu


Precisão 9.98×10−5 9.99×10−5


46

Tabela 27: Resultados para os métodos SRS para o problema SHERMAN4Resultados para o método SRS - problema SHERMAN4


1.15 Convergiu 842 19271.072 1.0×10−4

1.25 Convergiu 717 16399.919 9.9×10−5

1.35 Convergiu 593 13894.090 9.9×10−5

1.45 Convergiu 499 11424.160 9.9×10−5

1.55 Convergiu 402 9243.843 9.8×10−5

1.65 Convergiu 309 7122.598 9.9×10−5

1.75 Convergiu 220 5066.562 9.8×10−5

1.85 Convergiu 126 2905.958 9.8×10−5

1.95 Convergiu 141 3215.166 9.7×10−5


Como mostrado nos resultados obtidos nos testes realizados com o problema SHER-MAN4, é fácil observar que todos os testes convergiram para um vetor solução aproximado dosistema. É importante destacar que o método de Gauss-Seidel obteve um melhor desempenhoem relação ao método de Jacobi. Já o método SRS foi superior que os demais métodos paraqualquer ω . O método de SRS atingiu o desempenho máximo com ω = 1.85. Frisando quepara esse ω a diferença entre o desempenho do método SRS e o método de Gauss-Seidel foibem elevada nos aspectos avaliados. Abaixo é mostrado o gráfico relacionado o fator omega eo tempo de convergência.

Figura 11: Gráfico dos resultados da matriz SHERMAN4, Fonte Própria(2013)

Após a exposição dos resultados obtidos, podemos montar um quadro comparativo comos resultados dos testes obtidos com os métodos de Jacobi e Gauss-Seidel e com o resultadodo método SRS para o melhor ω de cada problema. Com isso, poderá ser feito uma melhorcomparação entre os métodos, esse quadro pode ser encontrado a seguir.

47

Tabe

la28

:Qua

dro

com

para

tivo

dos

mét

odos

Prob

lem

aM

étod

oR

esul

tado

No

deIt

eraç

ões

Tem

pode

Exe

cuçã

oPr

ecis

ãoal

canç

ada

Prob

lem

a1(3

0x

30)(

10−

5 )Ja

cobi

Con

verg

iu7

0.07

1s4.

89x1

0−6

Prob

lem

am

30G

auss

-Sei

del

Con

verg

iu5

0.04

7s3.

17x1

0−5

SRS

(ω=

1.05

)C

onve

rgiu

60.

062s

2.6x

10−

6

Prob

lem

a2(4

8x

48)(

10−

5 )Ja

cobi

Não

Con

verg

iu50

0017

3.06

7s1.

9078

9Pr

oble

ma

BC

SST

RU

C1

Gau

ss-S

eide

lC

onve

rgiu

1866

75.7

07s

9.97

x10−

7

SRS

(ω=

1.95

)C

onve

rgiu

182

7.47

2s8.

5x10

−6

Prob

lem

a3(2

25x

225)

(10−

5 )Ja

cobi

Con

verg

iu62

352

0.68

2s9.

88x1

0−6

Prob

lem

apd

e225

Gau

ss-S

eide

lC

onve

rgiu

327

301.

360s

9.79

x10−

6

SRS

(ω=

No)

Não

Con

verg

iu50

00N

ãoco

nver

giu

Não

obte

vePr

oble

ma4

(765

x76

5)(1

0−5 )

Jaco

biC

onve

rgiu

217

2050

.232

s0

Prob

lem

aM

CFE

Gau

ss-S

eide

lC

onve

rgiu

207

2262

.787

s0

SRS

(ω=

No)

Não

Con

verg

iu50

00N

ãoco

nver

giu

Não

obte

vePr

oble

ma5

(900

x90

0)(1

0−5 )

Jaco

biC

onve

rgiu

792

1011

9.88

1s9.

99x1

0−6

Prob

lem

aG

R30

30G

auss

-Sei

del

Con

verg

iu44

566

32.3

99s

9.86

x10−

6

SRS

(ω=

1.85

)C

onve

rgiu

7210

93.4

84s

9.80

x10−

6

Prob

lem

a6(1

000

x10

00)(

10−

4 )Ja

cobi

Não

conv

ergi

u50

0076

528.

376s

1.19

x10−

4

Prob

lem

aSH

ER

MA

N1

Gau

ss-S

eide

lC

onve

rgiu

3229

5322

3.87

6s9.

99x1

0−5

SRS

(ω=

1.95

)C

onve

rgiu

181

3370

.495

s8,

53x1

0−5

Prob

lem

a7(1

104

x11

04)(

10−

4 )Ja

cobi

Con

verg

iu17

8035

310.

688s

9.98

x10−

5

Prob

lem

aSH

ER

MA

N4

Gau

ss-S

eide

lC

onve

rgiu

1058

2393

8.81

3s9.

99x1

0−5

SRS

(ω=

1.85

)C

onve

rgiu

126

3215

.166

s9.

85x1

0−5

Font

e:Fo

nte

próp

ria(

2013

)

48

Com as informações obtidas na tabela (28) é possível realizar um análise dos melhoresresultados para cada problema testado, de acordo com as duas características abordadas quesão tempo de execução e número de iterações. Assim é possível a realização da confecção dosgráficos a seguir:

Figura 12: Gráfico comparativo entre o número de iterações para o problema m30, FontePrópria(2013)

Figura 13: Gráfico comparativo entre o número de iterações para os problemas de grande porte,Fonte Própria(2013)

49

Figura 14: Gráfico comparativo entre o tempo de convergência em segundos para o problemam30, Fonte Própria(2013)

Figura 15: Gráfico comparativo entre o tempo de convergência em segundos para o problemaBCSSTRUC1, Fonte Própria(2013)

50

Figura 16: Gráfico comparativo entre o tempo de convergência em segundos para os problemasde grande porte, Fonte Própria(2013)

Analisando os gráficos acima, junto a tabela (28) é possível realizar o análise abaixo, deforma comparativa dos resultados.

Em análise ao problema m30, foi observado que em relação ao número de iterações ométodo de Gauss-Seidel obteve um melhor desempenho, mas com pouca diferença em relaçãoaos demais métodos, da mesma forma que em relação ao tempo de execução o mesmo métodofoi superior. Porém em relação a distância relativa o método de SRS obteve um melhor de-sempenho. É importante destacar que neste problema foram obtidos resultados próximos. Emrelação ao método de SRS pode-se notar que o melhor ω foi próximo de 1.

Em análise ao problema BCSSTRUC1, é possível observar que tanto em relação aonúmero de iterações quanto em relação ao tempo de execução o método de SRS foi superior aosdemais métodos com uma grande vantagem em relação ao método de Gauss-Seidel que obteveo segundo melhor desempenho, sendo que em relação a distância relativa o método de Gauss-Seidel obteve um melhor desempenho. É importante destacar que neste problema o método deJacobi não obteve convergência. Em relação ao método de SRS, pode-se notar que o melhor ωfoi próximo de 2 diferente do problema anterior.

Em análise ao problema pde225, destacamos que o método SRS não obteve convergên-cia utilizando o máximo de 5000 iterações, neste problema o método de Gauss-Seidel obteve omelhor desempenho em todos os aspectos levados em consideração.

Em análise ao problema MCFE, observamos que assim como o problema anterior, ométodo SRS não obteve convergência, e da mesma forma o método de Gauss-Seidel foi superiorao método de Jacobi em número de iterações e tempo de execução, porém em relação a distânciarelativa os métodos se igualaram.

Observando os resultados obtidos para o problema GR3030, é possível notar que o

51

método SRS foi superior aos demais em todos os aspectos estudados, sendo que em tempode execução e número de iterações obteve um desempenho bem elevado em relação aos demaismétodos, sendo que esse problema atende todas os critérios de convergência do método. Épossível notar também que assim como o problema BCSSTRUC1 o melhor ω foi próximo de2.

Em observação aos resultados obtidos para o problema SHERMAN1, podemos ressaltarque o método de Jacobi não obteve convergência, sendo assim será realizado uma comparaçãoentre os métodos de SRS e Gauss-Seidel. É possível notar que o método SRS foi superior nosaspectos estudados, porém é importante destacar que os resultados obtidos para o método SRStiveram uma grande vantagem em relação ao método de Gauss-Seidel, como por exemplo, umadiferença de mais de 3000 iterações entre os métodos. É possível verificar que o melhor ω paraesse problema foi próximo de 2.

O último problema analisado é o problema SHERMAN4, onde todos os métodos con-vergiram para uma aproximação da solução. Os resultados obtidos para os métodos de Jacobie Gauss-Seidel foram bastante semelhantes, levando em consideração número de iterações etempo de execução obteve uma pequena superioridade para o método de Gauss-Seidel, sendoque em relação a distância relativa o método de Jacobi foi superior, porém com pouca diferen-ça. Mesmo assim o método SRS obteve o melhor desempenho nos três aspectos analisados, aexemplo no problema anterior, o método obteve uma grande vantagem em relação aos demaismétodos. Da mesma forma que no problema anterior, o método obteve seu melhor desempenhocom ω próximo de 2.

Em geral o método estudado obteve um ótimo desempenho. O método foi mais efi-ciente em quatro dos sete problemas estudados, em dois o método não convergiu pelo fato dosproblemas não atenderem aos critérios de convergências para esse método. De certa forma,nos problemas maiores, o método obteve uma grande vantagem em relação aos demais méto-dos, obtendo uma grande redução de tempo e processamento computacional, e no problema demenor porte o método não foi tão eficiente. Em quatro de sete problema os melhores ω sãoencontrados no intervalo de 1.80 < ω < 2. Porém não foi encontrado nenhuma relação entre omelhor valor de ω e o tipo de matriz do sistema. Dessa forma, os gráficos a seguir expressambem esses resultados.

52

Figura 17: Gráfico comparativo entre os métodos, Fonte Própria(2013)

Figura 18: Gráfico demostrativo do melhor ω , Fonte Própria(2013)

53

5 CONSIDERAÇÕES FINAIS

Neste trabalho apresentamos uma revisão bibliográfica do método da SRS, que é ummétodo numérico para solução de sistemas de equações lineares. Este método pertence a classedos métodos iterativos estacionários (CAMPOS, 2010), e possui certas limitações de aplicação,pois necessita atender a condições de convergência previamente estabelecidas. A bibliografiaé relativamente escassa, mas após exaustiva pesquisa conseguimos algumas fontes que falamsobre método.

Este método, para ter a convergência garantida, deve ser aplicado em matrizes que se-jam definidas positivas, o que restringe sua aplicação a uma determinada classe de matrizes.Contudo, observadas as condições iniciais, o método mostrou um bom desempenho computa-cional, quando comparado a outros métodos iterativos estacionários, a exemplo dos métodos deGauss-Seidel e Jacobi.

A determinação do parâmetro omega é de fundamental importância para a velocidadede convergência do método. Para determinação deste parâmetro temos o teorema 2.9, quenecessita da determinação do raio espectral, e que a matriz seja tridiagonal. Nos casos em que amatriz é apenas simétrica definida positiva, esta equação não pode ser aplicada. Também exigea determinação do maior autovalor em módulo, o que é um procedimento relativamente custosocomputacionalmente, chegando a alguns casos a ter um esforço computacional maior do que aresolução do próprio sistema (CAMPOS, 2010)

Em geral, o método mostrou-se com um desempenho superior aos demais métodos estu-dados, destacando superioridade em quatro dos problemas analisados. No problema m30, o de-sempenho foi equivalente e nos problemas pde225 e MCFE, o método não obteve convergência.Este último fato ocorreu pelo motivo das matrizes não serem positivas definidas, o que acaba pornão garantir a convergência do método de SRS. Salientamos que os problemas SHERMAN1 eSHERMAN4 as matrizes não eram positivas definidas, mas obtivemos convergência do métodopara a solução do sistema. Esta condição é suficiente, porém não é necessária.

Nos problemas de grande porte GR3030, SHERMAN1 e SHERMAN4 o método teveum desempenho bastante superior aos demais métodos iterativos, chegando a utilizar apenas6,34% do tempo gasto pelo método de Gauss-Seidel para a resolução do mesmo problema.

Sugestões para trabalhos futuros

Os resultados obtidos neste trabalho foi de certa forma favoráveis para a utilização dométodo SRS, este apresentou bons resultados, porém é um trabalho em que foi testado diversosvalores para o fator ω desta forma sugere-se um futuro trabalho com intuito de buscar comodeterminar o valor de melhor ω a ser utilizado para cada tipo de problema, desta forma melho-rando a utilização do método de Sobre Relaxação Sucessiva - SRS.

54

REFERÊNCIAS

ARENALES, Selma; DAREZZO, Artur. Cálculo Numérico: Aprendizagem com Apoio deSoftware. 1a ed. São Paulo: Thomson, 2008.

BOLDRINI, José Luiz; COSTA, Sueli I. Rodrigues; FIGUEIREDO, Vera Lúcia; WETZLER,Henry G.Álgebra Linear, ampliada e revisada, 3a Edição, Editora HARBRA Ltda. 1980.

BURDEN, Richard L; FAIRES, Douglas. Análise Numérica. São Paulo: Cengage, 2008.

CALLIOLI, Carlos A.; DOMINGUES, Hygino H.; COSTA, Roberto C. F. Algebra Lineare Aplicações. 6a ed. rev. São Paulo: Atual, 1990.

CAMPOS, Filho; FERREIRA, Frederico. Algoritmos Numéricos. 2. ed. Rio de Janeiro:Ltc, 2010.

FRANCO, Neide Bertold. Cálculo Numérico. São Paulo: Prentice Hall, 2006.

FREITAS, Sérgio Roberto de.Métodos Numéricos. Notas de Aula, 2000, disponível em <htt p ://www.decom.u f op.br/bob/com400/livros/livro1.pd f > . Acesso em: 06 nov. 2011.

GAVALA, Francisco Javier Cobos. Cálculo Numérico: Apuntes para el curso de 2001-2002.Disponível em: <www.decom.u f op.br/bob/com400/livros/ap_cal_num_esp.pd f >. Acessoem: 30 ago. 2011.

JUNIOR, Valdenir de Souza. Cálculo Numérico Algoritmos. Notas de Aula, 2007, disponivelem: <htt p : //vsouza junior.coolpage.biz/doc/cnalgoritmos.pd f >. Acesso em: 05 de jan.2013.

LEON, Steven J. Álgebra Linear: com aplicações. 8a ed. Rio de Janeiro: LTC, 2011.

LIPSCHUTZ, Seymour; LIPSON, Marc Lars. Teoria E Prob. de Algebra Linear. 3a ed.São Paulo: BOOKMAN, 2004.

MATRIX MARKET - Um repositório visual de dados de teste para uso em estudos com-parativos de algoritmos para álgebra linear numérica, disponível em<http://math.nist.gov/MatrixMarket/>. Acesso 05 de jan. 2013.

OLIVEIRA, João Paulo Carau de. Proposta preliminar de um método interativo híbridopara a resolução de sistemas de equações lineares. 2012. 51 f. Trabalho de Conclusão deCurso - Universidade Federal Rural do Someárido - UFERSA, Angicos, 2012.

RUGGIERO, Márcia A. Gomes; LOPES, Vera Lúcia da Rocha. Cálculo Numérico: AspectosTeóricos e Computacionais. 2. ed. São Paulo: Makron Books, 1996.

SPERANDIO, Délcio. Cálculo Numérico: Características matemáticas e computacionaisdos métodos numéricos. São Paulo: Pearson Pretice Hall, 2003.

Documents

UNIVERSIDADE FEDERAL RURAL DO SEMIÁRIDO - UFERSA ... · do método de Sobre Relaxação Sucessiva - SRS, ... exemplo, na análise de um circuito elétrico, no cálculo estrutural