Teoria de Erros

Teoria de Erros
Métodos Numéricos e Estatı́sticos
Parte I-Métodos Numéricos
Teoria de Erros
Luı́sa Morgado
Lic. Eng. Biomédica e Bioengenharia-2009/2010
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
O que é a Análise Numérica?
Ramo da Matemática dedicado ao estudo e desenvolvimento de
métodos (métodos numéricos) para a resolução de problemas demasiado complicados ou impossı́veis do ponto de vista analı́tico.
Exemplo
Todos sabemos imediatamente determinar as raı́zes da
equação
x 2 − 2x + 1 = 0.
E da equação
lnx + x + 1 = 0?
R1
0
2xdx = 1 mas como determinar uma primitiva de
Luı́sa Morgado
Teoria de Erros
R
2
e x dx?
Teoria de Erros
Quando recorremos a uma calculadora ou a um computador para
resolver numericamente um dado problema matemático, dois tipos
de erro podem surgir:
Erros de arredondamento: as máquinas, de capacidade
limitada, não conseguem representar todos os números reais;
Erros de truncatura: surgem sempre que se substitui um
problema contı́nuo por um discreto, ou quando se substitui
um processo de cálculo com um número infinito de operações,
por outro com um número finito.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Representação de números inteiros
Um inteiro N 6= 0 com n + 1 dı́gitos é representado na base decimal, univocamente,
por
N
=
± (dn dn−1 . . . d1 d0 )10
=
dn × 10n + dn−1 × 10n−1 + · · · + d1 × 101 + d0 × 100 ,
sendo di um inteiro tal que 0 ≤ di < 10, i = 0, 1, . . . , n, dn 6= 0.
Exemplo
483 = 4 × 102 + 8 × 101 + 3 × 100 = (483)10 .
Se um número inteiro, N 6= 0 está representado numa outra base b, b ≥ 2 que não a
decimal, então
N
=
± (dn dn−1 . . . d1 d0 )b
=
±dn × b n + dn−1 × b n−1 + · · · + d1 × b 1 + d0 × b 0 ,
com 0 ≤ di < b, i = 0, 1, . . . , n, dn 6= 0 e em que as operações no segundo membro
são efectuadas na base 10.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Mudança de base
Mudança da base b para a base 10:
É imediata.
Exemplo
4
3
2
1
0
(10110)2 = 1 × 2 + 0 × 2 + 1 × 2 + 1 × 2 + 0 × 2 = 22.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Mudança de base
Mudança da base 10 para a base b:
Sendo b ≥ 2,
N
d0
= ±dn × b n−1 + dn−1 × b n−2 + · · · + d1 +
,
b
b
|
{z
}
|{z}
Quociente
Resto
i.e., o digito de menor ordem, d0 na representação de N na base b, é o resto da
divisão de N por b. Dividindo o quociente da divisão de N por b, novamente
por b, obtemos o dı́gito d1 que será o resto daı́ resultante, e assim
sucessivamente, até efectuarmos a n-ésima divisão cujo quociente é dn .
Exemplo
22
22
0
|{z}
|2
11
1
|{z}
d0
d1
|2
5
1
|{z}
|2
2
|2
0
|{z}
1
|{z}
d3
d4
(22)10 = (10110)2 .
d2
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Representação de números reais
A representação de um número x ∈ R na base 10 é dada por
x = ± (dn dn−1 . . . d1 d0 .d−1 d−2 . . . d−k )10 ,
e deve ser interpretada por
x = ±dn × 10n + · · · + d1 × 101 + d0 × 100 + d−1 × 10−1 + . . . + d−k × 10−k ,
onde 0 ≤ di < 10, i = 0, . . . , n e 0 ≤ d−j < 10, j = 1, . . . , k.
Analogamente, a representação do real x na base b, b ≥ 2 é definida por
x
=
± (dn dn−1 . . . d1 d0 .d−1 d−2 . . . d−k )b
=
±dn × b n + · · · + d1 × b 1 + d0 × b 0 + d−1 × b −1 + . . . + d−k × b −k ,
onde 0 ≤ di < b, i = 0, . . . , n e 0 ≤ d−j < b, j = 1, . . . , k.
Os dı́gitos dn · · · d1 d0 constituem a parte inteira e os dı́gitos d−1 . . . d−k a parte
fraccionária da representação de x na base b.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Mudança da base b para a base 10
Imediata de acordo com a igualdade anterior!
Exemplo
(11001.01)2
4
3
2
1
0
=
1 × 2 + 1 × 2 + 0 × 2 + 0 × 2 + 1 × 10 + 0 × 2
=
25.25.
−1
+1×2
−2
Seja x um número real representado na base 10. Suponhamos que
pretendemos representá-lo noutra base que não a decimal.
Como a conversão da parte inteira, segue as mesmas regras da
mudança de base de um número inteiro, vamos admitir que x é um
número real com parte inteira igual a zero.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Mudança da base 10 para a base b
Seja
x
= ± (.d−1 d−2 . . . d−k )b
= ±d−1 × b −1 + . . . + d−k × b −k .
Como
bx = ±
d−1
+ d−2 × b −1 . . . + d−k × b −k+1 ,
|{z}
|
{z
}
parte inteira
parte fraccionária
donde d−1 é a parte inteira do resultado.
Se multiplicarmos a parte fraccionária de bx por b, obtemos o
dı́gito d−2 e assim sucessivamente.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Exemplo
Representemos o número 22.8125 na base binária (base 2).
Vimos anteriormente que 22 = (10110)2 .
Representemos então 0.8125 na base 2.
cálculo
cálculo
cálculo
cálculo
de
de
de
de
d−1
d−2
d−3
d−4
0.8125 × 2 = 1.6250
0.6250 × 2 = 1.2500
0.2500 × 2 = 0.5000
0.5000 × 2 = 1.0000
Como no último cálculo, a parte fraccionária é zero, a
representação é finita.
Assim, 0.8125 = (.1101)2 e portanto
22.8125 = (10110.1101)2 .
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Notação cientı́fica ou de vı́rgula flutuante
Nas aplicações cientı́ficas, há a necessidade de recorrer a números
muito grandes e a números muito pequenos, cuja representação
obriga a um grande número de dı́gitos, a maioria dos quais são
zero.
Em notação de vı́rgula flutuante, um número real x, na base b,
com t dı́gitos, pode ser representado por:
x = ±(.d1 d2 . . . dt )b b e ,
di ∈ {0, 1, . . . , b − 1},
onde b é a base, (.d1 d2 . . . dt ) é a mantissa, o expoente, e, é
um inteiro tal que L < e < U, com L e U valores inteiros.
Esta representação diz-se normalizada quando d1 6= 0.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
As representações binária e hexadecimal são as mais utilizadas para fins
computacionais;
Numa representação normalizada, a mantissa é um número que pertence ao
intervalo [b −1 , 1 − b −t ];
O sistema de representação de números reais em vı́rgula flutuante, é então
caracterizado por quatro parâmetros
1
2
3
a base b;
o número t de dı́gitos na mantissa;
o domı́nio de variação do expoente, i.e., L e U;
resumidamente F (b, t, L, U);
O maior número em valor absoluto de F (b, t, L, U) é B = 1 − 5−t b U . Reais
não pertencentes ao intervalo [−B, B] não poderão ser exactamente
representados no sistema de representação F (b, t, L, U);
A gama de valores b, t, L e U possı́vel de representar varia muito consoante a
máquina em questão.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Todo o real x admite a forma normalizada
x = ±0.a1 a2 . . . at at+1 . . . × b e .
A sua representação em F (b, t, L, U) faz-se por arredondamento,
que pode ser efectuado por uma de duas maneiras:
arredondamento por corte: x ' x̄ = ±0.a1 a2 . . . at × b e ;
arredondamento simétrico: soma-se 12 b e−t a x e em seguida
arredonda-se por corte, para t dı́gitos.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Exemplo
No sistema de vı́rgula flutuante F (10, 7, −99, 99)
1
O número π não possui uma representação exacta, pois
π = 3, 14159265 . . . = 0, 314159265 . . . × 101 .
Para o representarmos aproximadamente neste sistema de vı́rgula flutuante,
obterı́amos
π ' 0, 3141592 × 101 (arredondamento por corte);
π ' 0, 3141593 × 101 (arredondamento simétrico);
2
O número 0.5 × 10100 não pode ser representado pois o seu expoente
100 > 99 −→ Overflow;
3
O número 0.5 × 10−100 não pode ser representado pois o seu expoente
−100 < −99 −→ Underflow;
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Valores aproximados e erros
Os erros podem expressar-se em termos absolutos ou relativos.
Seja x uma quantidade exacta e x̄ um valor aproximado de x. A
ex̄ = x − x̄ chama-se erro (cometido na aproximação de x
por x̄);
4x̄ = |ex̄ | = |x − x̄| chama-se erro absoluto;
a rx̄ =
|ex̄ |
|x|
=
4x̄
|x|
chama-se erro relativo.
1
No caso em que ex̄ > 0 ⇔ x > x̄ diz-se que a aproximação é por defeito; no
caso em que ex̄ < 0 ⇔ x < x̄ diz-se que a aproximação é por excesso;
2
Usualmente, na prática x é uma quantidade desconhecida e assim sendo, é
ηx̄
comum fazer-se rx̄ ≈ |x̄|
, onde ηx̄ é um majorante do erro absoluto.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Exemplo
1
Seja x = 0.555 e x̄ = 0.55. Então
4x̄
rx̄
2
= |x − x̄| = |0.555 − 0.55| = 0.005;
0.005
4x̄
=
' 0.009 = 0.9%;
=
x
0.555
Sendo y = 400.65 e ȳ = 400.6 um valor aproximado de y ,
então
4ȳ
rȳ
= |y − ȳ | = |400.675 − 400.67| = 0.005;
4ȳ
0.005
=
=
' 0.00001 = 0.001%;
y
400.675
Tal como este exemplo ilustra, o erro relativo fornece mais informação acerca da
aproximação cometida, pois como se pode ver, embora os erros absolutos sejam
iguais, no segundo caso, o erro relativo é significativamente menor.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Casas decimais correctas e algarismos significativos
Daqui em diante, salvo indicação em contrário, consideramos todas
as quantidades representadas na base 10 na notação normalizada.
Seja x uma quantidade exacta e x̄ um valor aproximado de x.
Dizemos que x̄ tem k casas decimais correctas sse
4x̄ = |x − x̄| ≤ 0.5 × 10−k ;
Dizemos que x̄ tem k algarismos significativos correctos
sse rx̄ ≤ 0.5 × 101−k .
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Exemplo
A aproximação x̄ = 3.14 para x = π tem 2 casas decimais
correctas e 3 algarismos significativos correctos, pois
4x̄
rx̄
= |x − x̄| = 0.001592 . . . = 0.1592 . . . × 10−2 < 0.5 × 10−2
= 0.000506 . . . = 0.0506 . . . × 10−2 < 0.5 × 101−3 ;
Mostre que o valor aproximado 0.0498 para e
−3
tem 4 casas
decimais correctas e 3 algarismos significativos correctos.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Propagação de erros
Experimente numa máquina de calcular, extrair 3 vezes a raı́z
quadrada de 40 e de seguida, elevar 3 vezes o resultado obtido ao
quadrado.
A grande maioria da calculadoras devolve um resultado diferente
de 40!!
Problema de propagação de erros: Se tivermos um valor x̄
que aproxima x, ao calcularmos a imagem por uma função f ,
vamos obter uma valor aproximado f (x̄) diferente de f (x). De
que forma o erro é propagado ao efectuarmos o cálculo de
uma função (ou operação) f num valor aproximado de x,
x̄?
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Seja x̄ um valor aproximado de x. Pela fórmula de Taylor:
f (x)
=
f (x̄) + f 0 (ξ)(x − x̄),
ξ ∈ I{x,x̄}
( intervalo aberto de extremos x e x̄)
0
− x̄}) ⇔ 4f (x̄) = |f 0 (ξ)|4x̄ .
⇔ f (x) − f (x̄) = f (ξ)(x| {z
{z
}
|
ex̄
ef (x̄)
E quando f (x) 6= 0, temos para o erro relativo
4f (x̄) f 0 (ξ) =
4x̄ ⇔ rf (x̄) = f 0 (ξ) x rx̄ f (x) f (x) |{z}
f (x) xrx̄
Supondo x e x̄ muito próximos, é legı́timo considerar
f 0 (ξ) ' f 0 (x), obtendo
4f (x̄) ' f 0 (x) 4x̄
0 xf (x) |rx̄ |
rf (x̄) ' f (x) Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Ao valor
cond(f (x)) =
xf 0 (x)
,
f (x)
dá-se o nome de número de condição de f em x.
Quando o número de condição de uma função f é muito elevado
numa vizinhança de x, então o erro relativo de f (x̄) será muito
grande mesmo que o erro relativo de x̄ seja pequeno.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Fórmulas de propagação do erro (absoluto e relativo)
Seja f = f (x1 , x2 , . . . , xn ) e consideremos que x̄ = (x̄1 , x̄2 , . . . , x̄n )
é um valor aproximado de x = (x1 , x2 , . . . , xn ). Seguindo os
mesmos passos, i.e, começando por utilizar a fórmula de Taylor
(para funções de duas ou mais variáveis), obterı́amos:
4f (x̄)
rf (x̄)
n X
∂f
.
∂xk (x) 4x¯k
k=1
∂f
n
xk
X
∂xk (x) .
|rx¯k |
f (x) k=1
| {z }
números de condição
Nota: Na prática, usualmente, a quantidade x é desconhecida e por isso é comum nas
fórmulas acima substituir x por x̄.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Exemplo
Sejam x̄ e ȳ valores aproximados de x e y , respectivamente.
Considere-se a diferença entre x e y :
D = f (x, y ) = x − y ,
e suponhamos que determinamos uma aproximação de D calculada
a partir dos valores aproximados x̄ e ȳ .
Determinemos um majorante do erro relativo associado a esta
aproximação.
Pela fórmula de propagação do erro relativo, temos
rD̄ ≤
ȳ rȳ
4x̄ + 4ȳ
x̄rx̄
+
≤
|x̄ − ȳ | |x̄ − ȳ |
|x̄ − ȳ |
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Sempre que x̄ e ȳ são números muito próximos, o valor |x̄ − ȳ |
torna-se muito pequeno e consequentemente, o erro relativo vem
demasiado grande (ou seja, a precisão do resultado é muito baixa).
Ao efeito causado pela perda de algarismos significativos quando
se subtraiem quantidades muito próximas, dá-se o nome de
cancelamento subtractivo.
Vejamos um exemplo:
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Exemplo
Dada a função:
f (x) =
cos x − 1
,
x2
2
sabe-se que para valores de x próximos de zero f (x) ≈ − 12 + x24 . Numa calculadora,
obteve-se f (10−16 ) = 0. Como se explica este resultado? Isto ocorre porque para
valores de x próximos de zero, cos x é aproximadamente 1, pelo que cos x − 1 é
aproximadamente zero, o que resulta num erro relativo terrivelmente grande. Isto
acontece sempre que se subtraem quantidades muito próximas para a precisão da
máquina. Para evitar este tipo de problemas e neste caso em particular, podemos:
1
efectuar o desenvolvimento em série de Taylor da função cos x;
2
notar que f (x) =
cos x − 1
cos2 x − 1
sin2 x
= 2
=− 2
. Se
2
x
x (cos x + 1)
x (cos x + 1)
calcularmos, na mesma calculadora, f (10−16 ) usando esta última expressão
obtemos f (10−16 ) = −0.5.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Seja x̄ = (x̄1 , x̄2 , . . . , x̄n ) um valor aproximado de x = (x1 , x2 , . . . , xn ). Suponhamos
que queremos calcular um valor aproximado de f (x), através de f (x̄). Qual a precisão
a considerar para os valores aproximados de x̄1 , x̄2 , . . . , x̄n , por forma a que o valor de
f (x̄), seja obtido com um erro que em valor absoluto não exceda uma quantidade
η > 0, previamente fixada. Pela fórmula de propagação do erro absoluto pretendemos
que:
∂f
∂f
(x̄1 , x̄2 , . . . , x̄n ) |∆x̄1 |+. . .+
(x̄1 , x̄2 , . . . , x̄n ) |∆x̄n | ≤ η
|∆f (x̄1 , x̄2 , . . . , x̄n )| ≤ ∂x̄1
∂x̄n
O problema apresentado desta forma é indeterminado. Na prática, para o resolver,
usa-se um dos dois princı́pios que se seguem:
→ Princı́pio dos erros iguais: Utiliza-se quando todas as quantidades têm as
mesmas unidades e quando os erros são da mesma natureza e ordem de
grandeza 1 , supondo:
k = |∆x̄1 | = . . . = |∆x̄n |.
→ Princı́pio dos efeitos iguais: Supõe-se
∂f
∂f
∂x̄ (x̄1 , x̄2 , . . . , x̄n ) |∆x̄1 | = . . . = ∂x̄ (x̄1 , x̄2 , . . . , x̄n ) |∆x̄n | = k.
n
1
1
Dois números não nulos y e z, dizem-se da mesma ordem de grandeza e escreve-se |y | ≈ |z| se
|y |
0.1 < |z| ≤ 1.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
Condicionamento e estabilidade
A equação quadrática
x2 −
1
1
x+
=0
3
36
tem as raı́zes reais são x1 = x2 = 1/6. Se escrevermos esta mesma equação utilizando
aritmética finita usando 6 c.d.c nas aproximações, obtemos a seguinte equação
x 2 − 0.333333 + 0.027778 = 0
que não tem raı́zes reais.
Um problema tal como este, em que pequenas alterações nos dados produzem grandes
variações no resultado final, diz-se um problema mal condicionado. Se tal não ocorre,
o problema diz-se bem condicionado.
No caso do cálculo de uma função, o mau condicionamento do problema corresponde
ao facto de f ter um número de condição elevado.
Ao usarmos um método numérico para a resolução de um problema mal condicionado,
devemos ter em atenção as aproximações cometidas ao longo da sua execução. Tal
está relacionado com a noção de estabilidade de um método numérico.
Dizemos que um método numérico é estável se a acumulação de erros durante a sua
execução não tem influência significativa no resultado. Quando tal não acontece, o
método diz-se instável.
Luı́sa Morgado
Teoria de Erros
Teoria de Erros
A explosão do Ariane 5
No dia 4 de Junho de 1996, 40 segundos após o seu lançamento, no
centro espacial da Guiana Francesa, o foguetão Ariane 5 explodiu.
Após o inquérito realizado, concluiu-se que a causa do fracasso era
um erro de software no sistema de referência inercial.
Concretamente, um número em vı́rgula flutuante com 64 bits
(relativo à velocidade horizontal do foguetão em relação à
plataforma de lançamento) foi convertido num inteiro de 16 bits.
Esta conversão falhou, pois o número era superior a 32767, o
maior inteiro representável num sistema de 16 bits.
Luı́sa Morgado
Teoria de Erros