Aulas 01 e 02 Sistema de Equacoes Lineares

Prévia do material em texto

Sistema de Equações
Lineares
Métodos Diretos
Solução de Equações Lineares
Duas equações 
simultaneas – A 
solução é a interseção 
de linhas retas.
Um sistema com n equações lineares e n 
variáveis
Na notação matricial Ax = b, temos
nnnnnn
n
b
b
b
b
x
x
x
x
aaa
aaa
aaa
A



2
1
2
1
21
222221
11111
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa




2211
22222121
11212111
O sistema linear tem uma única solução quando 
se det(A) ≠ 0.
Metodologias para Solução de uma Sistema 
Linear
A. Métodos Diretos
São aqueles que conduzem a solução exata a
menos de erros de arredondamento introduzidos
pela máquina, após número finito de passos:
• Tem a vantagem de fornecer a solução após um 
número finito de passos;
• São inviáveis quando o sistema é muito grande 
ou mal condicionado;
• Exemplos de métodos diretos: Eliminação 
Gaussiana e Eliminação de Gauss Jordan.
Metodologias para Solução de uma Sistema Linear
B. Métodos Iterativos
• São aqueles que se baseiam na construção de uma 
sequência de aproximações:
• Útil se a sequência convirgir para a solução do 
sistema;
• Em cada passo os valores calculados anteriormente 
são usados para aperfeiçoar a aproximação;
• São mais econômicos na utlização de memória;
• Exemplos de métodos iterativos: Método de Gauss 
Jacobi e método de Gauss Seidel.
Métodos Diretos
1. Eliminação Gaussiana
a. Complexidade;
b. Estratégias de Pivoteamento;
c. Resíduos;
d. Normas.
2. Métodos das Decomposições
a. Decomposição LU;
b. Decomposição de Cholesky;
c. Decomposição QR. 
A.1. Eliminação Gaussiana
Sistema de Equações Lineares onde a matriz é
triangular (A = (aij), j ≥ I, bi, 1≤i, j ≤ n ), por exemplo
superior.
nnnn
nn
nn
nn
bxa
bxaxa
bxaxaxa
bxaxaxaxa




33333
22323222
11313212111
F
ig
u
re
 4
-1
Figure 4-10
Figure 4-11
Figure 4-12
Figure 4-13
Figure 4-14
Figure 4-15
Figure 4-18
F
ig
u
re
 4
-1
6
Eliminação Gaussiana Dois passos da Eliminação 
Gaussiana:
1131321211
'
223
'
23
'
22
"
33
"
33
"
3
'
2
1
"
33
'
23
'
22
131211
3
2
1
333231
232221
131211
/)(
/)(
/
axaxabx
axabx
abx
b
b
b
a
aa
aaa
b
b
b
aaa
aaa
aaa
Back Substitution –
Encontrar o valor das varíaveis 
Forward Elimination –
Transformar as equações em 
um sistema triangular
A.1.a. Eliminação Gaussiana Ingênua
Ë chamada Eliminação Gaussiana Ingênua por que não 
evita a divisão por zero.
"
33
"
33
'
23
'
232
'
22
1313212111
3333232131
2323222121
1313212111
bxa
bxaxa
bxaxaxa
bxaxaxa
bxaxaxa
bxaxaxa
Forward Elimination
Propósito: Reduzir o sistema a condição de 
triangular superior
Forward Elimination
'
33
'
332
'
32
'
23
'
232
'
22
1313212111
3333232131
2323222121
1313212111
bxaxa
bxaxa
bxaxaxa
bxaxaxa
bxaxaxa
bxaxaxa
Passo 1: Remover x1 de todas as equações exceto 
da primeira (O qual serve como equação pivo.)
)3(
)2(
)1(
3333232131
2323222121
1313212111
ebxaxaxa
ebxaxaxa
ebxaxaxa
Objetivando remover x1 seja a seguinte notação. 
Nota: (ei) denota 
a i-ésima linha.
Forward Elimination
Se a11 ≠ 0, defina m21 = a21 / a11.
Podemos substituir (e2) por {(e2) – m21 x (e1)}. Então:
1212313212321221221
121231321211121323222121
)()(0
)()(
bmbxamaxamax
bmbxaxaxamxaxaxa
1212
'
2132123
'
23122122
'
22 bmbbamaaamaa
Logo
Temos então
)'2(
)1(
'
23
'
232
'
22
1313212111
ebxaxa
ebxaxaxa
De forma similar para (e3').
Note:a11 é chamado coeficiente do 
pivo.
"
33
"
33
'
23
'
232
'
22
1313212111
'
33
'
332
'
32
'
23
'
232
'
22
1313212111
bxa
bxaxa
bxaxaxa
bxaxa
bxaxa
bxaxaxa
Forward Elimination
Step 2: Removemos x2 de todas equações exceto das duas 
primeiras (e1) and (e2'). Isto é:
Assim sendo, 
)'3(
)'2(
)1(
'
33
'
332
'
32
'
23
'
232
'
22
1313212111
ebxaxa
ebxaxa
ebxaxaxa
(Basicamente repetimos o passo 1 sobre cada subsistema)
Forward Elimination
Se a'22 ≠ 0, então m32 = a'32 / a'22.
Substituimos (e3') por {(e3') – m32 x (e2')}. Então
'
232
'
33
'
2332
'
332
'
232
'
33
'
232
'
22323
'
332
'
32
)(0
)()(
bmbxamax
bmbxaxamxaxa
'
232
'
3
"
3
'
2332
'
33
"
33 bmbbamaa
Porém
Temos
"
33
"
33
'
23
'
232
'
22
1313212111
bxa
bxaxa
bxaxaxa
Forward Elimination
Em geral, dado um sistema de n equações lineares e n
variáveis, o procedimento se repete transformando a matriz em
triangular.
)1()1(
)1(
2
)1(
23
)1(
232
)1(
22
)0(
1
)0(
13
)0(
132
)0(
121
)0(
11
332211
22323222121
11313212111
n
nn
n
nn
nn
nn
nnnnnnn
nn
nn
bxa
bxaxaxa
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa







Back Substitution
121for
)1(
1
)1()1(
)1(
)1(
,,nni
a
xab
x
a
b
x
i
ii
n
ij j
i
ij
i
i
in
nn
n
n
n 
Após a redução em um sistema triangular tem-se:
)1()1(
)2(
1
)2(
,11
)2(
1,1
)1(
2
)1(
23
)1(
232
)1(
22
)0(
1
)0(
13
)0(
132
)0(
121
)0(
11
n
nn
n
nn
n
nn
n
nnn
n
nn
nn
nn
bxa
bxaxa
bxaxaxa
bxaxaxaxa



Resolvemos de forma direta:.
Pseudocódigo para
Forward Elimination
for k = 1 to n-1
for i = k+1 to n
factor = aik / akk
for j = k+1 to n
aij = aij – factor * akj 
bi = bi – factor * bk
m21 = a21 / a11
1212
'
2 bmbb
132123
'
23
122122
'
22
amaa
amaa
Pseudocódigo para
Back Substitution
xn = bn / ann
for i = n-1 downto 1
sum = 0
for j = i+1 to n
sum = sum + aij * xj
xi = (bi – sum) / aii
121for
)1(
1
)1()1(
,,nni
a
xab
x
i
ii
n
ij j
i
ij
i
i
i 
)1(
)1(
n
nn
n
n
n
a
b
x
Figure 4-19
Complexidade
A quantidade de operações de adição, subtração,
multiplicação e divisão no pior caso
for k = 1 to n-1
for i = k+1 to n
factor = aik / akk
for j = k+1 to n
aij = aij – factor * akj
bi = bi – factor * bk
Passo k aik / akk aij – factor * akj bi – factor * bk
* and / + and - * and / + and - * and /
1 (n-1) (n-1)2 (n-1)2 (n-1) (n-1)
2 (n-2) (n-2)2 (n-2)2 (n-2) (n-2)
… … … … … …
n-2 2 22 22 2 2
n-1 1 12 12 1 1
Total n(n-1)/2 n(n-1)(2n-1)/6 n(n-1)(2n-1)/6 n(n-1)/2 n(n-1)/2
Complexidade (Forward Elimination)
6
)12)(1(
2
)1(
1
2
1
ppp
j
pp
j
p
j
p
j
Note:
Complexidade (Back Substitution)
+ - * /
xn 0 0 0 1
xn-1 (i=n-1) 1 1 1 1
… … … …
x2 (i=2) (n-1) 1 n-1 1
x1 (i=1) n 1 n 1
Total n(n-1)/2 n-1 n(n-1)/2 n
xn = bn / ann
for i = n-1 downto 1
sum = 0
for j = i+1 to n
sum = sum + aij * xj
xi = (bi – sum) / aii
Complexidade
• Adição / Substração
3
onSubstitutiBack
1
2
)2(
neliminatioForward
6
)12)(1(
2
)2( 3n
n
nnnnnnn
    
• Multiplicação / Divisão
33
)13(
onSubstitutiBack
2
)2(
neliminatioForward2
)2(
2
)2(
6
)12)(1(
32 nnnn
n
nnnnnnnnn
  
Complexidade
• Complexidade – O(n3)
• Para n grande, o número de operações é da 
ordem de n3.