Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Matemática Computacional, MEMec, LEAN, MEAer
Propriedades
11 12 13 14 11 12 13 14
31 32 33 34 31 32 33 34
41 4
21 22 23 24 21 22 23 24
21 22 23
2 43 44 41 42
24
43 44
0 0 00 0 00 00 0 0
11
11
a a a a a a a a
a a a a a a a aa a a a a a a
a a a a a a a aa a a am m m m
am
=
+ + + +
( ) 1 1 1AB B A− − −=
Exemplo: Adicionar à linha 3, a linha 2 multiplicada por um factor multiplicativo m
2) Inversa do produto
1) Combinação linear de linhas duma matriz – soma de uma linha com outra linhamultiplicada por um factor multiplicativo
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss(1) 1 1 1
1 1 22 1 1
A A= = −
(1) (1) (2)M A A=
21
31
12
1 1 1 1 1 1 1 1 1 1 11 1 1 2 1 1 1 2 2 10 1 2 1 1 0 1 2 1 1 1
0 0 0 00 00
10mm
⇔ = = − − −
− −
−−
−−
(2) (2) (3)M A A=
3212
00
1 1 1 11 1 1 1 1 1 10 1 2 10 1 2 1 2 1
30 1 1 1 1 10 1
0 00 00 0
0 0 00
20m
⇔ = = − − − − − − − − − −
ou seja (1)
(1) (1) (2) (2) (1) (3)
(2) (2) (3) M
A AM A A M M A AM A A
== ==
(3)M A A =
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss
M A U=
( )
32
1(2) 110 10 1
0 1
0 00
2
001
0
10m
M− =
A(3) é triangular superior, i.e., (3)
0
0 0
1 1 12 1
32
A U = = −
−
Então 1A M U− =
( ) 11 (2) (1)M M M−− = ( ) ( )1 1(1) (2)M M
− −=
( )21
( )
1
1
3
11 1
1 10 1
0 01
0 00 0
0 12mm
M−
= =
( ) ( )1 11 (1) (2)M M M− −− =
21 21
31 32 31 32
0 00 0 0 0 0 11 1 11
12
2
11 0 1 10 1 0 1 1 1
000 0 0m m
m m m m
= = =
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss
Então 1A M U A L U−= ⇔ =
21
31 32
1 1111
1
0 00 0
11
1
2
00
2
mm
L
m
M− = = =
Ou seja, através do método de Gauss podemos obter uma factorização A=LU.
Depois de se obter uma factorização A=LU (que requer um número de operações da ordemde n3) o sistema de equações é resolvido mediante uma substituição descendente seguidaduma substituição ascendente (que requerem um número de operações da ordem de n2)
M –1 é triangular inferior i.e.,
↑ ↑
⇔ = − − −
Matriz dos factores Matriz do final damultiplicativos factorização de Gauss
1 1 1 11 1 11 1 2 11 1 2
1 32 1 1 2 12
0 00 0
02
0
Matemática Computacional, MEMec, LEAN, MEAer
Factorização A=LU – Resolução do sistema
i) L y = b – substituição descendente
( ) ( )y
Ax b LU x b L Ux b= ⇔ = ⇔ =
1
2
3
1 1 1 41 1 2 42 1 1 5
xAx b x
x
= ⇔ − =
1 1 1 11 1 11 1 2 11 1 2
1 32 1 1 2 12
0
2
00 0
0 0A LU
− = ⇔ − = −
L y bU x y
= =
1
2
3
0 00
1 41 1 4
1 52 12
yL y b y
y
= ⇔ =
1
1 2 2 1
1 2 3 3 1 2
44 4 0
1 12 5 5 2 3
2 2
yy y y y
y y y y y y
=+ = = − =
+ + = = − − = −
{ }4 0 3 Ty = −
Matemática Computacional, MEMec, LEAN, MEAer
Factorização A=LU – Resolução do sistema
ii) U x = y – substituição ascendente
1
2
3
1 1 1 420
0
1 0
20
3 3
xU x y x
x
− = ⇔ = −−
3 3
32 3 2
1 2 3 1 2 3
33 2
2
2 0 12
4 4 1
x x
xx x x
x x x x x x
− = − =
−− + = = =−
+ + = = − − =
1Solução final, 1
2x
=
Matemática Computacional, MEMec, LEAN, MEAer
i) Factorização A = LDU, com L e U de diagonal unitária
iii) Por definição, uma matriz [A] diz-se definida positiva se { } { } { } [ ]{ }0 , 0Tx x A x∀ ≠ >
iv) Na factorização A = LDU, se a matriz A for simétrica definida positiva, prova-se que as entradas da diagonal de D são positivas, ou seja dii > 0
v) Neste caso, duma matriz simétrica definida positiva,
( ) ( )( ) ( )1/2 1/2 1/2 1/2 * * TT T TA L D L L D D L L D D L L L= = = =
onde L* é uma matriz de diagonal NÃO unitária
Nota: Para o caso duma matriz diagonal (mas apenas para este caso)
11
22
nn
ddD
d
=
11
1/2 22
nn
ddD
d
=
Factorização de Choleski – matrizes simétricas definidas positivas
ii) Se a matriz A for simétrica, então U=LT (ou L=UT), pelo que A = LDLT (ou A=UT DU)
Matemática Computacional, MEMec, LEAN, MEAer
vi) As entradas da matriz L* podem ser obtidas através das condições
( )11/2
2
1
1
1,
jj
j ij ij im jm jjjj jm
j mm
l a l l ll a l i j−
=
−
=
= − >
= −
( )11 11 11 21 31 41
21 22 21 22 22 32 42* *
31 32 33 31 32 33 33 43
14 42 43 44 41 42 43 44 44
0 0 00 0 0
0 0 00 0 0
T
a l l l l la a l l l l l
A L La a a l l l l la a a a l l l l l
= ⇔ =
( )( ) ( )
( ) ( ) ( )( ) ( ) ( ) ( )
=
= = +
= = + = + +
= = + = + + = + + +
211 11
2 221 21 11 22 21 22
2 2 231 31 11 32 31 21 32 22 33 31 32 33
22 2 241 41 11 42 41 21 42 22 43 41 31 42 32 43 33 44 41 42 43 44
a l
a l l a l l
a l l a l l l l a l l l
a l l a l l l l a l l l l l l a l l l l
ou seja
( )( )
[ ] ( ) ( )( )[ ] ( ) ( ) ( ) ( )( )
1/211 11
1/2221 21 11 22 22 21
1/22 231 31 11 32 32 31 21 22 33 33 31 32
1/222 241 41 11 42 42 41 21 22 43 43 41 31 42 32 33 44 44 41 42 43
l a
l a l l a l
l a l l a l l l l a l l
l a l l a l l l l a l l l l l l a l l l
=
= = −
= = − = − +
= = − = − + = − + +
Factorização de Choleski – matrizes simétricas definidas positivas
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss – escolha de Pivot
− − =
1
2
3
4
4 1 3 0 20 0 1 1 00 2 2 4 40 1 0 1 0
xxxx
Resolva pelo método de Gauss o sistema de equações
⏐ = ⏐ = −
=
=
−
(1) (1) (2) (2)
32
42
40 1 1 02 2 4 41 0
2 01 0
1 3 0 20001 0
A A
m
b
m
b
??
i) Condensação
Troca de linhas (ou seja de equações)
para que o pivot não seja nulo
⏐ = −
−
(2) (2)
2 2 4 40 1
4 1 3 0 2000
1 01 0 1 0
A b
=
⏐ =
−
−
(2) (2)
42
2 2 4 40 1 1 01 0 1 0
4 1 3 0 2
1
0002
A
m
b ⏐ = − − − −
−
(3) (3)
2 2 4 40 1
4 1 3 0 2000
1 00 1 1 2
A b
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss – escolha de Pivot
− ⏐ = − − − − = −43
(3) (3) 4 1 3 0 20 2 2 4 4
10 0 1 01 1 20 01 1
A
m
b − ⏐ = − − −
(4) (4) 4 1 3 0 20 2 2 4 40 0 1 1 00 0 0 2 2
A b
− ⋅ = − =4 42 2 1x x
ii) Substituição ascendente
−
= − − −
1
2
3
4
00 00 0
4 1 3 0 22 2 4 4
10
1 02 2
xxxx
− = = =3 4 3 40 1x x x x− ⋅ + ⋅⋅ + ⋅ + ⋅ = = = −3 4
2 3 4 24 (2 4 )
2 2 4 4 12
x xx x x x
− − ⋅⋅ + − ⋅ = = =2 31 2 3 1
2 ( 3 ) 34 3 2
4 2x xx x x x
Em aritmética em ponto flutuante, devido aos arredondamentos, em geral a escolha de pivot é vantajosa mesmo quando o pivot não é nulo
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss – importância da escolha de Pivot
b) Resolva agora efectuando escolha de pivot (na mesma com uma mantissa com 4 dígitos)
a) Resolva o sistema pelo método de Gauss utilizando uma mantissa com 4 dígitos, ou seja, simulando os cálculos em FP(10,4,2,A)
= −
1
2
0.0003 1.246 1.2490.4370 2.402 1.968
xx
⏐ = − 2
) (
1
(1 1) 0.0003 1.246 1.2490.4370 2.402 1.968
Am
b
Considere o sistema de equações
⏐ =
(2) (2)
(2) (2)
22 2
0.0003 1.246 1.2490 a b
A b
= − × = − − ×(2) (1) (1)22 22 21 12 2.402 1457 1.246a a m a = − −2.402 1815. 422 = −1817. 402
= − × = − ×(2) (1) (1)2 2 21 1 1.968 1457 1.249b b m b = −1.968 1819.793 = −1818. 032= −1.968 1820
= − −2.402 1815
Nota:solução exacta,x1=10, x2=1
i) Condensaçãoa)
= = → =21 210.4370
1456.6(6) 14570.0003
m m
Matemática Computacional, MEMec, LEAN, MEAer
⏐ = − −
(2) (2) 0.0003 1.246 1.2490 1817 1818
A b
−= = → =−2 2
18171.00065 1.001
1818x x
ii) Substituição ascendente
= − −
1
2
0.0003 1.246 1.2490 1817 1818
xx
− ⋅⋅ + ⋅ = = 21 2 1
1.249 1.2460.0003 1.246 1.249
0.0003xx x x − ×= 1.249 1.246 1.001
0.0003
−=11.249 1.247 246x
0.0003 = 0.020.0003
= 6.666(6)
A solução obtida é x1=6.667, x2=1.001, enquanto a solução exacta é x1=10, x2=1.
Comparando com a solução exacta verifica-se que o valor obtido para x1 possui 33% de erro.
= 6.667
Método de Gauss – importância da escolha de Pivot
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss – importância da escolha de Pivot
− ⏐ = 2
) )
1
(1 (1 0.4370 2.402 1.9680.0003 1.246 1.249
Am
b − ⏐ =
(2) (2)2
(2) (2)
2 2
0.4370 2.402 1.9680 a b
A b
− −= = × → = ×4 421 21
0.00036.8649886 10 6.865 10
0.4370m m
−= − × = − × × −(2) (1) (1) 422 22 21 12 1.246 6.865 10 2.402a a m a = +1.246 0.001648973
= 1.248
−= − × = − × ×(2) (1) (1) 42 2 21 1 1.249 6.865 10 1.968b b m b = −1.249 0.001351 032
= +1.246 0.001649
b) Uma forma de minimizar os problemas numéricos é efectuar escolha de pivot
⏐ = −
(1) (1) 0.0003 1.246 1.2490.4370 2.402 1.968
A b
i) Condensação
− ⏐ =
(1) (1) 0.4370 2.402 1.9680.0003 1.246 1.249
A b
Troca de linhas (ou seja de equações)
= 1.247649
= −1.249 0.001351
= 1.247649 = 1.248
para que o pivot tenha maior
valor absoluto
Matemática Computacional, MEMec, LEAN, MEAer
− ⏐ =
(2) (2) 0.4370 2.402 1.9680 1.248 1.248
A b
= = → =2 21.248
1 1.0001.248
x x
ii) Substituição ascendente
− =
1
2
0.4370 2.402 1.9680 1.248 1.248
xx
+ ⋅⋅ − ⋅ = = 21 2 1
1.968 2.4020.4370 2.402 1.968
0.4370xx x x + ×= 1.968 2.402 1.000
0.4370
+=11.968 2.402
0.4370x = 4.370
0.4370= 10
A solução obtida é x1=10, x2=1, igual à solução exacta
Método de Gauss – importância da escolha de Pivot
Matemática Computacional, MEMec, LEAN, MEAer
Tipos de Pivot
−
− − − − − −
=
( ) ( ) ( ) ( ) ( ) ( )( ) 1, 1 1, 1 1, 1, 1, 1,
( ) ( ) ( ) ( ) ( )1, 1 1, 1, 1, 1,
( ) ( ) ( ) ( ), , , ,
( ) ( ) ( ) ( ), , , ,
,
0
0 0
0 0
0 0
k k k k k kk k k p q n
k k k k kk k k k k p k q k n
k k k kk k k p k q k n
k k k kp k p p p q p n
q k
a a a a a aA
a a a a a
a a a a
a a a a
a
( ) ( ) ( ) ( ), , ,
( ) ( ) ( ) ( ), , , ,0 0
k k k kq p q q q n
k k k kn k n p n q n n
a a a
a a a a
Tipos de pivot: - pivot parcial- pivot total- pivot diagonal
- pivot parcial com patamar
submatrizactiva
Os candidatos a pivot encontram-se na submatriz activa
Matemática Computacional, MEMec, LEAN, MEAer
Pivot parcial( ) ( ) ( ) ( ) ( ) ( )( ) 1,1 1, 1 1, 1, 1, 1,
( ) ( ) ( ) ( ) ( )1, 1 1, 1, 1, 1,
( ) ( ) ( ) ( ), , , ,
( ) ( ) ( ) ( ), , , ,
,
0
0 0
0 0
0 0
k k k k k kk k k p q n
k k k k kk k k k k p k q k n
k k k kk k k p k q k n
k k k kp k p p p q p n
q k
a a a a a aA
a a a a a
a a a a
a a a a
a
−
− − − − − −
=
( ) ( ) ( ) ( ), , ,
( ) ( ) ( ) ( ), , , ,0 0
k k k kq p q q q n
k k k kn k n p n q n n
a a a
a a a a
pivot parcial – os candidatos a pivot são os elementos da coluna k da submatriz activa
( ) ( )Escolher: max k kik pki k
a a≥
→ =
Trocar linha com linha p k→
linha p
linha k
coluna k
Matemática Computacional, MEMec, LEAN, MEAer
Algoritmo pivot parcial
# inicialização# linha pi
para # para to
vot
# escolha do elemento pivot# para todos as entradas aba
1 até
ixo de
das as colunas a conde 1
para 1 até s
nsar
kk
kk
k n
p kpivot a
k
k n ai
=
= −
==
= +
# 1. escolher pivot
# linha pivot
# troca de linhas# se , então trocar linha com a
e então
se entãopara até
linha # para todas as entradas não nulas das linhas a trocar
ik
ik
a pivotp ipivot a
p
k
p k p kkj k n
>
= =
=
≠=
≠
# para todas as linhas abaixo da linha # factor multiplicativo
# pa
para 1 até /
para 1 a ra todos as entradas nté ão nulas dessa
kj
kj pj
pj
ik ik kk
aux aa aa aux
i k nm a a
j k n
k
= = =
= +=
= +
# 2. condensação
linha
ij ij ik kja a m a
= −
Matemática Computacional, MEMec, LEAN, MEAer
Pivot total( ) ( ) ( ) ( ) ( ) ( )( ) 1,1 1, 1 1, 1, 1, 1,
( ) ( ) ( ) ( ) ( )1, 1 1, 1, 1, 1,
( ) ( ) ( ) ( ), , , ,
( ) ( ) ( ) ( ), , , ,
,
0
0 0
0 0
0 0
k k k k k kk k k p q n
k k k k kk k k k k p k q k n
k k k kk k k p k q k n
k k k kp k p p p q p n
q k
a a a a a aA
a a a a a
a a a a
a a a a
a
−
− − − − − −
=
( ) ( ) ( ) ( ), , ,
( ) ( ) ( ) ( ), , , ,0 0
k k k kq p q q q n
k k k kn k n p n q n n
a a a
a a a a
pivot total – os candidatos a pivot são todos os elementos da submatriz activa
( ) ( )
,Escolher: max k k
ik pqi j ka a
≥→ =
Trocar linha com linha e trocar coluna com coluna p k q k→
linha p
linha k
coluna qcoluna k
Matemática Computacional, MEMec, LEAN, MEAer
Pivot diagonal( ) ( ) ( ) ( ) ( ) ( )( ) 1,1 1, 1 1, 1, 1, 1,
( ) ( ) ( ) ( ) ( )1, 1 1, 1, 1, 1,
( ) ( ) ( ) ( ), , , ,
( ) ( ) ( ) ( ), , , ,
,
0
0 0
0 0
0 0
k k k k k kk k k p q n
k k k k kk k k k k p k q k n
k k k kk k k p k q k n
k k k kp k p p p q p n
q k
a a a a a aA
a a a a a
a a a a
a a a a
a
−
− − − − − −
=
( ) ( ) ( ) ( ), , ,
( ) ( ) ( ) ( ), , , ,0 0
k k k kq p q q q n
k k k kn k n p n q n n
a a a
a a a a
pivot diagonal – os candidatos a pivot são os elementos da diagonal da submatriz activa
( ) ( )Escolher: max k kii qqi k
a a≥
→ =
Trocar linha com linha e trocar coluna com coluna q k q k→
linha q
linha k
coluna qcoluna k
Com pivot diagonal, a simetria duma matriz
simétrica é mantida
Matemática Computacional, MEMec, LEAN, MEAer
Pivot parcial com patamar( ) ( ) ( ) ( ) ( ) ( )( ) 1,1 1, 1 1, 1, 1, 1,
( ) ( ) ( ) ( ) ( )1, 1 1, 1, 1, 1,
( ) ( ) ( ) ( ), , , ,
( ) ( ) ( ) ( ), , , ,
,
0
0 0
0 0
0 0
k k k k k kk k k p q n
k k k k kk k k k k p k q k n
k k k kk k k p k q k n
k k k kp k p p p q p n
q k
a a a a a aA
a a a a a
a a a a
a a a a
a
−
− − − − − −
=
( ) ( ) ( ) ( ), , ,
( ) ( ) ( ) ( ), , , ,0 0
k k k kq p q q q n
k k k kn k n p n q n n
a a a
a a a a
pivot parcial – os candidatos a pivot são os elementos da coluna k da submatriz activa
( ) ( )Escolher: max k kik pki k
a a≥
→ =( ) ( )Trocar linha com linha se: , 0 1k kpk kkp k a aτ τ→ > ≤ ≤
linha p
linha k
coluna k
Com patamar, a troca só é efectuada
se “valer a pena”, i.e., se apk for francamente superior a akk
τ é o valor do patamar
Matemática Computacional, MEMec, LEAN, MEAer
Propriedades
1 0 0 00 1 0 00 0 1 00 0 0 1
I
=
(1) A troca de 2 linhas duma matriz A pode ser traduzida pela pré-multiplicação duma matriz de permutação elementar P(e)
(2) A matriz de permutação elementar P(e) pode ser obtida a partir da matriz identidade à qual é efectuada as correspondentes trocas de linhas
Ex: matriz 4x4, matriz elementar de troca das linhas 1 e 3
( )
0 0 00 1 0 0
0 0 01
1
1
0 0 0
eP
=
Linhas1234
3214
Ex: troca das linhas 1 e 3 duma matriz A (4x4)
11 12 13 14 31 32
21 22 23 24 21 22 23 24( )
31 32 33 34
41 42 43 44 41 42 43 44
11 12 1
3 34
3 1
3
4
0 0 00 1 0 0
0 0 00 0 0 11
1
P e
a a a aa a a a a a a a
A P Aa a a aa a a
a a aa
a a a
a
a
a a a a
= = =
Matemática Computacional, MEMec, LEAN, MEAer
Propriedades
(4) As matrizes de permutação elementar P(e) possuem as seguintes propriedades:
( ) ( )) e ei P P I⋅ = ( )( ) ( ))Te eii P P=
(3) A troca de 2 colunas duma matriz A pode ser traduzida pela pós-multiplicação duma matriz de permutação elementar P(e)
Ex: troca das colunas 2 e 3 duma matriz A (4x4)
11 12 13 14 11 14
21 22 23 24 21 24( )
31 3
13
23
2 33 34 31 34
41 42 43
12
22
3
44 41 44
33
43
2
42
1 0 0 00 0 00 0 0
0 11
1
0 0
P e
aa
a a a a a aa a a a a a
A A Pa a a a a
aa
aa a a a
aaaa aa
= = =
1 0 0 00 1 0 00 0 1 00 0 0 1
I
=
Ex: matriz 4x4, matriz elementar de troca das colunas 2 e 3
( )
1 0 0 00 0 00 0 0
1
11
0 0 0
eP
=
Colunas1 2 3 4
1 3 2 4
Matemática Computacional, MEMec, LEAN, MEAer
Propriedades
− = = − − −
−
−
21
3121( ) (1)
31
41 41
1 0 0 0 1 0 0 0 1 0 0 00 0 0 1 0 0 0
1 10
)0 0 0 0 1 0 0
1 10
0 0 0 1 0 0 1 0 0 1
e
mm
Mm
m
mi P
m
(5) Troca de 2 linhas duma matriz de factores multiplicativos
21(1)
31
41
1 0 0 01 0 00 1 00 0 1
mM
mm
− = − −
Ex: Seja
e considere-se a troca das linhas 2 e 3
Linhas1234
1324
=
( )
1 0 0 00 0 00 0 00 0 0 1
11
eP
Matemática Computacional, MEMec, LEAN, MEAer
Propriedades
− = −
−( ) (1) ( )
41
3
21
1
1 0 0 01 0 00 1 00 0 1
e e
mP
m
mM Pou seja
pelo que P(e)M(1)P(e) corresponde a trocar os factores multiplicativos das linhas 2 e 3
− = − −
21( ) (1) ( )
31
41
1 0 0 0 1 0 0 0 1 0 0 00 0 0 1 0 0
10 0 0
)0 0 0 0 1 0 0 0 00 0 0 1 0 0 1
11
0
1
0 0 1
e e mii P M P
mm
41
3
21 21
1 3
41
1
1 0 0 0 1 0 0 0 1 0 0 00 0 0 0 0 0 0
0 0 0 0 0 0 00 0 1 0 0 0
11
1 0 01
1
1 11m
mm
m
m
m
−
=
− −=
− −
−
Matemática Computacional, MEMec, LEAN, MEAer
Condensação de Gauss com pivot parcial
(1)
(1 ) (1) (1)
(2) (1) (1 ) (1) (1) (1)
P
P
A A
A P A
A M A M P A
=
=
= =
(1)
0 0 1 00 1 0 01 0 0 00 0 0 1
P =
Ex: Seja A uma matriz (4x4) e considere-se o processo decondensação de Gauss com troca das linhas 1 e 3 na primeirafase da condensação, troca das linhas 2 e 3 na segunda fase etroca das linhas 3 e 4 na terceira fase da condensação
Fase 1 – troca das linhas 1 e 3 seguida de condensação
Fase 2 – troca das linhas 2 e 3 seguida de condensação
(2) (1) (1) (1)
(2 ) (2) (2) (2) (1) (1) (1)
(3) (2) (2 ) (2) (2) (1) (1) (1)
P
P
A M P A
A P A P M P A
A M A M P M P A
=
= =
= =
(1) 21
31
41
1 0 0 01 0 00 1 00 0 1
mM mm
− = − −
(2)
1 0 0 00 0 1 00 1 0 00 0 0 1
P =
(2)
32
42
1 0 0 00 1 0 00 1 00 0 1
M mm
= − −
11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44
a a a aa a a aA a a a aa a a a
=
Matemática Computacional, MEMec, LEAN, MEAer
Condensação de Gauss com pivot parcialAtendendo a que P(2)P(2) = I, podemos reescrever A(3) na forma
(1) (2)
(21)Corresponde atrocar os factoresmultiplicativos de
devido a ,ou seja, a trocar os
coeficientes
(3) (2) (2) (1) (1) (1)
(
das linhas 2 e 3
3) (2) (2) (1) (1(2) (2) ) (1)
M P
P
A M P M P A
A M P M P PP A
==
Linhas1234
3214
3124
(21) (2) (1)
0 0 1 01 0 0 00 1 0 00 0 0 1
P P P = =
Fase 3 – troca das linhas 3 e 4 seguida de condensação
(3) (2) (2) (1) (2) (2) (1) (1)
(3 ) (3) (3) (3) (2) (2) (1) (2) (2) (1) (1)
(4) (3) (3 ) (3) (3) (2) (2) (1) (2) (2) (1) (1)
P
P
A M P M P P P A
A P A P M P M P P P A
A M A M P M P M P P P A
=
= =
= =
(3)
1 0 0 00 1 0 00 0 0 10 0 1 0
P =
(3)
43
1 0 0 00 1 0 00 0 1 00 0 1
Mm
= −
Matemática Computacional, MEMec, LEAN, MEAer
Condensação de Gauss com pivot parcialAtendendo a que P(3)P(3) = I, podemos reescrever A(4) na forma
Linhas1234
3214
3124
(321) (3) (2) (1)
0 0 1 01 0 0 00 0 0 10 1 0 0
P P P P = =
Ou seja, a partir do método de Gauss com pivot parcial, podemos obter uma factorizaçãoPA = LU, onde P é a matriz que considera todas as permutações efectuadas e L é a matrizdos factores multiplicativos tendo em consideração as trocas de linhas efectuadas àposteriori
(2) (3)
Corresponde atrocar os factoresmultiplicativos de
devido a ,ou sej
(4) (3) (3) (2) (2) (1) (2) (2) (
a, a trocar oscoeficientes das
linhas 3 e
1) (1)
(4) (3 (3)) (3) (2) (2) (1) (2)
4
(3
M P
A M P M P M P P P A
A M P P P M PPM
==
(1) (3)
(321)Corresponde atrocar os factoresmultiplicativos de
devido a ,ou seja, a trocar os
coeficientes das linhas
) (2(3) ) (1( ) (3
e 4
1) )
3
P
M P
P PP AP
3142
( )( ) ( )(321)
(4) (3) (3) (2) (3) (3) (2) (1) (2) (3) (3) (2) (1) (1)
P PM
A M P M P P P M P P P P P A
=
=
(4)A M P A =
1 (4)M A P A− = L U P A =
Matemática Computacional, MEMec, LEAN, MEAer
Normas de matrizesNormas de vectores
= + + +1 21 nx x x x
( )= + + +1
2 2 2 21 22 nx x x x norma Euclideana
∞ ==
1, ,max ii n
x x
norma 1
norma do máximo (ou do infinito)
Normas de matrizes (mxn)
≤ ≤=
= 1 11
maxm
i jj ni
A a
∞ ≤ ≤=
= 11
maxn
i ji mj
A a
( )= =
=
12
2
1 1
m n
i jF
i j
A a norma de Frobenius
Matemática Computacional, MEMec, LEAN, MEAer
Número de condição (de matrizes)Admitindo que existem perturbações nos valores da matriz A e do vector b, então resultam perturbações na solução do sistema x
[ ] { } { }⋅ = → ⋅ =A x b A x b ( ) ( )δ δ δ⋅ = ⇔ + ⋅ + = + A x b A A x x b b
(i) Admitir que apenas existem perturbações no 2º membro (e consequentemente na solução)
( )δ δ⋅ + = +A x x b b δ δ ⋅ + ⋅ = +A x A x b bδ δ⋅ =
⋅ =
A x bA x b
⋅ =A x b = ⋅ ≤ ⋅b A x A x ≤b
xA
(*)
δ δ δ δ−⋅ = = ⋅1A x b x A b δ δ δ− − = ⋅ ≤ ⋅1 1x A b A bδ δ− ≤ ⋅1x b
Ax x
Matemática Computacional, MEMec, LEAN, MEAer
Número de condição (de matrizes)
Tendo em atenção (*),
(ii) Perturbações na matriz A (e consequentemente na solução)
δ δ δ− −≤ ⋅ ≤ ⋅1 1x b bA A
bx xA
≤b
xA
δ δ− ≤ ⋅ ⋅
con
1
d A
x bA A
x bδ δ
≤ ⋅cond x b
Ax b
−= ⋅ 1cond A A AO número de condição duma matriz traduz, em termos relativos,a relação entre as perturbações na solução x e as perturbaçõesno segundo membro b.
Analogamente se demonstra que a relação entre as perturbações na solução x e asperturbações da matriz A também dependem do número de condição da matriz
Um número de condição elevado indica que as perturbações do segundo membro sãoampliadas sobre a solução do sistema
Matemática Computacional, MEMec, LEAN, MEAer
Efeito dos erros de arredondamento
(i) Pivot parcial – em certos casos patológicos γ pode ser muito elevado podendo atingir ovalor máximo de 2n – 1. Contudo, estes casos patológicos são raros e na prática a factorizaçãocom pivot parcial é em geral numericamente estável
Na resolução dum sistema (de dimensão n) em ponto flutuante, devido aosarredondamentos, a factorização obtida não é exactamente igual à matriz original
Pode demonstrar-se que os elementos da matriz erro são majorados por:
matrizdos
erros
L U A E↑
⋅ = +
1ije n u γ α≤ ⋅ ⋅ ⋅1
- constante da ordem da unidade de arredondamento - maior elemento (em módulo) de
- factor de crescimento dos coef. de durante factorizaçãoij
uAA
αγ
(ii) Pivot total – o majorante de γ cresce lentamente (com o aumento da dimensão dosistema) não se conhecendo casos para os quais seja superior a n. Logo a utilização de pivottotal é numericamente estável.
Matemática Computacional, MEMec, LEAN, MEAer
Efeito dos erros de arredondamentoIntroduzindo o conceito de resíduo,
Atendendo a que
r b A x= − ⋅
onde o número de condição surge novamentecomo factor de ampliação
( )r b A x A x A x A x x A xδ= − ⋅ = ⋅ − ⋅ = ⋅ − = ⋅
1r A x x A rδ δ −= ⋅ = ⋅ δ − = ⋅1x A r 1x A rδ − ≤ ⋅
(de fácil cálculo após se obter )x
1x rA
x xδ − ≤ ⋅
bA x b A x b x
A⋅ = ⋅ ≥ ≥
Então 1 1x r x rA A
bx x xA
δ δ− −≤ ⋅ ≤ ⋅δ − ≤ ⋅ ⋅
con
1
d A
x rA A
x b
δ≤ ⋅cond
x rA
x bOu seja
Resumindo, o número de condição da matriz desempenha um papel fundamental nos errosexistente na solução do sistema de equações
Matemática Computacional, MEMec, LEAN, MEAer
Matriz em banda0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 00 0 0 0 0
0 0 0 0 0 0 00 0 0 00 0 0 0 0
0 00 0 0 0 0 0 00 0 0 00 0 0 0 0 0 00 0 0 0 0 00 0 0 0 0 0 0
XX X
X XX X XX X X
X X X X XX X
X X X XXX X X X
X XX X X X
X X XX X X X
XX X X X X
X XX
XX
XX
XX
XX
XX
X
XX XX
X X XX
A
XXXX X X
=
largura de banda superior: número de diagonais não nulas, acima da diagonal principal
largura de banda inferior: número de diagonais não nulas, abaixo da diagonal principal
largura de banda = largura de banda superior + largura de banda inferior + 1ou seja, largura de banda é o numero total de diagonais não nulas