Métodos de Resolução de Sistemas Lineares

Prévia do material em texto

Vimos que dado o SELA: 
 
a x a x a x b
a x a x a x b
a x a x a x b
n n
n n
n1 n nn n n
11 1 12 2 1 1
21 1 22 2 2 2
1 2 2
+ + + =
+ + + =
+ + + =
ì
í
ïï
î
ï
ï
...
...
...
...
 
 
 
 Pode-se resolver este Sistema pelo Método de Gauss- Jordan 
 
 
x 1
1( )k + = 1
11a
 ( )b a x a x a xk k n nk1 12 2 13 3 1- - - -( ) ( ) ( ). . . . . 
 
x ( )2 1 2 21 1 23 3 1( ) ( ) ( ) ( ). ....k k k n nkb a x a x a x+ = - - - - 1a 22 
 
x ( )nk
nn
n n
k
n
k
n n n
k
a
b a x a x a x( ) ( ) ( ) ( ).... .+ - -= - - - -
1
1 1 2 2 1 1 1
1
 
 
Dado CI para podermos resolve-lo, ie, dando 
)0(x uma 
aproximação inicial, calcularemos as aproximações 
 
)()2()1( ,....,, nxxx 
 
 cujo critério de convergência do método de Gauss- Jordan : 
 
 
 
 
 
 
Seja o sistema linear Ax=b e 
 
seja ak kj
j
n
kka a=
æ
è
çç
ö
ø
÷÷
=
å
1
/ Se a a= <max k 1 
 
então o método de Gauss-Jacobi gera uma sequência {x(k)} 
convergente para a solução do sistema dado, independentemente da 
escolha da aproximação inicial, x(0). 
 
Exemplo: 
 
ï
î
ï
í
ì
-=-++
=++
-=++
61032
3151
2210
321
321
321
xxx
xxx
xxx
 
 
 
13.0
10
12
1 á=
+
=a 
14.0
5
11
2 á=
+
=a 
12.0
10
32
3 á=
+
=a 
 
 
 
 
 
 
 
No caso do exemplo: 
 
Seja ï
î
ï
í
ì
-=++
=++
-=++
6860
3225
23
321
321
321
xxx
xxx
xxx
 
 
 
Note que o critério das linhas não é satisfeito pois 
14
1
13
1 ñ=
+
=a 
contudo o permutando a primeira equação com a segunda, teremos o 
sistema 
 
 
ï
î
ï
í
ì
-=++
-=++
=++
6860
23
3225
321
321
321
xxx
xxx
xxx
 
 
que é equivalente ao sistema original e a matriz deste novo sistema 
satisfaz o critério das linhas. E a convergencia é assegurada. 
 
 
 
 
 
 
 
 
Método Iterativo de Gauss Seidel: 
 
 
 
Da mesma forma que no método de Gauss Jacobi, no método 
de Gauss Seidel o sistema linear Ax=b é escrito na forma 
equivalente 
 
x 1
1( )k + = 1
11a
 ( ))(1)(313)(2121 ..... knnkk xaxaxab ---- 
 
x ( ))(1)(323)1(1212
22
)1(
2 .....a
1
 knn
kkk xaxaxab ----= ++ 
 
x ( ))1( 111)1(22)1(11)1( .....1 +--+++ ----= knnnknknn
nn
k
n xaxaxaba 
 
Ou seja neste método, no momento de se calcular j
kx )1( + , 
 
Usamos todos os valores ,1)1(
+kx ...., 1)1( -
+
j
kx que já foram 
calculados e os valores 1
)(
+j
kx , ..., nkx )( restantes 
 
 
 
 
O critério de Convergência, de SASSENFELD, pode ser 
apresentado como: 
 
Se Ax=b seja 
11
11312
1
....
a
aaa n+++=b
 e 
jj
njjjjjjjj
j a
aaaaa 1111221 ........ ++++++= +--
bbb
b
 
Seja ( )jnj bb ££= 1
max
 então 
 se 1áb o método de Gauss-Jacobi gera uma sequência {x(k)} 
convergente para a solução do sistema dado, independentemente da 
escolha da aproximação inicial, x(0). 
Além do mais quanto menor for b mais rápida vai sr as 
convergencia. 
Exeercicio: b= 
5.2
0.1
6.3
2.0
-
- A= 
12.03.01.0
2.012.01.0
1.02.012.0
1.01.05.01
--
--
-
 1áb 
 
No caso de A= 
301
110
312
- b=
3
1
9
 12 >=b 
 
Trocando a primeira equação pela terceira temos 
1
3
2
á=¢b
 entao vale o critério de Sanseenfeld e temos 
convergencia 
 
 
Fatoração LU 
 
Seja o sistema linear A.x = b, o processo de fatoração para 
resolução deste sistema consiste em decompor a matriz A dos 
coeficientes em um produto de 2 ou mais fatores, e em seguida, 
resolver uma seqüência de sistemas lineares que nos conduzirá a 
solução do sistema linear original. 
 
Por exemplo, se pudermos fazer a fatoração 
 
 A = C.D ® A.x = C.D.x = b ® C.(D.x) = b. 
 
 Se y = D.x então 
 
resolver o sistema linear A.x = b 
 
é resolver o sistema linear 
 
 C.y = b e, em seguida, 
 
 o sistema linear D.x = y, 
 
o que resultará na solução do sistema linear original. 
 
A fatoração LU é um dos processos de fatoração mais utilizados. 
 
L: triangular inferior com diagonal unitária 
 
U: triangular superior 
 
 
 
 Nas proxima aulas, discutiremos os oblemas relativo Cálculo 
dos Fatores LU