PySci 003 Propaga+â º+â úo do erro

Prévia do material em texto

LNCC 
Propagação de erro e a 
Comp. Científica 
Prof. Paulo R. G. Bordoni 
UFRJ 
 
Multiplique o número dado 
sucessivamente por 2, 
colete o 
 “vai 0” ou “vai 1” 
e acrescentando-os a 
0. 
Na aula sobre racionais e reais 
vimos o algoritmo para realizar a 
mudança da representação de um 
número base 10 para a base 2 pode 
ser descrito por: 
0.1 = 0. 
0.1 
∗ 2 
0.2 
0 
0.2 
∗ 2 
0.4 
0 
0.4 
∗ 2 
0.8 
0 
0.8 
∗ 2 
1.6 
1 
0.6 
∗ 2 
1.2 
1 
0.2 
∗ 2 
0.4 
0 1... 0 1 
Lá, fiz um exemplo de como 
converter 
0.3 para a base 2. 
 Vou repeti-lo para x = 0.1. 
x = 0.000110011... = 1.10011001...∗2-4 
O 1º passo para a obter a 
representação IEEE 754, 
padrão Single (32 bits), do x 
consiste em normalizá-lo: 
O 2º passo verifica se o expoente de x, exp , 
está na faixa normal: -127 < exp < 128. 
Nesse caso, a fração F de x será constituída 
pelos 23 bits após o 1. e, em seguida, 
truncada (*). 
Ou arredondada, ou ... 
Em “Racionais e reais ”, vimos que 80% 
dos números decimais 
com apenas 1 dígito após a vírgula geram 
dízimas periódicas na base 2 
0.0 
0.1 
0.2 
0.3 
0.4 
0.5 
0.6 
0.7 
0.8 
0.9 
Este programa faz a mudança de 
base para os números 
0.0, 0.1, ..., 0.9. 
Confirme os erros de 
conversão. 
 
 1.00000000000000000000001 
 
 
Observe que 1+ε é o próximo número que 
existe após o 1 na representação IEEE 754. 
Em outras palavras, ε é a distância entre 
esses dois números. 
4 8 12 16 20 23 
posição 
Define-se ε = 2-23. 
Por tradição ele é chamado 
épsilon da máquina. 
Professora, se o épsilon da máquina é 
corresponde a 24 dígitos de precisão 
na fração (base 2). 
Quantos dígitos serão na base 10 ? 
É só resolver a equação: 
2-24 = 10-X 
 x = 24∗ log10 2 
 = 24∗ 0.301030 
 = 7.22472 
 ≅ 7 dígitos 
 Δ = 0.000000000000000000000001111... 
4 8 12 16 20 
23 
posição 
Seja Δ o número abaixo, : 
 Δ = ( 2-24 + 2-25 + 2-26 ...) 
 = 2-24 ( 1 + ½ + ¼ + ... ) 
 = 2-24 ∗2 
 = 2-23 Fazendo as contas, 
descobrimos que Δ = ε 
Se x* é uma aproximação para x, o erro 
absoluto E cometido ao aproximar 
x por x* é E = | x - x*| 
O erro relativo Er é 
Er = E/x 
quando x ≠ 0 
Ao truncar a fração F de x = 0.1 após o 
23 bit, estamos cometendo um erro 
absoluto E, satisfazendo 
E < ε ∗ 2-4 
Para qualquer x no padrão IEEE 754 
define-se ULP(x) por 
ULP(x) = ε ∗ 2-exp(x) 
ULP é uma abreviatura para 
Unit in the Last Position of x 
Er = |x – x*|/x < ε 
Ao truncar a fração F de x = 0.1 após o 23 bit, 
estamos cometendo um erro relativo Er, 
satisfazendo 
Er < ε. 
Isto vale para a representação 
x* qualquer número real x 
na faixa normal da representação 
Single do padrão IEEE 754 
Este programa exibe tais 
erros de aproximação. 
Veja: 
0.0 
0.1 
0.2 
0.3 
0.4 
0.5 
0.6 
0.7 
0.8 
0.9 
80% 
0.00 
0.01 
... 
0.24 
0.25 
0.26 
... 
0.49 
0.50 
0.51 
... 
0.74 
0.75 
0.76 
... 
0.99 
96% 
0.000 
0.001 
... 
0.124 
0.125 
0.126 
... 
0.499 
0.500 
0.501 
... 
0.874 
0.875 
0.876 
... 
0.999 
99.2% 
0.0000000 
0.0000001 
... 
0.xxxxxxx 
0.xxxxxxx 
0.xxxxxxx 
... 
0.4999999 
0.5000000 
0.5000001 
... 
0.xxxxxxx 
0.xxxxxxx 
0.xxxxxxx 
... 
0.9999999 
99.9936% 
Já vimos que grande 
maioria gera dízima s na 
base 2. 
O programa a calcula o 
“epsolon da máquina”. 
Eis seu resultado! 
Em Double, que é o 
padrão de Python. 
Já informamos que a 
consequência é funesta para o 
cálculo de funções ... 
y x 
x 
x* 
Y = f(x) 
y* = f(x*) f 
f 
O que é realmente calculado 
ao avaliar uma função no computador 
(IEEE 754) ... 
y x 
x 
x* 
Y = f(x) 
y* = f(x*) f 
f 
O fator de ampliação 
| y* - y | / |x* - x | 
é denominado 
número de condicionamento de f em x 
e anotado Condf (x) 
Quando ele é grande, a 
função é dita “mal 
condicionada em x” 
Uma outra consequência é 
que a adição, no computador, 
deixa de ser associativa! 
É o que mostra este 
programa. 
A continuação do programa. 
Veja os resultados! 
Eis aí um problema 
com a divisão! 
y x 
x 
x* 
Y = f(x) 
y* = f(x*) f 
f 
Quando dois números x e y são muito 
próximos, sua diferença x* - y*, em ponto 
flutuante, pode não significar NADA! 
Ela fica poluída pelos erros. 
Na literatura, tal fato é conhecido 
como cancelamento catastrófico. 
Veremos um belo exemplo ao lidar com 
aproximações para derivadas. 
y x 
x 
x* 
Y = f(x) 
y* = f(x*) f 
f 
A multiplicação de um número x por um 
número y muito grande (mesmo que y não 
tenha erro), amplia muito o erro no produto 
x* ∗ y* 
A multiplicação é mal 
condicionada quando um 
dos fatores é grande. 
y x 
x 
x* 
Y = f(x) 
y* = f(x*) f 
f 
Pense comigo: 
como x * já possui um erro da ordem de 10-7 
(com 99.99% de certeza) 
então, ao multiplicá-lo por 1000 
o erro passará a ser da ordem de 10-4. 
y x 
x 
x* 
Y = f(x) 
y* = f(x*) f 
f 
O mesmo se aplica para 
divisão por números muito 
pequenos. 
A divisão é mal 
condicionada quando um o 
divisor é muito pequeno. 
Algo mais sofisticado 
envolvendo o cálculo de 
derivadas ... 
Sua continuação ... 
Um problema clássico de 
Computação Científica é a 
resolução de equações. 
Se f: (a,b) ⊂ ℝ ⟶ ℝ, 
é uma função dada pela expressão 
y = f(x), 
muitas vezes desejamos obter 
(se houver) aquele valor de x ∊ (a,b) 
(ou aqueles) para o qual 
f(x) = 0. 
Quando, por exemplo, 
queremos saber o valor de 2, 
desejamos obter x para o 
qual 𝑥2 = 2. 
Um outro exemplo: 
descobrir aqueles valores de x 
(se houver algum) para os quais 
3𝑥3 − 5𝑥2 + 2 = 0 
Uma forma de resolver equações do tipo 
f(x) = 0 é através de 
métodos iterativos. 
Assuma que r é uma raiz dessa equação. 
Então f(r) = 0. 
Um método iterativo para achar r 
envolve a criação de uma 
sequência x0, x1, x2, ..., xK, ... 
que converge para r. 
Diremos que um elemento xN dessa sequência 
aproxima r com erro menor que ε 
quando | xN – r | < ε . 
Um outro teste é verificar se |f(xN )| < ε . 
Então, na prática, usamos xN como a raiz. 
Nos métodos iterativos, cada elemento 
xK+1 é obtido do anterior xK via uma 
equação de iteração. 
Iniciamos com um valor arbitrário x0, 
o “chute inicial’. 
Um método importante ara achar raízes de 
equações é o de Newton-Rhapson. 
 Nele: 
xK+1 = xK – f(xK) / f ’ (xK), k = 0, 1, 2, ... 
x0 escolhido arbitrariamente 
No caso de 2, temos f(x) =x 2 -2 
e a equação de iteração fica: 
xK+1 = xK – (xK2- 2) / 2xK, k = 0, 1, 2, ... 
x0 = 2 
Eis um programinha 
para calcular a raiz 
quadrada de um 
número. 
O resultado. 
Outro exemplo. 
Observe que a 
quantidade de iterações 
depende de x. 
Vamos mostrar uma aplicação do 
Método de Newton-Raphson 
envolvendo as raízes sextuplas da 
unidade no plano complexo: 
z6+1 = 0. 
Vamos construir uma linda fractal 
pintando o quadrado [0,1]x[0,1] do 
plano complexo com 6 cores. 
Uma cor para cada raiz da unidade 
Este programa 
mostra as 
propriedades das 
raízes da unidade. 
Confira: 
Novamente: 
Dividiremos o quadrado complexo em 
800x800 pixeis. Cada pixel será um 
chute inicialpara o método, assim 
teremos 640.000 chutes iniciais. 
Cada um deles receberá a cor 
corresponde à raiz para qual o método 
convergir, graduado pelo número de 
iterações. 
Limitaremos a 30 o número de iterações. 
O código do programa é o 
seguinte: 
Continuação do código: 
Veja como ela é 
linda! 
Parece uma joia!! 
Tchau, até a 
próxima aula!