Embed Size (px)
Citation preview
Introdução aos Métodos Numéricos
Instituto de Computação UFFDepartamento de Ciência da Computação
Otton Teixeira da Silveira Filho
Conteúdo
● Erros e Aproximações Numéricas
● Sistemas de Equações Lineares. Métodos diretos
● Interpolação
● Ajuste de Curvas
● Zeros de Função
● Sistemas de Equações Lineares. Métodos Iterativos
● Integração Numérica
● Introdução à Resolução de Equações Diferenciais Ordinárias
Conteúdo
● Sistemas de Equações Lineares. Métodos diretos
Pivotamento
Pivotamento parcial e total
São procedimentos que podem diminuir o ruído numérico da eliminação gaussiana e da fatoração LU
Só será apresentado o caso da eliminação gaussiana
Pivotamento parcial
● Começando pela primeira coluna, ache o maior elemento em módulo desta coluna
● Troque a linha na qual está este valor como a primeira linha
● Faça a eliminação
Pivotamento parcial
● Ache o maior elemento em módulo da segunda coluna abaixo da primeira linha
● Troque a linha na qual está este valor como a segunda linha
● Faça a eliminação
Pivotamento parcial
● Ache o maior elemento em módulo da terceira coluna abaixo da segunda linha
● Troque a linha na qual está este valor como a terceira linha
● Faça a eliminação
Pivotamento parcial
Faça o equivalente para as demais colunas
Qual é a ideia por trás disto?
Pivotamento parcial
A maior fonte de ruído numérico é a divisão pelo pivô pois se o pivô for menor que o termo a ser eliminado teremos potencialmente um elevado ruído numérico
Ao escolhermos o maior em módulo da coluna a ser eliminada, reduzimos o ruído numérico
Não há garantia mas funciona bem em muitas situações
Pivotamento parcial
O custo computacional é basicamente o custo da busca do maior elemento em módulo.
Um exemplo do algoritmo para um vetor coluna da matriz
Pivotamento parcial
Seja o vetor de n elementos
● Afirmarmos que o primeiro elemento é o maior em módulo e o guardamos numa variável M, valor provisoriamente de máximo e em IM a linha deste máximo provisório.
● Se M < |v2| , façamos M=|v2| e IM = 2. Caso não, avançamos para o próximo elemento
● Se M < |v3|, faremos M=|v3|e IM = 3. Caso não, avançamos para o próximo elemento.
● Faremos isto até o último elemento
● Custo computacional por coluna: O(n), custo total O(n2)
v⃗
Pivotamento parcial
Façamos um exemplo para esclarecer a questão de acharmos o maior elemento de um vetor.
Dado o vetor
v⃗=(13
−428
)
Pivotamento parcial
● M = 1, IM = 1
● M <|3|, portanto M = 3, IM = 2
● M < |-4|, portanto M = 4, IM = 3
● M > |2|
● M < |8|, portanto M = 8, IM = 5. Obtivemos a posição do valor maior em módulo do vetor
v⃗=(13
−428
)
Pivotamento parcial
O exemplo que será apresentado é ilustrativo da técnica mas é, claramente, desnecessário (sob o ponto de vista numérico) fazer pivotamento deste sistema.
Pivotamento parcial
Comecemos com o sistema
Observe que o maior valor em módulo da primeira coluna está na segunda linha. Troquemos
(4 1 −2 16 2 1 23 −1 9 −11 4 2 −3
) x⃗= (49 /1247 /621 /435 /12
)
Pivotamento parcial
Primeiro pivotamento
Façamos a eliminação
(6 2 1 24 1 −2 13 −1 9 −11 4 2 −3
) x⃗= (47 /649 /1221 /435 /12
)
Pivotamento parcial
Primeiro pivotamento
que resulta em
(6 2 1 24 1 −2 13 −1 9 −11 4 2 −3
) x⃗= (47 /649 /1221 /435 /12
)m21=−a21 /a11=−4 /6=−2/3m31=−a31 /a11=−3 /6=−1/2m41=−a41 /a11=−1 /6
Pivotamento parcial
Primeiro pivotamento
O maior valor em módulo da segunda coluna abaixo da primeira linha está na quarta linha
(6 2 1 20 −1 /3 −8 /3 −1/30 −2 17 /2 −20 11/3 11/6 −10 /3
) x⃗=(47 /6
−41 /364 /3
29 /18)
Pivotamento parcial
Segundo pivotamento
Façamos a eliminação
(6 2 1 20 11/3 11/6 −10 /30 −2 17 /2 −20 −1 /3 −8 /3 −1/3
) x⃗=(47 /6
29 /184 /3
−41 /36)
Pivotamento parcial
Segundo pivotamento
que resulta em
(6 2 1 20 11/3 11/6 −10 /30 −2 17 /2 −20 −1 /3 −8 /3 −1/3
) x⃗=(47 /6
29 /184 /3
−41 /36)
m32=−−2
11 /3=6 /11
m42=−−1 /311/3
=1 /11
Pivotamento parcial
Segundo pivotamento
Observe que o maior valor em módulo da terceira coluna abaixo da segunda linha está na posição correta. Façamos a eliminação
(6 2 1 20 11/3 11/6 −10 /30 0 19 /2 −42/110 0 −5 /2 −7 /11
) x⃗=(47 /6
29 /1873 /33
−131/132)
Pivotamento parcial
Eliminação
que resulta em
(6 2 1 20 11/3 11/6 −10 /30 0 19 /2 −42/110 0 −5 /2 −7 /11
) x⃗=(47 /6
29 /1873 /33
−131/132) m43=−
−5 /219 /2
=5
19
Pivotamento parcial
Eliminação
que a resolução deste sistema triangular nos dará
(6 2 1 20 11/3 11/6 −10 /30 0 19/2 −42/110 0 0 −343 /209
) x⃗=(47 /6
29 /1873/33
−343 /836)
Pivotamento parcial
a solução
(6 2 1 20 11/3 11/6 −10 /30 0 19/2 −42/110 0 0 −343 /209
) x⃗=(47 /6
29 /1873/33
−343 /836)
x 4=−343836
×(−209343 )= 1
4x3=
219 ( 73
33+
4211
×14 )= 1
3 x2=311 ( 11
6×
13−
103
×14 )=1
2
x1=16 (47 /6−2×
12+
1×13
+2×14 )=1
Pivotamento parcial
Solução
x⃗=(1
1/21/31/4
)
Pivotamento total
A busca do maior valor da matriz agora é feita em toda matriz ou submatriz que ainda não passou pelo processo de eliminação
Isto exigirá:
● troca de linhas e de colunas
● um algoritmo que compute as mudanças de colunas
● Custo computacional por submatriz O(n2), total O(n3)
Pivotamento total
Pivotamento total
Devido à estas características (aumento de complexidade de algoritmo, aumento de custo computacional) este pivotamento é usado em situações especiais.
Não aprofundaremos o estudo sobre este item.
Casos especiais
Vimos algoritmos genéricos para a resolução de sistemas de equações lineares mas é comum termos sistemas com estruturas particulares que podem ser exploradas para conseguirmos maior eficiência
Casos especiais
Ilustraremos o uso inteligente destas estruturas usando um único exemplo com aplicação da eliminação gaussiana
Sistemas tridiagonais
Um sistema tridiagonal tem a estrutura
e há várias situações onde aparecem sistemas com esta simetria.
Observe que teremos que fazer uma única eliminação em cada coluna
(a1 b1 0 0 0 ⋯ 0 0 0c2 a2 b2 0 0 ⋯ 0 0 00 c3 a3 b3 0 ⋯ 0 0 00 0 c4 a4 b4 ⋯ 0 0 0⋮ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮ ⋮0 0 0 0 0 ⋯ cn−1 an−1 bn−1
0 0 0 0 0 ⋯ 0 cn an
) x⃗=(d1
d2
d3
d4
⋮dn−1
dn
)
Sistemas tridiagonais
O fator de eliminação do elemento é que aplicado a segunda linha só afetará da seguinte forma
(a1 b1 0 0 0 ⋯ 0 0 0c2 a2 b2 0 0 ⋯ 0 0 00 c3 a3 b3 0 ⋯ 0 0 00 0 c4 a4 b4 ⋯ 0 0 0⋮ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮ ⋮0 0 0 0 0 ⋯ cn−1 an−1 bn−1
0 0 0 0 0 ⋯ 0 cn an
) x⃗=(d1
d2
d3
d4
⋮dn−1
dn
)−c2/a1c2
a2 e d2
a2←a2−c2
a1
b1 ;d2←d2−c2
a1
d1
Sistemas tridiagonais
Com isto temos o processo de eliminação na primeira coluna concluído com custo de duas divisões (podendo ser uma), uma soma e uma multiplicação.
Façamos o mesmo procedimento para a segunda linha
Sistemas tridiagonais
O fator de eliminação do elemento é que aplicado a segunda linha só afetará da seguinte forma
(a1 b1 0 0 0 ⋯ 0 0 0c2 a2 b2 0 0 ⋯ 0 0 00 c3 a3 b3 0 ⋯ 0 0 00 0 c4 a4 b4 ⋯ 0 0 0⋮ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮ ⋮0 0 0 0 0 ⋯ cn−1 an−1 bn−1
0 0 0 0 0 ⋯ 0 cn an
) x⃗=(d1
d2
d3
d4
⋮dn−1
dn
)−c3 /a2c3
a3 e d3
a3←a3−c3
a2
b2 ;d3←d3−c3
a2
d2
Sistemas tridiagonais
Observe que a generalização do procedimento para as demais linhas é bem simples.
Na enésima linha teremos
Sistemas tridiagonais
O fator de eliminação do elemento é que resulta em
(a1 b1 0 0 0 ⋯ 0 0 0c2 a2 b2 0 0 ⋯ 0 0 00 c3 a3 b3 0 ⋯ 0 0 00 0 c4 a4 b4 ⋯ 0 0 0⋮ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮ ⋮0 0 0 0 0 ⋯ cn−1 an−1 bn−1
0 0 0 0 0 ⋯ 0 cn an
) x⃗=(d1
d2
d3
d4
⋮dn−1
dn
)−cn /an−1cn
an←an−cn
an−1
bn−1 ;dn←dn−cn
an−1
dn−1
Sistemas tridiagonais
O algoritmo ficará como
ai←ai−ci
ai−1
bi−1 ;d i←di−c i
ai−1
d i−1 ;i=2,3,⋯n
Sistemas tridiagonais
Sendo este o resultado final da eliminação
Partamos agora para a retrosubstituição adaptada a este caso
(a1 b1 0 0 0 ⋯ 0 0 00 a2 b2 0 0 ⋯ 0 0 00 0 a3 b3 0 ⋯ 0 0 00 0 0 a4 b4 ⋯ 0 0 0⋮ ⋮ ⋮ ⋮ ⋮ ⋯ ⋮ ⋮ ⋮0 0 0 0 0 ⋯ 0 an−1 bn−1
0 0 0 0 0 ⋯ 0 0 an
) x⃗=(d1
d2
d3
d 4
⋮dn−1
dn
)
Sistemas tridiagonais
Teremos o que se segue
xn=dn
an
an−1 xn−1+bn−1 xn=dn−1⇒ xn−1=dn−1−bn−1 xn
an−1
an−2 xn−2+bn−2 xn=dn−2⇒ xn−2=dn−2−bn−2 xn−1
an−2
a1 x1+b1 x2=d1⇒ x1=d1−b1 x2
a1
⋮
Sistemas tridiagonais
O algoritmo tomará a forma
com custo computacional O(n)
xn=dn
an
xi=di−bi x i+1
ai
; i=n−1,⋯,1
Sistemas tridiagonais
A própria maneira que o algoritmo é apresentado nos mostra que este tipo de sistema pode ser armazenado em vetores.
Sistemas tridiagonais
Representarmos este sistema na forma matricial é um inconveniente. Existem apenas 3n -2 elementos potencialmente não nulos e o restante, n(n-3) – 2 elementos, são nulos.
Efetivamente, ao usamos a estrutura de dados vetor, comum nas linguagens de programação, iremos utilizar de 3n espaços de memória.
Assim um sistema com 100 variáveis a determinar, se conservársemos a notação matricial, ocuparíamos 9700 posições com zeros, informação irrelevante para a resolução do sistema.
Sistemas tridiagonais – Um exemplo
Seja o sistema abaixo. Resolva-o pelo uso do algoritmo apresentado
(4 1 0 0 0 01 3 2 0 0 00 2 6 3 0 00 0 −1 5 2 00 0 0 2 3 20 0 0 0 1 7
) x⃗=(61334273547
)
Sistemas tridiagonais – Um exemplo
Passemos da representação matricial para a forma de armazenamento vetorial
(4 1 0 0 0 01 3 2 0 0 00 2 6 3 0 00 0 −1 5 2 00 0 0 2 3 20 0 0 0 1 7
) x⃗=(61334273547
) a⃗=(436537
) ; b⃗=(123220
) ; c⃗=(012
−121
) ; d⃗=(61334273547
)
Sistemas tridiagonais
Apliquemos o algoritmo de eliminação dado por
ai←ai−ci
ai−1
bi−1 ;d i←di−c i
ai−1
d i−1 ;i=2, 3,⋯n
Sistemas tridiagonais – Um exemplo
Façamos a eliminação:
c2
a1
=14
; a2←3−14
1⇒ a2=114
; d2←13−14
6⇒d 2=232
ai← ai−ci
ai−1
bi−1; d i←d i−ci
ai−1
d i−1 ;i=2,3,⋯n
a⃗=(436537
) ; b⃗=(123220
) ; c⃗=(012
−121
) ; d⃗=(6
1334273547
)⇒ a⃗=(4.....); d⃗=(
6.....)
Sistemas tridiagonais – Um exemplo
Façamos a eliminação:
c2
a1
=14
; a2←3−14
1⇒ a2=114
; d2←13−14
6⇒d 2=232
c3
a2
=2
11/4=
811
; a3←6−811
2⇒a3=5011
;d3←34−811
232
⇒ d3=28211
ai← ai−ci
ai−1
bi−1; d i←d i−ci
ai−1
d i−1 ;i=2,3,⋯n
a⃗=(436537
) ; b⃗=(123220
) ; c⃗=(012
−121
) ; d⃗=(6
1334273547
)⇒ a⃗=(4
11 /4....
); d⃗=(6
23 /2....
)
Sistemas tridiagonais – Um exemplo
Façamos a eliminação:
c2
a1
=14
; a2←3−14
1⇒ a2=114
; d2←13−14
6⇒d 2=232
c3
a2
=2
11/4=
811
; a3←6−811
2⇒a3=5011
;d3←34−811
232
⇒ d3=28211
ai← ai−ci
ai−1
bi−1; d i←d i−ci
ai−1
d i−1 ;i=2,3,⋯n
c 4
a3
=−1
50/11=−
1150
; a4←5+1150
3⇒a4=28350
;d 4←27+1150
28211
⇒ d4=81625
a⃗=(436537
) ; b⃗=(123220
) ; c⃗=(012
−121
) ; d⃗=(6
1334273547
)⇒ a⃗=(4
11/450 /11
.
.
.) ; d⃗=(
623 /2
282 /11...
)
Sistemas tridiagonais – Um exemplo
Façamos a eliminação:
c2
a1
=14
; a2←3−14
1⇒ a2=114
; d2←13−14
6⇒d 2=232
c3
a2
=2
11/4=
811
; a3←6−811
2⇒a3=5011
;d3←34−811
232
⇒ d3=28211
ai← ai−ci
ai−1
bi−1; d i←d i−ci
ai−1
d i−1 ;i=2,3,⋯n
c 4
a3
=−1
50/11=−
1150
; a4←5+1150
3⇒a4=28350
;d 4←27+1150
28211
⇒ d4=81625
a⃗=(436537
) ; b⃗=(123220
) ; c⃗=(012
−121
) ; d⃗=(6
1334273547
)⇒ a⃗=(4
11/450 /11283 /50
.
.) ; d⃗=(
623 /2
282 /11816 /25
.
.)
c5
a4
=2
283 /50=
100283
; a5←3−100283
2⇒a5=649283
; d5←35+100283
81625
⇒ d 5=6641283
Sistemas tridiagonais – Um exemplo
Façamos a eliminação:
c2
a1
=14
; a2←3−14
1⇒ a2=114
; d2←13−14
6⇒d 2=232
c3
a2
=2
11/4=
811
; a3←6−811
2⇒a3=5011
;d3←34−811
232
⇒ d3=28211
ai← ai−ci
ai−1
bi−1; d i←d i−ci
ai−1
d i−1 ;i=2,3,⋯n
c 4
a3
=−1
50/11=−
1150
; a4←5+1150
3⇒a4=28350
;d 4←27+1150
28211
⇒ d4=81625
a⃗=(436537
) ; b⃗=(123220
) ; c⃗=(012
−121
) ; d⃗=(6
1334273547
)⇒ a⃗=(4
11/450/11
283 /50649 /283
.) ; d⃗=(
623/2
282/11816 /25
6641 /283.
)
c5
a4
=2
283 /50=
100283
; a5←3−100283
2⇒a5=649283
; d5←35+100283
81625
⇒ d 5=6641283
c6
a5
=1
649 /283=
283649
; a6←7−283649
2⇒ a6=3977649
; d6←47−283649
6641283
⇒ d6=23862649
Sistemas tridiagonais – Um exemplo
Eliminação concluida
a⃗=(436537
) ; b⃗=(123220
) ; c⃗=(012
−121
) ; d⃗=(6
1334273547
)⇒ a⃗=(4
11/450 /11
283 /50649 /283
3977 /649) ;d⃗=(
623/2
282 /11816 /25
6641 /28323862 /649
)
Sistemas tridiagonais
Apliquemos o algoritmo correspondente à retrosubstituição dado por
xn=dn
an
; x i=d i−bi xi+1
ai
; i=n−1,⋯,1
Sistemas tridiagonais
Retrosubstituição
b⃗=(123220
) ; a⃗=(4
11/450 /11283 /50
649 /2833977 /649
) ; d⃗=(6
23/2282 /11816 /25
6641/28323862 /649
)xn=
dn
an
; xi=d i−bi x i+1
ai
;i=n−1,⋯,1
x6=d6
a6
=23862/6493977 /649
=6
x5=6641/283−2×6
649 /283=
3245 /283649 /283
=5
x4=816 /25−2×5
283 /50=
566 /25283 /50
=4
x3=282/11−3×4
50/11=
150 /1150 /11
=3
x2=23 /2−2×3
11 /4=
11/211 /4
=2
x1=6−1×2
4=1
Sistemas tridiagonais
Está bom, concordo:
Exagerei nas frações
Sistemas tridiagonais
Solução
x⃗=(123456
)
