Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Computa¸c˜ao em precis˜ao finita Ricardo Biloti
[email protected]
C´ alculo Num´erico – UNICAMP
1S/2017 http://goo.gl/tj2oD
http://goo.gl/tj2oD
Introdu¸c˜ ao
Ricardo Biloti
Cancelamento
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Seus direitos e deveres s˜ ao: • Vocˆ e´ e livre para copiar e redistribuir este material, em qualquer meio ou formato, para adapt´ a-lo, transform´ a-lo ou utiliz´ a-lo para construir seu pr´ oprio material.
Licen¸ca
• Vocˆ e deve dar os cr´ editos apropriados, fornecendo link para a licen¸ca e indicando se altera¸co ˜es foram feitas. Vocˆ e pode fazer isto de qualquer forma razo´ avel, por´ em sem tentar passar a ideia ou sugerir que o autor endosse suas altera¸c˜ oes ou seu uso do material. • Vocˆ e n˜ ao pode utilizar este material para fins comerciais. • Se vocˆ e alterar, transformar ou construir seu pr´ oprio material com base neste trabalho, vocˆ e dever´ a distribu´ı-lo sob a mesma licen¸ca usada no original.
Este trabalho ´ e licenciado sob os termos da Licen¸ca Internacional Creative Commons Atribui¸c˜ ao-N˜ aoComercial-CompartilhaIgual 4.0. Para ver uma c´ opia desta licen¸ca, visite http://creativecommons.org/licenses/by-nc-sa/4.0/.
http://goo.gl/tj2oD
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Erros
Repare que no c´ alculo do erro absoluto e do erro relativo sempre ´ e necess´ ario conhecer x. Ou seja, para medir se uma aproxima¸c˜ ao ´ e boa ou n˜ ao ´ e necess´ ario compar´ a-la com o valor exato. Por´ em, em geral procuramos aproxima¸co ˜es quando n˜ ao conhecemos o valor exato. Como ent˜ ao medir o erro de uma aproxima¸c˜ ao? Em problemas pr´ aticos isto nem sempre ´ e de fato poss´ıvel. V´ arios m´ etodos num´ ericos contudo fornecem estimativas para o erro absoluto e/ou relativo das aproxima¸c˜ oes que produzem.
Se x ´e uma quantidade num´erica e xˆ sua aproxima¸c˜ao, ent˜ao Quando se deparar com um m´ etodo num´ erico ou com uma aproxima¸c˜ ao num´ erica, vocˆ e deve sempre se perguntar se ´ e poss´ıvel fornecer ou se ´ e conhecida uma estimativa para o erro. Do contr´ ario, como julgar a qualidade da aproxima¸c˜ ao?
Eabs (ˆ x ) = |x − xˆ| Erel (ˆ x) =
|x − xˆ| , |x|
Eadm (ˆ x) =
|x − xˆ| L
Tamb´ em ´ e usual (e mais vi´ avel) adimensionalizar o erro absoluto utilizando para isso uma dimens˜ ao caracter´ıstica do problema. Por exemplo, se o problema for estimar a distˆ ancia entre duas cidades pr´ oximas, uma dimens˜ ao caracter´ıstica razo´ avel seria L = 1 km. Se o problema for estimar a popula¸c˜ ao de um pa´ıs, L = 1 milh˜ ao de habitantes faz sentido. J´ a para trabalhar com a altura de pessoas L poderia ser escolhido como 1.70 m.
(x 6= 0)
onde L ´e uma dimens˜ao caracter´ıstica do problema.
http://goo.gl/tj2oD
Introdu¸c˜ ao
Ricardo Biloti
Cancelamento
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Exemplo
Norma Euclidiana
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 diferen¸ca, mas para quem est´ a interessado na distˆ ancia entre duas cidades, um erro na casa dos metros ´ e desprez´ıvel. No exemplo dado, apesar dos erros absolutos serem da mesma ordem (≈ 10−3 ), os erros relativos s˜ ao de ordens diferentes. Isto permite concluir que no segudo caso a aproxima¸c˜ ao ´ e melhor que no primeiro caso.
I
x = 1.00000, e xˆ = 1.00499 Eabs (ˆ x ) = 4.99 · 10−3
I
Erel (ˆ x ) = 4.99 · 10−3
x = 9.00000, e xˆ = 8.99501 Eabs (ˆ x ) = 4.99 · 10−3
http://goo.gl/tj2oD
Ricardo Biloti
Erel (ˆ x ) = 5.54 · 10−4
Computa¸c˜ ao em precis˜ ao finita
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Tipos de erros
• Erros de representa¸c˜ ao s˜ ao igualmente inevit´ aveis. Eles surgem sempre que os dados do problema s˜ ao digitalizados. Dentre todas as fontes de erros, essa ´ e a menos problem´ atica. Em geral, erros de representa¸c˜ ao s˜ ao muitas ordens de magnitude menor que os erros originados por outras causas. • Erros introduzidos pelo c´ alculo em precis˜ ao finita s˜ ao o objeto de estudo deste t´ opico do curso. Estudaremos qual o impacto na qualidade das quantidades calculadas causado pelo fato das contas serem feitas em no computador.
I
Erros de medi¸c˜ao/aquisi¸c˜ao
I
Erros de representa¸c˜ao
I
Erros de c´alculo em precis˜ao finita
I
Erros introduzidos por algoritmos num´ericos
http://goo.gl/tj2oD
Introdu¸c˜ ao
Ricardo Biloti
Cancelamento
• Por fim, h´ a erros introduzidos pelo emprego de m´ etodos num´ ericos que apenas aproximam a solu¸c˜ ao de um determinado problema. Esta fonte de erro ser´ a analizada no decorrer do curso, sempre que um novo m´ etodo for abordado.
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Representa¸c˜ao em ponto flutuante
x=
√
2 = 1.41421356237310...
xˆ = fl(x) = 0.1414214 · 10+01 I
Base: 10
I
Mantissa: 0.1414214
I
Expoente: 01
Ricardo Biloti
Norma Euclidiana
As quatro caracter´ısticas que definem um sistema de ponto flutuante s˜ ao: (a) a base do sistema num´ erico, (b) quantos d´ıgitos significativos, ou mantissa, s˜ ao armazenados, (c) qual o menor expoente represent´ avel, e (d) qual o maior expoente represent´ avel. Para evitar m´ ultiplas representa¸c˜ oes para o mesmo n´ umero, convenciona-se que o primeiro d´ıgito de um n´ umero de ponto flutuante seja sempre zero e o segundo d´ıgito seja sempre diferente de zero. Do contr´ ario o n´ umero 1.3 por exemplo poder´ıa tanto ser representado como 0.13000 · 101 como 0.01300 · 102 ou como 0.00130 · 103 , e assim por diante. Por exemplo, num sistema de ponto flutuante, de base 10, capaz de armazenar 7 d´ıgitos para √ a mantissa e expoentes entre −99 e 99, 2 seria representado como fl(x) = 0.1414214 · 10+01 ,
Num sistema de ponto flutuante
http://goo.gl/tj2oD
• Erros de medi¸c˜ ao s˜ ao inerentes ` a aquisi¸c˜ ao de dados experimentais, podendos ser apenas minorados, mas nunca evitados. S˜ ao causados por falha humana, de equipamento, imprecis˜ oes do experimento, etc.
Computa¸c˜ ao em precis˜ ao finita
onde fl(x) ´ e a nota¸c˜ ao para a representa¸c˜ ao de ponto flutuante do n´ umero x. No computadores atuais, o usual ´ e que o sistema de ponto flutuante utilize base 2, armazene 52 bits (52 d´ıgitos bin´ arios), e aceite expoentes entre −1022 e 1023.
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
No sistema de ponto flutuante descrito, qual seria a menor e a maior distˆ ancia entre dois n´ umeros consecutivos represent´ aveis?
Exemplos
Num sistema de base 10, 5 d´ıgitos para mantissa e 2 para expoente fl(π) = 0.31416 · 101
π = 3.14159265358979...
Qual o menor e o maior n´ umero represent´avel em m´odulo? 0.10000 · 10−99
http://goo.gl/tj2oD
Introdu¸c˜ ao
Cancelamento
Ricardo Biloti
0.99999 · 1099
e
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Precis˜ao × acur´acia
´ importante distinguir precis˜ E ao de acur´ acia. Enquanto que o primeiro termo se refere a uma propriedade do sistema de ponto flutuante da m´ aquina, o segundo termo diz respeito ` a toda estrat´ egia utilizada para a c´ alculo da quantidade aproximada. Dizemos que uma m´ aquina ´ e muito precisa se os erros em opera¸c˜ oes como somas/subtra¸c˜ oes e produtos/divis˜ oes for pequeno. J´ a o adjetivo acurado se presta a qualificar o resultado final obtido pelo algoritmo. Um algoritmo para o c´ alculo de tens˜ oes em uma estrutura met´ alica por exemplo envolve milh˜ oes de opera¸c˜ oes alg´ ebricas elementares. Sua qualidade n˜ ao ´ e determinada apenas pela qualidade com que estas opera¸c˜ oes s˜ ao executadas.
Precis˜ ao Erro cometido em opera¸c˜ oes alg´ebricas elementares Acur´ acia Erro presente em quantidade aproximadas
http://goo.gl/tj2oD
Norma Euclidiana
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Por fim, cabe destacar que estes dois termos s˜ ao empregados de maneira confusa e s˜ ao muitas vezes intercambiados. O comum ´ e que a palavra precis˜ ao seja utilizada nos dois contextos.
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Unidade de arredondamento
A unidade de arredondamento ´e o menor n´ umero positivo de ponto flutuante u tal que fl(1 + u) > 1
I
u ≈ 1.19209 · 10−07 (em precis˜ao simples) u ≈ 2.22045 ·
10−16
http://goo.gl/tj2oD
Introdu¸c˜ ao
A diferen¸ca entre precis˜ ao simples e precis˜ ao dupla ´ e o espa¸co utilizado para o armazenamento do n´ umero de ponto flutuante. Em precis˜ ao simples s˜ ao utilizados 32 bits, enquanto que 64 bits s˜ ao necess´ arios para a representa¸c˜ ao em precis˜ ao dupla. O esquema abaixo descreve como esses bits s˜ ao distribu´ıdos para representar a mantissa (f ) e o expoente (e), al´ em do sinal (s) de um n´ umero de ponto flutuante. Precis˜ ao simples:
1 s
Precis˜ ao dupla:
1 s
8 e 11 e
23 f 52 f
A unidade de arredondamento, assim como outras quantidades como os maiores e menores n´ umeros represent´ aveis, e os resultados esperados de a¸co ˜es como arredondamentos, truncamentos, etc, s˜ ao propriedades do sistema de ponto flutuante.
No padr˜ao IEEE I
O padr˜ ao IEEE-754-1985 (revisado em 2008), Standard for Binary Floating-Point Arithmetic, ´ e aplamente adotado por fabricantes de processadores. Este padr˜ ao normatiza o sistema de ponto flutuante implementado em processadores.
Cancelamento
Steve Hollash escreveu um bom texto introdut´ orio de sobre o padr˜ ao IEEE-754-1985 (http://steve.hollasch.net/cgindex/coding/ieeefloat.html).
(em precis˜ao dupla)
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
O importante ´ e ter em mente que m´ aquinas muito precisas n˜ ao bastam para obter resultados acurados. Pense, por exemplo, que n˜ ao basta um ter bisturi a laser (instrumento de alta precis˜ ao) para que uma cirurgia seja bem sucedida (resultado acurado). Por outro lado, sem um bom bisturi, dificilmente uma cirurgia seria bem sucedida.
Precis˜ao 6⇒ acur´acia
Via de regra, as m´ aquinas atuais s˜ ao bem precisas. Mesmo assim, para muitos problemas ´ e dif´ıcil conseguir boas solu¸c˜ oes aproximadas.
Alta precis˜ao n˜ao ´e suficiente para garantir resultados acurados
http://goo.gl/tj2oD
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Erro de cancelamento
Para efeito de exposi¸c˜ ao, vamos considerar um sistema de ponto flutuante simples (SPFS) capaz de representar apenas os cinco d´ıgitos mais significativos de um n´ umero e um u ´nico d´ıgito para expoente. Neste SPFS, a unidade de arredondamento ´ e u = 10−4 . Vamos analisar a seguinte conta simples: 49213 + 31.728 − 49244 = 0.728 Repare que todos os n´ umero envolvidos s˜ ao representados corretamente no nosso sistema de ponto flutuante simplificado.
Sistema de ponto flutuante com cinco d´ıgitos significativos Queremos calcular 49213 + 31.728 − 49244 = 0.728
http://goo.gl/tj2oD
Introdu¸c˜ ao
Ricardo Biloti
Cancelamento
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Erro de cancelamento
As opera¸c˜ oes s˜ ao realizadas da esquerda para a direita. A primeira soma ´ e feita e o resultado ´ e um n´ umero com oito d´ıgitos significativos. Sendo assim, apenas o cinco mais significativos s˜ ao preservados em nosso sistema de ponto flutuante. A conta ´ e conclu´ıda com a subtra¸c˜ ao de 49244 de 49245, cujo resultado exato 1 ´ e corretamente obtido.
49213 + 31.728 − 49244 = 0.728 49213 + 31.728 49244.728
fl(49213 + 31.728) = 49245 fl(49245 − 49244) = 1
http://goo.gl/tj2oD
Norma Euclidiana
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Erro de cancelamento
Neste exemplo o valor correto x deveria ser 0.728, enquanto que o valor obtido foi 1. O erro relativo nesta aproxima¸c˜ ao ´ e 0.374, bem maior que o erro embutido nas opera¸c˜ oes alg´ ebricas elementares executadas. Au ´nica conta realizada com erro foi a adi¸c˜ ao inicial. Por´ em o erro relativo naquela opera¸c˜ ao foi pequeno |49245 − 49244.728| = 5.52 · 10−6 , 49244.728 o que ´ e compat´ıvel com o sistema de ponto flutuante simples. Entretanto o erro relativo da aproxima¸c˜ ao como um todo ´ e bem maior:
x = 49213 + 31.728 − 49244 = 0.728
|1 − 0.728| = 3.74 · 10−1 . 0.728 Como isto ´ e poss´ıvel? Onde este erro grosseiro foi originado?
xˆ = fl(49213 + 31.728 − 49244) = 1 Erel (ˆ x ) = 0.374 10−4 = u
http://goo.gl/tj2oD
Introdu¸c˜ ao
Ricardo Biloti
Cancelamento
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Perda de d´ıgitos
49213 + 31.728 49244.728 fl(49213 + 31.728) = 49213 + 32 = 49245 A subtra¸c˜ao foi exata fl(49245 − 49244) = 1
Ricardo Biloti
O problema surgiu na adi¸c˜ ao inicial. O resultado num´ erico daquela opera¸c˜ ao s´ o pˆ ode preservar os cinco d´ıgitos mais significativos dos oito d´ıgitos que compunham o resultado exato. Isso n˜ ao ´ e um problema para a adi¸c˜ ao em si. De fato, o erro relativo nesta opera¸c˜ ao foi de 5.52 · 10−6 , menor que a unidade de arredondamento do SPFS. Entretanto aqueles trˆ es d´ıgitos perdidos, que n˜ ao eram importantes para o resultado da adi¸c˜ ao, passaram a ser importantes quando a subtra¸c˜ ao seguinte foi executada. Na subtra¸c˜ ao, todos aqueles cinco d´ıgitos mais significativos foram cancelados. Os trˆ es d´ıgitos perdidos seriam ent˜ ao novamente necess´ arios, por´ em n˜ ao h´ a mais como recuper´ a-los.
Trˆes d´ıgitos significativos perdidos
http://goo.gl/tj2oD
Norma Euclidiana
Computa¸c˜ ao em precis˜ ao finita
Neste sentido, a subtra¸c˜ ao apenas evidenciou um problema que foi gerado pela perda de d´ıgitos significativos em um passo anterior.
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
F´ormula de Heron para a ´area de triˆangulos
Heron, no ano 60, escreveu a ´ area de um triˆ angulo em termos do comprimentos de seus lados. Numericamente, a ´ area computada desta forma torna-se mais imprecisa a medida que o triˆ angulo torna-se mais achatado. Para tais triˆ angulos, s ser´ a aproximadamente igual a um dos lados, digamos a. Nesse caso, a f´ ormula tal como apresentada, sofre pelo cancelamento de d´ıgitos significativos na subtra¸c˜ ao de s − a. No gr´ afico, foi exibido o erro relativo no c´ alculo da ´ area de um triˆ angulo retˆ angulo com hipotenusa 4 e altura progressivamente menor.
p A = s(s − a)(s − b)(s − c),
s = (a + b + c)/2 Uma maneira de evitar esse problema ´ e computar a ´ area pela f´ ormula
Erro relativo em A
1
A=
1p (a + (b + c))(c − (a − b))(c + (a − b))(a + (b − c)) 4
-3
10
onde os lados do triˆ angulo foram ordenados pelo comprimento, isto ´ e, a ≥ b ≥ c. Para evitar o cancelamento de d´ıgitos, o c´ alculo deve ser feito na ordem indicada pelos parˆ enteses.
-6
10
-9
10
-12
10
-15
10
-2
10
-4
10
-6
10
-8
10
-10
10
-12
10
-14
10
-16
10
Altura
http://goo.gl/tj2oD
Introdu¸c˜ ao
Cancelamento
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
A id´ eia para este exerc´ıcio ´ e procurar uma forma de rescrever as express˜ oes de maneira a evitar o cancelamento de d´ıgitos. √ √ Por exemplo, no caso de x 2 + 1 − x, se x for muito grande teremos que x 2 + 1 ≈ x, e portanto a subtra¸c˜ ao destas quantidades implicar´ a no cancelamento de d´ıgitos significativos.
Exerc´ıcio
Esta express˜ ao pode por´ em ser reescrita como hp i √x 2 + 1 + x p 1 x2 + 1 − x = x2 + 1 − x √ = √ , x2 + 1 + x x2 + 1 + x
Para que valores de x, as express˜ oes abaixo podem sofrer por erros de cancelamento? Reescreva as express˜ oes abaixo de maneira a reduzir poss´ıveis erros. √ 3. (1 − cos x)/ sin x 1. x 2 + 1 − x p √ 2. 1 + x − 1 4. (1 − cos x)/2
http://goo.gl/tj2oD
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
que n˜ ao sofre de cancelamento uma vez que n˜ ao h´ a a subtra¸c˜ ao de quantidades pr´ oximas. √ √ Por exemplo, se x = 109 , fl x 2 + 1 − x = 0, enquanto que fl 1/[ x 2 + 1 + x] = 5 · 10−10 .
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Considere o problema de encontrar as ra´ızes de uma equa¸c˜ ao quadr´ atica. Como existe f´ ormula fechada para as ra´ızes desta equa¸c˜ ao, basta utiliz´ a-la. Apenas por conveniˆ encia, considere a equa¸c˜ ao normalizada de maneira que o termo quadr´ atico tenha coeficiente 1.
Norma Euclidiana
Para esse exemplo, com os coeficientes b e c dados, r1 e r2 s˜ ao as duas ra´ızes desta equa¸c˜ ao (todos os d´ıgitos exibidos est˜ ao corretos).
Equa¸c˜ao quadr´atica
Problema Encontrar as duas ra´ızes reais de x 2 − bx + c = 0 Se b 2 − 4c ≥ 0, r=
http://goo.gl/tj2oD
Introdu¸c˜ ao
b±
Ricardo Biloti
Cancelamento
√
b 2 − 4c 2
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Equa¸c˜ao quadr´atica
x 2 − bx + c = 0 b = 4.7379100021 r1 = 4.7375680682...
http://goo.gl/tj2oD
Ricardo Biloti
c = 0.0016199351 r2 = 0.0003419340...
Computa¸c˜ ao em precis˜ ao finita
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Vamos acompanhar a sequˆ encia de c´ alculo necess´ aria para o compto da menor ra´ız. Todas as opera¸co ˜es s˜ ao realizadas no nosso sistema de ponto flutuante simplificado.
Norma Euclidiana
O erro relativo ´ e bem superior ` a unidade de arredondamento do SPFS (que ´ e uma medida para o erro relativo m´ aximo esperado em opera¸c˜ oes elementares).
Sequˆencia de c´alculo
r=
b−
b = 4.7379100021 1. 2. 3. 4. 5. 6.
b 2 − 4c 2 c = 0.0016199351
b2 4c 2 b √ − 4c b 2√ − 4c b − √b 2 − 4c (b − b 2 − 4c)/2
http://goo.gl/tj2oD
Introdu¸c˜ ao
√
Ricardo Biloti
Cancelamento
= = = = = =
2.2448 · 10+1 6.4797 · 10−3 2.2442 · 10+1 4.7373 · 10+0 6.0000 · 10−4 3.0000 · 10−4
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Erro
Erel (ˆ r2 ) =
http://goo.gl/tj2oD
|3.0000 · 10−4 − 3.4193 · 10−4 | = 1.2263·10−1 10−4 = u 3.4193 · 10−4
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Sequˆencia de c´alculo
r=
b−
√
b = 4.7379100021 1. 2. 3. 4. 5. 6.
b2 4c 2 b √ − 4c b 2√ − 4c b − √b 2 − 4c (b − b 2 − 4c)/2
http://goo.gl/tj2oD
Introdu¸c˜ ao
b 2 − 4c 2 c = 0.0016199351
Ricardo Biloti
Cancelamento
= = = = = =
2.2448 · 10+1 6.4797 · 10−3 2.2442 · 10+1 4.7373 · 10+0 6.0000 · 10−4 3.0000 · 10−4
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Sequˆencia de c´alculo
r=
b−
b = 4.7379100021 1. 2. 3. 4. 5. 6.
http://goo.gl/tj2oD
√
b 2 − 4c 2 c = 0.0015
b2 4c 2 b √ − 4c b 2√ − 4c b − √b 2 − 4c (b − b 2 − 4c)/2
Ricardo Biloti
= = = = = =
2.2448 · 10+1 6.0000 · 10−3 2.2442 · 10+1 4.7373 · 10+0 6.0000 · 10−4 3.0000 · 10−4
Computa¸c˜ ao em precis˜ ao finita
Norma Euclidiana
De fato, repare que o valor encontrado para a ra´ız seria o mesmo se, ao inv´ es de utilizar 1.6199·10−3 para c, tiv´ essemos utilizado c = 1.5·10−3 . Ou seja, quatro d´ıgitos significativos de c foram perdidos no decorrer das opera¸c˜ oes. Esta perda s´ o foi sentida no passo 5, quando a subtra¸c˜ ao cancelou os d´ıgitos mais significativos e aqueles anteriormente perdidos passariam a ser novamente importantes.
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Se ao inv´ es de calcular a menor ra´ız, calcul´ assemos a maior, o passo 5 seria uma adi¸c˜ ao ao inv´ es de uma subtra¸c˜ ao, e n˜ ao haveria mais a necessidade de manter os d´ıgitos perdidos no passo 3.
Norma Euclidiana
Veja que o erro relativo no compto da maior ra´ız ´ e bem menor, e compat´ıvel com o erro de arredondamento do SPFS.
Maior raiz
r=
b+
b = 4.7379100021 1. 2. 3. 4. 5. 6.
b 2 − 4c 2 c = 0.0016199351
b2 4c 2 b √ − 4c b 2√ − 4c b + √b 2 − 4c (b + b 2 − 4c)/2
http://goo.gl/tj2oD
Introdu¸c˜ ao
√
Cancelamento
Ricardo Biloti
= = = = = =
2.2448 · 10+1 6.4797 · 10−3 2.2442 · 10+1 4.7373 · 10+0 9.4752 · 10+0 4.7376 · 10+0
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Como fazer para estimar ent˜ ao a menor ra´ız?
Erro
Erel (ˆ r1 ) =
http://goo.gl/tj2oD
|4.7376 − 4.7375680682| = 6.74 · 10−6 4.7375680682
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Um alternativa inteligente ´ e trocar o algoritmo para o c´ alculo desta ra´ız. Utilizando a rela¸c˜ ao r1 r2 = c, podemos calcular a menor ra´ız sem fazer qualquer subtra¸c˜ ao que evidenciaria uma perda de d´ıgitos significativos anterior.
Norma Euclidiana
A melhor estrat´ egia ent˜ ao seria sempre calcular primeiro a ra´ız que n˜ ao tem problema com cancelamento de d´ıgitos. A outra ra´ız seria calculada atrav´ es da rela¸c˜ ao r1 r2 = c.
Segunda raiz
r2 =
c = 3.4193 · 10−4 r1
http://goo.gl/tj2oD
Introdu¸c˜ ao
Ricardo Biloti
Cancelamento
Erel (ˆ r2 ) = 1.1600 · 10−5
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Isto ´ e o melhor que pode ser feito com esta express˜ ao para as ra´ızes de uma equa¸c˜ ao quadr´ atica. Entretanto isto ainda n˜ ao resolve todos os problemas.
Estrat´egia
Se b 2 ≈ 4c ainda haver´ a cancelamento de d´ıgitos significativos que n˜ ao pode ser evitado. Por fim, o c´ alculo de b 2 ainda pode apresentar overflow ou underflow.
√ b + sign(b) b 2 − 4c r1 = 2
r2 =
c r1
Problemas I
b 2 ≈ 4c
I
overflow ou underflow em b 2
http://goo.gl/tj2oD
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Vamos analisar um caso em que n˜ ao h´ a qualquer subtra¸c˜ ao de n´ umeros pr´ oximos, mesmo assim h´ a perda de d´ıgitos significativos. Ou seja, n˜ ao basta evitar a subtra¸c˜ ao de n´ umeros pr´ oximos para evitar a perda de d´ıgitos.
Norma Euclidiana
Computacionalmente, n˜ ao podemos somar infinitos termos. Por isto, fixamos um certo N e realizamos a soma at´ e este ´ındice. Em tese, qu˜ ao maior for N melhor ´ e a aproxima¸c˜ ao de S por SN .
Somas infinitas
Perda de d´ıgitos significativos podem ocorrer sem que haja cancelamento.
http://goo.gl/tj2oD
Introdu¸c˜ ao
Cancelamento
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Exemplo
Considere a soma
∞ X π2 1 S= = k2 6 k=1
Computacionalmente S ≈ SN =
N X 1 k2 k=1
http://goo.gl/tj2oD
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
O algoritmo mais simples e intuitivo para realizar computacionalmente esta soma acumula parcela por parcela os termos da soma. O s´ımbolo ← significa uma atribui¸c˜ ao, ou seja, k ← k + 1, significa que ` a vari´ avel k ser´ a atribu´ıdo o valor que ela tem atualmente acrescido de 1.
Exemplo
Algoritmo I
k ← 2, s ← 1
I
enquanto k ≤ N, I
s ← s + 1/k 2
I
k ←k +1
http://goo.gl/tj2oD
Introdu¸c˜ ao
Ricardo Biloti
Cancelamento
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Depois de somadas 4095 parcelas, temos que s = S4095 = 1.64472532 . . .. A soma parcial seguinte, S4096 , ´ e calculada como S4096 = fl(S4095 + 1/40962 ).
Exemplo
Como s j´ a´ e um n´ umero de ponto flutuante, fl(s) = s e como fl(s · p) = fl(s) fl(p), temos que
s = S4095 = 1.64472532 . . . Para k = 4096, S4096 = fl(s + 1/40962 ) = fl(s + 2−24 ) 2−24 = fl s 1 + s −24 2 = s fl 1 + s 2−24 ≈ 3.5804 · 10−8 < 1.1920 · 10−7 ≈ u s
http://goo.gl/tj2oD
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
2−24 S4096 = s fl 1 + . s Por´ em, como 2−24 /s ´ e menor que a unidade de arredondamento (em precis˜ ao simples), o resultado de ponto flutuante da soma desta quantidade com 1 ´ e 1, e portanto a soma n˜ ao se altera: S4096 = S4095 . O problema aqui ´ e que o termo 1/40962 ´ e muito pequeno em compara¸c˜ ao com S4095 e portanto a sua soma ´ e desprez´ıvel dentro do sistema de ponto flutuante.
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
A alternativa ´ e acumular as parcelas na ordem inversa. Desta forma, cada nova parcela (maior) sempre ser´ a somada a um valor acumulado tamb´ em crescente, n˜ ao havendo a disparidade de grandezas que acontece no algoritmo ingˆ enuo.
Perda de d´ıgitos
A perda de d´ıgitos ocorre quando somamos n´ umeros de grandezas muito distintas. Solu¸c˜ ao I
k ← N, s ← 0
I
enquanto k ≥ 1, I
s ← s + 1/k 2
I
k ←k −1
http://goo.gl/tj2oD
Introdu¸c˜ ao
Ricardo Biloti
Cancelamento
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Compara¸c˜ao 1
Ordem decrescente Ordem crescente
|SN - (π2/6)|
1e-02
1e-04
1e-06
1e-08 0
5
10
15
20
log2(N)
http://goo.gl/tj2oD
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
25
30
2 Neste gr´ afico exibimos o erro SN − π6 , para N = 2n , calculado pelo algoritmo crescente (ingˆ enuo) como triˆ anguloss e calculado pelo algoritmo decrescente (ordem inversa) como c´ırculos. Enquanto que o erro se reduz apenas at´ e N = 212 = 4096 no algoritmo ingˆ enuo, no algoritmo decrescente ´ e poss´ıvel chegar perto da precis˜ ao da m´ aquina. Note que as contas foram feitas em precis˜ ao simples.
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Outro exemplo de opera¸c˜ ao simples mas que deve ser feita com cuidado ´ e o c´ alculo da norma de um vetor. A f´ ormula da norma euclidiana ´ e facilmente traduzida em um algoritmo simples.
Norma de Euclidiana Se x = (x1 , x2 , . . . , xn )T , kxk2 =
q x12 + x22 + · · · + xn2
Algoritmo I
k ← 1, s ← 0
I
enquanto k ≤ n,
I
I
s ← s + (xk · xk )
I
k ←k +1
s←
√
s
http://goo.gl/tj2oD
Introdu¸c˜ ao
Ricardo Biloti
Cancelamento
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Exemplo 1
Veja que o problema acontece quando 8 · 104 deve ser elevado ao quadrado, pois esse termo sozinho j´ a gera o overflow.
Em um sistema de ponto flutuante com cinco d´ıgitos significativos e um para expoente
x = (6 · 104 , 8 · 104 ),
kxk2 = 105 ,
s = 3.6 · 109 + (8 · 104 × 8 · 104 ) (overflow)
http://goo.gl/tj2oD
Nesse exemplo simples, o c´ alculo da norma pelo algoritmo ingˆ enuo apresentado, para um vetor com apenas duas componentes, j´ a resulta em overflow. Repare que tantos as coordenadas do vetor como o valor da norma s˜ ao quantidades representadas no sistema de ponto flutuante.
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Exemplo 2
Nesse exemplo, novamente todas as componentes do vetor podem ser representadas no sistema de ponto flutuante, seu valores ao quadrado tamb´ em s˜ ao represent´ aveis, assim como o valor da norma do vetor. Por´ em o ac´ umulo dos valores ao quadrado das componentes gera o overflow.
Em um sistema de ponto flutuante com cinco d´ıgitos significativos e um para expoente,
x = (7 · 104 , 6 · 104 , 5 · 104 ),
kxk2 = 1.0488 · 105 ,
s = (7 · 104 × 7 · 104 ) + (6 · 104 × 6 · 104 ) + (5 · 104 × 5 · 104 ) (overflow)
http://goo.gl/tj2oD
Introdu¸c˜ ao
Cancelamento
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
C´alculo da norma
Problemas I
Overflow/underflow quando s = s + xk2
I
Overflow/underflow no c´alculo de xk2
http://goo.gl/tj2oD
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Norma Euclidiana
Com os dois exemplos, vimos que tanto o passo de elevar uma componente ao quadrado, quanto o passo de acumular esses valores podem gerar overflow (assim como underflow).
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
A solu¸c˜ ao, no caso desse algoritmo, ´ e escalar o vetor pela sua compomente de maior valor absoluto antes de computar sua norma.
Norma Euclidiana
Essa vers˜ ao do algoritmo n˜ ao sofre dos problemas dos exemplos anteriores, sendo sempre capaz de computar a norma de um vetor, desde que o valor da norma seja represent´ avel no sistemas de ponto flutuante.
Escalamento x = (6 · 104 , 8 · 104 )
kxk2 =
q (6 · 104 )2 + (8 · 104 )2
v # " u 4 2 u 6 · 10 +1 = t(8 · 104 )2 8 · 104 = 8 · 104
q (6/8)2 + 1
= 105
http://goo.gl/tj2oD
Introdu¸c˜ ao
Cancelamento
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Equa¸c˜ ao quadr´ atica
Somas infinitas
Algoritmo
Por´ em, h´ a um incoveniente. Esse algoritmo precisa percorrer o vetor duas vezes. A primeira delas, apenas para poder descobrir o maior valor absoluto das componentes do vetor, de modo a realizar o escalamento.
I
k ← 0, s ← 0, γ ← max|xk |,
I
enquanto k ≤ n,
I
I
s ← s + (|xk |/γ) · (|xk |/γ)
I
k ←k +1
√ s←γ s
http://goo.gl/tj2oD
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
Introdu¸c˜ ao
Cancelamento
Equa¸c˜ ao quadr´ atica
Somas infinitas
Norma Euclidiana
Essa u ´ltima vers˜ ao faz o escalamento sem precisar pecorrer o vetor duas vezes, mas sim descobrindo o fator de escala durante o processo e corrigindo-o, se necess´ ario.
Algoritmo
Esse ´ e o algoritmo que de fato ´ e utilizado para computar norma de vetores em bibliotecas de algoritmos num´ ericos de qualidade, como a BLAS (do inglˆ es, Basic Linear Algebra Subprograms).
I
k ← 0, γ ← 1, s ← 0
I
enquanto k ≤ n, I
Se γ > |xk |, ent˜ao I
s ← s + (|xk |/γ) · (|xk |/γ)
dnrm2 (BLAS-1)
sen˜ao
I
I
I
s ← 1 + s(γ/|xk |) · (γ/|xk |)
I
γ ← |xk |
k ←k +1
√ s←γ s
http://goo.gl/tj2oD
Ricardo Biloti
Computa¸c˜ ao em precis˜ ao finita
