Métodos Iterativos_Sistemas Lineares

5/10/2018 Métodos Iterativos_Sistemas Lineares - slidepdf.com

http://slidepdf.com/reader/full/metodos-iterativossistemas-lineares 1/24

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA MECÂNICA

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

Disciplina: Métodos MatriciaisProfessora: Liliane Basso BarichelloAluno: Tiago dos Santos

Porto Alegre

2010



2

SUMÁRIO

RESUMO.......................................................................................................................... 3

1 MÉTODOS ITERATIVOS PARA SOLUÇÃO DE SISTEMAS LINEARES ................. 4

1.1 Introdução .......................................................................................................... 4 1.2 Condição de Convergência ................................................................................ 5 1.3 Critério de Parada .............................................................................................. 6 1.4 Método Iterativo de Jacobi ................................................................................. 6

1.4.1 Algorítmo e Complexidade .......................................................................... 8 1.5 Método Iterativo de Gauss-Seidel ...................................................................... 9

1.5.1

Algorítmo e Complexidade ........................................................................ 10

1.6 Método Iterativo da Sobre-Relaxação Sucessiva ............................................ 12 1.6.1 Algorítmo e complexidade ........................................................................ 13

2 RESULTADOS NUMÉRICOS ................................................................................. 15

2.1 Primeiro Caso .................................................................................................. 15 2.2 Segundo Caso ................................................................................................. 17

3 DISCUSSÃO DOS RESULTADOS ......................................................................... 22

4 CONCLUSÃO ......................................................................................................... 23

REFERÊNCIAS BIBLIOGRÁFICAS ............................................................................... 24



3

RESUMO

Neste trabalho serão apresentados e implementados computacionalmente,

utilizando o programa Matlab, três métodos iterativos para solução de sistemas lineares:

método de Jacobi, método de Gauss-Seidel e método da sobre-relaxação prograssiva.

Onde, por meio da solução de dois problemas numéricos, os métodos acima citados

serão comparados utilizando-se uma análise de convergência para os problemas.

Também serão analisados os raios espectrais das matrizes de iteração de cada método

nos distintos problemas solucionados.

Particularmente para o método da sobre-relaxaçã sucessiva, será analisada a

influência do parâmetro ω na convergência da solução.

Com base nos resultados obtidos, método da sobre-relaxação mostrou melhor

convergência nos dois problemas, em segundo lugar está o método de Gauss-Seidel.

Essa ordem também foi verificada nos raios espectrais das matrizes de iteração, onde a

matriz de iteração da sobre-relaxação apresentou menor raio espectral e o método de

Jacobi aprsentou o maior valor, em ambos sistemas lineares solucionados.



4

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

1.1 Introdução

Um sistema de equações lineares b Ax = pode ser resolvido por um processo

onde, a partir de um vetor inicial0

x , uma seqüência de vetores }{321

KK , , , , , k x x x x

é gerada de modo a convergir para a solução x do sistema. Nesse processo é

realizada uma série de operações repetidas, e por isso tal processo é denominado

iterativo.

Dado o sistema linear:

;3,2,1;

;

1

mi x Abn

j

jiji K==

=

∑=

b Ax

(1.1.1)

Onde, b é um vetor de constantes de ordm m , A é a matriz de coeficientes de

tamanho nm× e x é o vetor solução de ordem n .

Sendo A uma matriz quadrada nn× , isolando-se o ésimoi − valor de x para

cada linha i do sistema, obtém-se:

;3,2,1;1

;3,2,1;

1

1

ni x A A A

b x

ni x Ab x A

n

i j j

jij

iiii

ii

n

i j j

jijiiii

K

K

=−=

=−=

∑

∑

≠

=

≠

=

(1.1.2)

(1.1.3)

No processo iterativo a eq. (1.1.3) pode ser representada conforme eq. (1.1.4).



5

;1

c Mx x +=+ k k

(1.1.4)

Onde, é a matriz de iteração e c é um vetor constante. O processo iterativo

é dito estacionário se não for alterada durante o processo. A seguir serão

apresentados três métodos iterativos estacionários: método de Jacobi, método de

Gauss-Seidel e método da sobre-relaxação sucessiva.

1.2 Condição de Convergência

A sequência de vetores solução }{321

KK , , , , , k x x x x converge para a solução

do sistema linear b Ax = , quando satisfeito o seguinte teorema:

Teorema 1.1: O método iterativo da eq. (1.1.4) converge com qualquer valor

inicial0

x se e somente se, 1)( < M , sendo )( M o raio espectral (módulo do

maior autovalor) da matriz de iteração M .

No entanto, a determinação de )( M ρ pode requerer maior esforço numérico

que a própria solução do sistema b Ax = . Por isso, usualmente se utiliza o chamado

critério das linhas para convergência, segundo o teorema:

Teorema 1.2 : É condição suficiente para a convergência dos métodos iterativos

de Jacobi e de Gauss-Seidel que a matriz dos coeficientes A seja diagonalmente

predominante, ou seja:

niaan

i j j

ijii K3,2,1;1

=>∑≠

=

(1.2.1)

Pelos Teoremas 1.1 e 1.2 , nota-se que a convergência não depende da escolha

do vetor inicial0

x . Outro critério de convergência é que o sistema iterativo (1.1.4)

converge se e somente se 0→k

M com ∞→k .



6

1.3 Critério de Parada

A cada iteração do processo descrito na eq. (1.1.4) o vetor solução obtido é mais

próximo da solução do sistema linear b Ax = , isto é:

;lim x x =→∞

k

k (1.3.1)

Como critério de parada do processo pode-se definir um erro relativo máximo

aceitável ε :

;

1

k

k k

x

x x−

−≥ε (1.3.2)

Ou limitar o número de operações, conforme a seguinte relação:

;máxk k ≥ (1.3.3)

Onde, máxk é o número máximo de iterações.

Para a determinação da tolerência ε , deve-se considerar a perda de precisão

devido à aritmética de ponto flutuante, para que não se defina uma exatidão impossível

de ser alcançada.

1.4 Método Iterativo de Jacobi

Considerando um sistema linear:

; b Ax = (1.4.1)



7

A matriz A pode ser decomposta em:

;U D L A ++= (1.4.2)

Onde, D é uma matriz diaginal, L e U são duas matrizes triangulares inferior

e superior, respectivamente, com a diagonal nula. Substituindo a eq. (1.4.2) na eq.

(1.4.1), obtém-se:

;

;)(

;)(

;)(;)(

1

111

c Jx x

b D xU L D x

b xU L Dx

b xU L Dx b xU D L

+=

++−=

++−=

=++

=++

+

−−+

k k

k k

(1.4.3)

(1.4.4)

(1.4.5)

A eq. (1.4.5) é semelhante à eq. (1.1.4), onde )(1

U L D J +=−

é a matriz de

iteração do método de Jacobi.

Usualmente, utiliza-se como valor inicial 0 x =0

; no entanto, substituindo esse

valor na eq. (1.4.5), obtem-se:

;1

ii

ii

A

b x =→= c x

Assim, será tomado como valor inicial

.0

ii

ii

A

b x = (1.4.6)



8

1.4.1 Algorítmo e Complexidade

Figura 1.4.1 – Rotina do método iterativo de Jacobi em Matlab.

function [x,Niter,erros,Conv]=ijacobi(A,b,Tol,IterMax)

% Esta rotina soluciona um sistema linear do tipo Ax=b, pelo método % iterativo de Jacobi. % Parâmetros de entrada: % A: Matriz de coeficientes nxn; % b: Vetor de constantes; % Tol: Tolerância desejada; % IterMax: Número máximo de iterações desejado. % Parâmetros de saída: % x: vetor solução; % Niter: Número de iterações realizadas; % erro: Erro relativo em norma infinita;

% Conv: Informação de convergência (Conv=1 houve convergência; Conv=1 não % houve convergência).

[m,n]=size(A); % Verifica tamanho da matriz A if m == n % Verifica se A é uma matriz quadrada

xi = zeros(m,1); % Cria vetor solução inicial x = zeros(m,1); % Cria vetor solução final for i = 1 : m

if A(i,i) == 0 error('A possui zero na diagonal')

end xi(i) = b(i)/A(i,i); % Monta vetor solução inicial

end erro = 1; % Atribui valor inicial ao erro Niter = 0; % Número de iterações

while erro > Tol Niter = Niter + 1; if Niter == IterMax

Conv = 0; error('Número máximo de iterações foi atingido')

end for i = 1 : m

soma = 0; for j = 1 : n

if i ~= j soma = A(i,j)*xi(j) + soma;

end end

x(i) = (-soma + b(i))/A(i,i); end erro = norm(x - xi, inf)/norm(x,inf); % Erro relatifo (N inf) erros(Niter) = erro; % Vetor contendo o erro de cada iteração xi = x;

end Conv = 1;

else disp('A não é uma matrix quadrada')

end



9

Na fig. (1.4.1) é apresentada a rotina, criada no ambiente Matlab, que resolve um

sistema linear do tipo b Ax = pelo método iterativo de Jacobi. Os parâmetros deentrada são: a matriz A , o vetor b , a tolerância desejada ε e o número máximo de

iterações máxk . Os dois últimos parâmetros são utilizados como critérios de parada,

conforme eqs. (1.3.2) e (1.3.3), respectivamente. E tem como parâmetros de saída o

vetor solução x , o número de iterações k , o erro relativok

ε em norma infinita de

cada iteração e informa se ocorreu convergência dentro do número de iterações

escolhido com base na tolerância informada ( 1=Conv ) ou não ( 0=Conv ).

A complexidade computacional do algorítmo é dada segundo a tab. (1.4.1).

Operações Complexidade

adições k knkn ++2

multiplicações knnk −+2

)1(

divisões k n +

Tabela 1.4.1 – Complexidade de Jacobi usando k iterações em sistema de ordem n > 1.(Campos, filho, 2001).

1.5 Método Iterativo de Gauss-Seidel

Seja o sistema linear mostrado na eq. (1.4.1), com a matriz A sendo

decomposta em U D L A ++= , sendo D uma matriz diaginal, L e U duas

matrizes triangulares inferior e superior, respectivamente, com a diagonal nula. O

sistema linear pode, então, ser reescrito na seguinte forma:

;

;)()(

;)(

;)(

1

111

d Sx x

b L DUx L D x

bUx x L D

b xU D L

+=

+++−=

+−=+

=++

+

−−+

k k

k k

(1.5.1)

(1.5.2)

(1.5.3)



10

Onde, U L DS 1)( −+−= é a matriz de iteração do método de Gauss-Seidel.

Uma maneira mais simples de implementar, sem a necessidade de calcular a matriz

inversa é mostrado abaixo:

;

;)(

;)(

;)(

11

1

bUx Lx Dx

bUx x L D

bUx x L D

b xU D L

+−−=

+−=+

+−=+

=++

++

+

k k k

k k

(1.5.4)

Na eq. (1.5.4) fica clara a diferença entre os métodos de Jacobi e Gauss-Seidel.

No método de Jacobi o vetor1+k

x é calculado usando somente valoresk

i x , enquanto,

no método de Gauss-Seidel o vetor1+k

x é obtido a partir dos elementos mais recentes,

incluindo1+k

x ek

x . O valor inicial utilizado será o mesmo da eq. (1.4.6).

1.5.1 Algorítmo e Complexidade

Na fig. (1.5.1) é apresentada a rotina, criada no ambiente Matlab, que resolve um

sistema linear do tipo b Ax = pelo método iterativo de Gauss-Seidel. Os parâmetros

de entrada são: a matriz A , o vetor b , a tolerância desejada ε e o número máximo de

iterações máxk . Os dois últimos parâmetros são utilizados como critérios de parada,

conforme eqs. (1.3.2) e (1.3.3), respectivamente. E tem como parâmetros de saída o

vetor solução x , o número de iterações k , o erro relativok

ε em norma infinita de

cada iteração e informa se ocorreu convergência dentro do número de iterações

escolhido com base na tolerância informada ( 1=Conv ) ou não ( 0=Conv ).



11


function [x,Niter,erros,Conv]=igauss_seidel(A,b,Tol,IterMax) % Esta rotina soluciona um sistema linear do tipo Ax=b, pelo método % iterativo de Gauss-Seidel. % Parâmetros de entrada: % A: Matriz de coeficientes nxn; % b: Vetor de constantes; % Tol: Tolerância desejada; % IterMax: Número máximo de iterações desejado. % Parâmetros de saída: % x: vetor solução; % Niter: Número de iterações realizadas; % erro: Erro relativo em norma infinita; % Conv: Informação de convergência (Conv=1 houve convergência; Conv=1 não % houve convergência). [m,n]=size(A); % Verifica tamanho da matriz A

if m == n % Verifica se A é uma matriz quadrada xi = zeros(m,1); % Cria vetor solução inicial x = zeros(m,1); % Cria vetor solução final for i = 1 : m


end xi(i) = b(i)/A(i,i); % Monta vetor solução inicial xi1 = xi; % Vetor que armazena valores iniciais de xi

end erro = 1; % Atribui valor inicial ao erro Niter = 0; % Número de iterações while erro > Tol

Niter = Niter + 1; if Niter == IterMax


end for i = 1 : m

soma = 0; for j = 1 : n


end end x(i) = (-soma + b(i))/A(i,i); xi(i) = x(i); % Atualiza o vetor solução inicial

end erro = norm(x - xi1, inf)/norm(x,inf); % Erro relatifo (N inf) erros(Niter) = erro; % Vetor contendo o erro de cada iteração xi = x; xi1 = xi;

end Conv = 1;


end



12

A complexidade computacional do algorítmo é dada segundo a tab. (1.5.1).

Operações Complexidade

adições k knkn ++2

multiplicações knnk −+2

)1(

divisões k n +

Tabela 1.5.1 – Complexidade de Gauss-Seidel usando k iterações em sistema de ordem n > 1.(Campos, filho, 2001).

1.6 Método Iterativo da Sobre-Relaxação Sucessiva

Considerando o sistema linear da eq. (1.4.1), com a matriz A sendo

decomposta em U D L A ++= , sendo D uma matriz diaginal, L e U duas

matrizes triangulares inferior e superior, respectivamente, com a diagonal nula.

Multiplicando o sistema linear por um parâmetro ω , tem-se:

;)( b xU D L ω ω =++ (1.6.1)

Somando o vetor nulo x D D )( − ao primeiro termo:

;

;)(])1[()(

;])1[()(

;])1[()(

;)()(

1

111

1

e Rx x

b L D xU D L D x

b xU D x L D

b xU D x L D

b xU D L x D D

+=

++−−+=

+−−=+

+−−=+

=+++−

+

−−+

+

k k

k k

k k

ωωωω

ωωω

ωωω

ω

ω

ω

ω ω

(1.6.2)

(1.6.3)

Onde, ])1[()(1

U D L D R ωωω −−+=−

é a matriz de iteração do método da

sobre-relaxação sucessiva (SOR: sucessive over-relaxation ).



13

Uma outra maneira de representar a forma de iteração do método da sobre-

relaxação é a seguinte, a partir da eq. (1.6.2):

;)1()(

;)1()(

;])1[()(

111

11

1

k k k k

k k k k

k k

ωω

ωω

ωωω

x bUx Lx D x

Dx bUx Lx Dx

b xU D x L D

−++−−=

−++−−=

+−−=+

+−+

++

+ω

(1.6.4)

O valor inicial utilizado para a iteração será o mesmo da eq. (1.4.6).

A convergência do método SOR depende da escolha do parâmetro ω , énecessário que 20 <<ω para garantir a convergência. Usualmente, utiliza-se

21 <<ω . Um valor ótimo de ω pode ser calculado segundo a eq. (1.6.5).

;)(11

2

2 J ρ −+

=otimω (1.6.5)

Onde, J é a matriz iterativa do método de Jacobi.

Na equação anterior otimω é determinado de forma a produzir o menor raio

espectral da matriz de iteração no método SOR.

1.6.1 Algorítmo e complexidade

Na fig. (1.6.1) é apresentada a rotina, criada no ambiente Matlab, que resolve umsistema linear do tipo b Ax = pelo método iterativo da sobre-relaxação sucessiva. Os

parâmetros de entrada são: a matriz A , o vetor b , a tolerância desejada ε , o número

máximo de iterações máxk e o parâmetro ω . Os valores de ε e máxk são utilizados

como critérios de parada, conforme eqs. (1.3.2) e (1.3.3), respectivamente.

A complexidade do método SOR é a mesma mostrada na tab. (1.5.1).



14


function [x,Niter,erros,Conv]=SOR(A,b,Tol,IterMax,w) % Esta rotina soluciona um sistema linear do tipo Ax=b, pelo método % iterativo da sobre-relaxação sucessiva. % Parâmetros de entrada: % A: Matriz de coeficientes nxn; b: Vetor de constantes; % Tol: Tolerância desejada; % IterMax: Número máximo de iterações desejado; % w: parâmetro 0 < w < 2 % Parâmetros de saída: % x: vetor solução; % Niter: Número de iterações realizadas; % erro: Erro relativo em norma infinita; % Conv: Informação de convergência (Conv=1 houve convergência; Conv=1 não % houve convergência). [m,n]=size(A); % Verifica tamanho da matriz A

if m == n % Verifica se A é uma matriz quadrada xi = zeros(m,1); % Cria vetor solução inicial x = zeros(m,1); % Cria vetor solução final for i = 1 : m


end xi(i) = b(i)/A(i,i); % Monta vetor solução inicial xi1 = xi; % Vetor que armazena valores iniciais de xi

end erro = 1; % Atribui valor inicial ao erro Niter = 0; % Número de iterações while erro > Tol

Niter = Niter + 1; if Niter == IterMax


end for i = 1 : m

soma = 0; for j = 1 : n


end end x(i) = w*(-soma + b(i))/A(i,i) + (1 - w)*xi(i); xi(i) = x(i); % Atualiza o vetor solução inicial

end erro = norm(x - xi1, inf)/norm(x,inf); % Erro relatifo (N inf) erros(Niter) = erro; % Vetor contendo o erro de cada iteração xi = x; xi1 = xi;

end Conv = 1;


end



15

E tem como parâmetros de saída o vetor solução x , o número de iterações k , o

erro relativo k ε em norma infinita de cada iteração e informa se ocorreu convergência

dentro do número de iterações escolhido com base na tolerância informada ( 1=Conv )

ou não ( 0=Conv ).

2 RESULTADOS NUMÉRICOS

Nessa seção serão analisados dois sistemas lineares distintos, utilizando-se os

três métodos iterativos apresentados no trabalho: método de Jacobi, método de Gauss-

Seidel e método da sobre-relaxação sucessiva. Sobre esses dois problemas serão

realizadas análises de convergência e do raio espectral de cada matriz de iteração.

2.1 Primeiro Caso

O primeiro problema numérico a ser análisado consiste em um exercício

proposto por Datta, 1995, exercício 49 página 307. Dado pelo seguinte sistema linear:

;

0

0

0

0

0

1

410100

141010

014001

100410

010141

001014

6

5

4

3

2

1

=

−−

−−−

−−

−−

−−−

−−

x

x

x

x

x

x

(2.1.1)

Como critérios de parada serão utilizados os seguintes valores:

;30

;001.0

=

=

máxk

ε

(2.1.2)



16

Na resolução do sistema linear pelo método SOR será utilizado o valor ótimo do

parâmetro ω , o qual resulta em 128.1=otimω .

Foram obtidos os seguintes valores valores para os raios espectrais das matrizes

de iteração para cada processo, conforme tab. (2.1.1).

( ) 6036,0= J ρ ( ) 3643,0=S ρ ( ) 1128,0= R ρ

Tabela 2.1.1 – Raios espectrais das matrizes de iteração para o primeiro caso.

Na fig. (2.1.1) são mostrados os valores dos erros relativos, obtidos pela norma

infinita, para cada iteração nos três métodos utilizados.

0 1 2 3 4 5 6 7 8 9 10 11 12

0

0.05

0.1

0.15

0.2

0.25

0.3

0.35

Número de iterações - κ

E r r o

r e l a t i v o

- ε

Análise de Convergência

Método de Jacobi

Método de Gauss-Seidel

Método da Sobre-Relaxação

Figura 2.1.1 – Análise de convergência para o primeiro caso.

Particularmente para o método SOR, é analisada a influência do parâmetro ω

na convergência da solução. A análise é realizado comparando-se o número de

iterações necessárias para que se atinja a tolerância desejada, para valores de

5,11 <<ω , com incrementos de 05,0=∆ω . Conforme fig. (2.1.2).



17

1 1.05 1.1 1.15 1.2 1.25 1.3 1.35 1.4 1.45 1.55

5.5

6

6.5

7

7.5

8

8.5

9

9.5

10

Parâmetro ω

N ú m e r o d e i t e r a ç õ e s - κ

Análise de convergência com relação aω

Figura 2.1.2 – Análise de convergência com relação a ω para o primeiro caso.

2.2 Segundo Caso

No segundo problema será resolvido um sistema linear cuja matriz de

coeficientes A é uma matriz esparsa de ordem 3636× , mostrada nas tabs. (2.2.1),

(2.2.2) e (2.2.3). E b é um vetor de ordem 36 , dado por:

.36,...,2,1:];34,14,1[:;0

;34:;2

];14,1[:;1

=

≠

=

=

=icom

i parai para

i para

bi (2.2.1)

Como critérios de parada serão utilizados os seguintes valores:

;100

;005.0

=

=

máxk

ε

(2.2.2)



18

Matriz A - coluna 01 a 12

0,0216 0 0 0 0 0 0 0 0 0 0 00 0,1963 0 0 0 0 0 0 0 0 0 0

0 0 5,7512 0 0 0 0 0 0 0 0 0

0 0 0 1,081 0 0 0 0 0 0 0 0

0 0 0 0 5,7512 0 0 0 0 0 0 -0,4601

0 0 0 0 0 0,0202 0 0 0 0 0 0

0 0 0 0 0 0 0,1618 0 0 0 0 0

0 0 0 0 0 0 0 0,1618 0 0 0 0

0 0 0 0 0 0 0 0 1,0135 0 0 0

0 0 0 0 0 0 0 0 0 5,3918 0 0

0 0 0 0 0 0 0 0 0 0 5,3918 00 0 0 0 -0,4601 0 0 0 0 0 0 0,1963

-0,0108 0 0 0 0 0 0 0 0 0 0 0

0 -0,0982 0,4601 0 0 0 0 0 0 0 0 0

0 -0,4601 1,4378 0 0 0 0 0 0 0 0 0

0 0 0 -0,5405 0 0 0 0 0 0 0 0

0 0 0 0 1,4378 0 0 0 0 0 0 0

0 0 0 0 0 -0,0101 0 0 0 0 0 0

0 0 0 0 0 0 -0,0809 0 0 0 -0,4044 0

0 0 0 0 0 0 0 -0,0809 0 0,4044 0 0

0 0 0 0 0 0 0 0 -0,5067 0 0 00 0 0 0 0 0 0 -0,4044 0 1,3479 0 0

0 0 0 0 0 0 0,4044 0 0 0 1,3479 0

0 0 0 0 0 0 0 0 0 0 0 -0,0982

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0,4601

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

Tabela 2.2.1 – Matriz de coeficientes A, coluna 01 a 12.



19


-0,0108 0 0 0 0 0 0 0 0 0 0 00 -0,0982 -0,4601 0 0 0 0 0 0 0 0 0

0 0,4601 1,4378 0 0 0 0 0 0 0 0 0

0 0 0 -0,5405 0 0 0 0 0 0 0 0

0 0 0 0 1,4378 0 0 0 0 0 0 0

0 0 0 0 0 -0,0101 0 0 0 0 0 0

0 0 0 0 0 0 -0,0809 0 0 0 0,4044 0

0 0 0 0 0 0 0 -0,0809 0 -0,4044 0 0

0 0 0 0 0 0 0 0 -0,5067 0 0 0

0 0 0 0 0 0 0 0,4044 0 1,3479 0 0

0 0 0 0 0 0 -0,4044 0 0 0 1,3479 00 0 0 0 0 0 0 0 0 0 0 -0,0982

0,0216 0 0 0 0 0 0 0 0 0 0 0

0 0,1963 0 0 0 0 0 0 0 0 0 0

0 0 5,7512 0 0 0 0 0 0 0 0 0

0 0 0 1,081 0 0 0 0 0 0 0 0

0 0 0 0 5,7512 0 0 0 0 0 0 -0,4601

0 0 0 0 0 0,0202 0 0 0 0 0 0

0 0 0 0 0 0 0,1618 0 0 0 0 0

0 0 0 0 0 0 0 0,1618 0 0 0 0

0 0 0 0 0 0 0 0 1,0135 0 0 00 0 0 0 0 0 0 0 0 5,3918 0 0

0 0 0 0 0 0 0 0 0 0 5,3918 0

0 0 0 0 -0,4601 0 0 0 0 0 0 0,1963

-0,0108 0 0 0 0 0 0 0 0 0 0 0

0 -0,0982 0,4601 0 0 0 0 0 0 0 0 0

0 -0,4601 1,4378 0 0 0 0 0 0 0 0 0

0 0 0 -0,5405 0 0 0 0 0 0 0 0

0 0 0 0 1,4378 0 0 0 0 0 0 0

0 0 0 0 0 -0,0101 0 0 0 0 0 0

0 0 0 0 0 0 -0,0809 0 0 0 -0,4044 0

0 0 0 0 0 0 0 -0,0809 0 0,4044 0 0

0 0 0 0 0 0 0 0 -0,5067 0 0 0

0 0 0 0 0 0 0 -0,4044 0 1,3479 0 0

0 0 0 0 0 0 0,4044 0 0 0 1,3479 0

0 0 0 0 0 0 0 0 0 0 0 -0,0982




20


0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0,4601 0 0 0 0 0 0 0

-0,0108 0 0 0 0 0 0 0 0 0 0 0

0 -0,0982 -0,4601 0 0 0 0 0 0 0 0 0

0 0,4601 1,4378 0 0 0 0 0 0 0 0 0

0 0 0 -0,5405 0 0 0 0 0 0 0 0

0 0 0 0 1,4378 0 0 0 0 0 0 0

0 0 0 0 0 -0,0101 0 0 0 0 0 0

0 0 0 0 0 0 -0,0809 0 0 0 0,4044 0

0 0 0 0 0 0 0 -0,0809 0 -0,4044 0 0

0 0 0 0 0 0 0 0 -0,5067 0 0 00 0 0 0 0 0 0 0,4044 0 1,3479 0 0

0 0 0 0 0 0 -0,4044 0 0 0 1,3479 0

0 0 0 0 0 0 0 0 0 0 0 -0,0982

0,0216 0 0 0 0 0 0 0 0 0 0 0

0 0,1963 0 0 0 0 0 0 0 0 0 0

0 0 5,7512 0 0 0 0 0 0 0 0 0

0 0 0 1,081 0 0 0 0 0 0 0 0

0 0 0 0 5,7512 0 0 0 0 0 0 -0,4601

0 0 0 0 0 0,0202 0 0 0 0 0 0

0 0 0 0 0 0 0,1618 0 0 0 0 0

0 0 0 0 0 0 0 0,1618 0 0 0 0

0 0 0 0 0 0 0 0 1,0135 0 0 0

0 0 0 0 0 0 0 0 0 5,3918 0 0

0 0 0 0 0 0 0 0 0 0 5,3918 0

0 0 0 0 -0,4601 0 0 0 0 0 0 0,1963




21

Na resolução do sistema linear pelo método SOR será utilizado o valor ótimo do

parâmetro ω , o qual resulta em 4784.1=otimω .

Foram obtidos os seguintes valores valores para os raios espectrais das matrizes

de iteração para cada processo, conforme tab. (2.2.4).

( ) 9357,0= J ρ ( ) 8755,0=S ρ ( ) 4784,0= R ρ

Tabela 2.2.4 – Raios espectrais das matrizes de iteração para o primeiro caso.

Na fig. (2.2.1) são mostrados os valores dos erros relativos, obtidos pela norma

infinita, para cada iteração nos três métodos utilizados.

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 3435

0

0.2

0.4

0.6

0.8

Número de iterações - κ

E r r o r e l a t i v o - ε

Análise de Convergência

Método de JacobiMétodo de Gauss-Seidel

Método da Sobre-Relaxação

Figura 2.2.1 – Análise de convergência para o segundo caso.

A análise de convergência em função do parâmetro ω para o segundo problema

é mostrada na fig. (2.2.2), para valores de 75,125,1 <<ω , com incrementos de

05,0=∆ω .



22

1.25 1.3 1.35 1.4 1.45 1.5 1.55 1.6 1.65 1.7 1.759

10

11

12

13

14

15

16

17

Parâmetro ω

N ú m e r o d e i t e r a ç õ e s - κ

Análise de convergência com relação a ω

Figura 2.2.2 – Análise de convergência com relação a ω para o segundo caso.

3 DISCUSSÃO DOS RESULTADOS

Nas tabs. (3.1.1) e (3.1.2) são mostrados os números de iterações necessárias

para a convergência do primeiro e segundo problema apresentados, sob a condição da

tolerância desejada, e os valores finais dos erros relativos obtidos para cada método.

Jacobi Gauss-Seidel SOR

Número de iter. 12 7 5

Erro relativo 0,0007 0,0005 0,0006

Tabela 3.1.1 – Resultados de convergência para o primeiro caso.

Jacobi Gauss-Seidel SOR

Número de iter. 31 21 9

Erro relativo 0,005 0,0048 0,005

Tabela 3.1.2 – Resultados de convergência para o segundo caso.



23

Em observação às figs. (2.1.1), (2.2.1) e às tabs. (3.1.1), (3.1.2) nota-se, que

apesar de obter um erro inicial mais alto, o método iterativo SOR convergiu maisrapidamente para ambos os sistemas lineares solucionados, atingindo a tolerância

desejada para cada um deles. O segundo mais rápido foi o método de Gauss-Seidel.

Esses resultados de convergência eram esperados, pois os raios espectrais das

matrizes de iteração dos diferentes métodos seguem a mesma ordem apresentada na

análise de convergência, para ambos os problemas.

Nas análises realizadas em função do parâmetro ω , mostradas nas figs. (2.1.2)

e (2.2.2), observa-se que realmente o método SOR converge para a solução, mais

rapidamente, quando utilizado o valor de otimω , que para o primeiro caso foi

128.1=otimω e para o segundo 4784.1=otimω .

4 CONCLUSÃO

Com a realização desse trabalho é possível notar que cada um dos métodosnuméricos utilizados possui suas características próprias, estritamente ligadas às

propriedades das matrizes de iteração. Para os problemas analisados o método

iterativo da sobre-relaxação sucessiva se mostrou ser mais eficiente. Porém, os três

métodos são limitados quanto à generalidade da matriz de coeficientes A , essa não

pode possuir valores nulos na diagonal principal, o que vai de encontro à condição de

ser uma matriz diagonalmente dominante, Teorema 1.2. E essa mesma matriz deve

possuir um baixo valor do raio espectral, Teorema 1.1.Também é possível perceber que a implementação computacional desses

métodos numéricos possui diferenças e particularidades quando comparada ao

problema analítico. Algumas pré-analises são necessárias para a definição e

implementação do métódo numérico a ser utilizado.



24

REFERÊNCIAS BIBLIOGRÁFICAS

Bronson, R. "Matrix Operations", Mac Graw Hill, 1989.

Campos, filho, F. F. “Algorítmos Numéricos”, LTC, 2001.

Datta, B. N. “Numerical Linear Algebra and Applications”. Brooks/Cole Publishing,

1995.

Golub, G., Van Loan, C."Matrix Computations", John Hopkins, 1984.

Documents

Métodos Iterativos_Sistemas Lineares