Objectos persistentes: pickle and shelve • Um objecto x pode ser
Transcrição
Objectos persistentes: pickle and shelve • Um objecto x pode ser
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 Programação – p.245 Objectos persistentes: 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. Computadores e Programação – p.246 Objectos persistentes: 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() Computadores e Programação – p.247 Redirecçã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. Computadores e Programação – p.248 Redirecção de input e output • 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. Computadores e Programação – p.249 Redirecção 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) Computadores e Programação – p.250 Redirecção de input e output • 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. Computadores e Programação – p.251 Derivação numé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 Computadores e Programação – p.252 Derivação numérica 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 Computadores e Programação – p.253 Derivação numérica • Fórmula de 3 pontos para a primeira derivada 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! Computadores e Programação – p.254 Derivação numérica • Fórmula de 5 pontos para a primeira derivada 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 ) Computadores e Programação – p.255 Derivação numérica • Fórmula de 5 pontos para a primeira derivada 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. Computadores e Programação – p.256 Derivação numérica • 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 Computadores e Programação – p.257 Derivação numérica • Fórmula de 5 pontos para a segunda derivada 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 ) Computadores e Programação – p.258 Derivação numérica • Fórmula de 5 pontos para a segunda derivada fk00 −fk−2 + 16fk−1 − 30fk + 16fk+1 − fk+2 4 = + O(h ) 12h2 Computadores e Programação – p.259 Interpolação numé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. . . Computadores e Programação – p.260 Interpolação numérica • 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 Computadores e Programação – p.261 Interpolação numérica • 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 Computadores e Programação – p.262 Interpolação numérica • 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. . . Computadores e Programação – p.263 Integração numé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) . Computadores e Programação – p.264 Integração numérica • 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 Computadores e Programação – p.265 Integração numérica • 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: Computadores e Programação – p.266 Integração numérica 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 Computadores e Programação – p.267 Integração numérica • 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. . . Computadores e Programação – p.268 Integração numérica • 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 Computadores e Programação – p.269 Integração numérica • 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 Computadores e Programação – p.270 Integração numérica • 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. Computadores e Programação – p.271 Integração numérica • 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 Computadores e Programação – p.272 Integração numérica • 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 Computadores e Programação – p.273 Resolução de equações nã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. . . Computadores e Programação – p.274 Resolução de equações não lineares • 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. . . Computadores e Programação – p.275 Resolução de equações não lineares • 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. . . Computadores e Programação – p.276 Resolução de equações não lineares • 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. . . Computadores e Programação – p.277 Resolução de equações não lineares • 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 Computadores e Programação – p.278 Resolução de equações não lineares • 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! Computadores e Programação – p.279 Resolução de equaçõ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 Computadores e Programação – p.280 Resolução de equações diferenciais • 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. . . Computadores e Programação – p.281 Resolução de equações diferenciais • 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. . . Computadores e Programação – p.282 Resolução de equações diferenciais • 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 Computadores e Programação – p.283 Resolução de equações diferenciais • 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. Computadores e Programação – p.284