Matriz em banda
A = X
X

X

0
X

X
0

0
0

0
0

 0
X
X
X
X
0
0
0
0
0
0
X
0
X
0
0
0
0
0
0
0
X
X
X
X
X
X
0
0
0
0
X
X
X
X
0
X
0
0
0
0
0
X
X
X
X
X
X
X
0
0
0
X
X
0
X
X
0
X
X
0
X
0
X
0
X
X
X
0
X
0
X
X
X
X
X
X
X
X
X
0
0
0
X
X
X
X
X
X
0
X
0
0
0
0
0
X
X
0
X
X
0
0
0
0
0
X
X
X
X
X
0
0
0
0
0
X
0
X
X
X
0
0

0

0
0

0
0

0
X

X
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 + 1
ou seja, largura de banda é o numero total de diagonais não nulas
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss – escolha de Pivot
Resolva pelo método de Gauss o sistema de equações
4
0

0

0
1 −3
0
2
1
0   x1  2 
1 −1  x2  0 
 =  
2 4   x3  4 

0 1  x4  0 
i) Condensação
A(1)⏐b(1) = A(2)⏐b(2) =  4
0

m32 = 2 0 ?  0

m42 = 1 0 ?  0
A(2)⏐b(2) =  4
0

0

m42 = 1 2  0
1 −3
0
2
1
0 2
1 −1 0 
2 4 4

0 1 0
1 −3
2
0
1
0 2
2 4 4 
1 −1 0 

0 1 0
Troca de linhas
(ou seja de equações)
para que o pivot
não seja nulo
A(2)⏐b(2) =  4
0

0

0
A(3)⏐b(3) =  4
0

0

0
1 −3
2
0
1
0 2
2 4 4 
1 −1 0 

0 1 0
1 −3
2
2 2 4 4 
0 1 −1 0 

0 −1 −1 −2 
0
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss – escolha de Pivot
A(3)⏐b(3) =  4
0

0

m43 = −1 1  0
1 −3
2
2 2 4 4 
0 1 −1 0 

0 −1 −1 −2 
0
A(4)⏐b(4) =  4
0

0

0
1 −3
2
0
0
2
2 4 4 
1 −1 0 

0 −2 −2 
0
ii) Substituição ascendente
4
0

0

0
1 −3
−2 ⋅ x4 = −2  x4 = 1
2
0
x3 − x 4 = 0  x3 = x 4 = 1
0
0   x1   2
2 4   x2   4 
 =  
1 −1  x3   0 

0 −2  x4  −2
4 − (2 ⋅ x3 + 4 ⋅ x4 )
= −1
2
2 − ( x2 − 3 ⋅ x 3 ) 3
=
4 ⋅ x1 + x2 − 3 ⋅ x3 = 2  x1 =
4
2
2 ⋅ x2 + 2 ⋅ x 3 + 4 ⋅ x 4 = 4  x2 =
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
Considere o sistema de equações
 0.0003 1.246   x1  1.249 
0.4370 −2.402   x  = 1.968 

 2 

Nota:
solução exacta,
x1=10, x2=1
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)
b) Resolva agora efectuando escolha de pivot (na mesma com uma mantissa com 4 dígitos)
a)
i) Condensação
A(1)⏐b(1) =  0.0003 1.246 1.249 


m21  0.4370 −2.402 1.968 
m21 =
A(2)⏐b(2) =  0.0003 1.246 1.249 
 0
(2)
a22
b2(2) 

0.4370
= 1456.6(6) → m21 = 1457
0.0003
(2)
(1)
(1)
a22
= a22
− m21 × a12
= −2.402 − 1457 × 1.246 = −2.402 − 1815. 422 = −2.402 − 1815 = −1817. 402
b2(2) = b2(1) − m21 × b1(1) = 1.968 − 1457 × 1.249 = 1.968 − 1819.793 = 1.968 − 1820 = −1818. 032
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss – importância da escolha de Pivot
A(2)⏐b(2) =  0.0003 1.246 1.249 
 0
−1817 −1818 

ii) Substituição ascendente
0.0003 1.246   x1   1.249 
 =

 0

1817
1818
−
−
x

 2 

x2 =
−1817
= 1.00065 → x2 = 1.001
−1818
0.0003 ⋅ x1 + 1.246 ⋅ x2 = 1.249  x1 =
1.249 − 1.246 ⋅ x2
0.0003
x1 =
=
1.249 − 1.246 × 1.001
0.0003
1.249 − 1.247 246
0.02
= 6.666(6) = 6.667
=
0.0003
0.0003
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.
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss – importância da escolha de Pivot
b) Uma forma de minimizar os problemas numéricos é efectuar escolha de pivot
i) Condensação
A ⏐b =  0.0003 1.246 1.249 
 0.4370 −2.402 1.968 


(1)
(1)
Troca de linhas
(ou seja de equações)
para que o pivot
tenha maior
valor absoluto
A(1)⏐b(1) =  0.4370 −2.402 1.968 


m21  0.0003 1.246 1.249 
m21 =
A(1)⏐b(1) =  0.4370 −2.402 1.968 
 0.0003 1.246 1.249 


A(2)⏐b(2) =  0.4370 −2.402 1.968 
 0
a2(2)2
b2(2) 

0.0003
= 6.8649886 × 10 −4 → m21 = 6.865 × 10 −4
0.4370
(2)
(1)
(1)
a22
= a22
− m21 × a12
= 1.246 − 6.865 × 10 −4 × −2.402 = 1.246 + 0.001648973 = 1.246 + 0.001649
= 1.247649 = 1.248
b2(2) = b2(1) − m21 × b1(1) = 1.249 − 6.865 × 10 −4 × 1.968 = 1.249 − 0.001351 032 = 1.249 − 0.001351
= 1.247649 = 1.248
Matemática Computacional, MEMec, LEAN, MEAer
Método de Gauss – importância da escolha de Pivot
A(2)⏐b(2) =  0.4370 −2.402 1.968 
 0
1.248 1.248 

ii) Substituição ascendente
0.4370 −2.402   x1  1.968 
 =

 0

1.248
x
1.248

 2 

x2 =
1.248
= 1 → x2 = 1.000
1.248
0.4370 ⋅ x1 − 2.402 ⋅ x2 = 1.968  x1 =
x1 =
1.968 + 2.402 ⋅ x2
1.968 + 2.402 × 1.000
=
0.4370
0.4370
1.968 + 2.402
0.4370
=
4.370
0.4370
= 10
A solução obtida é x1=10, x2=1, igual à solução exacta
Matemática Computacional, MEMec, LEAN, MEAer
Tipos de Pivot
Tipos de pivot: - pivot parcial
- pivot total
- pivot diagonal
(k )

a
1,
1
A =

 0
 

 0

 
 0

 
 0

 

 0
(k )






- pivot parcial com patamar
a1,(k )k −1
a1,(k )k  a1,(k )p  a1,(k )q  a1,(k )n 





 
ak(k−)1, k−1 ak(k−)1, k  ak(k−)1, p  ak(k−)1, q  ak(k−)1, n 

0
ak(k, )k  ak(k, )p  ak(k, )q  ak(k, )n 






 
0
ap(k, )k  ap(k,)p  ap(k, )q  ap(k,)n 






 
0
aq(k, )k  aq(k, )p  aq(k, )q  aq(k, )n 





 

0
an(k, )k  an(k, )p  an(k, )q  an(k, )n 
submatriz
activa
Os candidatos a pivot encontram-se na submatriz activa
Matemática Computacional, MEMec, LEAN, MEAer
Pivot parcial
A(k ) =  a1, 1

 0
 

 0

 
 0

 
 0

 

 0
(k )






a1,(k k) −1
a1,(k )k  a1,(k )p  a1,(k q)  a1,(k n) 





 
ak(k−)1, k −1 ak(k−)1, k  ak(k−)1, p  ak(k−)1, q  ak(k−)1, n 

0
ak(k, )k  ak(k, )p  ak(k, )q  ak(k, )n 






 
0
ap(k, )k  ap(k,)p  ap(k,)q  ap(k,)n 






 
0
aq(k, )k  aq(k, )p  aq(k, )q  aq(k, )n 





 

0
an(k, )k  an(k, )p  an(k, )q  an(k, )n 
linha k
linha p
coluna k
pivot parcial – os candidatos a pivot são os elementos da coluna k da submatriz activa
(k )
→ Escolher: max aik(k ) = apk
i≥k
→ Trocar linha p com linha k
Matemática Computacional, MEMec, LEAN, MEAer
Algoritmo pivot parcial
para k = 1 até n − 1
# para todas as colunas a condensar
 # 1. escolher pivot
 # inicialização
p = k
# linha pivot = k

 pivot = akk
 # escolha do elemento pivot
para i = k + 1 até n
# para todos as entradas abaixo de akk

se aik > pivot então



# linha pivot = k
p = i


 pivot = a

ik



 # troca de linhas
se p ≠ k então
# se p ≠ k , então trocar linha p com a linha k

# para todas as entradas não nulas das linhas a trocar
para j = k até n


aux = akj





akj = apj


apj = aux



 # 2. condensação

# para todas as linhas abaixo da linha k
para i = k + 1 até n
mik = aik / akk

# factor multiplicativo


para j = k + 1 até n
# para todos as entradas não nulas dessa linha


 aij = aij − mik akj



Matemática Computacional, MEMec, LEAN, MEAer
Pivot total
A(k ) =  a1, 1

 0
 

 0

 
 0

 
 0

 

 0
(k )






a1,(k k) −1
a1,(k )k  a1,(k )p  a1,(k q)  a1,(k n) 





 
ak(k−)1, k −1 ak(k−)1, k  ak(k−)1, p  ak(k−)1, q  ak(k−)1, n 

0
ak(k, )k  ak(k, )p  ak(k, )q  ak(k, )n 






 
0
ap(k, )k  ap(k,)p  ap(k,)q  ap(k,)n 






 
0
aq(k, )k  aq(k, )p  aq(k, )q  aq(k, )n 





 

0
an(k, )k  an(k, )p  an(k, )q  an(k, )n 
coluna k
linha k
linha p
coluna q
pivot total – os candidatos a pivot são todos os elementos da submatriz activa
(k )
→ Escolher: max aik(k ) = apq
i , j ≥k
→ Trocar linha p com linha k e trocar coluna q com coluna k
Matemática Computacional, MEMec, LEAN, MEAer
Pivot diagonal
A(k ) =  a1, 1

 0
 

 0

 
 0

 
 0

 

 0
(k )






a1,(k k) −1
a1,(k )k  a1,(k )p  a1,(k q)  a1,(k n) 





 
ak(k−)1, k −1 ak(k−)1, k  ak(k−)1, p  ak(k−)1, q  ak(k−)1, n 

0
ak(k, )k  ak(k, )p  ak(k, )q  ak(k, )n 






 
0
ap(k, )k  ap(k,)p  ap(k,)q  ap(k,)n 






 
0
aq(k, )k  aq(k, )p  aq(k, )q  aq(k, )n 





 

0
an(k, )k  an(k, )p  an(k, )q  an(k, )n 
coluna k
Com pivot diagonal, a
simetria duma matriz
simétrica é mantida
linha k
linha q
coluna q
pivot diagonal – os candidatos a pivot são os elementos da diagonal da submatriz activa
(k )
→ Escolher: max aii(k ) = aqq
i ≥k
→ Trocar linha q com linha k e trocar coluna q com coluna k
Matemática Computacional, MEMec, LEAN, MEAer
Pivot parcial com patamar
A(k ) =  a1, 1

 0
 

 0

 
 0

 
 0

 

 0
(k )






a1,(k k) −1
a1,(k )k  a1,(k )p  a1,(k q)  a1,(k n) 





 
ak(k−)1, k −1 ak(k−)1, k  ak(k−)1, p  ak(k−)1, q  ak(k−)1, n 

0
ak(k, )k  ak(k, )p  ak(k, )q  ak(k, )n 






 
0
ap(k, )k  ap(k,)p  ap(k,)q  ap(k,)n 






 
0
aq(k, )k  aq(k, )p  aq(k, )q  aq(k, )n 





 

0
an(k, )k  an(k, )p  an(k, )q  an(k, )n 
Com patamar, a
troca só é efectuada
se “valer a pena”,
i.e., se apk for
francamente
superior a akk
linha k
linha p
coluna k
pivot parcial – os candidatos a pivot são os elementos da coluna k da submatriz activa
(k )
→ Escolher: max aik(k ) = apk
i≥k
(k )
→ Trocar linha p com linha k se: τ apk
> akk(k )
, 0 ≤τ ≤ 1
τ é o valor
do patamar
Matemática Computacional, MEMec, LEAN, MEAer
Normas de matrizes
Normas de vectores
x 1 = x1 + x2 +  + xn
x 2 = ( x1 + x2 +  + xn
2
x
∞
2
norma 1
2
)
= max xi
2
norma Euclideana
norma do máximo (ou do infinito)
i = 1, , n
Normas de matrizes (mxn)
1

ai j

ai j
m
A 1 = max
1≤ j ≤n
i =1
n
A
∞
= max
1≤i ≤m
j =1

A F =


(
m
i =1
n
j =1

2
ai j 


)
1
2
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 = b

 A ⋅ x + A ⋅δ x = b + δ b
b = A⋅ x ≤ A ⋅ x
A ⋅δ x = δ b  δ x = A ⋅δ b 
−1

b
A
≤ x
 A⋅ x = b
 
A ⋅δ x = δ b
(*)
δ x = A−1 ⋅ δ b ≤ A−1 ⋅ δ b

δx
x
≤ A−1 ⋅
δb
x
Matemática Computacional, MEMec, LEAN, MEAer
Número de condição (de matrizes)
Tendo em atenção (*),
δx
x
≤ A−1 ⋅
δb
x
b
A
≤ A−1 ⋅
≤ x
δb
b
A

δx
−1
δb
≤ A⋅ A ⋅


 b
x

cond A
O 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ções
no segundo membro b.
δx
x
≤ cond A ⋅
δb
b
cond A = A ⋅ A−1
Um número de condição elevado indica que as perturbações do segundo membro são
ampliadas sobre a solução do sistema
(ii) Perturbações na matriz A (e consequentemente na solução)
Analogamente se demonstra que a relação entre as perturbações na solução x e as
perturbações da matriz A também dependem do número de condição da matriz
Matemática Computacional, MEMec, LEAN, MEAer
Efeito dos erros de arredondamento
Na resolução dum sistema (de dimensão n) em ponto flutuante, devido aos
arredondamentos, a factorização obtida não é exactamente igual à matriz original
L ⋅ U = A + E
↑
matriz
dos
erros
Pode demonstrar-se que os elementos da matriz erro são majorados por:
eij ≤ n ⋅ u ⋅ γ ⋅ α1
u - constante da ordem da unidade de arredondamento
α1 - maior elemento (em módulo) de Aij
γ - factor de crescimento dos coef. de A durante factorização
(i) Pivot parcial – em certos casos patológicos γ pode ser muito elevado podendo atingir o
valor máximo de 2n – 1. Contudo, estes casos patológicos são raros e na prática a factorização
com pivot parcial é em geral numericamente estável
(ii) Pivot total – o majorante de γ cresce lentamente (com o aumento da dimensão do
sistema) não se conhecendo casos para os quais seja superior a n. Logo a utilização de pivot
total é numericamente estável.
Matemática Computacional, MEMec, LEAN, MEAer
Efeito dos erros de arredondamento
Introduzindo o conceito de resíduo, r = b − A ⋅ x (de fácil cálculo após se obter x)
r = b − A ⋅ x = A ⋅ x − A ⋅ x = A ⋅ ( x − x ) = A ⋅ δ x
r = A ⋅δ x  δ x = A ⋅ r
−1
A⋅ x = b 
Atendendo a que
Então
Ou seja
δx
x
≤ A−1 ⋅
δx
x

r
x
δx

≤ cond A ⋅
x
r
b
δ x = A ⋅r
−1
A⋅ x ≥ b
≤ A−1 ⋅
r
b
A



δx ≤ A
x ≥
−1
⋅r

δx
x
≤ A
−1
r
⋅
x
b
A
δx
r
≤ A−1 ⋅ A ⋅


 b
x
cond A
onde o número de condição surge novamente
como factor de ampliação
Resumindo, o número de condição da matriz desempenha um papel fundamental nos erros
existente na solução do sistema de equações
Matemática Computacional, MEMec, LEAN, MEAer