SOLUCAO_NUMERICA_DE_SISTEMAS_DE_EQUACOES (2)

Prévia do material em texto

� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 67 
 
 444 SOLUÇÃO NUMÉRICA DE SISTEMAS DE 
EQUAÇÕES ALGÉBRICAS LINEARES 
 
 
4.1 – Introdução Num determinado circuito eléctrico, as correntes 1i , 2i e 3i 
passam através das impedâncias 1z , 2z e 3z são dadas por: 
 
 





−=−
−=−
=++
323312
212211
321 0
eeiziz
eeiziz
iii
 
 
 
Se 101 =z , 82 =z , 33 =z , 6521 =− ee e 12032 =− ee 
 
a) Calcule os valores das correntes 1i , 2i e 3i por um método direto e 
estável. 
 
No capítulo 3 tratamos de determinar o valor de x satisfaz uma única 
equação, ( ) 0=xf . Nesta seção temos por objetivo determinar 
nxxx ,...,, 21 que satisfazem simultaneamente um conjunto de 
equações: 
 
 
( )
( )
( )
1 1 2 1
2 1 2 2
1 2
, , , 0
, , , 0
, , , 0
n
n
n n n
f x x x b
f x x x b
f x x x b
= =
= =
= =
…
…
⋮
…
 (4.1) 
 
Tais sistemas podem ser lineares ou não lineares. Nesta seção 
trataremos das equações algébricas lineares que tem a forma geral: 
 
 CAPÍTULO 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 68 
 
11 1 12 2 13 3 1 1 1
21 1 22 2 23 3 2 2 2
1 1 2 2 3 3
a a a a a
a a a a a
 
a a a a a
j j n n
j j n n
n n n nj j nn n n
x x x x x b
x x x x x b
x x x x x b
 + + + + + + =

+ + + + + + =


 + + + + + + =
⋯ …
⋯ …
⋮
⋯ …
 (4.2) 
 
 
onde os a ’s são coeficientes constantes, os b ’s são constantes e n é o 
número de equações. 
 
Notação matricial: 
O sistema de equações (4.2) pode ser escrito de forma compacta: 
 
 
bxA
��
= (4.3) 
 
Onde, 
 












=
nnn32n1
2n232221
1n131211
a a a a
 
a a a a
a a a a
⋯
⋱⋮
⋯
⋯
n
A (4.4) 
 














=
nx
x
x
x
⋮
�
 
2
1
 (4.5) 
 














=
nb
b
b
b
⋮
�
 
2
1
 (4.6) 
 
n
x ℜ∈
�
 é o vetor de incógnitas (solução do sistema), nnA ×ℜ∈ é a matriz dos 
coeficientes e nb ℜ∈ é o termo independente. 
 Os métodos que serão estudados neste capítulo tratam de resolver 
sistemas lineares de n equações a n incógnitas. Caso existam mais incógnitas do 
que equações, o método não funcionará, ou seja, ele não permite resolver 
sistemas com grau de liberdade maior ou igual a 1. Já os sistemas com mais 
equações do que incógnitas podem ser resolvidos, desde que não hajam 
contradições que o tornem um sistema impossível (SI). Neste estudo, vamos nos 
concentrar em sistemas lineares do tipo n x n, onde o número de equações é 
igual ao número de incógnitas. 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 69 
 Há algumas formas especiais de matrizes quadradas que são importantes 
e devem ser observadas. Uma matriz simétrica é aquela em que jiij aa = para 
todos os i ’s e j ‘s. Por exemplo, a matriz simétrica 33× : 
 
[ ]










=
8 7 2
7 3 1
2 1 5
A 
 
 Uma matriz diagonal é uma matriz quadrada cujos elementos fora da 
diagonal principal são iguais à zero, como na matriz abaixo: 
 
 
 












=
44
33
22
11
a 0 0 0
 0 a 0 0
0 0 0
0 0 0 
a
a
A 
 
 
Uma matriz triangular superior é uma matriz em que todos os elementos 
abaixo da diagonal principal são zero, como na matriz a seguir: 
 












=
44
3433
242322
14131211
a 0 0 0
 a a 0 0
a a a 0
a a a a
A 
 
Uma matriz triangular inferior é uma matriz em que todos os elementos 
acima da diagonal principal são zero, como na matriz a seguir: 
 












=
44434241
333231
2221
11
a a a a
 0 a a a
0 0 a a
0 0 0 a
A 
 
Uma matriz de banda tem todos os elementos iguais a zero, com a 
possível exceção de uma faixa centrada na diagonal principal: 
 












=
4443
343332
232221
1211
a a 0 0
 a a a 0
0 a a a
0 0 a a
A 
 
Essa matriz possui largura da banda 3 e tem nome especial – matriz tri 
diagonal. Vamos fazer uma análise geométrica da solução de alguns sistemas 
lineares: 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 70 
 
Ex1: 
2
0
x y
x y
+ =

− =
 Se o det ≠ 0 o sistema possui solução única 
 
 
 
 
 
 
 
 
 
Ex2: 
2
2 2 2
x y
x y
+ =

+ =
 O sistema não possui solução 
 
 
 
Ex3: 
2
2 2 4
x y
x y
+ =

+ =
 O sistema possui infinitas soluções 
 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 71 
 
 
 
Os métodos numéricos desenvolvidos para a solução de sistemas de 
equações algébricas lineares são de dois tipos: métodos diretos e métodos 
indiretos. No caso dos métodos diretos é realizado um número fixo de operações 
ao final das quais se obtém o resultado. Os métodos indiretos são construídos 
com procedimentos iterativos onde a solução é obtida após um número variável 
de iterações, estando este número associado ao critério de convergência 
estabelecido a priori. Em ambos os casos existem vantagens e desvantagens. 
Nas próximas seções serão apresentados alguns destes métodos. 
 
 
 
 
4.2 – Métodos 
Diretos 
 
4.2.1 – Eliminação 
Gaussiana 
 
 
 Conhecendo as operações matriciais elementares estudadas no curso de 
álgebra linear vamos introduzir os métodos computacionais para solução de 
sistemas de equações lineares. Operações realizadas sobre linhas (colunas) de 
uma matriz A. São de três tipos: 
 
 
I) Troca de duas linhas (colunas); 
II) Multiplicação de uma linha (coluna) por um escalar 0≠k ; 
III) Substituir uma linha (coluna) pela sua adição a um múltiplo não 
nulo de outra linha (coluna). 
 
 
O método de Gauss ou eliminação gaussiana consiste na operação de um 
sistema de equações lineares por meio dessas operações elementares até que seja 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 72 
obtido um sistema equivalente na forma escalonada. Em sistemas consistentes, a 
forma escalonada pode, então, ser facilmente resolvida por solução descendente. 
Em sistemas dependentes uma solução poderá ser encontrada por meio da 
atribuição de valores às variáveis livres. 
A denominação do método é uma homenagem ao matemático alemão 
Carl Friedrich Gauss. Referências sobre esse método já existiam em antigos 
textos indianos e chineses, de cerca de 2000 anos atrás. Entretanto, os europeus 
o desconheciam até que Gauss o utilizou enquanto trabalhava num sistema de 
equações que buscava determinar por aproximação a órbita do asteroide Ceres. 
Essa aproximação foi feita através do método dos quadrados mínimos, método 
também atribuído a Gauss. Gauss trabalhava num sistema de 17 equações a 17 
incógnitas, dimensão impraticável para solução manual. Na pesquisa por um 
método, chegou a esse processo de eliminação. 
Em outras palavras neste método o problema bxA
��
= é reduzido a um 
sistema equivalente: 
 
 
dxU
��
= (4.7) 
 
 
onde U é uma matriz triangular superior, sendo este problema facilmente 
resolvido por uma substituição de trás para frente (backward sweep). 
Obviamente além de o sistema ter número de incógnitas e equações iguais, para 
ser resolvido pelos métodos a serem estudados a matriz dos coeficientes precisa 
ser diferente de zero (Sistema possível e determinado nnA ×ℜ∈ e 0≠A ). 
 Para a obtenção do sistema (4.7) a partir do sistema original bxA
��
= , são 
realizadas as manipulações que serão descritas a seguir. 
 Reescrevendo o sistema originalcom um total de n equações e 
n incógnitas: 
 
 
( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( ) ( )111
3
1
32
1
21
1
1
1
2
1
2
1
23
1
232
1
221
1
21
1
1
1
1
1
13
1
132
1
121
1
11
 
nnnnjnjnnn
nnjj
nnjj
bxaxaxaxaxa
bxaxaxaxaxa
bxaxaxaxaxa
=++++++
=++++++
=++++++
…⋯
⋮
…⋯
…⋯
 (4.8) 
 
 
onde, o índice (1) representa os coeficientes com seus valores iniciais. Com as 
manipulações a serem realizadas os valores dos coeficientes serão alterados e 
estes índices assumirão então outros valores (2), (3),…,conforme o número de 
operações realizadas. Definindo os multiplicadores: 
 
 
( )
( ) ni
a
a
m ii , 3, 2, ,1
11
1
1
1 …== (4.9) 
 
 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 73 
multiplicando a primeira equação por 1im e subtraindo a equação resultante da 
equação i correspondente, elimina-se o coeficiente de 1x , i.e. 1ia . Este 
procedimento é realizado para todas as equações ni ,,3 ,2 …= , ou seja, 
 
( ) ( ) ( )
njniamaa jiijij …… ,3 ,2 e ,,3 ,2 ,
1
11
12
==−= (4.10) 
( ) ( ) ( ) ,,3 ,2 ,111
12 nibmbb iii …=−= (4.11) 
e 
( ) ,,3 ,2 ,021 niai …== (4.12) 
 
 O sistema (4.8) passa então a ser escrito como 
 
( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( )222
3
2
32
2
2
2
3
2
3
2
33
2
332
2
32
2
2
2
2
2
23
2
232
2
22
1
1
1
1
1
13
1
132
1
121
1
11
0
 
0
0
nnnnjnjnn
nnjj
nnjj
nnjj
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
bxaxaxaxaxa
=++++++
=++++++
=++++++
=++++++
…⋯
⋮
…⋯
…⋯
…⋯
 (4.13) 
 
 Observe que a primeira equação não foi modificada com relação à 
primeira equação do sistema original (4.8). Após este passo continuamos o 
processo de eliminação com o multiplicador: 
 
 
( )
( ) ni
a
a
m ii , 3, ,2
22
2
2
2 …== (4.14) 
 
 Agora a segunda equação é multiplicada por 2im e subtraindo a equação 
resultante da equação i correspondente, elimina-se o coeficiente de 2x , i.e. 2ia . 
Este procedimento é realizado para todas as equações ni ,,4 ,3 …= , de forma que: 
 
 
( ) ( ) ( ) ,,4 ,3 e ,,4 ,3 ,222
23 njniamaa jiijij …… ==−= (4.15) 
 ( ) ( ) ( ) ,,4 ,3 ,222
23
nibmbb iii …=−= (4.16) 
 
e 
 
( ) ,,4 ,3 ,032 niai …== (4.17) 
 
 O sistema (4.13) passa então a ser escrito na forma equivalente 
 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 74 
( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )333
3
3
3
3
5
3
5
3
53
3
53
3
4
3
4
3
43
3
43
3
3
3
3
3
33
3
33
2
2
2
2
2
23
2
232
2
22
1
1
1
1
1
13
1
132
1
121
1
11
00
 
00
00
00
0
nnnnjnjn
nnjj
nnjj
nnjj
nnjj
nnjj
bxaxaxa
bxaxaxa
bxaxaxa
bxaxaxa
bxaxaxaxa
bxaxaxaxaxa
=++++++
=++++++
=++++++
=++++++
=++++++
=++++++
⋯⋯
⋮
…⋯
…⋯
…⋯
…⋯
…⋯
 (4.18) 
 
 O processo aqui descrito é então continuado até que se obtenha o sistema de 
equações algébricas lineares na forma dada pela Eq. (4.7), ou seja, 
 
( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
( ) ( )n
nn
n
nn
n
nn
n
nnn
n
nn
nn
nn
nn
bxa
bxaxa
bxaxa
bxaxaxa
bxaxaxaxa
=++++
=+++++
=++++
=++++
=++++
−
−
−
−−
−
−−
⋯
⋯
⋮
⋯
…
…
000
000
 
00
0
1
1
1
,11
1
1,1
3
3
3
33
3
33
2
2
2
23
2
232
2
22
1
1
1
13
1
132
1
121
1
11
 (4.19) 
 
De forma genérica, o procedimento adotado para a obtenção do sistema 
(4.19) a partir do sistema (4.8), consiste no uso de multiplicadores 
 
( )
( ) nkkink
a
a
m
k
kk
k
ik
ik ,,2,1,1,,2,1, …… ++=−== (4.20) 
 
de forma que os novos coeficientes calculados no passo k sejam 
 
 ( ) ( ) ( ) nkkjnkkinkamaa kkjik
k
ij
k
ij ,,2 ,1 e ,,2 ,1 ,1,,2 ,1 ,
1
……… ++=++=−=−=+ (4.21) 
 
e 
 
( ) ( ) ( )
nkkinkbmbb
k
kik
k
i
k
i ,,2 ,1 ,1,,2 ,1 ,
1
…… ++=−=−=
+ (4.22) 
 
sendo nulos então os coeficientes 
 
( )
nkkinka
k
ik ,,2 ,1 ,1,,2 ,1 ,0
1
…… ++=−==+ (4.23) 
 
 Para a obtenção do sistema (4.19) são aplicadas, portanto, as Eqs. (4.20) 
a (4.23), sendo operadas no passo k , as linhas nkk ,,2 ,1 …++ , com 
1,,2 ,1 −= nk … . 
 O coeficiente ( )kkka é denominado pivo, e segundo a definição dos 
multiplicadores dada de forma genérica pela Eq. (4.20), é necessário que 
 
( ) 0≠kkka (4.21) 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 75 
 
 No início de cada passo k de eliminação de coeficientes, quando a linha 
k é mantida fixa, é feita uma troca de posição de equações, de forma que fique 
um termo diferente de zero na posição do pivot. 
 A solução do sistema (4.19) é muito simples, sendo feita uma simples 
substituição de trás para frente (backward sweep). Começando da última 
equação escrevemos 
 
( )
( )n
nn
n
n
n
a
b
x = (4.22) 
 
 Conhecendo nx podemos calcular então 1−nx usando a penúltima 
equação do sistema (4.19), 
 
( ) ( )
( )1
1,1
1
,1
1
1
1 −
−−
−
−
−
−
−
−
=
n
nn
n
n
nn
n
n
n
a
xab
x (4.23) 
 
 Este passo é então continuado até que todas as incógnitas sejam 
determinadas. De forma genérica escreve-se 
 
( )
( ) ( ) 1,,2 ,1 , ,
1
1
…−−=





−= ∑
+=
nnnlxab
a
x
n
lj
j
l
lj
l
ll
ll
l
 (4.24) 
 
 
 
 
 
 
 
 
 
 
Vamos agora ao algoritmo para o método de eliminação gaussiana: 
 
 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 76 
 
 
 
Vamos agora ao algoritmo para a substituição regressiva: 
 
 
 
A implementação computacional do método de eliminação gaussiana é 
relativamente simples, e fornece o resultado após um número fixo de operações. 
Porém, a qualidade do resultado pode ser comprometida pelos erros de 
arredondamento que são acumulados a cada operação. 
 Visando minimizar a propagação de erros de arredondamento podem ser 
usadas as técnicas de pivoteamento parcial ou de pivoteamento completo, que 
serão sucintamente descritas a seguir. 
 
 
 
 
Exemplo: Resolva o sistema linear pelo Método de Eliminação de Gauss. 
 
 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 77 





=+−−
=−+
=+−
3352
12
22
321
321
321
xxx
xxx
xxx
 
 
 
4.2.2 - Fatoração L.U 
 
 
� Considere um sistema linear Ax b= onde A é uma matriz quadrada e invertível; 
� Suponha que é possível obter uma Fatoração LU de forma que LU A= ; 
� L seja quadrada, da mesma ordem de A e triangular inferior, invertível; 
� U seja quadrada, da mesma ordem de A e triangular superior, invertível; 
� Assim, LUx b= . Fazendo Ux y= temos que Ly b= ; 
� Logo resolver o sistema Ax b= é equivalente a resolver o sistema Uz y= ; 
� z=U-1y=U-1L-1b=(LU)-1b = A-1b=x. 
 
Dados o sistema linear e a fatoração da matriz , temos: 
 
Seja . A solução do sistema linear pode ser obtida da resolução dos sistemas 
lineares triangulares: 
i) 
ii) 
Exemplo: Resolver o sistema linear usando a fatoração : 
 
 
 
 
 
 
 Resolvendo : 
 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 78 
 i) 
 
 ii) 
 
 
 
 
4.3 – Métodos 
Iterativos 
 
 
 Para sistemas com um grande número de equações o uso de métodos 
diretos implica em um número extremamente elevado de operações a serem 
realizadas. Neste caso os métodos iterativos são melhores, e em alguns casos são 
os únicos que poderão ser usados na prática. 
 É comum também que a matriz seja esparsa, ou seja, com um grande número de 
coeficientes nulos, e muitas vezes podendo ser representada de forma simples. 
Neste caso os métodos iterativos são superiorespor utilizarem apenas os 
coeficientes diferentes de zero, enquanto que ao se utilizar métodos diretos a 
maioria dos coeficientes nulos seriam trocados por valores diferentes de zero. 
Por exemplo, em um sistema linear 2x2 usando como estimativa inicial ( )0 01 2,x x 
o próximo passo é encontrar ( )1 11 2,x x até a convergência e um determinado 
critério de parada como representa a Figura 4.0. 
 
 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 79 
Figura 4.0 – Representação da convergência dos métodos iterativos 
 
 
4.3.1 – Método 
de Gauss-Jacobi 
 
 
 Considere novamente o problema 
 
bxA
��
= (4.36) 
 
onde o objetivo é obter o vetor de incógnitas 
 














=
nx
x
x
x
⋮
� 2
1
 (4.37) 
 
 Cada equação do sistema (4.36) é dada por 
 
nibxaxaxaxaxa ininnniiiiii ,,2 ,1 ,11,2211 …⋯⋯ ==++++++ −− (4.38) 
 
ou seja, 
 
nibxaxaxa i
n
ij
jij
i
j
iiijij ,,2 ,1 , 
1
1
1
…==++ ∑∑
+=
−
=
 (4.39) 
 
 Da Eq. (4.39) obtém-se então 
 
nixab
a
x
n
ij
j
jiji
ii
i ,,2 ,1 ,
1
1
…=










−= ∑
≠
=
 (4.40) 
Podemos representar na forma matricial: Suponha um sistema linear com 
incógnitas 1x , ..., nx da seguinte forma: 
 
 
 
 
 
 
 
 
 
Suponha também que todos os termos aii sejam diferentes de zero (i = 1, 
... , n). Se não for o caso, isso às vezes pode ser resolvido com uma troca na 
ordem das equações. Então a solução desse sistema satisfaz as seguintes 
equações: 
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
. . .
. . .
. . .
n n
n n
n n nn n n
a x a x a x b
a x a x a x b
a x a x a x b
+ + + =
 + + + =


 + + + =
⋯
⋯
⋮ ⋮ ⋮ ⋮
⋯
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 80 
 
 
 
 
 
 
 
 
 
 
 
 
O Método de Jacobi consiste em estimar os valores iniciais para x1
(0), 
x2
(0), ..., xn
(0), substituir esses valores no lado direito das equações e obter daí 
novos valores x1
(1), x2
(1), ..., xn
(1). Em seguida, repetimos o processo e colocamos 
esses novos valores nas equações para obter x1
(2), x2
(2), ..., xn
(2), etc. Desta forma 
temos: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Considerando que as equações no sistema (4.36) estejam ordenadas de 
forma que os coeficientes na diagonal sejam não nulos, 0≠iia , um procedimento 
iterativo é construído usando a Eq. (4.40) conforme descrito no seguinte 
algoritmo: 
{ }
{ }
{ }
1 1 12 2 1
11
2 2 21 1 2
22
1 1 1 1
1
. .
1
. .
1
. .
n n
n n
n n n n n n
nn
x b a x a x
a
x b a x a x
a
x b a x a x
a
− −

= − − −


= − − −




= − − −

⋯
⋯
⋮ ⋮ ⋮ ⋮
⋯
{ }
{ }
{ }
1 2
2 1
1 1
( 1) ( ) ( )
1 12 1
11
( 1) ( ) ( )
2 21 2
22
( 1) ( ) ( )
1 1
1
. .
1
. .
1
. .
n
n
n n
k k k
n
k k k
n
k k k
n n n n
nn
x b a x a x
a
x b a x a x
a
x b a x a x
a −
+
+
+
−

= − − −


= − − −




= − − −

⋯
⋯
⋮ ⋮ ⋮ ⋮
⋯
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 81 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Como o método de Gauss-Jacobi pode não convergir, é necessário que 
no algoritmo seja incluída a parada do mesmo caso um número máximo de 
iterações definido a priori seja atingido. 
 
 
Exemplo: Dado o sistema de equações lineares abaixo, determine a sua solução 
de acordo com o método de Jacobi, considerando uma tolerância ε ≤ 10-2. 
 
 
 
A solução analítica é x1=4/3 e x2=7/3. De acordo com Jacobi, temos que: 
 
 
 
 
 
 
 
 
Tomando uma solução inicial arbitrária x1=0 e x2=0, teremos a seguinte 
tabela de resultados: 
 
 
 



−=−
=−
3.2
1.2
21
21
xx
xx
Vamos agora ao algoritmo do método de Gauss Jacobi: 
 
1) Escolha uma estimativa inicial 0x
�
 e faça o contador de iterações 
0=k ; 
 
2) Calcule uma nova estimativa para as incógnitas com a Eq. (4.40), 
 
nixab
a
x
n
ij
j
k
jiji
ii
k
i ,,2 ,1 ,
1
1
1
…=










−= ∑
≠
=
+ (4.41) 
 
3) Verifique se o critério de parada estabelecido a priori foi satisfeito. 
Como exemplo usamos a diferença relativa das incógnitas em duas 
iterações sucessivas 
 
ni
x
xx
k
i
k
i
k
i ,,2 ,1 ,
1
…=<
−+
ε com 0≠kix (4.42) 
 
onde ε é um número relativamente pequeno, por exemplo 510− . 
Caso o critério de parada não esteja satisfeito faça 1+= kk e volte 
ao passo 2. 
 
( )
( )
1
2
( 1) ( )
2
( 1) ( )
1
1
. 1
2
1
3
2
k k
k k
x x
x x
+
+

= +

 = +

� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 82 
 
Tabela 1 – Representação do processo iterativo de Gauss-Jordan 
K x1 x2 E(x1) E(x2)
0 0 0
1 0,5 1,5 0,5 1,5
2 1,25 1,75 0,75 0,25
3 1,375 2,125 0,125 0,375
4 1,5625 2,1875 0,1875 0,0625
5 1,59375 2,28125 0,03125 0,09375
6 1,640625 2,296875 0,046875 0,015625
7 1,648438 2,320313 0,007813 0,023438
8 1,660156 2,324219 0,011719 0,003906
9 1,662109 2,330078 0,001953 0,005859
 
 
 
Portanto, o resultado aproximado para a tolerância solicitada é x1=1,66 e 
x2=2,33. Outro método para realizar o teste de parada seria realizar k iterações. 
 
Exemplo: Resolva o seguinte sistema linear usando o Método de Gauss-Jacobi. 





=+−
−=−+
=−−
4,71102,03,0
3,193,071,0
85,72,01,03
321
321
321
xxx
xxx
xxx
 
 
 
 
 
4.3.2 – Método 
de Gauss-Seidel 
 
 
 No método de Gauss-Jacobi é utilizada a estimativa anterior kx
�
 para o 
cálculo da nova estimativa 1+kx
�
. No método de Gauss-Seidel ao se calcular a 
nova estimativa para a incógnita 1+kix , ni ,,2 ,1 …= , são usadas as novas 
estimativas ,1+klx 1,,2 ,1 −= il … , já calculadas, e as estimativas anteriores 
,klx niil ,2 ,1 …++= , para as incógnitas ainda não calculadas. Partindo da Eq. 
(4.42) escrevemos: 
 
 
nixaxab
a
x
i
j
n
ij
k
jij
k
jiji
ii
k
i ,,2 ,1 ,
1 1
1 1
11
…=






−−= ∑ ∑
−
= +=
++ (4.43) 
 
 
 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 83 
 
 
 
 
 
 
 
 
 
 
 
 
 
 O algoritmo apresentado na seção anterior pode ser utilizado fazendo a 
troca da Eq. (4.41) pela Eq. (4.43). Conforme descrito no algoritmo apresentado 
na seção 4.3.1, o procedimento iterativo é continuado até que o critério: 
 
0 ,1,,3 ,2 ,
1
≠−=<
−+ k
ik
i
k
i
k
i MNi
M
MM
…ε (4.44) 
 
seja satisfeito. 
 
 Exemplo:De acordo com Gauss Seidel,considerando o mesmo exemplo temos 
que: 
 
 
 
 
 
 
 
 
Tomando uma solução inicial arbitrária x1=0 e x2=0, teremos a seguinte 
tabela de resultados: 
 
Tabela 2 – Representação do processo iterativo usando método de Gauss-Seidel 
K x1 x2 E(x1) E(x2)
0 0 0
1 0,5 1,75 0,5 1,75
2 1,375 2,1875 0,875 0,4375
3 1,59375 2,296875 0,21875 0,109375
4 1,648438 2,324219 0,054688 0,027344
5 1,662109 2,331055 0,013672 0,006836
6 1,665527 2,332764 0,003418 0,001709
 
 
 
{ }
{ }
{ }
1 2
2 1
1 1
( 1) ( ) ( )
1 12 1
11
( 1) ( 1) ( )
2 21 2
22
( 1) ( 1) ( 1)
1 1
1
. .
1
. .
1
. .
n
n
n n
k k k
n
k k k
n
k k k
n n n n
nn
x b a x a x
a
x b a x a x
a
x b a x a x
a −
+
+ +
+ + +
−

= − − −


= − − −




= − − −

⋯
⋯
⋮ ⋮ ⋮ ⋮
⋯
( )
( )
1
2
( 1) ( )
2
( 1) ( 1)
1
1
. 1
2
1
3
2
k k
k k
x x
x x
+
+ +

= +

 = +

� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 84 
Exemplo: Resolva o seguinte sistema linear usando o Método de Gauss-Seidel. 





=+−
−=−+
=−−
4,71102,03,0
3,193,071,0
85,72,01,03
321
321
321
xxx
xxx
xxx
 
 
 
Estudo da convergência do método de Gauss-Seidel 
 
 Voltando à Eq. (4.40) que descreve de forma genérica o método de 
Gauss-Seidel, este converge com o uso de qualquer estimativa inicial 0x
�
 quando 
ocorre a dominância da diagonal, i.e. 
 
niaa
n
ij
j
ijii , ,2 ,1 ,
1
…=≥ ∑
≠
=
 (4.45) 
 
e parapelo menos uma linha 
 
∑
≠
=
>
n
ij
j
ijii aa
1
 (4.46) 
 
 Esta é uma condição suficiente e não uma condição necessária, 
implicando, portanto, no fato de que convergência pode ser observada mesmo 
que não se tenha a dominância da diagonal. 
 
 
 
4.3.3 – Método das 
Sobre-Relaxações 
Sucessivas (SOR: 
Successive Over 
Relaxation) 
 
 A técnica de sobre-relaxação pode ser usada na tentativa de acelerar 
qualquer método iterativo. Conforme representado na Fig. 4.1, o atirador tem 
uma chance maior de acertar um alvo em movimento se tentar antecipar a 
trajetória do mesmo, atirando, portanto, um pouco à frente da posição observada 
no momento do disparo. 
 
 
 
 
 
 
 
 
 
 
 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 85 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 4.1 – Um atirador aumenta as chances de acertar o alvo se levar em consideração a 
trajetória do mesmo. 
 
Vamos aplicar esta técnica à solução de um sistema de equações algébricas 
lineares com o método de Gauss-Seidel. Ao final de cada iteração do método de 
Gauss-Seidel é feita uma correção da estimativa obtida buscando uma aceleração 
da convergência do método. 
A correção é feita usando 
 
( ) k
i
k
i
k
i SORGSSOR
xxx ωω −+= ++ 111 (4.47) 
 
onde 0>ω é o parâmetro de relaxação. 
 Para que ocorra convergência, ω tem que ser menor que 2. Para 
21 << ω tem-se uma sobre-relaxação e para 10 << ω tem-se uma sub-relaxação. 
Com 1=ω volta-se ao método de Gauss-Seidel. 
 Em alguns casos é possível obter analiticamente o valor de ω ótimo, 
optω , para o qual o número de iterações é mínimo. No entanto, na maioria das 
vezes é feita uma busca de uma aproximação para optω empregando 
experimentação numérica. O valor obtido pode então ser aplicado em outros 
problemas semelhantes. 
 
 
 
4.4 - Exercícios 
 
 
4.4.2 – Uma fábrica de tintas pretende utilizar as sobras de tinta de 4 diferentes 
tonalidades de tinta verde para criar uma tonalidade de verde mais popular. Uma 
unidade de medida ( ..mu ) da nova tinta será composta por, 1x ..mu de tinta 
tipo 1, 2x ..mu de tinta tipo 2, 3x ..mu de tinta tipo 3 e 4x ..mu de tinta tipo 
4. Cada ..mu de tinta nova é composta por 4 pigmentos que estão relacionados 
pelo seguinte sistema de equações lineares: 
 
Atirador 
Lançador 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 86 







=+
=+++
=++
=++
284
3172602016
27101080
40103080
41
4321
432
431
xx
xxxx
xxx
xxx
 
 
Os coeficientes da matriz representam a porcentagem de pigmento em cada uma 
das 4 diferentes tonalidades de tinta verde, por exemplo, a tinta com a nova 
tonalidade deverá conter 31% de pigmento 3, sabendo que a tinta tipo 1 contém 
16%, a tinta tipo 2 20%, a tinta tipo 3 60% e a tinta tipo 4 contém 72% do 
mesmo pigmento. 
 
a) Analisando apenas as condições suficientes de convergência, verifique se o 
método de Gauss-Seidel converge, quando aplicado a este sistema. 
b) Resolva o sistema de equações usando o método iterativo de Gauss-Seidel, 
utilizando para aproximação inicial o ponto ( )T0;2,0;2,0;5,0 e utilizando com 
critério de parada ε = 0.25 ou 2=máxn . 
 
4.4.3 – Resolva os sistemas usando (i) o método de eliminação de Gauss 
(escalonamento); (ii) método de Gauss-Jacobi; (iii) método de Gauss-Seidel. 
Para os casos (i) e (ii) a precisão deve ser inferior a 0,02. 
 
a) 
3x1 + 2x2 + 4x3 = 1 
x1 + x2 + 2x3 = 2 
4x1 + 3x2 – 2x3 = 3 
 
b) 
3x1 – 4x2 + x3 = 9 
x1 + 2x2 + 2x3 = 3 
4x1– 3x3 = -2 
 
c) 
10x1 + 2x2 + x3 = 7 
x1 + 5x2 + x3 = -8 
2x1 + 3x2 + 10x3 = 6. 
 
d) 
5x1 + x2 + x3 = 5 
3x1 + 4x2 + x3 = 6 
3x1+ 3x2 + 6x3 = 0. 
 
e) 
x1 + x2 = 3 
x1 – 3x2 = -3. 
 
f) 
2x1 + 2x2 + x3 + x4 = 7 
x1 – x2 + 2x3 – x4 = 1 
3x1 + 2x2 – 3x3 – 2x4 = 4 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 87 
4x1 + 3x2 + 2x3 + x4 = 12. 
 
g) Programe os métodos de eliminação gaussiana, Algoritmo de Gauss-Seidel e 
Gauss-Jacobi e então verifique se as respostas que encontrou nas questões acima 
estão corretas. 
 
4.4.4 – Resolva o Sistema linear tipo banda triangular usando o algoritmo de 
Thomas, 
 
 
 
4.4.5 – Implemente na linguagem de programação que preferir o algoritmo de 
Thomas e use-o para encontrar a Solução do sistema de banda tridiagonal a 
seguir: 
 
 
4.4.6 – Um engenheiro de Produção supervisiona a produção de quatro tipos de 
computadores. Existem quatro espécies de recursos necessários à produção: 
mão-de-obra, metais, plásticos e componentes eletrônicos. As quantidades destes 
recursos, necessárias para produzir cada computador são: 
 
 
 
Considere um consumo diário de 504 h de mão-de-obra, 1970 Kg de metais, 970 
Kg de plásticos e 601 componentes. 
 
a) Use um método direto e estável para calcular o número de computadores 
(número inteiro) de cada tipo produzidos por dia. 
b) Use o método iterativo de Gauss-Seidel, tomando como aproximação inicial 
x(1) =(9, 10, 12, 10). Apresente apenas os cálculos relativos às duas primeiras 
iterações, indicando uma estimativa do erro relativo. 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 88 
c) Comente os resultados obtidos, analisando as condições suficientes de 
convergência. 
 
4.4.7 – Considere a figura representando um sistema de 4 molas ligadas em série 
sujeito a uma força F de 2000 Kg. Em uma situação de equilíbrio, as equações 
força-balanço deduzidas definem inter-relações entre as molas: 
 
 
em que k1 = 150, k2 = 50, k3 = 75 e k4 = 225 são as constantes das molas 
(kg/s2). 
a) Perceba na figura acima que entre as molas existem chapas metálicas onde 
estas se apoiam. Cada uma das chapas inicialmente está na posição sob a 
posição 321 ,, xxx e 4x respectivamente. Determine usando o algoritmo de 
Thomas o deslocamento resultante de cada uma das chapas em relação a 
posição inicial. 
 
4.4.8 – Para cada um dos sistemas lineares a seguir, analise a existência ou não 
de solução, bem como a unicidade da solução. Se o sistema for possível e 
determinado, aplique um dos métodos de solução de sistemas lineares estudados 
neste capítulo para resolvê-lo. 
 
� SOLUÇÃO NUMÉRICA DE SISTEMAS DE EQUAÇÕES ALGÉBRICAS LINEARES 
� UNIVERSIDADE FEDERAL DO PAMPA 
 
 89