Aula 03 e 04 Sistema de Equacoes Lineares

Prévia do material em texto

1
Métodos Diretos
1. Eliminação Gaussiana
a. Eliminação Gaussiana “Ingênua”;
b. Estratégias de pivoteamento;
c. Normas;
d. Resíduos.
2
Dificuldades dos Métodos de Eliminação
• Divisão por zero
– Quando o coeficiente do pivo é zero ou próximo de zero. Exemplo:
• Erros de arredondamento
– Os erros de arredondamento se propagam significativamente
quando calculamos a solução de um sistema de grande porte.
• Sistema mal condicionado
– Quando o determinante esta próximo de zero 
– ||A||||A-1|| >>1
562
3764
83
321
321
32
=++
−=++
=+
xxx
xxx
xx
3
(a) Singular ( não tem solução)
(b) Singular (infinitas soluções)
(c) Sistemas mal condicionados (próximos a singularidade)
Causas das dificuldades
4
Sistema Mal Condicionado
Quando existe uma pequena variação nos
coeficientes dos sistema
– Sistema bem condicionado – Resulta de forma similar 
em pequena variação na solução.
– Sistema mal condicionado – Resulta em uma grande
variação na solução.
4.1021.1
102
21
21
=+
=+
xx
xx
3
4
)1.1(2)2(1
)10(1.1)4.10(1
2
)1.1(2)2(1
)4.10(2)10(2
1
==
==
−
−
−
−
x
x
Um exemplo de mal condionamento e sua solução
5
Sistema mal condicionado
)change5%aboutonly(4.108.10)1(2)8(1.1
4.10)1(2)8(05.1
10)1(2)8(
≅=+
=+
=+
Se trocarmos o coeficiente a21 de 1.1 to 1.05, tem-se
4.10205.1
102
21
21
=+
=+
xx
xx
1
8
)05.1(2)2(1
)10(1.1)4.10(1
2
)05.1(2)2(1
)4.10(2)10(2
1
==
==
−
−
−
−
x
x
Substituindo-se em ambas as equações tem-se:
A troca de 5% em um dos coeficientes resulta em uma grande troca na
solução. Entretanto quando substituimos nas equações somos incapazes
de observar este grande desvio.
6
Estratégias de Pivoteamento
• Chamamos estratégia de Pivoteamento à troca de linha
e/ou coluna de modo que o pivô seja o maior elemento
da coluna que estamos eliminando.
• Na Eliminação Gaussiana, se o coeficiente do pivô akk(k) = 0
para algum k, o método não segue adiante.
7
Estratégias de Pivoteamento
• Pivoteamento parcial
–Troca somente das linhas
–Escolha r, o menor indice para o qual
i.e. escolha o maior coeficiente na coluna para torna-se 
o coeficiente pivô.
–Troca-se as linhas k e r
nikaa kik
k
rk ≤≤= )()( max
8
Exemplo
• Considere um sistema de equações em uma da iteração:
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
−−
−
=
150420
77530
63010
51123
b
A
)1(
)1(
3aamax )1(32
)1(
2j4,3,2j
==
=
• Escolher o pivô;
→ pivô = 3 
• Trocar as linhas 2 e 3
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
−−
−
=
150420
63010
77530
51123
b
A
)1(
)1(
9
Estratégias de Pivoteamento
• Pivoteamento parcial com escala
– Escolhe-se para pivô o elemento aij com 
maior índice dado por:
a
a a
ki
k knmax , ,1 "m r
O denominador é o máximo absoluto da linha candidata.
Exemplo: Ver notas de aulas
10
Considere o seguinte sistema linear
− + =
− + =
− =
R
S|
T|
1 2 1
1 1
2 1 1
.414214
.414214
.414214
x y
x y z
y z
Cuja solução é w = [1.707107..., 1.707107..., 1.707107...]T . 
Verifique da necessidade de usar uma técnica de escolha do pivô
quando resolve o sistema por eliminação Gaussiana.
Aplicação das Estratégias de Pivoteamento
11
Escreve a matriz ampliada resultante da aplicação da primeira 
operação linear:
−
−
−
L
N
MMM
O
Q
PPP
→
′= −
1 2 0 1
1 1 1 1
0 2 1 1 2 2 11 1
1
.414214
.414214
.414214 L L a L
→
−
−
−
L
N
MMM
O
Q
PPP
−
1 2 0 1
0 10 1 1707107
0 2 1 1
6
.414214
.
.414214
Porque razão será aconselhável usar uma técnica de escolha do 
pivô ?
O próximo pivô a usar (a22) é um valor muito próximo de zero e dada 
a limitada capacidade de representação numérica das máquinas 
poderá provocar grandes erros relativos na solução final.
12
Descreve técnicas de pivoteamento:
Pivoteamento parcial: escolhe-se para pivô o elemento aij
mais afastado de zero .
No exemplo, escolhe-se a linha 2, 3 ou 4 com o 
melhor pivô segundo um critério que minimize
os erros numéricos.
As duas seguintes técnicas usam a troca de linhas 
(apenas entre as linhas que faltam triangularizar):
a a a a
a
a
a
11 12 13 14
22
32
42
0
0
0
" "
" "
" "
L
N
MMMM
O
Q
PPPP
Qual será o pivot ?
Critérios de escolha do pivô:
Pivoteamento parcial com escala: escolhe-se para pivô
o elemento aij com maior índice dado por:
a
a a
ki
k knmax , ,1 "m r
(O denominador é o máximo 
absoluto da linha candidata.)
13
−
−
−
L
N
MMM
O
Q
PPP
→−
1 2 0 1
0 10 1 1707107
0 2 1 1
6
.414214
.
.414214
Escolhendo o pivoteamento parcial, termina o método
de eliminação de Gauss:
Trocando as linhas 2 e 3.
L L2 3
6
1 2 0 1
0 2 1 1
0 10 1 1707107
↔⎯ →⎯⎯⎯
−
−
−
L
N
MMM
O
Q
PPP−
.414214
.414214
.
′ = −− −
⎯ →⎯⎯⎯⎯⎯
−
−
L
N
MMM
O
Q
PPPL L L3 3
10
2
6
2
1 2 0 1
0 2 1 1
0 0 0 9999993 1707108
.414214
.414214
. .
x
x
x
1
2
3
2 060663
1957109
1707108
=
=
=
R
S|
T|
.
.
.
Esta solução aproximada é, relativamente,
próxima da exata porque se aplicou o
pivoteamento parcial. Experimenta agora,
sem pivoteamento.
14
Estratégias de Pivoteamento (continuação)
• Pivoteamento Completo
– Troca-se ambas linhas e colunas em busca do 
melhor elemento para pivô.
– Escolha de r e s, os menores inteiros para
isto é, a escolha do maior coeficiente na sub-
matrix para torna-se o coeficiente pivô.
– Troca-se as linhas k e r, e colunas k e s.
njikaa kij
k
rs ≤≤= ,max )()(
15
Estratégias de Pivoteamento (continuação)
• Pivoteamento Completo
k j i, ,a )1k(ij ≥∀−
uma extensa comparação entre os elementos e a troca de 
linhas e colunas.
O pivoteamento completo não é empregado, pois envolve 
16
Singularidade
• Consideremos x1 + x2 + x3 = 4
2x1 – x2 – x3 = 7
x1 – 2x2 – 2x3 = 12
x1 + x2 + x3 = 4
– 3x2 – 3x3 = -1
– 3x2 – 3x3 = 8
x1 + x2 + x3 = 4
– 3x2 – 3x3 = -1
0x3 = 9
Observamos a singularidade durante o processo de eliminação
17
Normas
Descreva as normas de vetores ||.||1, ||.||2 e ||.||∞ :
x xi
i
n
1
1
=
=
∑ x xi
i
n
2
2
1
=
=
∑ b g x xi n i∞ ≤ ≤= max1 m r
x T= −1 1 3 x ∞ = − =max{ , , }1 1 3 3
18
Normas
A a
j n iji
n
1 1 1
= RST
UVW≤ ≤ =∑max
Máximo das somas do valor 
absoluto por colunas.
A a
i n ijj
n
∞ ≤ ≤ =
= RST
UVW∑max1 1
Máximo das somas do valor 
absoluto por linhas.
Descreva as normas matriciais ||.||1, e ||.||∞:
Calcule a norma infinito da matriz A:
A− =
L
N
MMM
O
Q
PPP
1
-7 / 69 16 / 69 2 / 23
-2 / 23 -2 / 23 5 / 23
22 / 69 -1 / 69 -3 / 23
Sendo
a i
i
1
1
3
22 69
=
∑ = + + =-7 / 69 16 / 69 2 / 23 /
a i
i
2
1
3
9 23
=
∑ = + + =-2 / 23 -2 / 23 5 / 23 /
a i
i
3
1
3
32 69
=
∑ = + + =22 / 69 -1 / 69 -3 / 23 /
A ∞ = =max{ }, ,2269
9
23
32
69
32
69
Resposta:
19
Normas
A a
j n iji
n
1 1 1
= RST
UVW≤ ≤ =∑max
Máximo das somas do valor 
absoluto por colunas.
A a
i n ijj
n
∞ ≤ ≤ =
= RST
UVW∑max1 1
Máximo das somas do valor 
absoluto por linhas.
Descreva as normas matriciais ||.||1, e ||.||∞:
A b= −
L
N
MMM
O
Q
PPP
=
L
N
MMM
O
Q
PPP
1 2 4
4 1 1
2 5 2
11
8
3
Cálculo da norma de A:
Logo ||A|| = 9 
20
Aplicação das Normas
A definição de número de condição ou condicionamento
de uma matriz A é:
cond = A A-1A
cond = A A-1A ∞ ∞× ≈ 4.
O número de condição indica, em termos relativos,se
uma matriz é mal ou bem condicionada. 
21
Aplicação:
Considere o sistema linear A x = b, onde:
A b= −
L
N
MMM
O
Q
PPP
=
L
N
MMM
O
Q
PPP
1 2 4
4 1 1
2 5 2
11
8
3
cuja solução é: x T= −1 1 3
b b− ≤∞ −10 3
Calcule um majorante do erro relativo (em norma) da 
respectiva solução
Admita que o segundo membro do sistema é
substituído por tal que:
x.
b
22
Qual é a definição de erro relativo em x ?
r x x
xx
= −
A b A b
x
A b b
x
− − −− = −
1 1 1c h
Escreva o erro relativo para usando, indirectamente, A x = b:
r x x
xx
= − =
r
A b b
xx
= − ≤
−1c h
Construa um majorante para o erro relativo conhecendo:
A b b
x
− × − ≤
1
Propriedade 
das normas b b− ≤∞ −10 3
A
x
−
−
1
310
23
r
A
xx
≤
−
−
1
310Relembrando que:
Calcule a norma ||.||∞ do vetor x:
x T= −1 1 3 x ∞ = − =max{ , , }1 1 3 3
a i
i
1
1
3
22 69
=
∑ = + + =-7 / 69 16 / 69 2 / 23 /
a i
i
2
1
3
9 23
=
∑ = + + =-2 / 23 -2 / 23 5 / 23 /
a i
i
3
1
3
32 69
=
∑ = + + =22 / 69 -1 / 69 -3 / 23 / (continua...)
A ∞ = =max{ }, ,2269
9
23
32
69
32
69
Resposta:
Calcule a norma infinito da matriz inversa A-1:
A− =
L
N
MMM
O
Q
PPP
1
-7 / 69 16 / 69 2 / 23
-2 / 23 -2 / 23 5 / 23
22 / 69 -1 / 69 -3 / 23
Sendo
24
Qual é a conclusão sobre o erro relativo ?
r
A
xx
≤ = × ≈
−
− −
1
3 310 32 69
3
10 0 00015/ .
Uma pequena variação relativa nos elementos do vector b, com ||b||=11, 
conduziu a uma pequena variação relativa em x (percentagem de erro de 0.015%) !
cond = A A-1A
cond = A A-1A ∞ ∞× ≈ 4.
Qual é a definição de número de condição de uma matriz A ?
Determine o número de condição da matriz A ?
25
Que acontece ao erro relativo, rx, se o número de
condição aumenta ?
Quanto maior for cond A, pior condicionado 
o problema é: o erro relativo rx aumenta face 
ao aumento do número de condição. 
r A r r
b b
bx b b
≤ × = −cond com ,
Observe a seguinte desigualdade:
26
Pseudocode for Gauss Elimination with Partial Pivoting
// Assume arrays start with index 1 instead of 0.
// a: Coef. of matrix A; 2-D array
// b: Coef. of vector b; 1-D array
// n: Dimension of the system of equations
// x: Coef. of vector x (to store the solution)
// tol: Tolerance; smallest possible scaled pivot allowed.
// er: Pass back -1 if matrix is singular. (Reference var.) 
Gauss(a, b, n, x, tol, er) {
Declare s[n] // as an n-element array for storing scaling factors
// si = the largest coef. of row i.
for i = 1 to n
si = abs(ai,1)
for j = 2 to n 
if (abs(ai,j) > si)
si = abs(ai,j)
Eliminate(a, s, n, b, tol, er) // Forward Elimination
if (isSingular)
Substitute(a, n, b, x) // Back Substitution
}
27
Pseudocode for Gauss Elimination with Partial Pivoting
// Partial Pivoting
Pivot(a, b, s, n, k) {
p = k // Assume row k is the pivot row
// Find the largest scaled coefficient in column k
big = abs(ak,k / sk)
for i = k+1 to n {
dummy = abs(ai,k / si)
if (dummy > big) {
big = dummy
p = i // Record new pivoting row
}
}
// Next: Swap row p and row k if p != k
// Continue next page
28
Pseudocode for Gauss Elimination with Partial Pivoting
if (p != k) {
// Swap row p and row k
for j = k to n {
dummy = ap,j
ap,j = ak,j
ak,j = dummy
}
// swap bp and bk
dummy = bp
bp = bk
bk = dummy
// swap sp and sk
dummy = sp
sp = bk
sk = dummy
}
}
29
Pseudocode for Gauss Elimination with Partial Pivoting
Eliminate(a, b, n, x, tol, er) {
for k = 1 to n-1 {
Pivot(a, b, s, n, k) // Partial Pivoting
if (abs(ak,k/sk) < tol) { // Check for singularity
er = -1;
return;
}
for i = k+1 to n
factor = ai,k / ak,k
for j = k+1 to n
ai,j = ai,j – factor * ak,j
bi = bi – factor * bk
}
if (abs(an,n/sn) < tol) // Check for singularity
er = -1;
}
Forward 
Elimination
30
Pseudocode for Gauss Elimination with Partial Pivoting
// Backward Subsitution
Substitute(a, n, b, x) {
xn = bn / an,n
for i = n-1 downto 1 {
sum = 0
for j = i+1 to n
sum = sum + ai,j * xj;
xi = (bi – sum) / ai,i
}
}
	Métodos Diretos
	Dificuldades dos Métodos de Eliminação
	Causas das dificuldades
	Sistema Mal Condicionado
	Sistema mal condicionado
	Estratégias de Pivoteamento
	Estratégias de Pivoteamento
	Exemplo
	Estratégias de Pivoteamento
	Estratégias de Pivoteamento (continuação)
	Estratégias de Pivoteamento (continuação)
	Singularidade
	Normas
	Normas
	Normas
	Aplicação das Normas
	Pseudocode for Gauss Elimination with Partial Pivoting
	Pseudocode for Gauss Elimination with Partial Pivoting
	Pseudocode for Gauss Elimination with Partial Pivoting
	Pseudocode for Gauss Elimination with Partial Pivoting
	Pseudocode for Gauss Elimination with Partial Pivoting