View
5
Download
0
Category
Preview:
Citation preview
Erros de Computação e
Representação Numérica
Computação – 2º Semestre 2016/2017
Exactidão e Precisão
Para caracterizar os resultados associados a cálculos e
medidas.
Exactidão (accuracy):
O valor calculado ou medido
estar próximo do valor real
Precisão (precision):
O valor calculado ou medido
estar próximo de outros
valores calculados ou medidos
214 Março 2017 Erros de Computação e Representação Numérica
Tipos de Erros Erros grosseiros ou enganos:
Programação, software,…
Erros do modelo: Simplificações e idealizações
(ex: coeficiente de resistência constante)
Incerteza nos dados: Erros de medição
(ex: uso do valor médio e informação estatística)
Erros de truncatura: Aproximações de um procedimento matemático para um número finito de
operações aritméticas.
(ex: truncatura de série infinita ou sequência iterativa antes da convergência)
Erros de arredondamento: Representação aproximada dos números reais e das operações aritméticas
(ex: irracionais não podem ser representados por um número finito de dígitos)
3Erros de Computação e Representação Numérica14 Março 2017
Tipos de Erros
Erros grosseiros ou enganos
Erros do modelo
Incerteza nos dados
Erros de truncatura
Erros de arredondamento
A qualidade dos resultados depende da sua conjugação
A incerteza no input pode ser amplificada pelo problema
Condicionamento de um problema
Erros cometidos durante a computação podem ser amplificados pelo método numérico
Estabilidade de um método
4Erros de Computação e Representação Numérica
Antes da computação
Durante a computação
14 Março 2017
Condicionamento de um problema
Um problema cuja solução é muito sensível a variações nos
dados (ou parâmetros) diz-se mal condicionado.
É bem condicionado se pequenas variações nos dados e
parâmetros induzem pequenas variações na solução.
A condição de f em x é uma medida quantitativa da
sensibilidade de f(x) a uma alteração de x:
O problema é mal condicionado se Cond >>1
5Erros de Computação e Representação Numérica
xf
xfx
x
xx
xf
xfxf
xfCondxx
~
~
lim~
14 Março 2017
Condicionamento de um problema
Ex: a função Tangente é sensível para valores perto de /2
A variação relativa no resultado é um quarto de milhão de
vezes maior que a variação relativa no argumento
6Erros de Computação e Representação Numérica
51058058.157079.1tan
41012490.657078.1tan
51048275.257079.1tan Cond
14 Março 2017
Instabilidade de um método
Um método numérico diz-se instável se a acumulação dos
erros durante o processo de cálculo tiver grande influência
no resultado final.
Num método estável, o efeito dos erros computacionais é
comparável ao efeito de pequenos erros de input.
A estabilidade não garante a qualidade dos resultados
Esta depende do condicionamento do problema e da
estabilidade do método
Usar um método estável num problema bem condicionado
produz sempre bons resultados.
7Erros de Computação e Representação Numérica14 Março 2017
Erro Absoluto e Erro Relativo
Erro (E):
diferença entre o valor exacto (x) e o valor aproximado ( )
Erro absoluto (|E|):
valor absoluto do erro (E)
Erro relativo ():
razão entre o erro (E) e o valor exacto (x)
8Erros de Computação e Representação Numérica
x~
xxE ~
xxE ~
x
xx ~
x
xx ~ %100
14 Março 2017
Algarismos Significativos
Notação Científica Normalizada:
Representação na forma com R, Z e
Ex:
Algarismos Significativos:
O número de algarismos de a em notação científica normalizada
Ex:
Ex:
9Erros de Computação e Representação Numérica
ba 10 101 aa b310250.1 5103.5 510300.5 31025.1
410250.1 3 2103.5 5
410300.5 5 31025.1 3
410250.11250 3
2103.5000053.0 5
410300.500005300.0 5
14 Março 2017
Algarismos Significativos
O número de algarismos significativos exactos de uma aproximação indica a qualidade da aproximação.
Quanto maior for o número de algarismos significativos exactos, menor é o erro relativo.
10Erros de Computação e Representação Numérica
3333.0~
3
1 xx(4 alg. sig.)
0003.0~
3000
1 yy(1 alg. sig.)
%01.0...3333333.0
...0000333.0~~
x
xxx %10
...0003333.0
...0000333.0~~
y
yyy
3333.0...3333333.0~~ xxEx
...0000333.0
0003.0...0003333.0~~ yyEy
...0000333.0
%01.0...0003333.0
...30000000333.0
...0003333.0
0003333.0...0003333.01
~
y3
1 103333.0~ y(4 alg. sig.)
14 Março 2017
Algarismos Significativos
Quanto menor for o erro relativo, maior é o número de
algarismos significativos exactos da aproximação.
11Erros de Computação e Representação Numérica
xnn
x~%105.0105.0 2
~ (n alg. sig.)
3333.0~
3
1 xx(4 alg. sig.)
0003.0~
3000
1 yy(1 alg. sig.)
xx~%105.0%105.0%01.0 321
~ (3 alg. sig.)
yy~%105.0%105.0%10 022
~ (0 alg. sig.)
14 Março 2017
Estimativas de Erro
Erro relativo ():
razão entre o erro (E) e o valor exacto (x)
mas normalmente não sabemos o valor exacto (x)!
Estimativa do erro relativo ( ):
razão entre o erro estimado ( ) e o valor aproximado ( )
Em métodos numéricos iterativos:
12Erros de Computação e Representação Numérica
~
x
E
x
xx
~ %100
x~
x
E~
~~ %100
i
iii
x
xx~
~~~ 1 %100 (critério de paragem: )%~ toli
14 Março 2017
𝐸
Estimativas de Erro
Exemplo de método numérico iterativo
Cálculo de y=e0.5 com 3 algarismos significativos:
Valor do erro relativo que garante a correcção dos 3 alg. sig.
Estimativa inicial:
Iterações:
13Erros de Computação e Representação Numérica
!!321
32
n
xxxxe
nx
%05.0%05.0105.0 3~ toly
1~0 y
!
5.0~~1
iyy
i
ii
i
iii
y
yy~
~~~ 1
5.0
5.0 ~
e
ye ii
5.15.0~~01 yy %3.33
5.1
15.1~1
%02.9
5.15.0
5.0
1
e
e
625.1~2 y 2
1.625 1.57.69%
1.625
%44.1
625.15.0
5.0
2
e
e
648697917.1~6 y %0158.0~
6 %00142.06 <tol
e0.5=1.648721…
14 Março 2017
Erros de Arredondamento
Diferença entre o resultado obtido pelo algoritmo com
aritmética exacta e o mesmo algoritmo com aritmética de
precisão limitada.
Originados pela representação aproximada dos números
reais e das operações aritméticas
Representação em Vírgula Flutuante
Algumas manipulações numéricas são muito sensíveis a
erros de arredondamento
Aritmética em Vírgula Flutuante
14Erros de Computação e Representação Numérica14 Março 2017
Representação Numérica
Representação decimal:
Representação binária:
15Erros de Computação e Representação Numérica
21012 10610710710510276.257
1875.11
)21212020(
)21212021()0011.1011(
10
4321
0123
2
14 Março 2017
Representação Numérica
Conversão de um inteiro para representação binária:
Conversão de uma fracção para representação binária:
16Erros de Computação e Representação Numérica
Quociente Resto
11/2 5
5/2 2
2/2 1
1/2 0
01 a
11 a
20 a
31 a
2
20123
10
)1011()(
)11(
aaaa
Produto Parte fraccionária
Parteinteira
0.375 0.375
0.75 0.75
1.5 0.5
1.0 0.0
10 a
20 a
31 a
41 a
21875.0
2375.0
275.0
25.0
2
24321
10
)0011.0()(
)1875.0(
aaaa
14 Março 2017
(11.1875)10= (1011.0011)2=1 × 23 + 0 × 22+1 × 21+1 × 20 + 0 × 2−1 + 0 × 2−2+1 × 2−3+1 × 2−4
Representação Numérica
Alguns números fraccionários não têm representação
binária exacta:
17Erros de Computação e Representação Numérica
Produto Parte fraccionária
Parte inteira
0.6 0.6
1.2 0.2
0.4 0.4
0.8 0.8
1.6 0.6
23.0
26.0
22.0 24.0 28.0
10 a
21 a
30 a
40 a
51 a
28125.0)01001.0()()3.0( 225432110 aaaaa
50.29882812)010011001.0( 2
14 Março 2017
Representação Binária em Vírgula Flutuante
Representação binária da forma:
sinal (0 para números positivos; 1 para números negativos)
mantissa
expoente (inteiro negativo ou positivo)
Ex: representação com palavras de 9 bits
1º bit: sinal do número; 2º bit: sinal do expoente
4 bits seguintes: mantissa; 3 bits seguintes: expoente
18Erros de Computação e Representação Numérica
ems 2
s
32122 .1101 aaammm (1 não é guardado!)
e
2101
2
5
2
210
21011.1
21011011.1
11.11011075.54
0 0 1 0 1 1 1 0 1
Sinal do
número
mantissa
Sinal do
expoente
expoente
14 Março 2017
Representação Binária em Vírgula Flutuante
A precisão da máquina é a diferença entre o número
1 e o número seguinte que pode ser representado
Ex: representação com palavras de 10 bits
1º bit: sinal do número; 2º bit: sinal do expoente
4 bits seguintes: expoente; 4 bits seguintes: mantissa
19Erros de Computação e Representação Numérica
mach
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
4210625.1 mach
Número
seguinte
101
102 0625.10001.1
(número de bits da mantissa)
Sinal do
númeroSinal do
expoente
expoente mantissa
14 Março 2017
Representação Binária em Vírgula Flutuante
O erro relativo || na representação de um número é
menor do que a precisão da máquina
Ex: representação com palavras de 10 bits
20Erros de Computação e Representação Numérica
mach
2
5
10 2
0101
2
0.02832 1.1100 2
1.1100 2
0 1 0 1 0 1 1 1 0 0
2
0101
2
4
1.1100 2 0.0274375
0.02832 0.0274375
0.02832
0.034472 2 0.0625
Sinal do
númeromantissaSinal do
expoente
expoente
14 Março 2017
Norma IEEE-754
Standard para aritmética em vírgula flutuante:
Formatos para representação de números em vírgula flutuante.
ex: de precisão simples (32 bits) e de precisão dupla (64 bits)
Regras de arredondamento.
ex: propriedades das conversões entre formatos
Operações aritméticas em vírgula flutuante.
Referência: What every computer scientist should know about
floating point arithmetic!
http://www.validlab.com/goldberg/paper.pdf
21Erros de Computação e Representação Numérica14 Março 2017
Representação Numérica em MATLAB
O MATLAB adoptou o formato de precisão dupla (64 bits)
da norma IEEE-754.
Palavras de 64 bits
22Erros de Computação e Representação Numérica
52 bits
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 … 0 0 0 0 0 0 0 0 0
Sinal (s) Expoente (e’) Mantissa (m)
1023'
221)1(Valor . es m
11 bits1 bit
(evita o bit do sinal do expoente)
14 Março 2017
Representação Numérica em MATLAB
Ex:Palavras de 64 bits
23Erros de Computação e Representação Numérica
52 bits
1 1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 … 0 0 0 0 0 0 0 0 0
Sinal (s) Expoente (e’) Mantissa (m)
1023'
221)1(Valor . es m
11 bits1 bit
1023)01000010001(
2
12210100000.11
102310582625.11
1035 105834.52625.11
14 Março 2017
Representação Numérica em MATLAB
Expoente:
11 bits para representar o e’:
e’=0 (tudo zeros) e e’=2047 (tudo uns) são reservados para
casos especiais, logo:
Casos especiais:
24Erros de Computação e Representação Numérica
2047222'0 0910 e
10232046102311023' eee
2046'1 e
10231022 e
s e' m Representa
0 tudo zeros tudo zeros 0
1 tudo zeros tudo zeros -0
0 tudo uns tudo zeros
1 tudo uns tudo zeros
0 ou 1 tudo uns não-zero NaN
14 Março 2017
Representação Numérica em MATLAB
Maior número representável (>> realmax):
Menor número representável (>> realmin):
Precisão da máquina (>> eps):
Permite uma representação aproximada de qualquer
número com cerca de 15/16 algarismos significativos:
25Erros de Computação e Representação Numérica
30810241023
2 107977.1221........1.1
30810221022
2 102251.2220........0.1
1652 102204.22 mach
xn
x~105.0~ (n alg. sig.)
xmachx~105.0102204.2 1516
~ (15 alg. sig.)
14 Março 2017
Aritmética em Vírgula Flutuante
Adição e Subtracção
com o ajuste da mantissa para igualar os expoentes podem-se
perder algarismos do número mais pequeno
ex: representação decimal (4-dígitos mantissa; 1-dígito expoente)
26Erros de Computação e Representação Numérica
04341.0
557.1
60041.1
1101557.0 110004341.0 110160041.0
1101600.0
1.764
2.764
1.0
3107642.0 3107641.0 3100001.0
0101000.0
(perde 2 alg. sig.)
(acrescenta 3 alg. não sig.)
14 Março 2017
Aritmética em Vírgula Flutuante
Multiplicação
o produto entre dois números com n-dígitos de mantissa pode
resultar num número não representável com 2n-dígitos de mantissa
ex: representação decimal (4-dígitos mantissa; 1-dígito expoente)
Divisão
o quociente entre dois números com n-dígitos de mantissa pode
resultar num número não representável
ex: 1/10 não é representável numa sequência binária finita
27Erros de Computação e Representação Numérica
06357.0
4.192
230868.12
3101924.0 1106357.0
21012230868.0
2101223.0
(perde 4 alg. sig.)
210 ...)01100110001100110.0()1.0(
14 Março 2017
Erros de Truncatura
Diferença entre o resultado correcto e o obtido por um
determinado algoritmo com aritmética exacta.
Originados por truncatura de séries infinitas ou interrupção
de uma sequência iterativa antes da convergência.
Ex: truncatura da Série de Taylor
28Erros de Computação e Representação Numérica14 Março 2017
Série de Taylor
Permite exprimir o valor de uma função num dado ponto
através de uma soma de termos (do valor da função e suas
derivadas num outro ponto)
O termo do resto, Rn, representa toda a soma dos termos
de n+1 a infinito:
29Erros de Computação e Representação Numérica
n
n
iii
n
iii
iii
ii Rxxn
xfxx
xfxx
xfxfxf )(
!
)()(
!2
)()(
!1
)()()( 1
)(2
1
"
1
'
1
11
)1()1(
,max,,min)!1(
)(
iiii
nn
n xxxxhn
fR
n
ni
n
iiii Rh
n
xfh
xfh
xfxfxf
!
)(
!2
)(
!1
)()()(
)(2
"'
1
ii xxh 1
14 Março 2017
Série de Taylor
Considerando x=xi+1, uma função f(x) pode ser aproximada por um polinómio da ordem que se quiser:
ordem zero:
primeira ordem:
segunda ordem:
n-ésima ordem:
Cada termo contribui para uma melhoria na aproximação.
Em geral, só com um número infinito de termos se pode garantir o resultado exacto.
Frequentemente, com apenas alguns termos obtêm-se boas aproximações em termos práticos.
30Erros de Computação e Representação Numérica
))(()()( '
iii xxxfxfxf
)()( ixfxf
n
ii
n
ii
ii
i xxn
xfxx
xfxx
xfxfxf )(
!
)()(
!2
)()(
!1
)()()(
)(2
"'
2"'
)(!2
)()(
!1
)()()( i
ii
ii xx
xfxx
xfxfxf
14 Março 2017
Série de Taylor
Aproximação da função:
De xi = 0 com h = 1 aproximar o valor de f(x) no ponto xi+1 = 1
31Erros de Computação e Representação Numérica
432 1.015.05.025.02.1)( xxxxxf
14 Março 2017
Série de Taylor
Aproximação de f(x) = ex
escolher x = xi+1 e xi = 0
como (ex)’ = ex tem-se: (ex)’ = (ex)” = (ex)(n) = ex
e como e0 =1 ficamos com a aproximação:
32Erros de Computação e Representação Numérica
n
iii
n
iii
iii
ii xxn
xfxx
xfxx
xfxfxf )(
!
)()(
!2
)()(
!1
)()()( 1
)(2
1
"
1
'
1
nn
xn
fx
fx
ffxf
!
)0(
!2
)0(
!1
)0()0()(
)(2
"'
nx xn
ex
ex
eee
!!2!1
02
000
!!21
2
n
xxxe
nx
14 Março 2017
Série de Taylor
Erro de truncatura Rn de uma aproximação de ordem n:
Em geral não se sabe o valor de
Diz-se que o erro de truncatura Rn é de ordem n+1:
quanto maior for o n menor é o erro (0<h<1)
quanto menor for o h menor é o erro (0<h<1)
Ex: se o erro é de ordem 1, O(h), ao reduzir para metade o h o erro é também
reduzido para metade;
se o erro é de ordem 2, O(h2), ao reduzir para metade o h o erro é reduzido para um quarto;
33Erros de Computação e Representação Numérica
11
)1()1(
,max,,min)!1(
)(
iiii
nn
n xxxxhn
fR
ii xxh 1
1 n
n hOR
14 Março 2017
Erro Numérico Total
Soma dos erros de truncatura e de arredondamento.
Os erros de truncatura aumentam com o passo h
Os erros de arredondamento diminuem com o aumento de h
Existe um ponto a partir do qual não vale a pena reduzir o passo porque a diminuição dos erros de truncatura não compensa o aumento dos erros de arredondamento
34Erros de Computação e Representação Numérica14 Março 2017
Recommended