Baixe o app para aproveitar ainda mais
Prévia do material em texto
Cálculo Numérico Teoria dos Erros Prof. Wellington Passos de Paula wpassos@ufsj.edu.br Programa 1. Conceitos Básicos a) Representação de números b) Conversão de números c) Aritmética de ponto flutuante 2. Erros a) Erros absolutos e relativos b) Erros de arredondamento e truncamento c) Análise de erros Cálculo Numérico Teoria dos Erros – Conceitos Básicos Prof. Wellington Passos de Paula wpassos@ufsj.edu.br Representação de números Sistema Decimal (10) 10 dígitos disponíveis [0,1,2, ... ,9] “Posição” indica potência positiva de 10 5432 = 5x103 + 4x102 + 3x101 + 2x100 Sistema Binário (2) 2 “bits” disponíveis [0,1] “Posição” indica potência positiva de 2 1011 na base 2 = 1x23 + 0x22 + 1x21 + 1x20 8+0+2+1 = 11 na base decimal Representação de números Fórmula Geral Base : Logo, a decomposição polinomial do número é dada por: Exemplo: Dado , temos que: , jik ,..., ,)...( 0121 aaaaa jj )1(0 ka 0 0 1 1 2 2 1 1 ... aaaaa jjjj ,)...( 0121 aaaaa jj 0123 1091041081066849 10 Representação de números Representação Números Fracionários Base Decimal (10) “Posição” da parte inteira indica potência positiva de 10 Potência negativa de 10 para parte fracionária 54,32 = 5x101 + 4x100 + 3x10-1 + 2x10-2 Base Binária (2) “Posição” da parte inteira indica potência positiva de 2 Potência negativa de 2 para parte fracionária 10,11 na base 2 = 1x21 + 0x20 + 1x2-1 + 1x2-2 2+0+1/2+1/4 = 2,75 na base decimal Outros sistemas de numeração Maior interesse em decimal (10) Nossa anatomia e cultura Binário (2) – uso nos computadores Outros Sistemas Octal (8), {0,1,2, ... , 7} Hexadecimal (16), {0,1,2, ... , 9, A,B,C,D,E,F} Duodecimal (relógio, calendário) Alguns sistemas numéricos Conversão de números – inteiros Binário para decimal Já visto (1011)2 = 1x23 + 0x22 + 1x21 + 1x20 = (11)10 Inteiro decimal para binário Divisão inteira (do quociente) sucessiva por 2, até que este seja = 0 ou 1 Binário = composição do último quociente (Bit Mais Significativo – BMS) com os restos das divisões (primeiro resto é bit menos significativo – bms) Em inglês, Most Significant Bit – MSB e least significat bit – lsb, respectivamente. Conversão de números – inteiros Exemplo: Converter 30 decimal para binário Binário = BMS ... bms = 1 1 1 1 0 1 1 1 1 0 = 1x24 + 1x23 + 1x22 + 1x21 + 0x20 = 16 + 8 + 4 + 2 + 0 = 30 decimal Conversão de inteiros entre sistemas Procedimentos Básicos Decimal Binário - Divisões sucessivas pela base do sistema para o qual desejamos converter o número (neste caso, divisões sucessivas por 2) Binário Decimal - Decomposição polinomial do número a ser convertido Conversão de inteiros entre sistemas Conversão de fração Base 2 para Base 10 Já visto (Decomposição Polinomial) (10,101)2 = 1x21 + 0x20 + 1x2-1 + 0x2-2 + 1x2-3 = = 2 + 0 + 1/2 + 0 + 1/8 = (2,625)10 Conversão de fração Base 10 para Base 2 Devemos multiplicar parte fracionária por 2 até que parte fracionária do resultado seja 0 (zero) X,XXX Bits da parte fracionária do número binário são obtidos das partes inteiras geradas após as multiplicações do número fracionário na base 10 X,XXX Bit imediatamente à direita da vírgula = Parte inteira da primeira multiplicação Não há inversão na ordem dos bits encontrados Conversão de fração Exemplo: converter 0,625 decimal para binário 0,625 x 2 = 1,25, logo a primeira casa fracionária é 1; nova fração (resto) é 0,25 (agregamos o bit 1 ao número na base 2) 0,25 x 2 = 0,5 segunda casa é 0; nova fração (resto) é 0,5 (pois já agregamos o bit 0 ao numero na base 2) 0,5 x 2 = 1,0 terceira casa é 1; nova fração (resto) é 0,0 (pois já agregamos o bit 1 ao numero na base 2) Resultado: 0,62510 = 0,1012 Conversão partes inteira e fracionária juntas Para converter um número com parte inteira e parte fracionária, devemos fazer a conversão de cada parte, separadamente Conversão partes inteira e fracionária juntas (8,375)10 = ( ? )2 Exercícios Transforme em binário: 5,8 Resposta: 5,8 = 101,11001100... , uma dízima. 11,6 Resposta: 11,6 = 1011,10011001100... a vírgula foi deslocada uma casa para a direita, pois 11,6 = 2 x 5,8 Aritmética de ponto flutuante Representação pode variar (“flutuar”) a posição da vírgula, ajustando potência da base. 54,32 = 54,32 x 100 = 5,432 x 101 = 0,5432 x 102 = 5432,0 x 10-2 Forma normalizada utiliza um único dígito antes da vírgula ( 0 ), e garante o que primeiro dígito depois da vírgula seja diferente de 0 Exemplo: 0,5432 x 101 Aritmética de ponto flutuante No sistema binário: 11010 = 11,010 x 23 = 0,11010 x 25 = 0,0011010 x 27 No caso dos números serem armazenados em um computador, os expoentes serão também gravados na base dois Como 310 = 112, 510=1012 e 710=1112 11,010 x (2)11 = 0,11010 x (2)101 = 0,0011010 x (2)111 Na representação normalizada, há apenas um dígito antes da vírgula ( 0 ) Exemplo: 0,11010 x (2)101 Aritmética de ponto flutuante Algumas definições No número 0,11010 x (2)101 , tomado como referência: 0,11010 = significando (ou “mantissa”) 101 = expoente Observações A base binária não precisa ser explicitada (o computador usa sempre a mesma) O “0” antes da vírgula, na representação normalizada – se esta for adotada, também pode ficar implícito, economizando um bit (“bit escondido”). Representação aritmética de ponto flutuante no computador onde: é a base em que o computador opera; é o número de dígitos na mantissa é o expoente (inteiro com sinal) e tddd )...(. 21 t ;01 d,,...,1),1(0 tjd j e Representação aritmética de ponto flutuante no computador O número de bits disponíveis para representar os números no computador não é infinito O padrão IEEE 754 para ponto (vírgula) flutuante é a representação mais comum para números reais em computadores de hoje, incluindo PC's compatíveis com Intel, Macintosh, e a maioria das plataformas Unix/Linux. O padrão (ou norma) IEEE 754 define dois formatos básicos para os números em ponto flutuante: O formato ou precisão simples, com 32 bits; e, O duplo com 64 bits Sinal: 0 = + e 1 = - Combinações: Sinal + Expoente + Mantissa Padrão IEEE 754 para floats Sinal Expoente(+/-) Significando Simples (32bits) 1 [bit31] 8 [bits30-23] 23 [bits22-00] Dupla (64 bits) 1 [bit63] 11 [bits62-52] 52 [bits51-00] Limitações na representação de floats A quantidade finita de bits na representação pode implicar nos seguintes erros: Truncamento ou Arredondamento Overflow Underflow Limitações na representação de floats Exemplo: Máquina no seguinte sistema: Logo o formato dos números nesse sistema: Menor valor representado em módulo: Maior valor representado em módulo: .5,5;3;10 et 5,5,0,90,10.0 1321 eddddd je 65 1010100.0 m 9990010999.0 5 M Limitações na representação de floats Situações possíveis: a) . Número contém 5 dígitos na mantissa Possíveis Soluções: Truncamento: Arredondamento: Assunto do próximo tópico 31023589.089.235 x 310235.0 310236.0 Limitações na representação de floats Situações possíveis: b) . Expoente não pode ser representado na máquina pois é menor que o mínimo (-5) Erro de underflow c) . Expoente não pode ser representado na máquina pois é maior que o máximo (5) Erro deoverflow 710345.0 x 910875.0 x Limitações na representação de floats Considere ]4,4[;3;10 et x arredondamento truncamento 1.25 10.053 -253.15 2.71828 0.000002 Underflow Expoente<-4 817235.89 Overflow Expoente>+4 110125.0 110125.0 210100.0 210101.0 310253.0 310253.0 110272.0 110271.0 Exercícios Considere uma máquina com sistema de representação de números definido por: base 10, precisão de 4 dígitos na mantissa e expoente no intervalo: [-6; 6]. Pede-se: a) Qual o menor e o maior número em módulo representado nesta máquina? Menor: 0.1000x10-6 = 10-7, Maior: 0.9999x106 = 999900 b) Como será representado o número 189,27 nesta máquina se for usado o arredondamento? E se for usado o truncamento? Trunc.: 0.1892x103, Arred.: 0.1893x103 c) Se a = 2578 e b = 0,6 qual o resultado de a + b se for usado o arredondamento? E se for usado o truncamento? Trunc.: 0.2578x104, Arred.: 0.2579x104 Cálculo Numérico Teoria dos Erros – Erros Prof. Wellington Passos de Paula wpassos@ufsj.edu.br Erros – Tipos Precisão Absoluto Relativo Representação Arredondamento Truncamento Erro Absoluto Diferença entre o valor exato de um número e o seu valor aproximado (em módulo) |x|xEAx EAx só poderá ser determinado se x for conhecido com exatidão Na prática, usualmente trabalhamos com um limitante superior para o erro, ao invés do próprio erro ( |E | < ε, sendo ε é o limitante) Ex: Para (3,14; 3,15) <0,01ππ-=EAπ Erro Absoluto – Considerações Erro Absoluto – Considerações Ex.: Sejam a = 3876,373 e e = 1,373 Considerando-se a parte inteira de a como ā o erro absoluto será: e a parte inteira de e, ē, o erro absoluto será: 0,373aaEAa 3876373,3876 0,373eeEAe 1373,1 Erro Absoluto – Considerações Obviamente, o resultado do erro absoluto é o mesmo nos dois casos Podemos então dizer que a e e estão representados com a mesma precisão? Não, pois o peso da aproximação em e é maior do que em a Erro absoluto não é suficiente para descrever a precisão de um cálculo Erro Relativo Razão entre o erro absoluto e o valor aproximado do número considerado (em módulo) |x| EA |x| |x|xER xx O erro relativo pode, entretanto, traduzir perfeitamente este fato, pois: ERx x 100 = Erro Percentual 4 a 100,0000963876 0,373ER 10 105,373 1 0,373ERe Erro Relativo – Considerações Ex. : Cálculo do erro relativo na representação dos números ā = 2112,9 e ē = 5,3, sendo |EA| < 0,1 Conclusão: a é representado com maior precisão do que e Erro Relativo – Considerações 5107,4 9,2112 1,0 a aa ERa 02,0 3,5 1,0 e ee ERe Erros de Arredondamento Ex. Cálculo de utilizando uma calculadora digital Valor apresentado: 1,4142136 Valor real: 1,41421356... Inexistência de forma de representação de números irracionais com uma quantidade finita de algarismos Apresentação de uma aproximação do número pela calculadora Erro de Arredondamento 2 Erros de Truncamento Descarte dos dígitos finais de uma representação exata por limitações de representação em vírgula flutuante Ex.: Representação truncada de em vírgula flutuante com 7 dígitos Valor apresentado: 1,4142135 Valor real: 1,41421356... 2 Representação aritmética de ponto flutuante no computador – Relembrando... onde: é a base em que o computador opera; é o número de dígitos na mantissa é o expoente (inteiro com sinal) e tddd )...(. 21 t ;01 d,,...,1),1(0 tjd j e Para t = 4, e = 3 e x = 234,57: x = 0,2345 x 103 + 0,7 x 10-1 fx = 0,2345 gx = 0,7 Erros de Truncamento e Arredondamento em um sistema de aritmética de ponto flutuante: Em um sistema que opera em ponto flutuante de t dígitos na base 10, e seja x: x = fx x 10e + gx x 10e-t (0,1 fx 1 e 0,1 gx 1) Erros de Arredondamento e Truncamento Para t = 5, e = 4 e x = 1234,568 x = 0,12345 x 104 + 0,68 x 10-1 fx = 0,12345 gx = 0,68 Erros – Truncamento No truncamento, gx x 10e-t é desprezado e e , visto que |gx| < 1 pois 0,1 é o menor valor possível para fx 1t e te e te e x te xx x 101010 10 100,1 10 10f 10g x EA ER 10,1 e x 10fx tete xx 1010gEA te x e x 10g10fx e x te x e xx f10gfxxEA 1010 No arredondamento simétrico (forma mais utilizada): , se (gx é desprezado) , se (soma 1 ao último dígito de fx) Erros – Arredondamento tee x e x 1010f 10f x 2 1gx 2 1gx Erros – Arredondamento Se , então: , visto que |gx| < 1/2 1t e te e te e x te xx x 102 1 10 10 100,1 100,5 10f 10g x EA ER 1100,1 2/1 tete xx 102 110gEA 2 1gx e x te x e xx f10gfxxEA 1010 Erros – Arredondamento Se , então: e e x te tee x te x x 10f 101/2 1010f 101/2 x EA ER tetextetexx 102 1101g1010gEA 2 1gx teextexexx 1010f10g10fxxEA 1t e te e te x 102 1 10 101/2 100,1 101/2ER 1100,1 Erros de Truncamento e Arredondamento em um sistema de aritmética de ponto flutuante: Sistema operando em ponto flutuante - Base 10 Erro de Truncamento e Erro de Arredondamento e Arredondamento gera erros menores, mas aumenta o tempo de execução uso do Truncamento te x 10EA 1tx 10ER 1t x 102 1ER tex 102 1EA Arredondamento e Truncamento Sistema de aritmética de ponto flutuante de 4 dígitos, precisão dupla Ex.: Seja x = 0,937 x104 e y = 0,1272 x102. Calcular x+y. Alinhamento dos pontos decimais antes da soma ( Alinhar sempre para o maior expoente dentre os operadores ) x = 0,937 x 104 e y = 0,001272 x 104, x+y = 0,937 x 104 + 0,001272 x 104, x+y = 0,938272 x 104 Resultado com 4 dígitos Arredondamento: x+y = 0,9383 x 104 Truncamento: x+y = 0,9382 x 104 Análise de Erros Sistema de aritmética de ponto flutuante de 4 dígitos, precisão dupla Ex. : Seja x = 0,937 x 104 e y = 0,1272 x102. Calcular x.y x.y = (0,937 x 104) x (0,1272 x 102) x.y = (0,937 x 0,1272) x 106 x.y = 0,1191864 x 106 Resultado com 4 dígitos Arredondamento: x.y = 0,1192 x 106 Truncamento: x.y = 0,1191 x 106 Análise de Erros Análise de Erros Considerações Ainda que as parcelas ou fatores de uma operação possam ser representados exatamente no sistema, não podemos esperar que o resultado armazenado seja exato. x e y tinham representação exata, mas os resultados x+y e x.y tiveram representação aproximada. Durante as operações aritméticas de um método, os erros dos operandos produzem um erro no resultado da operação Propagação ao longo do processo Análise de Erros – Propagação Ex. : Sejam as operações a seguir processadas em uma máquina com 4 dígitos significativos e, fazendo- se: a = 0,3491 x 104 e b = 0,2345 x 100. (b + a) − a = b + (a − a) ? (b + a) − a = (0,2345 x100+0,3491x104) − 0,3491x104 = (0,00002345 x104+0,3491x104) − 0,3491x104 (0,34912345 x104) − 0,3491x104 (arredondamento) 0,3491 x 104 − 0,3491 x104 = 0,0000 b + (a − a) = 0,2345x100 + (0,3491 x 104 −0,3491x104)= 0,2345 x 100 +(0,0000 x 104)= 0,2345 x 100 Análise de Erros – Propagação Os dois resultadossão diferentes, quando não deveriam ser. (b + a) − a = 0,0000 e b + (a − a) = 0,2345 x 100 Causa Arredondamento da adição (b + a), a qual tem 8 dígitos A máquina só armazena 4 dígitos (desprezando os menos significativos) Análise de Erros – Propagação Resolução numérica de um problema Importância do conhecimento dos efeitos da propagação de erros Determinação do erro final de uma operação Conhecimento da sensibilidade de um determinado problema ou método numérico Análise de Erros – Propagação Análise dos Erros Absoluto e Relativo Expressões para o determinação dos erros nas operações aritméticas Erros presentes na representação das parcelas ou fatores, assim como no resultado da operação Supondo um erro final arredondado, sendo x e y, tais que: yx EAy yEAxx e Análise de Erros – Propagação Adição Erro Absoluto Erro Relativo yx yER yx xER yx y y EA yx x x EAER yx yx yx )EA(EA)yx( )EAy() EAx(yx yx yx yxyx EAEAEA yx EA yx EA yx EAEA yx EA ER yxyxyxyx Análise de Erros – Propagação Subtração Erro Absoluto Erro Relativo )EA(EA)yx( )EAy()EAx(yx yx yx yxyx EAEAEA yx yER yx xER yx y y EA yx x x EAER yx yx yx yx EA yx EA yx EAEA yx EA ER yxyxyxyx Análise de Erros – Propagação Multiplicação Erro Absoluto Erro Relativo muito pequeno yxxyyx EAEAEAyEAxyxEAyEAxx.y xyyx EAyEAxyxEAyEAxx.y yxx.y ERERER xyx.y EAyEAxEA y EA x EA xy EAy xy EAx xy EAyEAx xy EA ER yxxyxyyxx.y . Análise de Erros – Propagação Divisão Erro Absoluto y EA 1 1 y EAx EAy EAx y x y x y x yyy EAy y y y EAyy y EA 1 1 y 1111 Prova em evidência:y Simplificação: (desprezam-se os termos de potência >1) y EA 1 1 y EAx EAy EAx y x y x y x ... y EA y EA y EA 1 y EA 1 1 3 y 2 yy y y EA y EA y x y EA y EAx y x yxyx 11 Análise de Erros – Propagação Divisão Erro Absoluto y EA y EA y x y EA y EAx y x yxyx 11 2 yx y EAx y EA y x y x 2y EAEA y EA y EAx y x y x yxx 2 y muito pequeno 2 yx yx y EAxEAy EA / Análise de Erros – Propagação Divisão Erro Relativo x y y EAxEAy x yEA y x EA ER 2 yx yx yx x/y / / yx yx x/y ERERy EA x EAER Análise de Erros – Propagação Erro Relativo da Adição Soma dos erros relativos de cada parcela, ponderados pela participação de cada parcela no total da soma. Erro Relativo da Subtração Diferença entre os erros relativos do minuendo e do subtraendo, ponderados pela participação de cada parcela no resultado da subtração. yx yER yx xERER yxyx yx yER yx xERER yxyx Análise de Erros – Propagação Erro Relativo da Multiplicação Soma dos erros relativos dos fatores. Erro Relativo da Divisão Diferença entre os erros relativos do dividendo e do divisor yxx.y ERERER yxx/y ERERER Análise de Erros – Propagação Nos erros anteriormente formulados, ainda não consideramos o erro de arredondamento ou truncamento no resultado final A análise completa da propagação do erro é feita considerando-se os erros nas parcelas ou fatores e no resultado de cada operação efetuada Ex.: Dada a soma x+y (x e y representados exatamente), faça o cálculo de ER(x+y) Como x e y são exatamente representados, ERx+y se resume ao Erro Relativo de Arredondamento (RA) no resultado da soma. EAx= EAy = 0, EAx+y = 0 1t yx 102 1RAER RA yx EA ER yxyx Análise de Erros – Propagação RAER yx Análise de Erros – Propagação Sistema de aritmética de ponto flutuante de 4 dígitos, precisão dupla Ex.: Seja x = 0,937 x104, y = 0,1272 x102 e z = 0,231 x101, calcular x+y+z e ER(x+y+z), sabendo que x, y e z estão exatamente representados. Solução: Alinhando as vírgulas decimais ( Alinhar sempre para o maior expoente dentre os operadores ) : x = 0,937000 x104 y = 0,001272 x104 e z = 0,000231 x104 Análise de Erros – Propagação Ex.: Seja x = 0,937 x104, y = 0,1272 x102 e z = 0,231 x 101, calcular x+y+z e ER(x+y+z), sabendo que x, y e z estão exatamente representados. Solução: A soma é feita por partes: (x+y)+z x+y = 0,937000 x104 + 0,001272 x104 x+y = 0,938272 x104 (arredondamento) x+y = 0,9383 x 104 = s s+z = 0,9383 x 104 + 0,000231 x 104 s+z = 0,938531 x 104 (arredondamento) x+y+z = 0,9385 x 104 Análise de Erros – Propagação Solução: s = x+y = então s = x + y = 0,9383 x 104 Cálculo do Erro Relativo: EAx=EAy=0, ERx+y=0syxs RAyx yER yx xERER ss RAER RAERER zszyx RA zs zER zs sERER zszyx Análise de Erros – Propagação Solução: EAz=0, ERz=0RAzyx zER zyx yxERER zszyx RA zyx yxERER szyx 1 zyx yxRA RA zs zER zs sERER zszyx RAzyx yxRAER szyx Análise de Erros – Propagação Solução: 3 zyx 0,9998.10ER 1t zyx 102 11 zyx yxER 3 4 4 109385,0 109383,0 10 2 11ER zyx 1zyx yxRARA zyx yxRAER szyx Análise de Erros – Propagação Ex. : Supondo que u é representado em um computador por ū, que é obtido por arredondamento. Obter os limites superiores para os erros relativos de v = 2ū e w = ū + ū. Análise de Erros – Propagação Ex. : Solução: 1t u 10ER 2 uv 2 RAERERER uu 22 1 2 102 12 tuER RARARA 2 Análise de Erros – Propagação Ex. : Solução: 1t vw 10ERER uuw RA uu uER uu uERER uuw 11 1010 2 122 ttw RAER RA uu uRAERw 2 RA u uRAERw 2 2 RA2 Exercício Considere uma máquina cujo sistema de representação de números é definido por . Tal máquina utiliza o arredondamento para os dígitos na mantissa. Os números x = 8543 e y = 2477 foram utilizados em algumas operações nesta máquina. Assim, faça o que se pede: a) Calcule os erros absolutos (EA) e erros relativos (ER) envolvidos no processo de utilização da máquina para cada número x e y. Resposta: et 3,10 ]5,5[e 444 10513,3100003,010854,0 xx EREAx 344 10210,1100003,010248,0 yyEREAy Exercício Considere uma máquina cujo sistema de representação de números é definido por . Tal máquina utiliza o arredondamento para os dígitos na mantissa. Os números x = 8543 e y = 2477 foram utilizados em algumas operações nesta máquina. Assim, faça o que se pede: b) Após a realização das operações x+y e x*y, foi percebido que uma das duas operações resultava no erro relativo maior. Qual foi? Resposta: Erro da multiplicação é maior et 3,10 ]5,5[e RAER yx 410445,5 RAER yx 410613,15
Compartilhar