Cálculo Numérico
Módulo V
Resolução Numérica de
Sistemas Lineares – Parte I
Profs.: Bruno Correia da Nóbrega Queiroz
José Eustáquio Rangel de Queiroz
Marcelo Alves de Barros
Sistemas Lineares

Forma Geral
a1 1x1  a1 2x 2  ...  a1n x n  b1
a2 1x1  a2 2x 2  ...  a2n x n  b2





an1 x1  an2 x 2  ...  ann x n  bn
onde:
aij
xi
bi
coeficientes
 incógnitas
 termos independentes

2
Sistemas Lineares

Exemplo 01
2 x1  4 x 2  5 x 3  5
4 x1  1x 2  5 x 3  2
2 x 1  4 x 2  5 x 3  1
2, 4, -5, 4, 1, -5, 2, 4 e 5  coeficientes
x1 , x2 e x3
 incógnitas
5, 2 e -1
 termos independentes
3
Sistemas Lineares

Forma Matricial
Ax = b
na qual:
 a11 a12  a1n 


 a21 a22  a2 n 
A



 
 


 an1 an2 an 3 ann 
 b1 
b 
b   2
  
 bn 
 x1 
x 
x   2
  
 xn 
4
Sistemas Lineares

Exemplo 02
Forma Geral
2x1  4x2  5x 3  5
4x1  1x2  5x 3  2
2x1  4x2  5x 3  1
Forma Matricial
2 4  5  x1   5 
4 1  5. x2    2 
2 4 5   x    1

  3  
5
Sistemas Lineares

Classificação I
Impossível  Não possui solução

Exemplo 03
 x1  x 2  3

2 x1  2 x 2  9
6
Sistemas Lineares

Classificação II
Possível  Possui 1 ou mais soluções

Determinado  Solução única

Exemplo 04
 x1  x 2  4
x  x  8
2
 1
7
Sistemas Lineares

Classificação III
Possível  Possui 1 ou mais soluções

Indeterminado  Mais de uma solução

Exemplo 05
 x1  x 2  4

2 x1  2 x 2  8
8
Sistemas Lineares

Classificação IV
Possível  Possui 1 ou mais soluções

Homogêneo  Vetor b=0 (x=0 sempre
existe solução)

Exemplo 06
 x1  x 2  0

2 x1  3 x 2  0
9
Sistemas Lineares

Sistemas Triangulares:
Possibilidade de resolução de forma
Direta

Inferior
 a11 0
a
a22
21
A   a31 a32


 
 an1 an2
0
0
a33

an 3
 0 
 0 

 0 

 
 ann 
10
Sistemas Lineares

Sistemas Triangulares:
Possibilidade de resolução de forma
Retroativa

Superior
 a11 a12
 0 a
22

A 0
0


 
0
 0
a13
a23
a33

0





a1n 
a2 n 

a3 n 
 
ann 
11
Solução Retroativa

Exemplo 7:
Dado o sistema:
3 x 1 4 x 2
x2
5 x 3
 x3
4 x3
 x4
 2 x4
 5 x4
2 x4
 10
 1
 3
 2
Primeiro passo para sua resolução:
2
x4 
1
2
12
Solução Retroativa

Exemplo 7:
Segundo passo:
4 x3  5 x4  3
4 x3  5  1  3
x3  2
Terceiro passo:
x 2  x 3  2 x 4  1
x 2  2  2  1  1
x 2  1
13
Solução Retroativa

Exemplo 7:
Último passo:
3 x1  4 x 2  5 x 3  x 4  10
3 x1  4  ( 1)  5  2  1  10
x1  1
14
Métodos Numéricos

Diretos
Solução pode ser encontrada a partir de um
número finito de passos

Método de Gauss

Método da Eliminação de Jordan

Fatoração LU
15
Métodos Numéricos

Iterativos
Solução a partir de uma seqüência de
aproximações para o valor do vetor solução
x , até que seja obtido um valor que satisfaça
à precisão pré-estabelecida

Método de Jacobi

Método de Gauss – Seidel
16
Método de Gauss

Propósito
 Transformação do sistema linear a ser
resolvido em um sistema linear triangular;
 Resolução do sistema linear triangular de
forma retroativa.
17
Método de Gauss

Transformação do Sistema Linear
 Troca da ordem das linhas;
 Multiplicação de uma das equações por
um número real não nulo;
 Substituição de uma das equações por
uma combinação linear dela mesma com
outra equação.
18
Método de Gauss

Passos do Método de Gauss
Construção da matriz aumentada Ab
 a11 a12  a1n b1 
a

a

a
b
2n
2
Ab    21 22




 

 an1 an2 an 3 ann bn 
19
Método de Gauss

Passos do Método de Gauss
Passo 1:

Eliminar os coeficientes de x1 presentes
nas linhas 2,3,...,n - sendo a21 = a31, = ...
= an1 = 0 - sendo a11 chamado de pivô da
coluna

Substituir a linha 2, L2, pela combinação
linear
L2  m21  L1 , na qual : m21
a21

a11
20
Método de Gauss

Passos do Método de Gauss
Substituir a linha 3, L3, pela combinação
linear:
L3  L3  m31  L1 , na qual : m31
a31

a11
21
Método de Gauss

Passos do Método de Gauss
Continuar a substituição até a linha n;
Caso algum elemento app=0, achar outra
linha k onde akp≠ 0 e trocar tais linhas.
Caso a linha k não exista, o sistema linear
não possui solução.
22
Método de Gauss

Passos do Método de Gauss
Eliminar os coeficientes de x2 nas linhas
3, 4, ..., n (fazer a32=a42=...=an2 = 0);
Eliminar os coeficientes de x3 nas linhas
4, 5, ..., n (fazer a43=a53=...=an3 = 0) e
assim sucessivamente.
23
Método de Gauss

Exemplo 8:
Resolver o sistema:
2 x1  3 x 2  x 3  5
4 x1  4 x 2  3 x 3  3
2 x 1  3 x 2  x 3  1

Matriz aumentada Ab
2
Ab  4
2
3
4
3
1
3
1
5
3
 1
24
Método de Gauss

Exemplo 8:
Faz-se:
L2  L2  m21  L1 , m21
a21

2
a11
Assim:
L2  4 4 3 3   2  2 3 1 5 
L2  0  2  1  7 
25
Método de Gauss

Exemplo 8:
Faz-se:
L3  L3  m31  L1 , m23
a31

1
a11
Assim:
L3  2 3 1 1  1  2 3 1 5 
L3  0  6 2  6
26
Método de Gauss

Exemplo 8:
Obtém-se a matriz:
 2 3 1 5 
Ab   0  2  1  7 
0  6 2  6 
27
Método de Gauss

Exemplo 8:
Substituindo a linha 3 por:
L3  L3  m32  L1 , m32
Têm-se:
a32

3
a22
L 3  0  6 2  6  3  0  2  1  7
L 3  0 0 5 15
28
Método de Gauss

Exemplo 8:
A matriz [Ab] fica assim com os seguintes
valores:
2
Ab  0
0
3
2
0
1
1
5
5
 7
15 
29
Método de Gauss

Exemplo 8:
Usa-se a solução retroativa:
5x 3  15  x 3  3


 2x 2  x 3  7  2x 2  3  7  x 2  2

2x  3  x  x  5 
2
3
 1
 2x 6  3  5  2x  2  x  1
1
1
1

30
Método de Gauss

Exemplo 9:
Resolver o sistema.
1 ,5 x1  5 ,4 x 2  3 ,3 x 3  10
4 ,2 x1  2 ,3 x 2  4 ,5 x 3  11,7
2 ,7 x1  5 ,7 x 2  7 ,8 x 3  8 ,9
Representando
aumentada:
o
sistema
pela
matriz
 1 ,5 5 ,4 3 ,3 10 
[ AB ]   4 ,2 2 ,3 4 ,5 11,7 
2 ,7 5 ,7 7 ,8 8 ,9 


31
Método de Gauss

Exemplo 9:
Escolhendo a primeira linha como pivô,
obtém-se:
L 2  L 2  m21  L1  4,2 2,3 4,5 11,7  
(4,2/1,5)  1,5 5,4 3,3 10 
L 2   0  12,82  4,74  16,3

L 3  L 3  m31  L1  2,7 5,7 7,8 8,9 
(2,7/1,5)  1,5 5,4 3,3 10 
L 3   0  4,02  1,86  9,1 
32
Método de Gauss

Exemplo 9:
Representando o sistema pela matriz
aumentada:
5,4
3,3
10 
1,5
[AB]   0  12,82  4,74  16,3 
 0
 4,02  1,86  9,1 
33
Método de Gauss

Exemplo 9:
Escolhendo agora a segunda linha como
pivô, têm-se:
L 3  L 3  m32  L1
L 3  0  4,02  1,86  9,1 
 4,02/  12,82  0  12,82  4,74  16,3
L 3  0 0 3,3463  3,9888
34
Método de Gauss

Exemplo 9:
Obtêm-se a seguinte matriz ampliada:
5,4
3,3
10
1,5

[AB]   0  12,82  4,74
 16,3 
 0
0
3,3463  3,9888
35
Método de Gauss

Exemplo 9:
 O que termina com a triangulação:
1,5x1  5,4  x 2  3,3  x 3  10

0  x1  12,82  x 2  4,74  x 3  16,3
0  x  0  x  3,3463  x  3,9888
1
2
3

36
Método de Gauss

Exemplo 9:
Com solução:
x3 = -3,9888/3,3463=-1,1918
x2 =[ -16,3 - (-4,74)(-1,1920)]/(-12,82) = 1,7121
x1 = [10 - 5,4(1,7122) - 3,3(-1,1920)]/1,5 = 3,1251
37
Método do Pivoteamento Parcial

Semelhante ao método de Gauss;

Minimiza a amplificação de erros de
arredondamento durante as eliminações;

Consiste em escolher o elemento de
maior módulo em cada coluna para ser o
pivô.
38
Método do Pivoteamento Parcial

Exemplo 10:
 Resolver o sistema com precisão de 4
casas decimais
1,5x1  5,4x2  3,3x 3  10
4,2x1  2,3x2  4,5x 3  11,7
2,7x1  5,7x2  7,8x 3  8,9
39
Método do Pivoteamento Parcial

Exemplo 10:
Matriz aumentada original deve ser
ajustada:
1,5 5,4 3,3 10 
4,2 2,3 4,5 11,7
2,7 5,7 7,8 8,9 


4,2 2,3 4,5 11,7
1,5 5,4 3,3 10 
2,7 5,7 7,8 8,9 


40
Método do Pivoteamento Parcial

Exemplo 10:
Sistema inalterado, elemento pivô 4,2.
Encontrar as novas linhas:
L 2  L 2  m21  L1  [1,5 5,4 3,3 10] 
(1,5/4,2)  [ 4,2 2,3 4,5 11,7]
L 2  [0 4,5786 1,6929 5,8214 ]
L 3  L 3  m31  L1  [2,7 5,7 7,8 8,9] 
(2,7/4,2)  [ 4,2 2,3 4,5 11,7]
L 3  [0 4,2214 4,9071 1,3786 ]
41
Método do Pivoteamento Parcial

Exemplo 10:
A matriz ampliada fica da forma:
2,3
4,5
11,7 
 4,2
 0 4,5786 1,6929 5,8214


 0 4,2214 4,9071 1,3786
Como o elemento
coluna, tem-se:
4,5786 já é o pivô da 2ª
L 3  L 3  m32  L 2  [0 4,2214 4,9071 1,3786 ] 
(4,2214/4, 5786)  [0 4,5786 1,6929 5,8214 ]
L 3  [0 0 3,3463  3,9886 ]
42
Método do Pivoteamento Parcial

Exemplo 10:
A matriz ampliada fica na forma:
2,3
4,5
11,7 
 4,2
 0 4,5786 1,6929 5,8214 


 0
0
3,3463 - 3,9886
43
Método do Pivoteamento Parcial

Exemplo 10:
A solução do sistema triangular que
resultou dessas operações é:
x3 = -3,9886/3,3463 = -1,1919
x2 = [5,8214-1,6929(-1,1919)]/(4,5786) = 1,7121
x1 = [11,7- 2,3(1,7121)- 4,5(-1,1919)]/4,2 = 3,1252
44
Método do Pivoteamento Parcial
Exemplo 9: Exemplo 10 (com pivoteamento):
x3 = -1,1918
x2 = 1,7121
x1 = 3,1252
x3 = -1,1919
x2 = 1,7121
x1 = 3,1251
Solução encontrada no Matlab:
x1 = -1,19198135198135
x2 = 1,71216783216783
x3 = 3,12522144522145
45
Método de Jordan

Consiste em efetuar operações sobre as
equações do sistema, com a finalidade de
obter um sistema diagonal equivalente;

Um sistema diagonal é aquele em que os
elementos aij da matriz coeficiente [A]
são iguais a zero, para i≠j,
i, j = 1,2,...,n.
46
Método de Jordan

Sistema diagonal equivalente:
a11 0
0
 0 a
0
22
[A]   0
0
a
33



 
0
0
 0
 0 
 0 

 0 
 
 ann 
47
Método de Jordan

Exemplo 11:
A partir do sistema:
x1  5 x 2  x 3  1
5 x1  2 x 2  3 x 3  2
2 x1  3 x 2  2 x 3  4
Com matriz aumentada:
 1 5 1 1  5 2 3 2 
Ab   5 2 3 2   1 5 1 1
2 3 2 4  2 3 2 4 
48
Método de Jordan

Exemplo 11:
Substituindo a linha 2 por:
L 2  L 2  m21  L1  1 5 1 1  (1/5)  5 2 3 2,
L 2  0 4,6 0,4 0,6,
m21
a21

 1/5  0,2
a11
Substituindo a linha 3 por :
L3  L 3  m31  L1  2 3 2 4  (2/5)  5 2 3 2
L3  0 2,2 0,8 3,2,
m31
a31

 2/5  0,4
a11
49
Método de Jordan

Exemplo 11:
A matriz ampliada resulta em:
5 2
3
2 
Ab  0 4,6 0,4 0,6
0 2,2 0,8 3,2


Substituindo a linha 3 por:
L3  L3  m32  L2  0 2,2 0,8 3,2  (2,2/4,6)  0
L3  0 0 0,609 2,913,
m32 
4,6 0,4 0,6
a32
 2,2/4,6  0,478
a22
50
Método de Jordan

Exemplo 11:
A matriz ampliada resulta em:
5 2
3
1 
Ab  0 4,6 0,4 0,6 
0 0 0,609 2,913


Substituindo a linha 2 por
L 2  L 2  m23  L 3  0 4,6 0,4 0,6 
(0,4/0,609)  0 0 0,609 2,913
L 2  0 4,6 0  1,313
51
Método de Jordan

Exemplo 11:
Matriz ampliada resulta em:
5 2
3
1

Ab  0 4,6 0  1,313
0 0 0,609 2,913 


Substituindo a linha 1 por
L1  5 2 3 1  (2/4,6)  0 4,6 0 1,313,
L1  5 0 3 1,571,
m12
a12

 2/4,6
a22
52
Método de Jordan

Exemplo 11:
Substituindo a linha 1 por:
L1  5 0 3 1,571 
(3/0.609)  0 0 0,609 2,913
L1  5 0 0  12,779
m13
a13

 3/0,609
a33
A matriz ampliada fica da seguinte forma:
5 0
0
12,779
Ab  0 4,6 0  1,313 
2,913 
0 0 0.609
53
Método de Jordan

Exemplo 11:
E as soluções são:

x1 =-2,556 , x2= -0,285, x3=4,783
54
Decomposição em LU

O objetivo é fatorar a matriz dos
coeficientes A em um produto de duas
matrizes L e U.
Seja:
1 0 0
l21 1 0
LU  l31 l32 1


 
ln1 ln2 ln3





0 u11 u12 u13
0  0 u22 u23
0   0
0 u33

0  


1  0
0
0





u1n 
u2n 

u3n 
 
unn 
55
Decomposição em LU

E a matriz coeficiente A:
a11 a12  a1n 
a

a

a
21
22
2
n
A







an1 an2 an3 ann 
Tem-se, então:
a11 a12  a1n 
a
a22  a2n 
21
A         [LU] 


an1 an2 an3 ann 
1 0 0
l21 1 0
l
l
1
 31 32


 
ln1 ln2 ln3





0 u11 u12 u13
0  0 u22 u23
0   0
0 u33

0  


1  0
0
0





u1n 
u2n 

u3n 
 
unn 
56
Decomposição em LU

Para se obter os elementos da matriz L e
da matriz U, deve-se calcular os
elementos das linhas de U e os elementos
da colunas de L como segue.
57
Decomposição em LU

1ª linha de U: Faze-se o produto da 1ª
linha de L por todas as colunas de U e a
iguala com todos os elementos da 1ª
linha de A, assim:
1  u11  a11  u11  a11 ,
1  u  a  u  a ,
12
12
12
12



1  u1n  a1n  u1n  a1n ,
u  a , j  1,2,...,n.
1j
 1j
58
Decomposição em LU

1ª coluna de L: Faz-se o produto de todas
as linhas de L, (da 2ª a até a nª), pela 1ª
coluna de U e a iguala com os elementos
da 1ª coluna de A, (abaixo da diagonal
principal), obtendo ,

a21
l

u

a

l

,
21
21
 21 11
u11

a
l31  u11  a31  l31  31 ,
u11




l  u  a  l  al1 ,
11
l1
l1
 l1
u11

al1
l

, l  1,2,..., n.
 l1
u11


59
Decomposição em LU

2ª linha de U: Faz-se o produto da 2ª
linha de L por todas as colunas de U, (da
2ª até a nª), e igualando com os
elementos da 2ª linha de A, (da diagonal
principal em diante), obtêm-se ,
l21  u12  u22  a22  u22  a22  l21  u12 ,


l21  u13  u23  a23  u23  a23  l21  u13 ,





l21  u1n  u2n  a2n  u2n  a2n  l21  u1n ,


u2 j  a2 j  l21  u1 j , j  3,..., n.
60
Decomposição em LU

2ª coluna de L: Faz-se o produto de todas
as linhas de L (da 3ª até a nª) pela 2ª
coluna de U e a iguala com os elementos
da 2ª coluna de A, (abaixo da diagonal
principal), obtendo ,

a32  l31  u12
l

u

l

u

a

l

,
32
22
32
32
 31 12
u22

a  l41  u12
l41  u12  l42  u22  a42  l42  42
,
u


22


l  u  l  u  a  l  al2  ll1  u12 ,
12
l2
22
l2
l2
 l1
u22

al2  ll1  u12
l

, l  3,..., n.
 l2
u22


61
Decomposição em LU

Temos a seguinte fórmula geral:

ulj  alj 



l  (a 
lj
 lj


l 1

l
llk  ukj ,
l  j,
k 1
lk
 ukj) / u jj ,
l  j.
62
Decomposição em LU

Resumo de Passos:
Seja um sistema Ax = b de ordem n, onde
A satisfaz as condições da fatoração LU.
Então, o sistema Ax = b pode ser escrito
como:

LUx = b
63
Decomposição em LU

Resumo dos Passos:
Fazendo Ux = y, a equação acima reduzse a Ly = b.
Resolvendo o sistema triangular inferior
Ly = b, obtém-se o vetor y.
64
Decomposição em LU

Resumo dos Passos:
 Substituição do valor de y no sistema
Ux = y  Obtenção de um sistema
triangular superior cuja solução é o vetor
x procurado;
 Aplicação da fatoração LU na resolução
de sistemas lineares  Necessidade de
solução de dois sistemas triangulares
65
Erros - Avaliação de Erros

No sistema Ax = b , no qual:
a11 a12
a
a22
21
[A]  

 
an1 an2
 a1n 
 a2n 

  
 ann 
 x1 
x 
x   2
  
 xn 
b1 
b 
b   2
  
bn 
o erro da solução é x – x’ .
66
Erros - Avaliação de Erros
 Procedimento
de Determinação do Erro
 Determinar:

Ax’ = b’
67
Erros – Resíduo
 Procedimento
de Determinação do Erro
 Fazer:

Resíduo = b – b’
Resíduo = b – b’ = Ax - Ax’ = A(x – x’) = Aerro
68
Erros – Resíduo

Verifica-se que:
O resíduo não é o erro, apenas uma
estimativa do mesmo;
Quanto menor for o resíduo, menor será
o erro.
69
Erros – Resíduo

Exemplo 12:
Refinar a solução do sistema:
1,5x1  5,4x2  3,3x 3  10
4,2x1  2,3x2  4,5x 3  11,7
2,7x1  5,7x2  7,8x 3  8,9
Cuja solução encontrada através pelo
método de Gauss, utilizando a solução
retroativa é:
x(0)  [3,1252 1,7121 - 1,1918]´
70
Erros – Resíduo

Exemplo 12:
O resíduo calculado é:
r (0)  b  Ax (0)
  0.0002
   0.0006
  0.0010
Vê-se pelo resíduo que a precisão
alcançada não foi satisfatória.
O vetor x(0) é chamado de vetor solução.
71
Erros – Resíduo

Exemplo 12:
Com o intuito de melhorar a solução,
considera-se um novo vetor x(1) chamado
de vetor solução melhorado.
72
Erros – Resíduo

Exemplo 12:
De forma que : x(1) = x(0) + δ(0), onde δ(0) é
o vetor de correção. Assim:
Ax(1)  b
A ( x (0 )   (0 ) )  b
Ax(0)  A (0)  b
A (0)  b  Ax(0)
A ( 0 )  r ( 0 )
73
Erros – Resíduo

Exemplo 12:
Calcular o vetor de correção:

δ

1
1,5 5,4 3,3 10     0,0002 
4,2 2,3 4,5 11,7.δ 2     0,0006 
2,7 5,7 7,8 8,9    


 δ3

0,0010

  
74
Erros – Resíduo

Exemplo 12:
A solução é:
δ
0,0000
(0) 

 0,0001
0,0002
75
Erros – Resíduo

Exemplo 12:
Desta forma, a solução melhorada será:
x
(1)
x
(0)
(0)
δ
3,1252 
 1,7122 


  1,1920
76
Erros – Resíduo

Exemplo 12:
Cujo novo resíduo é:
r
(1)
(1)
 b  Ax
0,0000


 0,0000
0,0000


77
Erros – Resíduo

Exemplo 12:
Em exemplos onde o resíduo ainda não
seja satisfeito pode-se utilizar o mesmo
procedimento:
x(2)=x(1)+δ(1)
Assim, o vetor correção δ(1), será
calculado por
A δ(1) =r(1).
78
Erros – Resíduo

Exemplo 12:
Acha-se assim, sempre uma solução
melhorada e com resíduo tendendo a
zero.
79
Sistemas Lineares - Bibliografia
 Ruggiero, M. A. Gomes & Lopes, V. L. da R. Cálculo
Numérico: Aspectos teóricos e computacionais.
MAKRON Books, 1996, 2ª ed.
 Asano, C. H. & Colli, E. Cálculo Numérico:
Fundamentos e Aplicações. Departamento de
Matemática Aplicada – IME/USP, 2007.
 Sanches, I. J. & Furlan, D. C. Métodos Numéricos.
DI/UFPR, 2006.
 Paulino, C. D. & Soares, C. Erros e Propagação de
Erros, Notas de aula, SE/ DM/ IST [Online]
http://www.math.ist.utl.pt/stat/pe/qeb/semestr
e_1_2004-2005/PE_erros.pdf [Último acesso 07
de Junho de 2007].
80