SOLUÇÃO DE SISTEMAS LINEARES E INVERSÃO DE MATRIZES

Prévia do material em texto

1
1- SOLUÇÃO DE SISTEMAS LINEARES E INVERSÃO DE MATRIZES 
 
 
1.1- Métodos exatos para solução de sistemas lineares 
 
Métodos para solução de sistemas de equações lineares são divididos principalmente 
em dois grupos: 1) Métodos Exatos: são aqueles que forneceriam a solução exata, não 
fossem os erros de arredondamento, com um número finito de operações; e 2) Métodos 
Iterativos: são aqueles que permitem obter as raízes de um sistema com uma dada precisão 
através de um processo infinito convergente. Veremos neste capítulo somente métodos 
exatos. 
 
1.1.1- Métodos para Sistemas Triangulares Inferiores. 
 
Seja o sistema triangular inferior: 
 
�
�
�
�
�
�
�
=+++
=+
=
nnnn22n11n
2222121
111
bxa....xaxa
.
bxaxa
ba
������
 
onde aii ≠ 0, i = 1, 2, ...,n. 
 
Por substituição progressiva podemos resolvê-lo pelas fórmulas: 
 
x1 = 
11
1
a
b
 
xi = ( bi - �
−
=
1i
1j
jijxa ) / aii ; i = 2, 3, ..., n. 
 
1.1.2- Métodos para Sistema Triangulares Superiores. 
 
 
Seja o sistema triangular superior 
 
�
�
�
�
�
�
�
=
=++
=+++
nnnn
2nn2222
1nn1212111
bxa
bxaxa
bxaxaxa
�������
�
�
 
onde aii ≠ 0; i = 1,2,...,n. 
 
 
 
 2
Por substituição Retroativa podemos resolvê-lo pelas fórmulas: 
xn = 
nn
n
a
b
 
xi = ( bi - �
+=
n
1ij
jijxa ) / aii i = n-1, ..., 1 
Exemplo 1.1.1: 
 
 a) Resolver o sistema triangular inferior, 
 
 
�
�
�
�
�
	
	
	
�
12/12/1
010
001
 
�
�
�
�
�
	
	
	
�
3
2
1
y
y
y
 = 
�
�
�
�
�
	
	
	
�
7
1
9
 
 
 Por substituição progressiva tem-se: y1 = 9 e y2 = 1 
 
 
2
1
y1 + 
2
1
y2 + y3 = 7 → y3 = 2 
 
 ∴ y = 
�
�
�
�
�
	
	
	
�
2
1
9
 
 
 b) Resolver o sistema triangular superior 
 
�
�
�
�
�
	
	
	
�
−
100
110
312
 
�
�
�
�
�
	
	
	
�
3
2
1
x
x
x
 = 
�
�
�
�
�
	
	
	
�
2
1
9
 
 
Por substituição retroativa: x3 = 2 
 -x2 + x3 = 1 → x2 = 1 
 2x1 + x2 + 3 x3 = 9 → x1 = 1 
 
∴ a solução deste sistema é x = 
�
�
�
�
�
	
	
	
�
2
1
1
. 
 
 
 
 
 
 3
1.2- O Método de eliminação de Gauss ou Método de Gauss Simples. 
 
 
Seja o sistema linear Ax = b, onde A tem todas as submatrizes principais não 
singulares. 
O método de eliminação de Gauss consiste em transformar o sistema dado num 
sistema triangular equivalente pela aplicação repetida da operação: 
“subtrair de uma equação outra equação multiplicada por uma constante 
diferente de zero”. 
 
É claro que tal operação não altera a solução do sistema, isto é, obtem-se com ela 
outro sistema equivalente ao original. 
 
Descrição do algoritmo: 
 
Consideremos o sistema: 
 
�
�
�
�
�
�
�
=+++
=+++
=+++
nnnn22n11n
2nn2222121
1nn1212111
bxaxaxa
bxaxaxa
bxaxaxa
�
�����
�
�
 
 
cuja matriz dos coeficientes chamaremos A(1) . 
 
Montamos a tabela 1: 
 
�
�
�
�
�
�
�
	
	
	
	
	
�
)1(
n
)1(
nn
)1(
2n
)1(
1n
)1(
2
)1(
n2
)1(
22
)1(
21
)1(
1
)1(
n1
)1(
12
)1(
11
baaa
baaa
baaa
�
��������
�
�
 
 
onde: 
 
aij(1) = aij ; bi(1) = bi ; i, j = 1, 2, ..., n 
 
 
Por hipótese temos que a11(1) ≠ 0, pois det ( A1) ≠ 0. 
 
Primeiro Passo: 
 
Eliminar a incógnita x1 da 2a , 3a , ..., na equações ( isto é, zerar os elementos da 
primeira coluna abaixo da diagonal) ; para isso: 
Subtraímos da 2a. equação a 1a. equação multiplicada por 
 )1(
11
)1(
21
a
a
 
 4
Subtraímos da 3a. equação a 1a. equação multiplicada por 
 )1(
11
)1(
31
a
a
 
Subtraímos da na. equação a 1a. equação multiplicada por 
 )1(
11
)1(
1n
a
a
 
Passamos então da tabela inicial à tabela 2: 
 
�
�
�
�
�
�
�
	
	
	
	
	
�
)2(
N
)2(
nn
)2(
3n
)2(
2n
)2(
2
)2(
n2
)2(
23
)2(
22
)1(
1
)1(
n1
)1(
13
)1(
12
)1(
11
baaa
baaa
baaaa
�
��������
�
�
 
 
onde: )1(
11
)1(
1i)1(
j1
)1(
ij
)2(
ij
a
a
aaa −= ; i = 2, 3, ..., n 
 
 )1(
11
)1(
1i)1(
1
)1(
i
)2(
i
a
a
bbb −= j = 1, 2, ..., n 
 
Temos por hipótese que a22
2 0( ) ,≠ pois det ( A2) ≠ 0 . 
 
Segundo passo. 
 
Eliminar a incógnita x2 da 3a. , 4a. , ..., na. equações (isto é, zerar os elementos da 
segunda coluna abaixo da diagonal) ; para isso 
Subtraímos da 3a. equação a 2a. equação multiplicada por )2(
22
)2(
32
a
a
 
Subtraímos da 4a. equação a 2a. equação multiplicada por )2(
22
)2(
42
a
a
 
- - - - - - - - - - - - - - - - - - - - - - - -- - - - - - - - - - - - - - - 
Subtraímos da na. equação a 2a. equação multiplicada por )2(
22
)2(
2n
a
a
 
Obtemos então a tabela 3: 
 
�
�
�
�
�
�
�
�
	
	
	
	
	
	
�
)3(
n
)3(
nn
)3(
3n
)3(
3
)3(
n3
)3(
33
)2(
2
)2(
n2
)2(
23
)2(
22
)1(
1
)1(
n1
)1(
13
)1(
12
)1(
11
baa
baa
baaa
baaaa
�
���������
�
�
�
 
 5
 
onde )2(
22
)2(
2i)2(
j2
)2(
ij
)3(
ij
a
a
aaa −= ; )2(
22
)2(
2i)2(
2
)2(
i
)3(
i
a
a
bbb −= ; i = 3, 4, ..., n; j = 2, 3, ..., n 
 
 
 
 
E assim sucessivamente, chegaremos ao: 
 
(n -1) º Passo 
 
Temos por hipótese que ( ) .0Adetpois,0a 1n)1n( 1n,1n ≠≠ −− −− 
Eliminar a incógnita xn-1 da na. equação (isto é, zerar o elemento da (n-1)ª coluna 
abaixo da diagonal); para isso: 
Subtraímos da na. equação, a (n-1)ª. equação multiplicada por .
a
a
)1n(
1n,1n
)1n(
1n,n
−
−−
−
−
 
E assim, obtemos a tabela n: 
 
�
�
�
�
�
�
�
�
�
	
	
	
	
	
	
	
�
−
−
−
−
−
−−
−
−
−
)n(
n
)n(
nn
)1n(
1n
)1n(
n,1n
)1n(
1n,1n
)3(
3
)3(
n3
)3(
1n,3
)3(
33
)2(
2
)2(
n2
)2(
1n,2
)2(
23
)2(
22
)1(
1
)1(
n1
)1(
1n,1
)1(
13
)1(
12
)1(
11
ba
baa
baaa
baaaa
baaaaa
�
�
�
 
onde: 
 
 )1n(
1n,1n
)1n(
1n,i)1n(
j,1n
)1n(
ij
)n(
ij
a
a
.aaa
−
−−
−
−
−
−
−
−= 
 bi( n) = bi(n – 1) - )1n(
1n,1n
)1n(
1n,i)1n(
1n
a
a
.b
−
−−
−
−
−
−
; i = n; j = n – 1, n. 
 
 
Assim, o sistema triangular superior obtido será: 
 
 
 6
�
�
�
�
�
��
�
�
�
�
=
=+
=+++
=++++
=+++++
−
−
−
−−
−
−−
−
−
−
)n(
nn
)n(
nn
)1n(
1nn
)1n(
n,1n1n
)1n(
1n,1n
)3(
3n
)3(
n3
)3(
1n,33
)3(
33
)2(
2n
)2(
n2
)2(
1n,23
)2(
232
)2(
22
)1(
1n
)1(
n1
)1(
1n,13
)1(
132
)1(
121
)1(
11
bxa
bxaxa
bxaaxa
bxaaxaxa
bxaaxaxaxa
�������������
�
�
�
 
 
 
é equivalente ao Sistema Linear original. 
 
 
Exemplo 1.2.1: 
 
Resolver o sistema: 
 
�
�
�
�
�
	
	
	
�
=
��
�
�
�
	
	
	
�
�
�
�
�
�
	
	
	
� −
13
7
7
823
142
126
3
2
1
x
x
x
 
 
usando o método de Eliminação de Gauss. 
 
Temos a tabela 1: 
 
�
�
�
�
�
	
	
	
� −
13823
7142
7126
 
 
 
 
 
 
 
 
 
 
 
 
 
 7
1a
a
a
aaa
0a
a
a
aaa
3
14b
a
abbb
3
4
a
a
a
aaa
3
10
a
a
a
aaa
0a
a
a
aaa
)2(
32)1(
11
)1(
31)1(
12
)1(
32
)2(
32
)2(
31)1(
11
)1(
31)1(
11
)1(
31
)2(
31
)2(
2)1(
11
)1(
21)1(
1
)1(
2
)2(
2
)2(
23)1(
11
)1(
21)1(
13
)1(
23
)2(
23
)2(
22)1(
11
)1(
21)1(
12
)1(
22
)2(
22
)2(
21)1(
11
)1(
21)1(
11
)1(
21
)2(
21
=�−=
=�−=
=�−=
=�−=
=�−=
=�−=
 
( ) ( ) ( ) ( )
( )
( )
2
19b
a
a
bbb 231
11
1
311
1
1
3
2
3 =�−= 
 
 
Assim obtemos a tabela 2: 
 
�
�
�
�
�
	
	
	
� −
2/192/1710
3/143/43/100
7126
 
 
2º Passo: 
 
 
10
81b
a
a
.bbb )3(3)2(
22
)2(
32)2(
2
)2(
3
)3(
3 =�−= 
Omitindo aqui a tabela 3, diretamente, obtemos o seguinte sistema triangular 
superior: 
2
17)2(
33)1(
11
)1(
31)1(
13
)1(
33
)2(
33 =�−= a
a
a
aaa
0)3(32)2(
22
)2(
32)2(
22
)12
32
)3(
32 =�−= a
a
a
aaa
10
81)3(
33)2(
22
)2(
32)2(
23
)2(
33
)3(
33 =�−= a
a
a
aaa
 8
 
�
�
�
�
�
	
	
	
�
=
�
�
�
�
�
	
	
	
�
�
�
�
�
�
	
	
	
� −
10/81
3/14
7
10/8100
3/43/100
126
3
2
1
x
x
x
 
 
Solução: 
 
1x7xx2x6
1x
3
14
x
3
4
x
3
10
1x
10
81
x
10
81
1321
233
33
=�=−+
=�=+
=�=∴
 
 
Portanto, a solução de : 
 
 
�
�
�
�
�
	
	
	
�
=
�
�
�
�
�
	
	
	
�
=
�
�
�
�
�
	
	
	
�
�
�
�
�
�
	
	
	
� −
1
1
1
xé
13
7
7
x
x
x
823
143
126
3
2
1
 
 
 
1.2.1 O Método de Gauss com Pivoteamento Parcial 
 
1) O elemento )k(kka é o pivot do Kº passo. 
 
 2) Se em algum passo K encontrarmos 0a )k(kk = isso significa que det (Ak) = 0. 
Nesse caso, o sistema ainda pode Ter solução determinada (basta que det (A) ≠ 0 ). 
O método pode ser continuado simplesmente permutando a kª equação com qualquer 
outra abaixo cujo coeficiente da Kª incógnita seja ≠ 0. 
 
3) Análise de propagação de erros de arredondamento para o algorítmo de Gauss indicam a 
conveniência de serem todos multiplicadores ( as constantes )k(kk)k(ik a/a do kº passo) 
menores que 1 em módulo; ou seja o pivot deve ser o elemento de maior valor absoluto da 
coluna, da diagonal (inclusive) para baixo. 
Podemos então em cada passo, escolher na coluna correspondente o elemento de 
maior valor absoluto, da diagonal (inclusive) para baixo, e fazer uma permutação nas 
equações do sistema, de modo que esse elemento venha a ocupar a posição diagonal. 
 
O exemplo abaixo ilustra as observações de nº 2 e 3. 
 
 
Exemplo 1.2.2: 
 
 9
Resolver usando o método de Eliminação de Gauss o sistema: 
�
�
�
�
�
=+−
=++
=−+
5x5xx
7xx3x3
3xx2x2
321
321
321
 
 
Montamos a tabela 
 
�
�
�
�
�
	
	
	
�
−
−
5511
7133
3122
 
 
Em vista da observação 3) : passamos da tabela inicial à tabela 
 
�
�
�
�
�
	
	
	
�
−
−
5511
3122
7133
 
isto é, colocamos na posição do pivot o maior elemento da coluna, e aplicando o 1º passo, 
obtemos: 
�
�
�
�
�
	
	
	
�
−
−−
3/83/1420
3/53/500
7133
 
Vemos aqui que o elemento 0a )2(32 = (como já dissemos (obs.2) isso significa que 
det(A2)= 0. De fato: det( A2) = 22
33
 = 0 ). 
 
Como o elemento 0)2(32 ≠a , permutamos a 3
ª
 equação com a 2ª equação e assim 
obtemos a tabela: 
 
�
�
�
�
�
	
	
	
�
−−
−
3/53/500
3/83/1420
7133
 
a qual corresponde a um sistema triangular. 
 
Portanto, temos: 
 
�
�
�
�
�
	
	
	
�
−
=
�
�
�
�
�
	
	
	
�
�
�
�
�
�
	
	
	
�
−
−
3/5
3/8
7
3/500
3/1420
133
3
2
1
x
x
x
 
Assim 
 10
 33
5
x− = 1
3
5
3 =�− x 
 
1x7xx3x3
1x
3
8
x
3
14
x2
1321
232
=�=++
=�=+−
 
Logo, a solução de: 
 
�
�
�
�
�
	
	
	
�
=
�
�
�
�
�
=+−
=++
=−+
1
1
1
xé
5x5xx
7xx3x3
3xx2x2
321
321
321
 
 
1.2.2 O Método de Gauss com Pivoteamento Total 
 
 Neste método é adotada a seguinte estratégia: 
- no k-ésimo passo é escolhido para pivô o elemento de maior módulo entre todos os 
elementos que ainda atuam no processo de eliminação, ou seja, o elemento pivô será: 
)1k(
ijakj,imax
−
≥
. 
 
 - esta estratégia não é usualmente empregada pois envolve uma comparação entre os 
elementos envolvidos na troca de linhas e colunas, o que , evidentemente acarreta um 
esforço computacional maior que a estratégia de pivoteamento parcial. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1.2.3- Exercícios 
 
1.2.3.1) Resolver pelo método de Eliminação de Gauss, o sistema: 
 
 11
�
�
�
�
�
=++
−=−−
−=+−
42
764
532
321
321
321
xxx
xxx
xxx
 
 
1.2.3.2) Considere o sistema: 
 
�
�
�
�
�
=+−
=++−
−=++
31032
2024
1225
321
321
321
xxx
xxx
xxx
 
Pede-se: 
a) Resolver pelo Método de Eliminação de Gauss. 
b) Calcular o determinante de A, onde A é matriz dos coeficientes. 
 
1.2.3.3) Verificar usando Eliminação de Gauss que o seguinte sistema não tem 
solução: 
 
�
�
�
�
�
=++
=++
=++
1x2x5x3
5xx3x2
3xx2x
321
321
321
 
 
1.2.3.4) Exercícios complementares: fazer exercícios relativos aos tópicos vistos dos 
livro: Barroso, L.C. e Ruggiero, M. A. G. (ver no link “Conclusão”)