Objectos persistentes: pickle and shelve • Um objecto x pode ser

Transcrição

Objectos persistentes:
pickle and shelve
• Um objecto x pode ser guardado num ficheiro f, aberto para
escrita usando o seguinte método do módulo pickle:
pickle.dump(x,f)
• Para ler de novo o objecto do ficheiro basta fazer
x = pickle.load(f)
Computadores e Programação – p.245
pickle and shelve
• A serialização (conversão para string) dos objectos é feita
automaticamente, bem como a sua reconversão no tipo original.
Praticamente qualquer objecto pode ser guardado num ficheiro.
Contudo há que ter o cuidado de carregar os objectos do ficheiro
exactamente pela mesma ordem em que foram guardados!
• Esta restrição é levantada no módulo shelve. Utilizando este
módulo podemos guardar os nossos objectos num ficheiro que
funciona como base de dados onde os objectos são indexados
por uma string única a cada objecto. A interface de utilização
desta base de dados assemelha-se à de um dicionário, como
mostra o exemplo seguinte.
• O módulo shelve permite implementar muito facilmente uma
base de dados sofisticada.
pickle and shelve
import shelve
db = shelve.open(’myfile’,’n’) # n = new file
x,y,z = 123, ’abc’, {1:’a’,2:’bbbb’}
class C:
def __init__(self,x):
self.x = x
def __str__(self):
return "C instance> %d" % (self.x)
if ___name__ == "__main__":
c = C(123)
db[’x’] = x
db[’y’] = y
db[’z’] = z
db[’c instance’]= c
db[’C class’] = C
db.close()
db = shelve.open(’myfile’,’c’) # c = append data
for c in "xyz": print db[c]
db.close()
Redirecção de input e output
• Por vezes é útil redireccionar a saída de um programa do écran
para um ficheiro. Também pode ser útil que um programa passe a
ler os dados que normalmente entram pelo teclado a partir de um
ficheiro. Se o programa correr no sistema operativo Linux (ou
num sistema Unix) a redirecção da entrada e saída pode fazer-se
na linha de comando:
python myprog < input.dat > output.out
• Outros sistemas operativos não dispõem desta facilidade. No
entanto, o Python permite fazer a redirecção dos ficheiros
standard de entrada, saída e de erro de uma forma portátil. Estes
ficheiros estão definidos no módulo sys com os nomes stdin,
stdout e stderr. Por omissão, sys.stdin aponta para o
teclado, e sys.stdout e sys.stderr para o écran. A
redirecção da entrada e saída faz-se pondo estes nomes a
apontar para outros ficheiros.
• O pequeno programa do próximo slide mostra um equivalente
portátil da instrução Unix dada atrás. Para correr o programa,
deve digitar-se na linha de comando
python myprog input.dat output.out
• Os ficheiros de nome “input.dat” e “output.dat” serão atribuídos
no início do programa a sys.stdin e sys.stdout.
• Notar que sys.argv é uma lista que contém as strings de
evocação do programa: sys.argv[0] é o nome do programa e
sys.argv[1:] os argumentos do programa, neste casos os
nomes dos ficheiros de input e output.
#!/usr/bin/env python
import sys
try:
sys.stdin = open(sys.argv[1],’r’)
except:
print "Error opening input file.",sys.stdin
sys.exit()
try:
sys.stdout = open(sys.argv[2],’w’)
except:
print "Error opening output file",sys.stdout
sys.exit()
for line in sys.stdin:
print line[:-1] #remove last char (CR)
• Como não houve redirecção do ficheiro sys.stderr, as
mensagens de erro eventualmente geradas pelo programa serão
ainda enviadas para o écran. Para que estas mensagens também
sejam enviadas para o ficheiro de saída que atribuímos a
sys.stdout bastava incluir a instrução sys.stderr =
sys.stdout a seguir à redirecção de sys.stdout.
Derivação numérica
Possuindo apenas duas listas de números (o valor fk de uma função
num conjunto discreto de pontos igualmente espaçados xk ) como
obter as derivadas da função num desses pontos?
x
f (x)
x1
x2
...
xn
f1
f2
...
fn
As várias fórmulas de derivação numérica obtêm-se fazendo
combinações simples da expansão em série de Taylor da função nos
pontos próximos do ponto onde se pretende calcular a derivada.
• Fórmula de 2 pontos para a primeira derivada
Partindo de
1
fk+1 = fk + fk0 (xk+1 − xk ) + fk00 (xk+1 − xk )2 + · · ·
2
obtém-se, visto que h = xk+1 − xk ,
fk0
fk+1 − fk
+ O(h)
=
h
Obtém-se subtraindo
fk−1 = fk −
fk0 h
1 00 2
+ fk h + · · ·
2
da expansão para fk+1
fk0
fk+1 − fk−1
+ O(h2 )
=
2h
O cancelamento dos termos em h2 nas expansões conduz a um
erro que é de ordem superior ao anterior!
4
2
−
fk+2 = fk + 2fk0 h + 2fk00 h2 + fk000 h3 + fk0000 h4 + . . .
3
3
1
1
1
+ 8 fk+1 = fk + fk0 h + fk00 h2 + fk000 h3 + fk0000 h4 + . . .
2
6
24
1 00 2 1 000 3
1 0000 4
0
− 8 fk−1 = fk − fk h + fk h − fk h + fk h + . . .
2
6
24
4 000 3 2 0000 4
0
00 2
+
fk−2 = fk − 2fk h + 2fk h − fk h + fk h + . . .
3
3
=
12hfk0 + O(h5 )
fk0
fk−2 − 8fk−1 + 8fk+1 − fk+2
+ O(h4 )
=
12h
• Para obter a fórmula de 7 pontos é preciso calcular ainda fk+3 e
fk−3 . A primeira derivada de f (x) é então obtida através de:
fk0 '
3
X
ci fk+i
i=−3
sendo os coeficientes ci ajustados de modo a que todos os
termos de ordem inferior a h6 se cancelem.
• Fórmula de 3 pontos para a segunda derivada
1
1
1
fk+1 = fk + fk0 h + fk00 h2 + fk000 h3 + fk0000 h4 + . . .
2
6
24
1
1
1
fk−1 = fk − fk0 h + fk00 h2 − fk000 h3 + fk0000 h4 + . . .
2
6
24
+
=
2fk + h2 fk00 + O(h4 )
logo
fk00 =
fk+1 − 2fk + fk−1
2
+
O(h
)
2
h
4
2
−
fk+2 = fk + 2fk0 h + 2fk00 h2 + fk000 h3 + fk0000 h4 + . . .
3
3
1
1
1
+ 16 fk+1 = fk + fk0 h + fk00 h2 + fk000 h3 + fk0000 h4 + . . .
2
6
24
1 00 2 1 000 3
1 0000 4
0
+ 16 fk−1 = fk − fk h + fk h − fk h + fk h + . . .
2
6
24
4 000 3 2 0000 4
0
00 2
−
fk−2 = fk − 2fk h + 2fk h − fk h + fk h + . . .
3
3
=
30fk + 12h2 fk00 + O(h6 )
fk00
−fk−2 + 16fk−1 − 30fk + 16fk+1 − fk+2
4
=
+
O(h
)
12h2
Interpolação numérica
• Conhecendo os valores de uma função, yi ≡ f (xi ) num conjunto
discreto de pontos, {xi , i = 0, . . . , N }, é possível obter uma
estimativa do valor da função num ponto x não pertencente a
esse conjunto se se fizer passar uma curva pelos pontos
conhecidos. A equação desta curva pode ser dada por um
polinómio (interpolação de Lagrange), um quociente de
polinómios, uma combinação linear de polinómios ortogonais
(polinómios de Chebushev, por exemplo), splines, etc.
• Se x0 < x < xN o processo designa-se por interpolação.
• Se x < x0 ou x > xN o processo designa-se por extrapolação.
• Um processo distinto de obter o valor de f (x) é o ajuste através
de uma minimização dos desvios quadráticos de uma curva aos
pontos conhecidos. Mas, neste caso, a curva não passa pelos
pontos. É o que acontece quando se ajusta, por exemplo, uma
recta a um conjunto de resultados experimentais. . .
• Se se pretender obter um polinómio interpolante de 1a ordem
(uma recta. . . )
P1 (x) = a + bx
com xj < x < xj+1 , os coeficientes do polinómio são
determinados impondo simplesmente que o polinómio passe
exactamente por (xj , f (xj )) e (xj+1 , f (xj+1 )):
(
P1 (xj ) = f (xj )
⇔
P1 (xj+1 ) = f (xj+1 )
(
a + bxj = yj
a + bxj+1 = yj+1
• Se se pretender obter um polinómio interpolante de 2a ordem
(uma parábola. . . )
P2 (x) = a + bx + cx2
com xj < x < xj+2 , são necessárias 3 equações para determinar
os 3 coeficientes do polinómio. Então estes são determinados
impondo que o polinómio passe exactamente por (xj , f (xj )),
(xj+1 , f (xj+1 )) e (xj+2 , f (xj+2 )):


2


 a + bxj + cxj = yj
 P2 (xj ) = f (xj )
a + bxj+1 + cx2j+1 = yj+1
P2 (xj+1 ) = f (xj+1 ) ⇔


 a + bx
 P (x ) = f (x )
2
2 j+2
j+2
j+1 + cxj+2 = yj+2
• A solução destes sistemas de equações pode ser escrita de uma
forma bastante compacta:
PN (x) =
N
X
i=0
N
Y
j=0
j 6= i
x − xj
yi
xi − x j
• Com uma dúzia de pontos é possível interpolar, por exemplo, as
funções trigonométricas com uma precisão muito elevada. É este
o método usado pelas máquinas de calcular para calcular estas e
outras funções. . .
Integração numérica
• A maneira mais simples de obter o valor numérico do integral de
uma função
Z b
f (x)dx
I=
a
é dividir o domínio de integração em N intervalos de largura
h = (b − a)/N e considerar que o integral da função num desses
intervalos é dado simplesmente através do produto do valor da
função no ponto médio do intervalo pela largura do intervalo:
I'
N
−1
X
i=0
f
xi +
h
2
h
(x0 ≡ a, xN ≡ b) .
• Este método corresponde a aproximar a área abaixo da função
por uma série de rectângulos
a
x1
x2
x3
x4
x5
x6
x7
x8
x9
b
• Este método de cálculo do integral não é muito eficaz, pois só
com intervalos muito pequenos se comete um erro pequeno. . .
• Para melhorar o processo, considere-se o integral apenas num
dos intervalos
Z
xj+1
Ij =
f (x)dx .
xj
• Se se expandir f (x) em série de Taylor em torno do xj e se
desprezarem todos os termos de ordem superior à primeira, vem
Ij '
Z
xj+1
xj
(f (xj ) + f 0 (xj )(x − xj )) dx
que se pode calcular recorrendo à fórmula de 2 pontos para a
derivada:
Ij '
Z
xj+1
xj
f (xj+1 ) − f (xj )
(x − xj ) dx =
f (xj ) +
h
f (xj ) + f (xj+1 )
f (xj+1 ) − f (xj ) h2
=h
= hf (xj ) +
h
2
2
• Então, o integral no intervalo [a, b] será:
I=
N
−1
X
j=0
N −1
h X
Ij '
(f (xj ) + f (xj+1 )) =
2 j=0


N
−1
X
h
f (xj ) + f (b)
f (a) + 2
=
2
j=1
• Esta regra de integração é conhecida como regra do trapézio e
corresponde a aproximar a área abaixo da função por uma soma
das áreas de vários trapézios:
a
x1
x2
x3
x4
x5
x6
x7
x8
x9
b
• Na prática, a regra do trapézio consiste em aproximar a função
entre os extremos de cada intervalo de largura h por uma recta. . .
• Para melhorar a regra do trapézio basta melhorar a aproximação.
A regra de Simpson consiste em aproximar a função entre os
extremos de cada intervalo por uma parábola. Esta regra de
integração pode ser deduzida de uma forma bastante simples.
Considere-se o integral apenas no intervalo entre xj−1 e xj+1
(recordar que são precisos 3 pontos para definir uma parábola. . . )
Ij =
Z
xj+1
f (x)dx .
xj−1
• Se se expandir f (x) em série de Taylor em torno do xj e se
desprezarem todos os termos de ordem superior à segunda, vem
Ij '
Z
xj+1
xj−1
1 00
f (xj ) + f (xj )(x − xj ) + f (xj )(x − xj )2 dx
2
0
• Este integral pode-se calcular recorrendo às fórmulas de 3 pontos
para as derivadas:
xj+1
f (xj+1 ) − f (xj−1 )
(x − xj )+
Ij '
f (xj ) +
2h
xj−1
1 f (xj+1 ) − 2f (xj ) + f (xj−1 )
2
(x
−
x
)
dx =
+
j
2
h2
Z
f (xj+1 ) − f (xj−1 )
· 0+
= 2hf (xj ) +
2h
f (xj+1 ) − 2f (xj ) + f (xj−1 ) 2h3
+
2h2
3
logo
Ij ' h
f (xj−1 ) + 4f (xj ) + f (xj+1 )
.
3
• Então, o integral no intervalo [a, b] será:
N
−1
X
N −1
h X
Ij '
(f (xj−1 ) + 4f (xj ) + f (xj+1 ) =
I=
3
j=0
j=1


N
−1
N
−1
X
X
h
f (a) + 4
f (xj ) + 2
f (xj ) + f (b)
=
3
j=2, j par
j=1, j ímpar
• A regra de Simpson é a regra de integração unidimensional mais
conhecida. Uma das razões para o seu sucesso é o facto de
produzir resultados melhores que o esperado, pois a primeira
correcção a esta regra — a inclusão do termo de terceira ordem
da série de Taylor — é nula, sendo preciso incluir o termo de
quarta ordem para obter uma melhoria.
• Seguindo o processo de obtenção das regras do trapézio e de
Simpson, é possível obter formas mais “precisas” para o cálculo
dos integrais. Mas a regra de Simpson é um bom compromisso
entre simplicidade da formulação e precisão. . .
• Há muitos outros métodos de calcular um integral (quadratura
gaussiana, por exemplo). . . Um dos mais conhecidos é o método
de Monte Carlo cujo algoritmo é o seguinte
◦ Gerar um par de números aleatórios (x, y), com a ≤ x ≤ b e
0 ≤ y ≤ fmax , onde fmax é um valor superior ao máximo da
função no intervalo [a, b]
◦ Se y < f (x), incrementar um contador Nin
◦ Repetir o processo N vezes: o integral é dado por
Nin
fmax (b − a) .
I'
N
• Este processo de “tiro ao alvo” é pouco eficaz para integrais a
uma ou duas dimensões. Mas para integrais sobre um número
grande de variáveis este método torna-se mais eficiente que a
regra de Simpson. . .
fmax
0a
b
Resolução de equações não lineares
• Frequentemente é necessário encontrar o zero de uma função
complicada resolvendo uma equação não linear. Há vários
métodos numéricos bastante simples e poderosos para o fazer,
sendo o mais robusto deles o chamado método da bissecção:
◦ Seja f (x) = 0 a equação que se pretende resolver. Se houver
um zero de f no intervalo [a, b] então, em geral, f (a) · f (b) < 0.
◦ No ponto c = a + (b − a)/2 verifica-se que ou f (a) · f (c) < 0
ou f (c) · f (b) < 0, o que permite determinar se o zero está no
intervalo [a, c] ou [c, b] (se só houver um zero em [a, b]. . . ).
Supondo que é a primeira condição que se verifica, pode-se
calcular f (d), com d = a + (c − a)/2 e determinar se o zero
está no intervalo [a, d] ou no intervalo [d, c]. . .
◦ Pode-se repetir este processo até que o intervalo onde se
encontra o zero seja muito pequeno. . .
• O método da bissecção é extremamente robusto mas não é muito
rápido. . . Em muitos casos é possível melhorar o processo de
busca do zero de f se o novo extremo do intervalo de procura (c,
d, etc.) for encontrado fazendo passar uma recta pelos extremos
do intervalo (a e b no início do processo. . . ) e determinando o
ponto onde essa recta cruza o eixo dos x. Este método é
conhecido por método da falsa posição e é, em geral, mais rápido
que o método da bissecção. Mas não é tão robusto, podendo não
encontrar o zero. . .
• Um outro método, semelhante ao método da falsa posição, é o
método da secante: se [xn , xn+1 ] for o intervalo de busca do zero
na enésima iteração, o intervalo para a iteração seguinte é
[xn+1 , xn+2 ] sendo xn+2 o ponto onde a recta que passa pelos
pontos (xn , f (xn )) e (xn+1 , f (xn+1 )) intersecta o eixo dos x.
Neste método não há portanto garantia que o zero se encontre
no intervalo de busca, ao contrário dos métodos anteriores. Tal
como o método da falsa posição, este método nem sempre é bem
sucedido. . .
• Se for possível calcular a derivada de f pode-se recorrer ao
método de Newton-Raphson para encontrar o zero. Este método
é bastante robusto e extremamente eficiente na maioria dos
casos:
◦ Seja xi uma estimativa para a posição do zero de f
◦ Se se expandir a função em série de Taylor em torno de xi e
se desprezarem os termos de ordem igual ou superior a 2
vem
f (x) ' f (xi ) + f 0 (xi )(x − xi ) ≡ f˜(x)
◦ Usando esta aproximação para f o zero encontra-se no ponto
f (xi )
f˜(z) = 0 ⇔ z = xi − 0
f (xi )
◦ Se f (z) 6= 0, considera-se xi+1 = z e repete-se o processo. . .
• Um exemplo simples de aplicação do método de
√
Newton-Raphson é o cálculo da raíz de um número ( n c). Este
cálculo pode ser transformado numa equação não linear:
x=
√
n
c ⇔ xn = c ⇔ xn − c = 0
• Os passos do método de Newton são, neste caso:
xi+1
• Por exemplo, para calcular
xni − c
= xi −
nxin−1
√
3
xi+1
7, vem
x3i − 7
= xi −
3x2i
• Se a primeira estimativa para
√
3
7 for x1 = 2, vem
23 − 7
= 1.91666666667
x2 = 2 −
3 × 22
1.916666666673 − 7
= 1.91293845831
x3 = 1.91666666667 −
2
3 × 1.91666666667
1.912938458313 − 7
= 1.9129311828
x4 = 1.91293845831 −
3 × 1.912938458312
obtendo-se o resultado “exacto” à terceira iteração!
Resolução de equações diferenciais
• Todos os algoritmos de resolução de equações diferenciais
partem da mesma ideia base: obter uma boa estimativa para as
derivadas na equação. Considerem-se, por enquanto, apenas
equações diferenciais ordinárias de primeira ordem e escreva-se
a equação da seguinte forma
y 0 (t) = f (t, y(t)) .
• O que se pretende obter (a solução da equação. . . ) é o valor de
y(t) para vários valores de t. É, obviamente, necessário ter uma
condição de fronteira para poder integrar a equação. Essa
condição é tipicamente o valor “inicial” de y(t), y(t0 ).
• Conhecendo y(t), y(t + ∆t) obtém-se simplesmente por
expansão em série de Taylor
1 00
y(t + ∆t) = y(t) + y (t)∆t + y (t)(∆t)2 + . . .
2
0
• Se se considerar apenas o termo de primeira ordem, obtém-se o
chamado método de Euler para a integração de uma equação
diferencial ordinária
y(t + ∆t) ' y(t) + y 0 (t)∆t
=⇒
yi+1 = yi + f (ti , yi )∆t
com y0 = y(t0 ).
• Este método é bastante simples de implementar mas só é
recomendável para equações muito simples. Repare-se que o
erro em cada passo de integração é da ordem de (∆t)2 , visto ser
este o primeiro termo desprezado na série de Taylor. . .
• Uma maneira de obter um método melhor é melhorar a estimativa
da derivada y 0 (t). No método de Euler, esta derivada é calculada,
para cada intervalo ∆t, apenas no início. A estimativa da derivada
é melhorada se se usar o valor desta para dar meio passo de
Euler e se voltar a calcular a derivada no ponto ti + ∆t/2:
yi+1 = yi + k2
(
k1 = f (ti , yi ) ∆t
k2 = f ti + ∆t
2 , yi +
k1
2
∆t
Este método é designado por método de Runge-Kutta de 2a
ordem e o erro em cada passo de integração é agora da ordem
de (∆t)3 . Mas é necessário calcular f (t, y) duas vezes em cada
passo. . .
• O método mais utilizado para integrar equações diferenciais
ordinárias é o método de Runge-Kutta de 4a ordem. A sua
popularidade advém da sua robustez e precisão (o erro em cada
passo é da ordem de (∆t)5 ), obtidas sem sacrificar em demasia a
rapidez (só se calcula a derivada 4 vezes em cada passo). A sua
fórmula é:
yi+1 = yi +
1
(k1 + 2k2 + 2k3 + k4 )
6

k1



 k
2

k3



k4
= f (ti , yi ) ∆t
k1
∆t
= f ti + 2 , yi + 2 ∆t
k2
∆t
= f ti + 2 , yi + 2 ∆t
= f (ti + ∆t, yi + k3 ) ∆t
• Para integrar equações diferenciais ordinárias de ordem superior
à primeira basta tratar as várias derivadas da função como
funções independentes e re-escrever a equação diferencial de
ordem n como n equações diferenciais de primeira ordem
acopladas. Por exemplo, a equação de movimento de um
oscilador harmónico amortecido,
mx00 (t) = −kx(t) − γx0 (t) ,
pode ser escrita como
(
x0 (t) = v(t)
k
x(t) −
v 0 (t) = − m
γ
m v(t)
• O sistema de equações de primeira ordem pode depois ser
integrado recorrendo a qualquer dos métodos já expostos.

Objectos persistentes: pickle and shelve • Um objecto x pode ser

Transcrição

Documentos relacionados

apendice C.p65

12.03.2009 às 23:23 Costa Rica, por fim

Derivadas: Exercícios resolvidos

Este teste é empregado para pesquisar os pontos de máximo e

Artigos pagina 1 van 9 Vivercidades - Revista 18-3

Enunciado

Relato de viagem: Costa Rica

3-5 setembro 2012

proposta de um modelo de educação não formal que

1º a 15 de agosto de 2012 - Instituto Interamericano de Derechos

FICHA TÉCNICA do hotel - Site

E O LEGADO DA COPA DO MUNDO? A água desapareceu do

Técnica Industrial Oswaldo Filizola Ltda