L3

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina

Introdu¸c˜ao `a Aritm´etica de M´aquina Eduardo Camponogara Departamento de Automa¸c˜ ao e Sistemas Universidade Federal de Santa Catarina

DAS-5103: C´alculo Num´erico para Controle e Automa¸c˜ao

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Sum´ ario

Introdu¸c˜ao `a Aritm´etica de M´aquina

Instabilidade de Problemas

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina

Sum´ario

Introdu¸c˜ao `a Aritm´etica de M´aquina

Instabilidade de Problemas

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Precis˜ ao e Exatid˜ ao de M´ aquinas Digitais

Precis˜ao e Exatid˜ao de M´aquinas Digitais

Conforme vimos, para cada m´aquina, calculadora ou computador h´a um sistema de ponto flutuante associado. Este sistema automaticamente define a precis˜ao da m´aquina.

´ Defini¸c˜ao (Epsilon de m´aquina) O ´epsilon da m´aquina ´e o menor n´ umero de ponto flutuante tal que: 1 + ǫ > 1.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Precis˜ ao e Exatid˜ ao de M´ aquinas Digitais

Precis˜ao e Exatid˜ao de M´aquinas Digitais

Defini¸c˜ao (Precis˜ao) A precis˜ao de uma m´aquina digital ´e definida como o n´ umero de d´ıgitos da mantissa dessa m´aquina.

Defini¸c˜ao (Exatid˜ao) Exatid˜ao ´e uma medida de perfei¸c˜ao do resultado.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Precis˜ ao e Exatid˜ ao de M´ aquinas Digitais

Precis˜ao e Exatid˜ao de M´aquinas Digitais

◮

A exatid˜ao de um resultado depende da precis˜ao da m´aquina e do m´etodo utilizado para a obten¸c˜ao do resultado.

◮

Quando n˜ao conhecemos o valor exato temos, em geral, que se x = limj→∞ xj , ent˜ao o n´ umero de d´ıgitos significativos de xj em rela¸c˜ao a xj+1 ´e dado por:   |xj+1 − xj | ) DIGSE (xj , xj+1 ) = − 0.3 + log(µ + |xj | onde µ ´e a unidade de erro de arredondamento e b = 10 ´e a base.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Precis˜ ao e Exatid˜ ao de M´ aquinas Digitais

Exemplo: Aproxima¸c˜oes de π Aproxima¸c˜ao xj 3.1410 3.1411 3.1412 3.1413 3.1414 3.1415 3.1416 3.1417 3.1418 3.1419

DIGSE (xj , π) 3.4 3.5 3.6 3.7 3.9 4.2 5.3 4.2 3.7 3.6

Somente uma das aproxima¸c˜ oes possue cinco d´ıgitos significantes exatos.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Precis˜ ao e Exatid˜ ao de M´ aquinas Digitais

Exemplo: Aproxima¸c˜oes de π

Conclus˜oes ◮

Somente duas das aproxima¸c˜ oes possuem os cinco d´ıgitos significantes exatos.

◮

Logo, exatid˜ao de um processo depente al´em da m´aquina, tamb´em do algoritmo.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Precis˜ ao e Exatid˜ ao de M´ aquinas Digitais

Exemplo

Exemplo Seja o n´ umero irracional

√

2 = 1.414213562 . . ..

a) 1.4142 ´e mais preciso e mais exato que 1.41, pois o primeiro √ tem maior n´ umero de casas decimais e aproxima melhor 2; b) 1.4149 ´e mais preciso que 1.414, pois tem mais casas decimais, por´em, ´e menos exato do que 1.414, j´a que o d´ıgito 9 do primeiro n˜ao ´e exato.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Instabilidade Quest˜oes de Instabilidade ◮

Veremos agora uma s´erie de problemas cujos diferentes modos de solu¸c˜ao podem acarretar diferentes resultados. Quando os resultados obtidos n˜ao s˜ao aceit´aveis, os erros podem ser causados: a) pelos modelos ou entrada de dados (erros inerentes) b) pelo arredondamento ou truncamento.

◮

Instabilidade pode ser entendida como uma sensibilidade a perturba¸c˜oes e pode ocorrer tanto no problema em si como no algoritmo, isto ´e, na maneira de resolvˆe-lo.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Instabilidade: Exemplo 1 Fun¸c˜ao de exponencial A instabilidade de algoritmos pode ser ilustrada atrav´es do exemplo de se calcular a constante de Euler. Vamos calcular e e e −5.5 pela s´erie de Taylor. Dado que: ex = 1 + x +

x2 x3 x4 + + + ... 2 3! 4!

Ent˜ao para x = 1, temos: e∼ = 1 + 1 + 0.5 + . . . = 2.7183 Comparando esta soma com o valor 2.718 281 828 obtido em uma calculadora, verificamos um erro relativo de 6.6 × 10−6 , que ´e bem pequeno.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Instabilidade: Exemplo 2

Fun¸c˜ao de exponencial Por outro lado, para x = −5.5, temos: e −5.5 ∼ = 1 − 5.5 + 15.125 − 27.730 + . . . = 0.002 636 3. Comparando agora com e −5.5 dado por uma calculadora, temos que: e −5.5 = 0.004 086 714 39, portanto, o erro relativo ´e 0.35 que ´e bem maior que o erro anterior.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Qual a causa da diferen¸ca?

Causas da diferen¸ca? A causa do erro ´e uma combina¸c˜ao de dois fatores: ◮

somas de grandezas de diferentes ordens; e

◮

subtra¸c˜ao de grandezas quase iguais.

Tal fenˆomeno ´e dito cancelamento subtrativo ou cancelamento catastr´ofico, que ´e bastante comum em c´alculos.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Cancelamento Subtrativo Cancelamento Subtrativo ◮

O cancelamento subtrativo n˜ao ´e a real causa do erro final da soma, ele apenas aumentou o efeito do erro final.

◮

Note que na primeira soma (para e), n˜ao houve tal aumento.

◮

1 e utilizarmos as Se mudarmos o c´alculo de e −5.5 para e 5.5 mesmas parcelas, obteremos 0.0040865 com erro relativo de 6.6 × 10−5 .

◮

Logo podemos utilizar a s´erie de Taylor para argumentos positivos.

◮

Na pr´atica tamb´em devemos utilizar um crit´erio de parada mais cuidadoso do que o simples n´ umero de termos da s´erie.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Qualidade da Aproxima¸c˜ao Qualidade ◮

P xj Seja f (x) = T c˜ao de e x obtida com a j=0 j! a aproxima¸ expans˜ao de Taylor de ordem T em torno do ponto x = 0.

◮

Na tabela abaixo ilustramos os valores obtidos com f (x) para x > 0.

◮

Tamb´em ilustramos as aproxima¸c˜ oes obtidas para e x com f (x) e 1/f (−x) quando x < 0.

◮

Ainda s˜ao dados os valores de e x computados atrav´es do Matlab.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Qualidade da Aproxima¸c˜ao

x -40 -20 -10 -5 -2 -1 0 1 2 5 10 20

f (x) 50.810 4.1736e-009 4.5400e-005 6.7379e-003 0.13534 0.36788 1.0000 2.7183 7.3891 1.4841e+002 2.2026e+004 4.8517e+008

1/f (−x) 4.2484e-018 2.0612e-009 4.5400e-005 6.7379e-003 0.13534 0.36788

e x (Matlab) 4.2484e-018 2.0612e-009 4.5400e-005 6.7379e-003 0.13534 0.36788 1.0000 2.7183 7.3891 1.4841e+002 2.2026e+004 4.8517e+008

|e x −f (x)| ex

10e020 102.48 7.2342e-007 2.1369e-011 4.1018e-014 3.0179e-014 0.0000 0.0000 2.4040e-014 1.9150e-014 3.3033e-014 2.4571e-014

1 |e x − f (−x) |/e x 5.4400e-016 2.0066e-016 2.9851e-016 2.5746e-016 2.0509e-016 1.5089e-016

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Qualidade da Aproxima¸c˜ao

Observa¸c˜ao A partir dos valores apresentados na tabela podemos perceber que o erro resultante da aproxima¸c˜ao f (x) ´e elevado para x < 0.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Exemplo 3 Outro exemplo de instabilidade Outro exemplo de instabilidade de algoritmo surge do c´alculo da R1 integral definida ln = 0 x n e x−1 dx para n = 1, 2, . . . Integrando por partes, temos: Z 1 x n e x−1 dx; u = x n e dv = e x−1 dx ln = 0 Z 1 1 vdu = [uv ]0 − 0 Z 1 n x−1 1 e x−1 nx n−1 dx = [x e ]0 − 0

= 1 − nln−1 , n = 2, 3, . . .

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Exemplo 3 Outro exemplo de instabilidade Podemos calcular analiticamente o valor de l1 , obtendo Z 1 xe x−1 dx l1 = 0 Z 1 e x−1 dx = [xe x−1 ]10 − 0

= 1 · e 0 − 0 · e −1 − [e x−1 ]10

= 1 − e 0 + e −1

= 1/e.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Exemplo 3 Outro exemplo de instabilidade Usando F = F (10, 6, −98, 99), temos os seguintes valores: l1 l2 l3 l4 l5

≃ ≃ ≃ ≃ ≃

0.367 0.264 0.207 0.170 0.145

879 242 274 904 480

l6 l7 l8 l9

≃ ≃ ≃ ≃

0.127 120 0.110 160 0.118 720 −0.068 480

Olhando o integrando x 9 e x−1 , verificamos que ´e sempre positivo em [0, 1] e, no entanto, o valor computado para l9 foi negativo.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

O Que Causou o Erro?

Causas do Erro ◮

Notemos que s´o foi feito um erro de arredondamento em l1 quando 1e foi tomado por 0.367879 em vez de 0.367879442.

◮

Como a f´ormula est´a correta, o erro final ´e devido apenas a este erro cometido em l1 .

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

O Que Causou o Erro? Causas do Erro ◮

Observemos como tal erro ocorreu. ◮

◮

Em l2 o erro foi multiplicado por −2, depois em l3 foi multiplicado por −3, etc. Ent˜ao o erro de l9 ´e exatamente (−2)(−3) . . . (−9) = 9!. Sendo 1 E1 = [ − 0.367879] = 4.412 × 10−7 , e teremos no final 4.412 × 10−7 · 9! = 0.1601

◮

Logo, embora a f´ormula esteja correta, ela ´e inst´avel. Com rela¸c˜ao ao ac´ umulo de erros, o algoritmo ´e de m´a exatid˜ao.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Um Algoritmo Est´avel Um Algoritmo Est´avel ◮

Um algoritmo est´avel ´e dado por: 1 − ln , n = . . . , 4, 3, 2. n Nesta f´ormula, a cada passo, o valor do erro em ln ´e decrescido por n1 (em vez de multiplicado por n). ln−1 =

◮

◮

Se come¸carmos com n ≫ 1 voltaremos e ent˜ao o erro inicial ou erros de arredondamento diminuir˜ao a cada passo.

◮

Resta-nos saber qual ser´a o valor inicial para ln .

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Um Algoritmo Est´avel Um Algoritmo Est´avel Observamos que: ln =

Z

1

n x−1

x e

0

.dx ≤

Z

0

1

x n+1 x .dx = n+1 

n

1 0

=

1 . n+1

Logo, ln tende a zero quando n tende ao infinito. Se aproximarmos l20 para zero, teremos: l20 l19 l18 l17 l16 l15

≃ ≃ ≃ ≃ ≃ ≃

0 0.050 0.050 0.052 0.055 0.059

000 000 777 719 017

0 0 8 0 6

l14 l13 l12 l11 l10 l9

≃ ≃ ≃ ≃ ≃ ≃

0.062 0.066 0.071 0.077 0.083 0.091

732 947 773 352 877 612

2 7 3 3 1 3.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Majorando o Erro

Majorando o erro em l20 por

1 21

temos:

1 1 E19 = 20 × 21 1 1 × E18 = 19 × 20 .. .. . . E15 = 4 × 10−8 .

1 21

= 0.0024 = 0.00012

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Continuando

Continuando o algoritmo, obtemos: l8 l7 l6 l5

≃ ≃ ≃ ≃

0.100 0.112 0.126 0.145

932 383 802 532

0 5 4 0

l4 l3 l2 l1

≃ ≃ ≃ ≃

0.170 0.207 0.264 0.367

893 276 241 879

4 7 1 5

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Outras Fontes de Problemas Vamos agora considerar o problema de calcular a m´edia aritm´etica de dois n´ umeros a e b. Algoritmo 1 1) Entrada(a, b) 2) s ← a + b 3) m ← 2s 4) Sa´ıda(m)

Algoritmo 2 1) Entrada(a, b) 2) s1 ← 2a 3) s2 ← b2 4) m ← s1 + s2 5) Sa´ıda(m)

Algoritmo 3 1) Entrada(a, b) 2) d1 ← a − b 3) d1 ← d21 4) m ← d1 + b 5) Sa´ıda(m)

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade

Problemas Com Algoritmos de M´edia Aritm´etica

Poss´ıveis Complica¸c˜oes ◮

Para um dado F = F (b, n, l1 , l2 ) podemos ter conforme os valores a, b ∈ F os seguintes problemas: ◮ ◮

◮

Algoritmo 1: overflow em 2 Algoritmo 2: underflow em 2 e 3

No algoritmo 3 n˜ao teremos provavelmente nenhum erro operacional, mas poderemos ter um erro no comando (2) se houver cancelamento subtrativo.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade de Problemas

Sum´ario

Introdu¸c˜ao `a Aritm´etica de M´aquina

Instabilidade de Problemas

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade de Problemas

Instabilidade de Problemas

◮

At´e aqui investigamos a instabilidade inerente a algoritmos.

◮

Agora vamos nos concentramos nos problemas que geram instabilidade intr´ınseca.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade de Problemas

Estabiliza¸c˜ao Duas Tarefas de Estabiliza¸c˜ao

Est´avel

Inst´avel

Figura: Ilustra¸c˜ao de equil´ıbrio est´avel e inst´avel.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade de Problemas

Estabiliza¸c˜ao

Duas Tarefas de Estabiliza¸c˜ao ◮

A segunda tarefa (equil´ıbrio) ´e inst´avel pois, se o l´apis ficar de p´e, ser´a por algumas fra¸c˜ oes de segundo e depois cair´a.

◮

J´a, no caso est´avel, uma pequena perturba¸c˜ao na posi¸c˜ao do l´apis n˜ao acarretar´a a queda, voltando este a posi¸c˜ao de equil´ıbrio.

◮

Algo semelhante ocorre com problemas num´ericos.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade de Problemas

Exemplo de Instabilidade Num´erica ◮

Consideremos ent˜ao o problema de encontrar as ra´ızes do polinˆomio: p(x) = x 20 − 210x 19 + . . .

= (x − 1)(x − 2)(x − 3) . . . (x − 19)(x − 20)

= 0. ◮ ◮

Obviamente as ra´ızes s˜ao 1, 2, 3, . . . 20 e est˜ao bem separadas. Computando as ra´ızes de p(x) + 2−23 x 19 = 0, num computador com sistema de ponto flutuante F = F (2, 90, e1 , e2 ) teremos resultados inesperados

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade de Problemas

Exemplo de Instabilidade Num´erica Computando as ra´ızes de p(x) + 2−23 x 19 = 0, num computador com sistema de ponto flutuante F = F (2, 90, e1 , e2 ) teremos: R1 R2 R3 R4 R5 R6 R7 R8

=1 =2 =3 =4 = 4.999 = 6.000 = 6.999 = 8.007

999 006 697 267

928 944 234 603

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade de Problemas

Exemplo de Instabilidade Num´erica Computando as ra´ızes de p(x) + 2−23 x 19 = 0, num computador com sistema de ponto flutuante F = F (2, 90, e1 , e2 ) teremos: R9 = 8.917 250 249 R10 , R11 = 10.095 266 R12 , R13 = 11.793 633 R14 , R15 = 13.992 358 R16 , R17 = 16.730 737 R18 , R19 = 19.502 439 R20 = 20.846 908 101

145 ± 0.643 881 ± 1.652 137 ± 2.518 466 ± 2.812 400 ± 1.940

500 329 830 624 330

900i 728i 070i 894i 347i

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade de Problemas

Instabilidade Num´erica Algumas Considera¸c˜oes ◮

Note que um termo da equa¸c˜ao mudou de −210x 19 para −210x 19 + 2−23 x 19 , ou seja, uma mudan¸ca no vig´esimo d´ıgito da base 2 de um dos coeficientes.

◮

Apesar desta pequena perturba¸c˜ao, o resultado ´e completamente inesperado e as mudan¸cas nas ra´ızes s˜ao grandes.

◮

A raz˜ao desta mudan¸ca dr´astica n˜ao ´e o arredondamento nem o algoritmo e sim um problema de condicionamento.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade de Problemas

Instabilidade Num´erica Algumas Considera¸c˜oes ◮

H´a certos problemas que, quando sofrem altera¸c˜ao nos dados de entrada, tˆem na sua resposta uma pequena diferen¸ca proporcional

◮

Outros mostram grande varia¸c˜ao no resultado mesmo com uma pequen´ıssima altera¸c˜ao nos dados de entrada.

◮

Os primeiros problemas s˜ao ditos bem condicionados e os segundos s˜ao ditos mal condicionados.

◮

A no¸c˜ao de problemas bem e mal condicionados ser´a elaborada na parte de solu¸c˜ao de sistemas de equa¸c˜oes lineares.

Introdu¸ca ˜o a ` Aritm´ etica de M´ aquina Instabilidade de Problemas

Coment´arios Finais

◮

Fim!

◮

Obrigado pela presen¸ca