aula04_erro

Prévia do material em texto

Ca´lculo Nume´rico
Noc¸o˜es de Erro e Aritme´tica de Ponto Flutuante
Heder S. Bernardino
Heder S. Bernardino Ca´lculo Nume´rico
Suma´rio
1 Aula Anterior
2 Introduc¸a˜o
3 Sistemas de Numerac¸a˜o
4 Representac¸a˜o de Nu´meros Inteiros no Computador
5 Representac¸a˜o de Nu´meros Reais no Computador
6 Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Teorema de Taylor
Teorema de Taylor
Suponha que as derivadas f (1), . . . , f (n+1) estejam definidas e sejam
cont´ınuas num intervalo [x0, x], enta˜o tem-se que
f(x) = Pn(x) +Rn(x)
onde
Pn(x) =
n∑
k=0
f (k)(x0)
(x− x0)
k
k!
Rn(x) =
∫ x
x0
f (n+1)(t)
(x− t)n
n!
dt
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Estimativa do erro
◮ A forma do erro de Lagrange, dada por
Rn(x) = f
(n+1)(t)
(x− x0)
(n+1)
(n+ 1)!
e´ muito parecida com o termo n+ 1 do Polinoˆmio de Taylor
◮ A diferenc¸a e´ o valor t na fo´rmula
◮ t e´ algum valor entre x0 e x
◮ Para estimar o erro, e´ comum utilizar o maior valor que f (n+1)(t)
pode assumir para t ∈ [x0, x] ou um outro limitante superior
◮ Por exemplo, nota-se que
|Rn(x)| ≤
|x− x0|
(n+1)
(n+ 1)!
max
t∈[x0,x]
∣∣∣f (n+1)(t)∣∣∣
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aproximac¸a˜o de Derivada
◮ Diferenc¸a Progressiva: x = xi+1
f(xi+1) = f(xi) + f
′(xi)
h︷ ︸︸ ︷
(xi+1 − xi)
f ′(xi) =
f(xi+1)− f(xi)
h
◮ Diferenc¸a Regressiva: x = xi−1
f(xi−1) = f(xi) + f
′(xi)
−h︷ ︸︸ ︷
(xi−1 − xi)
f ′(xi) =
f(xi)− f(xi−1)
h
◮ Diferenc¸a Central:
f ′(xi) =
f(xi+1)− f(xi−1)
2h
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Introduc¸a˜o
Introduc¸a˜o
◮ O objetivo aqui e´ estudar me´todos nume´ricos
◮ Logo, e´ importante entender como os nu´meros sa˜o representados no
computador e como as operac¸o˜es aritme´ticas sa˜o realizadas
◮ Limitac¸o˜es da representac¸a˜o finita
◮ Determinar os casos em que erros ocorrem
◮ Noc¸o˜es de erro
◮ Efeitos nume´ricos
◮ Cancelamento
◮ Propagac¸a˜o do erro
Heder S. Bernardino Ca´lculo Nume´rico
Sistemas de Numerac¸a˜o
Sistemas de Numerac¸a˜o
Heder S. Bernardino Ca´lculo Nume´rico
Sistemas de Numerac¸a˜o
Sistema Decimal
◮ O sistema decimal e´ normalmente adotado
◮ Dez d´ıgitos sa˜o utilizados para representar os nu´meros
◮ base 10
◮ Sistema posicional
◮ Qualquer nu´mero inteiro no sistema decimal pode ser representado
como
N = (anan−1 . . . a1a0)10
= an × 10
n + an−1 × 10
n−1 + · · ·+ a1 × 10
1 + a0 × 10
0
onde ai ∈ {0, 1, . . . , 8, 9}
Heder S. Bernardino Ca´lculo Nume´rico
Sistemas de Numerac¸a˜o
Sistema Decimal
◮ Por exemplo
(21)10 = 2× 10
1 + 1× 100
(2001)10 = 2× 10
3 + 0× 102 + 0× 101 + 1× 100
Heder S. Bernardino Ca´lculo Nume´rico
Sistemas de Numerac¸a˜o
Sistema Bina´rio
◮ Os computadores adotam um sistema com dois estados
◮ Sistema bina´rio
◮ base 2
◮ Tambe´m e´ posicional
◮ Os nu´meros na˜o negativos podem ser representados como
N = (anan−1 . . . a1a0)1
= an × 2
n + an−1 × 2
n−1 + · · ·+ a1 × 2
1 + a0 × 2
0
onde ai ∈ {0, 1}
Heder S. Bernardino Ca´lculo Nume´rico
Sistemas de Numerac¸a˜o
Sistema Bina´rio
◮ Por exemplo
(101)2 = 1× 2
2 + 0× 21 + 1× 20
(1001)2 = 1× 2
3 + 0× 22 + 0× 21 + 1× 20
Heder S. Bernardino Ca´lculo Nume´rico
Sistemas de Numerac¸a˜o
Sistema Hexadecimal
◮ O sistema hexadecimal e´ uma alternativa ao sistema bina´rio para
simplificar a representac¸a˜o valores grandes
◮ Base 16
◮ D´ıgitos:
◮ {0, 1, . . . , 8, 9,A,B,C,D,E,F}
◮ Exemplo
(A00E)16 = A× 16
3 + 0× 162 + 0× 161 + E× 160
= 10× 163 + 0× 162 + 0× 161 + 14× 160
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Representac¸a˜o de Nu´meros Inteiros no
Computador
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Conversa˜o de Bases
◮ A conversa˜o entre os sistemas bina´rio e hexadecimal e´ simples
◮ Cada d´ıgito do sistema hexadecimal e´ representado por 4 d´ıgitos
bina´rios
Bina´rio Hexadecimal Bina´rio Hexadecimal
0000 0 1000 8
0001 1 1001 9
0010 2 1010 A
0011 3 1011 B
0100 4 1100 C
0101 5 1101 D
0110 6 1110 E
0111 7 1111 F
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Conversa˜o de Bases
◮ Um nu´mero na base β pode ser convertido para base decimal como
(N)10 = an × β
n + an−1 × β
n−1 + · · ·+ a1 × β
1 + a0 × β
0
onde ai sa˜o os d´ıgitos do nu´mero representado em na base β
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Exemplo
◮ Exemplo 1
Converta (110)2 para a base decimal.
◮ Soluc¸a˜o:
(110)2 = (6)10
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Exemplo
◮ Exemplo 2
Converta (1001)2 para a base decimal.
◮ Soluc¸a˜o:
(1001)2 = (9)10
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Conversa˜o de Bases
◮ Conversa˜o da base decimal para a base β
◮ Diviso˜es sucessivas do nu´mero em base decimal por β ate´ que o
quociente seja igual a zero
◮ O nu´mero na base β e´ formado pela concatenac¸a˜o em ordem inversa
dos restos das diviso˜es
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Exemplo
◮ Exemplo 3
Converta (14)10 para a base 2.
◮ Soluc¸a˜o:
(14)10 = (1110)2
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Exemplo
◮ Exemplo 4
Converta (35)10 para a base 2.
◮ Soluc¸a˜o:
(35)10 = (100011)2
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Representac¸a˜o de Nu´meros Inteiros no Computador
◮ Para nu´mero na˜o negativos, a representac¸a˜o e´ direta
33⇒ 0 0 1 0 0 0 0 1
◮ Para nu´mero inteiros com sinal, uma possibilidade e´ reservar 1 bit
para indicar o sinal
◮ 0⇒ positivo
◮ 1⇒ negativo
−33⇒ 1 0 1 0 0 0 0 1
◮ 32 bits sa˜o normalmente adotados para representac¸a˜o simples
◮ Valores em [0, 232 − 1] podem ser representados quando o sinal na˜o e´
considerado
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Complemento a Dois
◮ O complemento a dois e´ outra forma de representar nu´meros inteiros
com sinal
◮ O bit mais significativo ainda e´ utilizado para o sinal
◮ Os nu´meros positivos sa˜o representados normalmente
◮ Um nu´mero negativo −y e´ representado pelo nu´mero bina´rio
correspondente ao inteiro positivo 2B − y
◮ B e´ o nu´mero de bits da ma´quina
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Complemento a Dois
◮ Por exemplo, em uma ma´quina que utiliza 4 bits
Bina´rio Decimal Bina´rio Decimal 2B − y
0000 0 1000 −8 24 − 8 = 8
0001 1 1001 −7 24 − 7 = 9
0010 2 1010 −6 24 − 6 = 10
0011 3 1011 −5 24 − 5 = 11
0100 4 1100 −4 24 − 4 = 12
0101 5 1101 −3 24 − 3 = 13
0110 6 1110 −2 24 − 2 = 14
0111 7 1111 −1 24 − 1 = 15
◮ Para inverter o sinal de um nu´mero em complemento a dois basta
◮ Inverter os bits
◮ Somar 1
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Exemplo
◮ Exemplo 5
Considerando uma ma´quina que utiliza 4 bits para representar
nu´meros inteiros com sinal e adotando complemento a dois.
Sabendo que (3)10 e´ representado por (0011)2, qual e´ a representac¸a˜o
bina´ria em complemento a dois para (−3)10?
◮ Soluc¸a˜o:
1101
Heder S. BernardinoCa´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Representac¸a˜o de Nu´meros Inteiros no Computador
◮ Complemento a dois
◮ Uma vantagem desse sistema e´ na˜o requerer um hardware espec´ıfico
para o operador de subtrac¸a˜o
◮ O operador de soma pode ser utilizado quando um nu´mero negativo e´
representado em complemento a dois
◮ Essa representac¸a˜o e´ adotada em muitos dos computadores atuais
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Inteiros no Computador
Exemplo
◮ Exemplo 6
Considerando uma ma´quina que utiliza 4 bits para representar
nu´meros inteiros com sinal e adotando complemento a dois.
Seja (4)10 = (0100)2, realize a operac¸a˜o 4− 3.
◮ Soluc¸a˜o:
(0001)2 = (1)10
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Representac¸a˜o de Nu´meros Reais no
Computador
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Representac¸a˜o de Nu´meros Reais no Computador
◮ Um nu´mero real positivo x pode ser escrito como
x =
n∑
i=0
aiB
i
︸ ︷︷ ︸
xint
+
∞∑
i=1
biB
−i
︸ ︷︷ ︸
xfrac
onde ai e bi sa˜o, respectivamente, os coeficientes da parte integral e
fraciona´ria do nu´mero x
◮ Por exemplo,
(123,45)10 = 1× 10
2 + 2× 101 + 3× 100 + 4× 10−1 + 5× 10−2
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Representac¸a˜o de Nu´meros Reais no Computador
◮ Se bi = 0 para todo i maior que um valor inteiro, enta˜o diz-se que a
frac¸a˜o termina
◮ Caso contra´rio, diz-se que a frac¸a˜o na˜o termina
◮ Exemplos:
0,45 = 4× 10−1 + 5× 10−2 ⇒ termina
0,666 . . . = 6× 10−1 + 6× 10−2 + 6× 10−3 + . . . ⇒ na˜o termina
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Mudanc¸a de Base
◮ Conversa˜o de base 2 para decimal
◮ Similar ao caso inteiro
◮ Conversa˜o de base decimal para bina´ria
◮ Converte-se a parte inteira
◮ Diviso˜es sucessivas
◮ Converte-se a parte fraciona´ria
◮ Multiplicac¸o˜es sucessivas
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Mudanc¸a de Base – Multiplicac¸o˜es sucessivas
◮ Seja (xfrac)10 a parte fraciona´ria de (x)10, a frac¸a˜o bina´ria
(,b1b2 . . . )2 e´ determinada como
c0 = xfrac
b1 = (2× c0)int c1 = (2× c0)frac
b2 = (2× c1)int c2 = (2× c1)frac
...
...
onde “int” representa a parte inteira do nu´mero e “frac” a parte
fraciona´ria
◮ O processo pode ser finalizado quando ci = 0
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Exemplo
◮ Exemplo 7
Converta o nu´mero (111,01)2 para a base 10.
◮ Soluc¸a˜o:
(7,25)10
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Exemplo
◮ Exemplo 8
Converta o nu´mero (3,25)10 para a base 2.
◮ Soluc¸a˜o:
(11,01)2
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Exemplo
◮ Exemplo 9
Converta o nu´mero (12,75)10 para a base 2.
◮ Soluc¸a˜o:
(1100,11)2
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Exemplo
◮ Exemplo 10
Converta o nu´mero (0,1)10 para a base 2.
◮ Soluc¸a˜o:
(0,000110011)2
◮ Ou seja, o nu´mero (0,1)10 e´ uma d´ızima perio´dica quando convertido
para a base 2
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Representac¸a˜o de Nu´meros Reais no Computador
◮ O computador representa os nu´meros em sistema bina´rio
◮ A representac¸a˜o e´ finita
◮ Nu´meros como o pi = 3,1415 . . . sa˜o aproximados
◮ Existem duas formas de representar nu´meros reais no computador
◮ Ponto fixo
◮ Ponto flutuante
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Representac¸a˜o em Ponto Fixo
◮ Neste sistema uma palavra (nu´mero) e´ representada por 3 campos
◮ 1 bit para o sinal
◮ bits que formam a parte integral
◮ bits que formam a parte fraciona´ria
◮ Por exemplo, o nu´mero (12,75)10 pode ser representado em um
sistema com 32 bits (15 bits para a parte integral e 16 bits para a
parte fraciona´ria) como
0 000000000001100 11000000000000000
◮ O sistema de ponto fixo limita muito a magnitude dos nu´meros que
podem ser representados
◮ Essa representac¸a˜o e´ raramente adotada
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Representac¸a˜o em Ponto Flutuante
◮ A representac¸a˜o em ponto flutuante e´ baseado na notac¸a˜o cient´ıfica
x = ±d× βe
onde d e´ a mantissa, β e´ a base do sistema de numerac¸a˜o e e e´ o
expoente
◮ A mantissa e´ um nu´mero na forma
(0,d1d2 . . . dt)β
onde t e´ o nu´mero de d´ıgitos e di ∈ {0, 1, . . . , (β − 1)}, i = 1, . . . , t
◮ O expoente e e´ definido no intervalo [L,U ]
◮ Um nu´mero e´ dito normalizado quando d1 6= 0
◮ Os sistemas apresentados no curso sa˜o normalizados (a menos que o
contra´rio seja dito)
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Representac¸a˜o em Ponto Flutuante
◮ Um sistema de ponto flutuante pode ser definido como
F (β, t, L, U)
onde
◮ β e´ a base do sistema
◮ t e´ o nu´mero de d´ıgitos da mantissa
◮ L e´ o menor valor para o expoente
◮ U e´ o maior valor para o expoente
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Representac¸a˜o em Ponto Flutuante
◮ Nota-se que os nu´mero em ponto flutuante sa˜o discretos
◮ Uma caracter´ıstica e´ a variac¸a˜o entre a discretizac¸a˜o de nu´meros com
magnitudes diferentes
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Exemplo
◮ Exemplo 11
Considerando o sistema F (10, 3,−5, 5).
Represente o nu´mero 1,23 nesse sistema.
◮ Soluc¸a˜o:
+0,123× 101
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Exemplo
◮ Exemplo 12
Considerando o sistema F (10, 3,−5, 5).
Qual o menor nu´mero em valor absoluto que esse sistema pode
representar?
◮ Soluc¸a˜o:
+0,100× 10−5 = 10−1 × 10−5 = 10−6
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Exemplo
◮ Exemplo 13
Considerando o sistema F (10, 3,−5, 5).
Qual o maior nu´mero que esse sistema pode representar?
◮ Soluc¸a˜o:
+0,999× 105 = 99900
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Representac¸a˜o em Ponto Flutuante
◮ Sejam m e M , respectivamente, o menor e o maior valores absolutos
representa´veis no sistema F (β, t, L, U)
◮ Dado um nu´mero x, enta˜o
◮ Se m ≤ |x| ≤M , enta˜o o nu´mero pode ser representado no sistema
◮ Os valores podem ser arredondados ou truncados
◮ Truncamento: d´ıgitos dt+1dt+2 . . . sa˜o removidos
◮ Arredondamento: na base 10, ale´m de remover os d´ıgitos dt+1dt+2 . . . ,
soma-se 1 ao d´ıgito dt se dt+1 ≥ 5,
◮ Se |x| ≤ m, enta˜o o nu´mero na˜o pode ser representado no sistema e
diz-se que ocorre underflow
◮ Se |x| ≥M , enta˜o o nu´mero na˜o pode ser representado no sistema e
diz-se que ocorre overflow
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Exemplo
◮ Exemplo 14
Considerando o sistema F (2, 3,−1, 2) com truncamento.
Represente o nu´mero (0,38)10 nesse sistema.
◮ Soluc¸a˜o:
(0,38)10 ≈ (0,0110)2 ⇒ +0,110× 2
−1
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Exemplo
◮ Exemplo 15
Considerando o sistema F (2, 3,−1, 2) com truncamento.
Represente o nu´mero (5,3)10 nesse sistema.
◮ Soluc¸a˜o:
(5,3)10 ≈ (101)2 ⇒ +0,101×2
3 ⇒ overflow
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Exemplo
◮ Exemplo 16
Considerando o sistema F (2, 3,−1, 2) com truncamento.
Represente o nu´mero (0,15)10 nesse sistema.
◮ Soluc¸a˜o:
(0,15)10 ≈ (0,00100)2 ⇒ +0,100× 2
−2 ⇒ underflow
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Padra˜o IEEE 754
◮ Define os formatos adequados para representar nu´meros (bina´rios) em
ponto flutuante
◮ precisa˜o simples (32 bits)
◮ precisa˜o dupla (64 bits)
◮ Um nu´mero e´ representado na forma normalizada como
±1,d1d2 . . . dt × 2
e
◮ Em precisa˜o simples
◮ 1 bit para o sinal
◮ 8 bits para o expoente
◮ 23 bits para a mantissa
± e1e2 . . . e8 d1d2 . . . d23
Heder S. Bernardino Ca´lculo Nume´rico
Representac¸a˜o de Nu´meros Reais no Computador
Padra˜o IEEE 754
◮ Como o sistema e´ bina´rio e normalizado enta˜o ganha-se 1 bit na
mantissa
◮ chamado de bit escondido
◮ Os oito bits do expoente (precisa˜o simples) representam o nu´mero
s = e+ 127
◮ ou seja, e = s− 127
◮ Possui representac¸o˜es para
◮ zero
◮ +∞
◮ −∞
◮ NaN (Not a Number)
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Sistemas de numerac¸a˜o
◮ Representac¸a˜o de nu´meros inteiros no computador
◮ Conversa˜o de bases
◮ Complemento a 2
◮ Representac¸a˜o de nu´meros reais no computador
◮ Conversa˜o de nu´meros fraciona´rios
◮ Representac¸a˜o em ponto flutuante
◮ Padra˜o IEEE 754
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Du´vidas?
Heder S. Bernardino Ca´lculo Nume´rico
	Aula Anterior
	Introdução
	Sistemas de Numeração
	Representação de Números Inteiros no Computador
	Representação de Números Reais no Computador
	Revisão