Métodos para Solução de Sistemas Lineares

Prévia do material em texto

Me´todos diretos e iterativos para a soluc¸a˜o de
Sistemas de Equac¸o˜es Lineares
Rafael K. S. Silva, Rodrigo Calheiros
Pontif´ıcia Universidade Cato´lica do Rio Grande do Sul
Avenida Ipiranga 6681, Telefone 5133203558 ramal 4463, Fax: 5133203758
{rksilva, rcalheiros}@inf.pucrs.br
Abstract
Resolution of linear equations systems
(SELAS) is much useful to solve several prob-
lems in different areas. This work shows the
concepts and use forms of the main direct and
iterative methods to SELA’s resolution. More
precisely, it presents the Gauss, Gauss-Jacobi e
Gauss-Seidel methods. Furthermore, other re-
sources used in SELA’s solution are presented.
Resumo
A resoluc¸a˜o de sistemas de equac¸o˜es li-
neares (SELAS) e´ bastante u´til para solucionar
diversos problemas de variadas a´reas. Este tra-
balho aborda os conceitos e formas de utilizac¸a˜o
dos principais me´todos diretos e iterativos para
a resoluc¸a˜o de SELAS. Mais precisamente,
apresenta-se os Me´todos de Gauss, Gauss-Jacobi
e Gauss-Seidel. Ale´m disso, sa˜o apresentados
outros recursos utilizados na soluc¸a˜o de SELAS.
1 Introduc¸a˜o
Muitos problemas de matema´tica
nume´rica sa˜o modelados em func¸a˜o de um
Sistema de Equac¸o˜es Lineares (SELA). Isso
vale em geral para o tratamento nume´rico de
equac¸o˜es funcionais lineares que ocorrem, entre
outras, como equac¸o˜es diferenciais parciais ou
ordina´rias e equac¸o˜es integrais que surgem em
diversos problemas da F´ısica e Engenharia [2].
Um dos problemas mais comuns em si-
tuac¸o˜es tecnolo´gicas e´ a soluc¸a˜o de m equac¸o˜es
lineares com n inco´gnitas, descrito como A−→x =
−→
b . O tratamento dessa espe´cie de problema
e sua teoria e´ feito na A´lgebra Linear. Este
trabalho se ocupara´ apenas com o tratamento
nume´rico que o problema requer. Mais precisa-
mente, sera˜o abordadas duas classes gerais de al-
goritmos para a resoluc¸a˜o de equac¸o˜es A−→x =
−→
b .
Trata-se dos Me´todos Diretos e Iterati-
vos para resoluc¸a˜o de SELAS. Um me´todo e´
dito direto quando a soluc¸a˜o exata −→x e´ ob-
tida realizando-se um nu´mero finito de operac¸o˜es
aritme´ticas, em precisa˜o infinita. Um me´todo
e´ dito iterativo (iterativo do grego repetic¸a˜o)
quando a soluc¸a˜o −→x e´ obtida como limite de
uma sequ¨eˆncia de aproximac¸o˜es sucessivas −→x 1,
−→x 2 e assim sucessivamente.
A sec¸a˜o 2 apresenta a ide´ia ba´sica de SE-
LAS, bem como algumas aplicac¸o˜es baseadas na
resoluc¸a˜o de sistemas de equac¸o˜es lineares. A
sec¸a˜o 3 aborda o uso dos Me´todos Diretos, ou
seja, o me´todo de Gauss simples e o me´todo de
Gauss com pivotamento. A sec¸a˜o 4 trata do pro-
blema de condicionamento em SELAS. A sec¸a˜o
5 apresenta a te´cnica de refinamento. A sec¸a˜o 6
aborda o uso dos Me´todos Iterativos de Gauss-
Seidel e Gauss-Jacobi, bem como os crite´rios
de convergeˆncia e uma ana´lise da complexida-
des dos mesmos. Por fim, a sec¸a˜o 7 apresenta
uma breve conclusa˜o sobre o assunto.
2 Sistemas de Equac¸o˜es Li-
neares
Sistemas de Equac¸o˜es Lineares (SELAS)
sa˜o sistemas compostos de um conjunto de
equac¸o˜es lineares, cuja forma geral de cada uma
e´ do tipo


a11x1 + a12x2 + . . . + a1jxj = b1
a21x1 + a22x2 + . . . + a2jxj = b2
...
ai1x1 + ai2x2 + . . . + aijxj = bi
(1)
O nome equac¸a˜o linear e´ devido ao fato
de que equac¸o˜es do tipo ax = b gerarem gra´ficos
que tem a forma de uma reta [1].
Sistemas lineares podem ser representa-
dos mais compactamente na forma de matrizes.
Um sistema de i equac¸o˜es de j inco´gnitas pode
ser representado em uma matriz i×j que conte´m
os seus coeficientes (termos amn da equac¸a˜o 1).
Uma matriz aumentada e´ uma matriz onde os
termos independentes (bn da equac¸a˜o 1) esta˜o
inclu´ıdos na matriz.
Em geral, um sistema de equac¸o˜es de j
varia´veis possui como soluc¸a˜o um conjunto de s
valores, que, ao serem substitu´ıdos no sistema
pelas suas respectivas varia´veis, validam todas
as equac¸o˜es do sistema. O gra´fico de um sis-
tema de duas inco´gnitas deste tipo (sistema com-
pat´ıvel determinado) e´ um conjunto de retas que
se interceptam em um u´nico ponto (figura 1(a)).
Pore´m, existem situac¸o˜es onde um sis-
tema de n equac¸o˜es na˜o gerara´ n varia´veis: o
sistema pode ter infinita soluc¸o˜es ou nenhuma
soluc¸a˜o. A primeira situac¸a˜o ocorre quando o
sistema possui menos equac¸o˜es do que varia´veis
ou quando uma equac¸a˜o e´ uma combinac¸a˜o li-
near das demais equac¸o˜es (isto e´, pode ser obtida
a partir da soma do produto de outras equac¸o˜es
do sistema por valores escalares). Neste caso,
diz-se que o sistema e´ compat´ıvel e indetermi-
nado, e o gra´fico gerado e´ o de retas que coinci-
dem (figura 1(b)).
A segunda situac¸a˜o ocorre quando os ter-
mos do lado esquerdo da equac¸a˜o podem ser
gerados pela combinac¸a˜o linear dos termos do
lado esquerdo das outras equac¸o˜es do sistema,
mas a mesma combinac¸a˜o na˜o e´ verificada no
lado direito. Sistemas deste tipo sa˜o ditos in-
compat´ıveis.
2.1 Aplicac¸o˜es de SELAS
A resoluc¸a˜o de sistemas de equac¸o˜es line-
ares e´ u´til para a soluc¸a˜o de diversos problemas.
Algumas aplicac¸o˜es sa˜o descritas a seguir [1, 2].
• Circuitos ele´tricos resistivos podem ser mo-
delados na forma de sistemas de equac¸o˜es
lineares: as varia´veis sa˜o as correntes que
circulam em cada malha, os coeficientes sa˜o
as resisteˆncias em cada elemento resistivo e
os termos independentes sa˜o as tenso˜es ge-
radas em cada malha;
• Te´cnicas de interpolac¸a˜o polinomial se va-
lem de resoluc¸a˜o de SELAS para a deter-
minac¸a˜o dos coeficientes do polinoˆmio que
aproxima os pontos tabulados;
• Ana´lises da complexidade computacional de
algoritmos recorrentes podem ser determi-
nadas com a utilizac¸a˜o de SELAS.
Existem ainda diversas outras aplicac¸o˜es
de SELAS em a´reas como Cadeias de Markov,
economia, geode´sia e sensoriamento remoto [6].
3 Me´todos Diretos
Me´todos Diretos sa˜o aqueles que, ex-
ceto por erros de arredondamento, fornecem a
soluc¸a˜o exata do sistema linear, caso ela exista,
apo´s um nu´mero finito de operac¸o˜es [2, 3, 4].
Pertencem a esta classe todos os me´todos
estudados nos cursos de 1o e 2o graus como a re-
gra de Cramer, por exemplo. Entretanto, tais
me´todos na˜o sa˜o usados em problemas pra´ticos,
que exigem a resoluc¸a˜o de sistemas lineares com
um nu´mero relativamente grande de equac¸o˜es,
pois apresentam problemas de desempenho e
eficieˆncia. Sendo assim, e´ necessa´rio o uso de
me´todos e te´cnicas mais eficientes (sec¸o˜es 3.1 e
3.2).
3.1 Me´todo de Eliminac¸a˜o de
Gauss
O me´todo de Eliminac¸a˜o de Gauss, ou al-
goritmo de Gauss, e´ o me´todo mais conhecido e
mais usado para resoluc¸a˜o de SELA denso de
porte pequeno a me´dio. Por sistemas de pe-
queno porte entende-se uma ordem de ate´ 30.
Para me´dio porte podemos ter sistemas de or-
dem 50. A partir da´ı, em geral teremos sistemas
de grande porte [2].
O algoritmo ba´sico de Gauss e´ descrito a
seguir considerando o SELA
A−→x =
−→
b ,
onde
A ∈ R e −→x ,
−→
b ∈ R.
A soluc¸a˜o para este sistema e´ obtida em
duas etapas:
• Etapa 1 - Triangularizac¸a˜o: Consiste em
transformar a matriz A numa matriz tri-
angular superior, mediante permutac¸o˜es e
combinac¸o˜es lineares de linhas.
• Etapa 2 - Retrossubstituic¸a˜o: Consiste
em calcular os componentes do vetor −→x ,
soluc¸a˜o de A−→x =
−→
b , a partir da
soluc¸a˜o imediata do u´ltimo componente de
−→x , e enta˜o substituir regressivamente nas
equac¸o˜es anteriores.
Por combinac¸o˜es lineares de linhas
entende-se:
(b)(a)
ax+by=c
dx+ey=f ax+by=cdx+ey=f ax+by=c
dx+ey=f
(c)
Figura 1: Sistemas lineares (a) compat´ıveis determinados (b) compat´ıveis indeterminados (c) in-
compat´ıveis
1. Adic¸a˜o de uma linha com um mu´ltiplo de
outra linha, para substituir uma das linhas
consideradas.
2. Eventualmente, quando resolvendo um
SELA, manualmente, pode-se necessitar fa-
zer apenas a multiplicac¸a˜o de uma linha por
uma constante.
3. Troca de linhas.
Se uma matriz A e´ transformada em ou-
tra matriz B, mediante uma se´rie de trocas ou
combinac¸o˜eslineares de linhas, diz-se que A e
B sa˜o equivalentes e possuem o mesmo determi-
nante.
O exemplo abaixo demonstra a aplicac¸a˜o
do algoritmo.
Dado o sistema


3x + 2y + w = 3
9x + 8y − 3z + 4w = 6
−6x + 4y − 8z = −16
3x− 8y + 3z − 4w = 18
tem-se:
A =


3 2 0 1
9 8 −3 4
−6 4 −8 0
3 −8 3 −4

 −→b =


3
6
−16
18


Para tornar mais pra´tica a aplicac¸a˜o do
me´todo costuma-se trabalhar com a matriz ex-
pandida na forma:


3 2 0 1 | 3
9 8 −3 4 | 6
−6 4 −8 0 | −16
3 −8 3 −4 | 18


Considerando a primeira equac¸a˜o por
E1, a segunda por E2, e assim sucessivamente,
obte´m-se atrave´s da aplicac¸a˜o da etapa de
triangularizac¸a˜o (etapa 1):
Passo 1:
−(9/3)E1 + E2; −(−6/3)E1 + E3;
−(3/3)E1 + E4


3 2 0 1 | 3
0 2 −3 1 | −3
0 8 −8 2 | −10
0 −10 3 −5 | 15


Passo 2:
−(8/2)E2 + E3; −(−10/2)E2 + E4


3 2 0 1 | 3
0 2 −3 1 | −3
0 0 4 −2 | 2
0 0 −12 0 | 0


Passo 3:
−(12/4)E3 + E4


3 2 0 1 | 3
0 2 −3 1 | −3
0 0 4 −2 | 2
0 0 0 −6 | 6


o sistema na forma triangular superior:


3x + 2y + 0z + w = 3
+ 2y − 3z + w = −3
0 + 4z − 2w = 2
−6w = 6
A cada passo o elemento de diagonal da
primeira linha de matriz-resto e´ chamado de
pivoˆ.
Apo´s a aplicac¸a˜o da etapa 1, aplica-se
a etapa de retrossubstituic¸a˜o (etapa 2). Como
E4 e´ uma equac¸a˜o do primeiro grau com uma
inco´gnita, tem-se: w = −1.
Substituindo o valor de w em E3, os va-
lores de z e w em E2 e os valores de y, z e w em
E1, obte´m-se a soluc¸a˜o:
−→x = (2− 1 0− 1)T.
O me´todo de Gauss, como executado no
exemplo, produz, em precisa˜o infinita, sempre
a soluc¸a˜o exata do SELA A−→x =
−→
b desde
que: a matriz A na˜o seja singular (det A 6=
0); e as linhas sejam trocadas sempre que ne-
cessa´rio (no caso de aii = 0). Em outras pala-
vras, os me´todos diretos sa˜o processos finitos e,
portanto, teoricamente, obteˆm a soluc¸a˜o (con-
vergem) de qualquer sistema na˜o singular de
equac¸o˜es.
E´ importante ressaltar tambe´m a quan-
tidade de operac¸o˜es requeridas na aplicac¸a˜o de
um me´todo direto para soluc¸a˜o de um SELA. A
eliminac¸a˜o gaussiana requer (4n3 + 9n2 − 7n)/6
operac¸o˜es aritme´ticas (adic¸a˜o, subtrac¸a˜o, multi-
plicac¸a˜o e/ou divisa˜o). Para valores grandes de
n, o nu´mero de operac¸o˜es aritme´ticas e´ aproxi-
madamente 2n3/3. Por exemplo, considerando
um sistema de 100 equac¸o˜es, o me´todo de eli-
minac¸a˜o gaussiana requer 681.550 operac¸o˜es [4].
3.2 Estrate´gias de Pivotamento
Conforme exposto anteriormente, o algo-
ritmo de Gauss requer o ca´lculo dos multiplica-
dores para iniciar a soluc¸a˜o de um SELA. Entre-
tanto, isso pode ocasionar problemas se o pivoˆ
estiver pro´ximo de zero ou for nulo, por exem-
plo. Isto porque trabalhar com um pivoˆ nulo
e´ imposs´ıvel e trabalhar com um pivoˆ pro´ximo
de zero pode conduzir a resultados totalmente
imprecisos, visto que eles da˜o origem a multi-
plicadores bem maiores que a unidade que, por
sua vez, origina uma ampliac¸a˜o dos erros de ar-
redondamento [3].
Para contornar estes problemas adota-se
uma estrate´gia de pivotamento, ou seja, adota-
se um processo de escolha da linha e/ou coluna
pivotal.
3.2.1 Algoritmo de Gauss com pivota-
mento
Este me´todo nada mais e´ do que o mesmo
algoritmo de Gauss, com uma troca de linhas
sistema´ticas, de modo a minimizar os erros de
arredondamento. Para tal, escolhe-se os pivoˆs
da seguinte maneira:
• 1o Pivoˆ: E´ o elemento de maior valor abso-
luto na coluna 1.
a11 = max|ai1|
i = 1, n
• 2o Pivoˆ: E´ o elemento de maior valor abso-
luto na coluna 2 da matriz-resto.
a22 = max|ai2|
i = 2, n
K-e´simo pivoˆ akk = max|aik |
i = k, n
Apo´s a realizac¸a˜o das trocas, se ne-
cessa´rio, e o estabelecimento da matriz final
aplica-se o algoritmo ba´sico de Gauss (sec¸a˜o
3.1).
Este algoritmo e´ dito de Pivotamento
Parcial, pois a escolha do pivoˆ e´ feita em deter-
minada coluna escolhendo-se o seu maior valor;
se for necessa´rio, ha´ a troca de linhas conveni-
entes.
Pode-se fazer a escolha do pivoˆ como
sendo o maior elemento de toda a matriz-resto
e na˜o como sendo o maior elemento da coluna.
Neste caso, pode ser necessa´ria a troca de colu-
nas ale´m da troca de linhas. Para tal, a pesquisa
de qual e´ o maior elemento e´ mais demorada e
e´ preciso termos um novo valor para guardar a
eventual troca de coluna. Tal me´todo e´ chamado
de Pivotamento Total. A melhora da exatida˜o
que este me´todo proporciona pode na˜o ser van-
tajosa em func¸a˜o do aumento da complexidade
do algoritmo.
4 Medidas de Condiciona-
mento
Dado um sistema A−→x =
−→
b e duas apro-
ximac¸o˜es da soluc¸a˜o exata −→x , como saber qual
delas e´ a melhor? Uma forma trivial seria cal-
cular os res´ıduos dados por:
−→r1 =
−→
b −A−→x1 e
−→r2 =
−→
b −A−→x2
Dado o SELA e as aproximac¸o˜es


0.24x + 0.36y + 0.12z = 0.84
0.12x + 0.16y + 0.24z = 0.52
0.15x + 0.21y + 0.25z = 0.64
−→x1 = (25,−14,−1)
T e −→x2 = (−3, 4, 0)
T ,
os res´ıduos sa˜o
−→r1 = (0.00, 0.00, 0.08) e
−→r2 = (0.12, 0.24, 0.25)
Sabendo-se que a soluc¸a˜o exata e´ −→x =
(−3, 4, 1), conclui-se que, embora ||−→r1 || < ||
−→r2 ||,
a melhor aproximac¸a˜o e´ −→x 2. Portanto, pode-se
dizer que nem sempre a aproximac¸a˜o de menor
res´ıduo e´ a mais exata. Isso comprova a neces-
sidade do estudo do condicionamento de uma
matriz.
Considerando a sensibilidade de alguns
SELAS em relac¸a˜o aos dados de entrada pode-
se dizer que: um problema e´ dito “mal condici-
onado” se pequenas alterac¸o˜es nos dados de en-
trada ocasionam grandes erros no resultado final
[2, 5].
Considere o sistema{
5x + 7y = 12
7x + 10y = 17
que tem como soluc¸a˜o “u´nica” x = 1, y = 1.
Mas considere o par de valores x = 2.415, y =
0. Enta˜o: {
5x + 7y = 12.075
7x + 10y = 16.905
Quando arredonda-se para dois d´ıgitos,
estes segundos termos concordam com os segun-
dos termos das equac¸o˜es originais, visto que os
valores originais foram dados com somente dois
algarismos, a segunda soluc¸a˜o deveria ser aceita
como sendo ta˜o boa quanto a “u´nica”.
O problema neste caso, e´ que as duas re-
tas sa˜o quase paralelas, como mostrado na figura
2. O ponto fornecido pela segunda soluc¸a˜o, em-
bora na˜o se situe em nenhuma reta, esta´ muito
pro´ximo de ambas. Por isso, a equac¸o˜es do sis-
tema dado sa˜o chamadas de mal-condicionadas.
Toda vez que duas retas (ou planos ou hiper-
planos) sa˜o quase paralelos, as equac¸o˜es sera˜o
mal-condicionadas.
E´ fa´cil verificar o que ocorre com o condi-
cionamento no caso de duas retas. Ja´ em outros
SELAS de ordem maior que 2 isto e´ muito dif´ıcil.
E´ preciso um meio para medir este condiciona-
mento [2].
O Condicionamento de um SELA A−→x =
−→
b e´ dado por:
cond(A) = ||A||.||A−1||.
Quanto maior o valor de cond(A) mais
sens´ıvel sera´ o sistema, ou seja, pior condicio-
nada e´ a matriz A. Um exemplo de mau con-
dicionamento e´ dado pelas Matrizes de Hilbert,
em que cada aij e´ obtido por:
aij =
1
i + j − 1
onde i = j = 1(1)n
Como exemplo pode-se citar uma matriz
de Hilbert de dez linhas e dez colunas. O nu´mero
de d´ıgitos perdidos chega a “13”.
5 Refinamento
Devido a dificuldade do ca´lculo das me-
didas de condicionamento, nem sempre elas sa˜o
utilizadas na pra´tica. Uma alternativa mais ba-
rata computacionalmente e cuja aplicac¸a˜o pode
ser u´til ate´ em sistemas bem condicionados e´ a
te´cnica de refinamento da soluc¸a˜o. Com o seu
uso, e´ poss´ıvel obter uma estimativa da exatida˜o
da resposta [2]. Estes me´todos, ale´m de reduzir
erros de arredondamento dos ca´lculos, tambe´m
sa˜o u´teis para resolver alguns sistemas mal con-
dicionados [4].
O princ´ıpio de funcionamento do refina-
mento e´ explicado a seguir. A partir de uma
primeira soluc¸a˜o −→x (0), para o sistema
A−→x =
−→
b
uma aproximac¸a˜o melhor pode ser obtida a par-
tir da diferenc¸a entre a soluc¸a˜o real do sistema
e a soluc¸a˜o aproximada com a resoluc¸a˜o do sis-
tema
A−→� =
−→
β
Onde A e´ a matriz de coeficientes da
equac¸a˜o e
−→
β =
−→
b −
−→
b (0)
sendo
−→
b (0) a soluc¸a˜o obtida para cadaequac¸a˜o
quando −→x (0) e´ utilizado e substitu´ıdo pelas
varia´veis.
A nova aproximac¸a˜o e´, enta˜o, dada por
−→x 1 = −→x 0 +−→� 0.
Novamente deve ser aplicado um me´todo
para a soluc¸a˜o do novo sistema de equac¸o˜es li-
neares e novamente pode ser aplicado o me´todo
do refinamento. Como regra geral, resolve-se o
sistema
(1,1)
(5x + 7y = 12)
(7x + 10y = 17)
(2.45,0)
1
2
3
1 2 30
Figura 2: Representac¸a˜o geome´trica de um sistema de duas equac¸o˜es mal condicionadas.
A−→� (i+1) =
−→
β (i+1),
sendo
−→
β (i+1) =
−→
b −
−→
b (i)
e a nova soluc¸a˜o aproximada e´, enta˜o,
−→x i+1 = −→x i +−→� i.
6 Me´todos Iterativos
Me´todos iterativos sa˜o aqueles cuja a
soluc¸a˜o do problema e´ obtida a partir da apro-
ximac¸a˜o sequ¨encial de uma soluc¸a˜o hipote´tica
inicial −→x ate´ a soluc¸a˜o final [2]. Em outras pa-
lavras, e´ estipulado um “chute” inicial e, a cada
passo de iterac¸a˜o (repetic¸a˜o) a soluc¸a˜o e´ refi-
nada. O crite´rio de parada da repetic¸a˜o podem
ser dois: um determinado nu´mero de iterac¸o˜es
ou um determinado valor de exatida˜o do resul-
tado.
A ide´ia dos me´todos iterativos para a
soluc¸a˜o de sistemas lineares sera´ descrita a se-
guir, para um sistema de treˆs equac¸o˜es. A
soluc¸a˜o de sistemas de ordem maior pode ser
trivialmente deduzida a partir da discussa˜o que
se segue.
Dado o sistema

x + 3y + 5z = 7
2x + 4y + 5z = 10
x + y + z = 0
isola-se cada uma das varia´veis em cada
uma das equac¸o˜es.
x = 7− 3y − 5z
y =
10− 4y − 5z
2
z = −y − z
O valor de cada uma das varia´veis pode
ser calculado conhecendo-se o valor das demais.
Inicialmente, para calcular o valor da primeira
varia´vel, podem ser utilizados os valores iniciais
do me´todo iterativo (x0, y0, z0). Tem-se enta˜o
x = 7− 3y0 − 5z0.
O ca´lculo do valor da pro´xima varia´vel
(digamos y) pode ser feito de duas formas:
1. Utilizando-se os valores dos valores iniciais
x0 e z0 ou
2. Utilizando-se o valor de x ja´ calculado e o
valor z0 do palpite inicial.
Generalizando para n varia´veis, as esco-
lhas sa˜o as seguintes:
1. Utilizar no ca´lculo da k-e´sima iterac¸a˜o de
xi os valores calculados na iterac¸a˜o k-1;
2. Utilizar no ca´lculo da k-e´sima iterac¸a˜o de
xi os u´ltimos valores dispon´ıveis de cada
varia´vel. Estes podem ser os valores da
iterac¸a˜o k-1, se a varia´vel ainda na˜o foi cal-
culada na atual iterac¸a˜o, ou pode ser o valor
obtido na iterac¸a˜o corrente, se tal varia´vel
ja´ foi atualizada.
O primeiro me´todo de atualizac¸a˜o e´ o uti-
lizado no me´todo de Gauss-Jacobi, e o segundo
e´ o utilizado no me´todo de Gauss-Seidel [2, 3, 4].
6.1 Crite´rios de convergeˆncia
Os me´todos iterativos para resoluc¸a˜o de
SELAS baseiam-se na aproximac¸a˜o gradativa
de
−→
x′ em direc¸a˜o a soluc¸a˜o da equac¸a˜o, como
pode ser visualizado na figura 3(a). Essa fi-
gura apresenta a representac¸a˜o geome´trica de
um sistema de equac¸o˜es de duas inco´gnitas: cada
equac¸a˜o representa uma reta no eixo cartesiano e
a soluc¸a˜o do sistema de equac¸o˜es e´ a intersecc¸a˜o
de ambas as retas.
Os me´todos de Gauss-Jacobi e Gauss-
Seidel buscam a intersecc¸a˜o de uma reta que
passa pelo ponto que representa cada uma das
soluc¸o˜es na˜o finais e que seja paralela a um dos
eixos cartesianos com uma das retas que repre-
senta as equac¸o˜es, cada vez buscando uma das
retas e sendo a reta trac¸ada paralela a um dos
eixos.
Pore´m, um sistema que converge para
um conjunto de equac¸o˜es pode divergir para o
mesmo conjunto, se for fixada uma varia´vel di-
ferente ou ate´ mesmo se as equac¸o˜es forem re-
solvidas em uma ordem diferente (figura 3(b)).
Embora seja fa´cil visualizar o problema
em um sistema de ordem 2, o mesmo na˜o e´ ver-
dade em sistemas maiores. Existe enta˜o a neces-
sidade de um me´todo pra´tico de determinac¸a˜o
da convergeˆncia ou na˜o convergeˆncia de um sis-
tema de equac¸o˜es. Este e´ o objetivo dos crite´rios
de convergeˆncia apresentados nesta sec¸a˜o.
O Crite´rio das Linhas e´ um crite´rio de
convergeˆncia para os me´todo de Gauss-Jacobi
e Gauss-Seidel. Ele estabelece uma condic¸a˜o
de suficieˆncia para a convergeˆncia de um sis-
tema, ou seja, se o crite´rio verifica, pode-se ga-
rantir a convergeˆncia dos me´todos independente
da aproximac¸a˜o inicial escolhida. Se o crite´rio
falha, nada pode ser afirmado quanto a` con-
vergeˆncia de um sistema por Gauss-Jacobi [3].
Formalmente, pode-se dizer que ambos os
me´todos geram uma sequ¨eˆncia convergente se,
dado um sistema linear Ax = b e definindo-se
αk =
∑n
j=1,j 6=k |akj |
akk
for va´lida a relac¸a˜o
max{αk} < 1.
Em outras palavras, garante-se a con-
vergeˆncia se cada um dos elementos da diago-
nal principal for maior em mo´dulo que a soma
dos demais elementos da mesma linha. Se a
relac¸a˜o na˜o for satisfeita, pode-se aplicar uma
permutac¸a˜o de linhas e/ou colunas procurando
arranjar a matriz de tal forma que a relac¸a˜o seja
va´lida.
Para o me´todo de Gauss-Seidel, existe
ainda um segundo crite´rio de convergeˆncia, que
e´ o Crite´rio de Sassenfeld. Se o crite´rio das li-
nhas e´ satisfeito, este crite´rio e´ automaticamente
satisfeito, pore´m o contra´rio na˜o e´ verdadeiro:
este crite´rio pode ser satisfeito mesmo quando o
crite´rio das linhas na˜o o e´.
O crite´rio de Sassenfeld diz que um
sistema converge independentemente da apro-
ximac¸a˜o inicial se
max{βk} < 1,
onde
β1 =
∑n
i=2 |a1i|
a11
e
βk =
∑k−1
i=1 |aki|βi +
∑n
i=k+1 |aki|
akk
.
6.2 Ana´lise de Complexidade dos
me´todos iterativos
A ana´lise da complexidade (quantidade
de operac¸o˜es) requeridas em um me´todo itera-
tivo e´ bastante simples. O que na˜o e´ trivial e´
determinar o nu´mero exato de operac¸o˜es reali-
zadas por um programa de resoluc¸a˜o de SELA’s
atrave´s de um me´todo iterativo, pois esta de-
pende do crite´rio de parada adotado. Para
evitar que o sistema entre em loop realizando
operac¸o˜es em um sistema que na˜o converge ou
que na˜o alcanc¸a o erro mı´nimo permitido, sem-
pre deve ser adotado como crite´rio de parada,
ale´m do erro mı´nimo desejado, o nu´mero de
iterac¸o˜es ma´ximo permitido. No pior caso, este
sera´ o nu´mero de vezes que as iterac¸o˜es sera˜o
executadas.
Os me´todos de Gauss-Seidel e Gauss-
Jacobi realizam, por iterac¸a˜o, 2n2−n operac¸o˜es
aritme´ticas [4]: n−1 multiplicac¸o˜es de varia´veis
1
2
34
5 1
2 3
4
(b)(a)
Figura 3: (a) Sistema convergente (b) Sistema na˜o-convergente
por coeficientes, n − 1 somas e 1 divisa˜o para
cada varia´vel do sistema, totalizando, para cada
varia´vel, 2n− 1 operac¸o˜es para cada uma das n
varia´veis. Para valores de n grandes, o termo
de menor grau e´ dominado pelo termo de maior
grau, e o custo dos me´todos se torna 2n2.
Devido a necessidade de observar a
poss´ıvel convergeˆncia da soluc¸a˜o do sistema, sob
pena de na˜o se chegar a um resultado va´lido em
sua resoluc¸a˜o, os testes de convergeˆncia tornam-
se praticamente obrigato´rios em resoluc¸a˜o itera-
tiva de SELAS e portanto devem ser considera-
das no custo desses me´todos.
O crite´rio das linhas possui um custo de
n2−n operac¸o˜es aritme´ticas: sa˜o realizadas n−2
somas e 1 divisa˜o para a determinac¸a˜o de cada
um dos n fatores α, somados a n−1 comparac¸o˜es
para determinar o maior fator. Para gran-
des valores de n predominam as n2 operac¸o˜es
aritme´ticas do crite´rio.
O crite´rio de Sassenfeld realiza, para o
coˆmputo de cada fator β, n − 2 somas e n − 2
produtos, permanecendo o seu custo na mesma
ordem de crescimento do crite´rio das linhas.
Ainda, permanece sendo predominante o cres-
cimento de ordem 2n2 do me´todo iterativo.
Percebe-se que custo computacional dos
me´todos iterativos e´ menor que o custo do
me´todo de Gauss, o que conta a favor dos
me´todos iterativos para a resoluc¸a˜o de grandes
sistemas. Outras vantagens dos me´todos iterati-
vos sobre os diretos sa˜o o fato de preservarem os
zeros da matriz original, possu´ırem um erro de
arredondamento menor, e o fato de ser poss´ıvel
a obtenc¸a˜o de altas exatido˜es mais rapidamente.
Pore´m, os me´todos iterativosteˆm a desvantagem
de serem menos eficientes para sistemas densos
de pequeno porte [2].
7 Concluso˜es
Os me´todos diretos sa˜o processos finitos
e, por isso, teoricamente, obteˆm a soluc¸a˜o de
qualquer sistema na˜o singular de equac¸o˜es. Ja´
os me´todos iterativos convergem apenas sob de-
terminadas condic¸o˜es.
Os me´todos diretos apresentam se´rios
problemas com erros de arredondamento. Uma
forma de minimizar isso e´ adotar te´cnicas de
pivotamento. Os me´todos iterativos teˆm me-
nos erros de arredondamento, visto que a con-
vergeˆncia, uma vez garantida, independe da
aproximac¸a˜o inicial. Com isso, somente os erros
cometidos na u´ltima iterac¸a˜o afetam a soluc¸a˜o,
pois os erros anteriores na˜o levara˜o a` divergeˆncia
do processo nem a` convergeˆncia a um outro ve-
tor que na˜o a soluc¸a˜o.
Os me´todos diretos sa˜o aplicados a SE-
LAS densos de porte pequeno a me´dio. Ja´
os me´todos iterativos sa˜o indicados para sis-
temas de grande porte. Enfim, e´ preciso co-
nhecer a natureza do problema para poder es-
colher qual classe de algoritmo (me´todos dire-
tos/iterativos) deve ser utilizada, pois somente
assim sera´ poss´ıvel obter resultados mais preci-
sos e consequ¨entemente, confia´veis.
Refereˆncias
[1] KOLMAN, Bernard. Introduc¸a˜o a` a´lgebra
linear com aplicac¸o˜es.. 6a Edic¸a˜o. Rio de Ja-
neiro: LTC, 1999.
[2] CLA´UDIO, D.M; MARINS, J.M. Ca´lculo
nume´rico computacional: teoria e
pra´tica. 3a Edic¸a˜o. Sa˜o Paulo: Atlas, 2000.
[3] RUGGIERO, M.A.G.; LOPES, V.L.R.
Ca´lculo nume´rico: aspectos teo´ricos
e computacionais. 2a Edic¸a˜o. Sa˜o Paulo:
Pearson, 1996.
[4] DORN, W.S.; McCRACKEN, D.D. Ca´lculo
nume´rico com estudos de casos em FOR-
TRAN IV. 1a Reimpressa˜o. Sa˜o Paulo: Cam-
pus, 1981.
[5] CLA´UDIO, D.M; DIVERIO, T.A; TOSCANI,
L.V. Fundamentos de matema´tica compu-
tacional. 1a Edic¸a˜o. Porto Alegre: D.C. Luz-
zatto, 1987.
[6] http://www.ime.eb.br/∼webde1/valeria/trab/
1999/AlgEngCart.htm. Acessado em 5 de julho
de 2004.