Computação em Precisão Finita

Prévia do material em texto

Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Computac¸a˜o em precisa˜o finita
Ricardo Biloti
Ca´lculo Nume´rico
Vera˜o, 2012
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Erros
Se x e´ uma quantidade nume´rica e xˆ sua aproximac¸a˜o, enta˜o
Eabs(xˆ) = |x − xˆ |
Erel (xˆ) =
|x − xˆ |
|x | , (x 6= 0)
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Repare que no ca´lculo do erro absoluto e do erro relativo sempre e´ necessa´rio conhecer
x . Ou seja, para medir se uma aproximac¸a˜o e´ boa ou na˜o e´ necessa´rio compara-la com
o valor exato. Pore´m, em geral procuramos aproximac¸o˜es quando na˜o conhecemos o
valor exato. Como enta˜o medir o erro de uma aproximac¸a˜o? Em problemas pra´ticos
isto nem sempre e´ de fato poss´ıvel.
Va´rios me´todos nume´ricos contudo fornecem estimativas para o erro absoluto e/ou
relativo das aproximac¸o˜es que produzem.
Quando se deparar com um me´todo nume´rico ou com uma aproximac¸a˜o nume´rica,
voceˆ deve sempre se perguntar se e´ poss´ıvel fornecer ou se e´ conhecida uma estimativa
para o erro. Do contra´rio, como julgar a qualidade da aproximac¸a˜o?
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Exemplo
I x = 1.00000, e xˆ = 1.00499
Eabs(xˆ) = 4.99 · 10−3 Erel (xˆ) = 4.99 · 10−3
I x = 9.00000, e xˆ = 8.99895
Eabs(xˆ) = 1.05 · 10−3 Erel (xˆ) = 1.16 · 10−4
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Um erro absoluto de mesma ordem pode ser mais ou menos significativo dependendo
das grandezas envolvidas. Por exemplo, para quem quer comprar uma toalha de mesa,
um metro a menos ou a mais faz muita diferenc¸a, mas para quem esta´ interessado na
distaˆncia entre duas cidades, um erro na casa dos metros e´ desprez´ıvel.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Tipos de erros
I Erros de medic¸a˜o/aquisic¸a˜o
I Erros de representac¸a˜o
I Erros de ca´lculo em precisa˜o finita
I Erros introduzidos por algoritmos nume´ricos
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
• Erros de medic¸a˜o sa˜o inerentes a` aquisic¸a˜o de dados experimentais e na˜o podem
ser evitados, mas apenas minorados. Sa˜o causados por falha humana, de
equipamento, impreciso˜es do experimento, etc.
• Erros de representac¸a˜o sa˜o igualmente inevita´veis. Eles surgem sempre que os
dados do problema sa˜o digitalizados. Dentre todas as fontes de erros, essa e´ a
menos problema´tica. Em geral, erros de representac¸a˜o sa˜o muitas ordens de
magnitude menor que os erros originados por outras causas.
• Erros introduzidos pelo ca´lculo em precisa˜o finita sa˜o o objeto de estudo deste
to´pico do curso. Estudaremos qual o impacto na qualidade das quantidades
calculadas causado pelo fato das contas serem feitas em precisa˜o finita.
• Por fim, ha´ erros introduzidos pelo emprego de me´todos nume´ricos que apenas
aproximam a soluc¸a˜o de um determinado problema. Esta fonte de erro sera´
analizada no decorrer do curso, sempre que um novo me´todo for abordado.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Representac¸a˜o em ponto flutuante
x =
√
2 = 1.41421356237310...
Num sistema de ponto flutuante
xˆ = fl(x) = 0.1414214 · 10+01
I Base: 10
I Mantissa: 0.1414214
I Expoente: 01
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
As treˆs caracter´ısticas que definem um sistema de ponto flutuante sa˜o: (a) a base do
sistema nume´rico, (b) quantos d´ıgitos significativos, ou mantissa, sa˜o armazenados, e
(c) quantos d´ıgitos esta˜o reservados para representar o expoente.
Para evitar multiplas representac¸o˜es para o mesmo nu´mero, convenciona-se que o
primeiro d´ıgito de um nu´mero de ponto flutuante seja sempre zero e o segundo d´ıgito
seja sempre diferente de zero.
Por exemplo, num sistema de ponto flutuante, de base 10, capaz de armazenar 7
d´ıgitos para a mantissa e mais dois d´ıgito para o expoente,
√
2 seria representado como
fl(x) = 0.1414214 · 10+01.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Representac¸a˜o em ponto flutuante
Num sistema de base 10, 5 d´ıgitos para mantissa e 2 para expoente
pi = 3.14159265358979... fl(pi) = 0.31416 · 101
Qual o menor e o maior nu´mero representa´vel em mo´dulo?
0.10000 · 10−99 e 0.99999 · 1099
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Precisa˜o × exatida˜o
Precisa˜o
Erro cometido em operac¸o˜es alge´bricas elementares
Exatida˜o
Erro presente em quantidade aproximadas
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
E´ importante distinguir precisa˜o de exatida˜o. Enquanto que o primeiro termo se refere
a uma propriedade do sistema de ponto flutuante da ma´quina, o segundo termo diz
respeito a` toda estrate´gia utilizada para a ca´lculo da quantidade aproximada.
Dizemos que uma ma´quina e´ muito precisa se os erros em operac¸o˜es como
somas/subtrac¸o˜es e produtos/diviso˜es for pequeno. Ja´ o adjetivo exato se presta a
qualificar algoritmos e na˜o ma´quinas. Um algoritmo para o ca´lculo de tenso˜es em uma
estrutura meta´lica por exemplo envolve milho˜es de operac¸o˜es alge´bricas elementares.
Sua qualidade na˜o e´ determinada apenas pela qualidade com que estas operac¸o˜es sa˜o
executadas.
Por fim, cabe destacar que estes dois termos sa˜o empregados de maneira confusa e
sa˜o muitas vezes intercambiados. O comum e´ que a palavra precisa˜o seja utilizada nos
dois contextos.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Unidade de arredondamento
A unidade de arredondamento e´ o menor nu´mero positivo de ponto
flutuante u tal que
(1 + u) > 1
No padra˜o IEEE
I u ≈ 1.19209 · 10−07 (em precisa˜o simples)
I u ≈ 2.22045 · 10−16 (em precisa˜o dupla)
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
O padra˜o IEEE-754-1985, Standard for Binary Floating-Point Arithmetic, e´ aplamente
adotado por fabricantes de processadores. Este padra˜o normatiza o sistema de ponto
flutuante implementado em processadores.
A diferenc¸a entre precisa˜o simples e precisa˜o dupla e´ o espac¸o utilizado para o
armazenamento do nu´mero de ponto flutuante. Em precisa˜o simples sa˜o utilizados 32
bits, enquanto que 64 bits sa˜o necessa´rios para a representac¸a˜o em precisa˜o dupla. O
esquema abaixo descreve como esses bits sa˜o distribu´ıdos para representar a mantissa
(f ) e o expoente (e), ale´m do sinal (s) de um nu´mero de ponto flutuante.
1 8 23
Precisa˜o simples: s e f
1 11 52
Precisa˜o dupla: s e f
A unidade de arredondamento, assim como outras quantidades como os maiores e
menores nu´meros representa´veis, e os resultados esperados de ac¸o˜es como
arredondamentos, truncamentos, etc, sa˜o propriedades do sistema de ponto flutuante.
Steve Hollash escreveu um bom texto introduto´rio de sobre o padra˜o IEEE-754-1985
(http://steve.hollasch.net/cgindex/coding/ieeefloat.html).
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Precisa˜o 6⇒ exatida˜o
Alta precisa˜o na˜o e´ suficiente para garantir resultados exatos
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
O importante e´ ter em mente que ma´quinas muito precisas na˜o bastam para obter
resultados exatos.
Via de regra, as ma´quinas atuais sa˜o bem precisas. Mesmo assim, para muitos
problemas e´ dif´ıcil conseguir boas soluc¸o˜es aproximadas.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Erro de cancelamento
Sistema de ponto flutuante com cinco d´ıgitos significativos
Queremos calcular
49213 + 31.728− 49244 = 0.728
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Para efeito de exposic¸a˜o, vamos considerar um sistema de ponto flutuante simples
(SPFS) capaz de representar apenas os cinco d´ıgitos mais significativos de um nu´mero
e um u´nico d´ıgito para expoente. Neste SPFS, a unidadede arredondamento e´
u = 10−4.
Vamos analisar a seguinte conta simples:
49213 + 31.728− 49244 = 0.728
Repare que todos os nu´mero envolvidos sa˜o representados corretamente no nosso
sistema de ponto flutuante simplificado.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Erro de cancelamento
49213 + 31.728− 49244 = 0.728
49213
+ 31.728
49244.728
fl(49213 + 31.728) = 49245
fl(49245− 49244) = 1
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
As operac¸o˜es sa˜o realizadas da esquerda para a direita. A primeira soma e´ feita e o
resultado e´ um nu´mero com oito d´ıgitos significativos. Sendo assim, apenas o cinco
mais significativos sa˜o preservados em nosso sistema de ponto flutuante.
A notac¸a˜o fl(x) significa a representac¸a˜o de ponto flutuante de x .
A conta e´ conclu´ıda com a subtrac¸a˜o de 49244 de 49245, cujo resultado exato 1 e´
corretamente obtido.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Erro de cancelamento
x = 49213 + 31.728− 49244 = 0.728
xˆ = fl(49213 + 31.728− 49244) = 1
Erel (xˆ) = 0.374 > 10
−4
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Neste exemplo o valor correto x deveria ser 0.728, enquanto que o valor obtido foi 1.
O erro relativo nesta aproximac¸a˜o e´ 0.374, bem maior que o erro embutido nas
operac¸o˜es alge´bricas elementares executadas.
A u´nica conta realizada com erro foi a adic¸a˜o inicial. Pore´m o erro relativo naquela
operac¸a˜o foi pequeno
|49245− 49244.728|
49244.728
= 5.52 · 10−6,
o que e´ compat´ıvel com o sistema de ponto flutuante simples. Entretanto o erro
relativo da aproximac¸a˜o como um todo e´ bem maior:
|1− 0.728|
0.728
= 3.74 · 10−1.
Como isto e´ poss´ıvel? Onde este erro grosseiro foi originado?
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Perda de d´ıgitos
Treˆs d´ıgitos significativos perdidos
49213
+ 31.728
49244.728
fl(49213 + 31.728) = 49213 + 32 = 49245
A subtrac¸a˜o foi exata
fl(49245− 49244) = 1
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
O problema surgiu na adic¸a˜o inicial. O resultado nume´rico daquela operac¸a˜o so´ pode
preservar os cinco d´ıgitos mais significativos dos oito d´ıgitos que compunham o
resultado exato. Isso na˜o e´ um problema para a adic¸a˜o em si. De fato, o erro relativo
nesta operac¸a˜o foi de 5.52 · 10−6, menor que a unidade de arredondamento do SPFS.
Entretanto aqueles treˆs d´ıgitos perdidos, que na˜o eram importantes para o resultado
da adic¸a˜o, passaram a ser importantes quando a subtrac¸a˜o seguinte foi executada.
Na subtrac¸a˜o, todos aqueles cinco d´ıgitos mais significativos foram cancelados. Os
treˆs d´ıgitos perdidos seriam enta˜o novamente necessa´rios, pore´m na˜o ha´ mais como
recupera-los.
Neste sentido, a subtrac¸a˜o apenas evidenciou um problema que foi gerado pela perda
de d´ıgitos significativos em um passo anterior.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Exerc´ıcio
Para que valores de x e y , as expresso˜es abaixo podem sofrer por
erros de cancelamento?
Reescreva as expresso˜es abaixo de maneira a reduzir poss´ıveis erros.
1.
√
x2 + 1− x
2. log x − log y
3.
√
1 + x − 1
4. (1− cos x)/ sin x
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
A ide´ia para este exerc´ıcio e´ procurar uma forma de rescrever as expresso˜es de maneira
a evitar o cancelamento de d´ıgitos.
Por exemplo, no caso de log x − log y , se x ≈ y , enta˜o log x ≈ log y , e portanto a
subtrac¸a˜o destas quantidades implicara´ no cancelamento de d´ıgitos significativos.
Esta expressa˜o pode pore´m ser reescrita como
log x − log y = log(x/y)
que na˜o sofre de cancelamento uma vez que na˜o ha´ a subtrac¸a˜o de quantidades
pro´ximas.
Por exemplo, se x = 5 · 104 e y = x + 10−10 enta˜o log(x)− log(y) = −1.7764 · 10−15,
enquanto que log(x/y) = −1.9984 · 10−15. O erro relativo, assumindo que a segunda
expressa˜o e´ mais exata, e´ 1.11 · 10−1.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Equac¸a˜o quadra´tica
Problema
Encontrar as duas ra´ızes reais de
x2 − bx + c = 0
Se b2 − 4c ≥ 0,
r =
b ±√b2 − 4c
2
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Vamos considerar agora o problema de encontrar as ra´ızes de uma equac¸a˜o quadra´tica.
Sabemos que exite fo´rmula fechada para as ra´ızes desta equac¸a˜o. Enta˜o basta
utiliza-la.
Apenas por convenieˆncia, vamos normaliza a equac¸a˜o de maneira que o termo
quadra´tico tenha coeficiente 1.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Equac¸a˜o quadra´tica
x2 − bx + c = 0
b = 4.7379100021 c = 0.0016199351
r1 = 4.7375680682... r2 = 0.0003419340...
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Para usar de exemplo, consideremos os coeficientes b e c dados. r1 e r2 sa˜o duas
ra´ızes desta equac¸a˜o (todos os d´ıgitos exibidos esta˜o corretos).
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Sequ¨eˆncia de ca´lculo
r =
b −√b2 − 4c
2
b = 4.7379100021 c = 0.0016199351
1. b2 = 2.2448 · 10+1
2. 4c = 6.4797 · 10−3
3. b2 − 4c = 2.2442 · 10+1
4.
√
b2 − 4c = 4.7373 · 10+0
5. b −√b2 − 4c = 6.0000 · 10−4
6. (b −√b2 − 4c)/2 = 3.0000 · 10−4
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Vejamos a sequ¨eˆncia de ca´lculo necessa´ria para o compto da menor ra´ız. Todas as
operac¸o˜es esta˜o sendo feitas no nosso sistema de ponto flutuante simplificado.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Erro
Erel (rˆ2) =
|3.0000 · 10−4 − 3.4193 · 10−4|
3.4193 · 10−4 = 1.2263 · 10
−1
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
O erro relativo foi bem superior a` unidade de arredondamento do SPFS (que mensura
o erro relativo nas operac¸o˜es elementares).
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Sequ¨eˆncia de ca´lculo
r =
b −√b2 − 4c
2
b = 4.7379100021 c = 0.0016199351
1. b2 = 2.2448 · 10+1
2. 4c = 6.4797 · 10−3
3. b2 − 4c = 2.2442 · 10+1
4.
√
b2 − 4c = 4.7373 · 10+0
5. b −√b2 − 4c = 6.0000 · 10−4
6. (b −√b2 − 4c)/2 = 3.0000 · 10−4
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Sequ¨eˆncia de ca´lculo
r =
b −√b2 − 4c
2
b = 4.7379100021 c = 0.0015
1. b2 = 2.2448 · 10+1
2. 4c = 6.0000 · 10−3
3. b2 − 4c = 2.2442 · 10+1
4.
√
b2 − 4c = 4.7373 · 10+0
5. b −√b2 − 4c = 6.0000 · 10−4
6. (b −√b2 − 4c)/2 = 3.0000 · 10−4
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
De fato, repare que o valor encontrado para a ra´ız seria o mesmo se, ao inve´s de
utilizar 1.6199 · 10−3 para c, tive´ssemos utilizado c = 1.5 · 10−3. Ou seja, quatro
d´ıgitos significativos de c foram perdidos no decorrer das operac¸o˜es. Esta perda so´ foi
sentida no passo 5, quando a subtrac¸a˜o cancelou os d´ıgitos mais significativos e
aqueles anteriormente perdidos passariam a ser novamente importantes.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Maior raiz
r =
b +
√
b2 − 4c
2
b = 4.7379100021 c = 0.0016199351
1. b2 = 2.2448 · 10+1
2. 4c = 6.4797 · 10−3
3. b2 − 4c = 2.2442 · 10+1
4.
√
b2 − 4c = 4.7373 · 10+0
5. b +
√
b2 − 4c = 9.4752 · 10+0
6. (b +
√
b2 − 4c)/2 = 4.7376 · 10+0
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Se ao inve´s de calcular a menor ra´ız, calcula´ssemos a maior, o passo 5 seria uma
adic¸a˜o ao inve´s de uma subtrac¸a˜o, e na˜o haveria mais a necessidade de manter os
d´ıgitos perdidos no passo 3.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Erro
Erel (rˆ1) =
|4.7376− 4.7375680682|
4.7375680682
= 6.74 · 10−6
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Veja que o erro relativo no compto da maior ra´ız e´ bem menor, e compat´ıvel com o
erro de arredondamento do SPFS.
Como fazer para estimar enta˜o a menor ra´ız?
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´ticaSomas infinitas
Segunda raiz
r2 =
c
r1
= 3.4193 · 10−4 Erel (rˆ2) = 1.1600 · 10−5
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Um alternativa inteligente e´ trocar o algoritmo para o ca´lculo desta ra´ız. Utilizando a
relac¸a˜o r1r2 = c, podemos calcular a maior ra´ız sem fazer qualquer subtrac¸a˜o que
evidenciaria uma perda de d´ıgitos significativos anterior.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Estrate´gia
r1 =
b + sign(b)
√
b2 − 4c
2
r2 =
c
r1
Problemas
I b2 ≈ 4c
I overflow ou underflow em b2
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
A melhor estrate´gia enta˜o seria sempre calcular primeiro a ra´ız que na˜o tem problema
com cancelamento de d´ıgitos. A outra ra´ız seria calculada atrave´s da relac¸a˜o r1r2 = c.
Isto e´ o melhor que pode ser feito com esta expressa˜o para as ra´ızes de uma equac¸a˜o
quadra´tica. Entretanto isto ainda na˜o resolve todos os problemas.
Se b2 ≈ 4c ainda havera´ cancelamento de d´ıgitos significativos que na˜o pode ser
evitado. Por fim, o ca´lculo de b2 ainda pode apresentar overflow ou underflow.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Somas infinitas
Perda de d´ıgitos significativos podem ocorrer sem que haja
cancelamento.
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Vamos analisar um caso em que na˜o ha´ qualquer subtrac¸a˜o de nu´meros pro´ximos,
mesmo assim ha´ perda de d´ıgitos significativos. Ou seja, na˜o basta evitar a subtrac¸a˜o
de nu´meros pro´ximos para evitar a perda de d´ıgitos.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Exemplo
Considere a soma
S =
∞∑
k=1
1
k2
=
pi2
6
Computacionalmente
S ≈ SN =
N∑
k=1
1
k2
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Computacionalmente, na˜o podemos somar infinitos termos. Por isto, fixamos um certo
N e realizamos a soma ate´ este ı´ndice. Em tese, qua˜o maior for N melhor e´ a
aproximac¸a˜o de S por SN .
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Exemplo
Algoritmo
I k ← 2, s ← 1
I enquanto k ≤ N,
I s ← s + 1/k2
I k ← k + 1
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
O algoritmo mais simples e intuitivo para realizar esta soma computacionalmente
acumula parcela por parcela os termos da soma.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Exemplo
s = S4095 = 1.64472532 . . .
Para k = 4096,
S4096 = fl(s + 1/4096
2) = fl(s + 2−24)
= fl
(
s
(
1 +
2−24
s
))
= s fl
(
1 +
2−24
s
)
2−24
s
≈ 3.5804 · 10−8 < 1.1920 · 10−7 ≈ u
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Depois de somadas 4095 parcelas, temos que s = S4095 = 1.64472532 . . .. A soma
parcial seguinte, S4096, e´ calculada como
S4096 = fl(S4095 + 1/4096
2).
Como s ja´ e´ um nu´mero de ponto flutuante, fl(s) = s e como fl(s · p) = fl(s) fl(p),
temos que
S4096 = s fl
(
1 +
2−24
s
)
.
Pore´m, como 2−24/s e´ menor que a unidade de arredondamento (em precisa˜o
simples), a soma desta quantidade com 1 resulta em 1, e portanto a soma na˜o se
altera: S4096 = S4095.
O problema aqui e´ que o termo 1/40962 e´ muito pequeno em comparac¸a˜o com S4095 e
portanto a sua soma e´ desprez´ıvel dentro do sistema de ponto flutuante.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Perda de d´ıgitos
A perda de d´ıgitos ocorre quando somamos nu´meros de grandezas
muito distintas.
Soluc¸a˜o
I k ← N, s ← 0
I enquanto k ≥ 1,
I s ← s + 1/k2
I k ← k − 1
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
A alternativa e´ acumular as parcelas na ordem inversa. Desta forma, cada nova
parcela (maior) sempre sera´ somada a um valor acumulado tambe´m crescente, na˜o
havendo a disparidade de grandezas que acontece no algoritmo ingeˆnuo.
Introduc¸a˜o Cancelamento Equac¸a˜o quadra´tica Somas infinitas
Comparac¸a˜o
0 4 8 12 16 20 24 28
n
1e-10
1e-08
1e-06
1e-04
1e-02
1
lo
g 
(er
ro)
Ordem crescente
Ordem decrescente
http://goo.gl/tj2oD Ricardo Biloti Computac¸a˜o em precisa˜o finita
Neste gra´fico exibimos o erro
∣∣∣SN − pi26 ∣∣∣, para N = 2n, calculado pelo algoritmo
crescente (ingeˆnuo) como c´ırculos e calculado pelo algoritmo decrescente (ordem
inversa) como quadrados. Enquanto que o erro se reduz apenas ate´ N = 212 = 4096
no algoritmo ingeˆnuo, no algoritmo decrescente e´ poss´ıvel chegar perto da precisa˜o da
ma´quina. Note que as contas foram feitas em precisa˜o simples.
	Introdução
	Cancelamento
	Equação quadrática
	Somas infinitas