Analise de Erros 4pp

Prévia do material em texto

1
Computação Científica II
(EEL7031)
Análise de Erros
e 
Aritmética de Ponto Flutuante
2
Análise de Erros e Aritmética de Ponto 
Flutuante
� Objetivos:
� Estudar a representação aproximada de números reais em notação 
digital de computadores e o modo de execução da operações.
� Obter uma base de conhecimentos para a análise e depuração de 
algoritmos, bem como para a validação de resultados obtidos através 
de métodos numéricos.
� Temas principais:
� Introdução
� Representação de números
� Sistemas de ponto flutuante
� Funções de arredondamento
� Tipos de erros que surgem com arredondamentos
� Conceitos de precisão e exatidão
� Instabilidade de algoritmos e problemas
3
Elementos da Simulação de Sistemas Físicos
Modelo Matemático
Programa Computacional
Resultados Numéricos
Algoritmo de Solução
Modelagem
Método de Solução
Implementação 
computacional
Processamento
� Equações algébricas:
� Lineares
� Não-lineares
� Equações diferenciais:
� Ordinárias
� Parciais
Sistema Físico
4
Simulação de Sistemas Físicos
� Aspectos gerais:
� A obtenção de uma solução numérica para um problema físico nem 
sempre fornece valores que se encaixam dentro de limites razoáveis, 
mesmo quando se aplicam métodos matemáticos adequados e os 
cálculos são efetuados de uma maneira correta.
� Deve-se ter bons conhecimentos relativos a todas as etapas da 
modelagem e simulação de sistemas físicos para a validação dos 
resultados numéricos obtidos.
� As operações em computadores digitais são realizadas com precisão 
aritmética finita, gerando erros ao longo de suas execuções.
� É importante ter conhecimentos razoáveis sobre a aritmética de 
precisão finita para se realizar avaliações a priori e delimitar os 
efeitos dos erros nos resultados dos algoritmos utilizados.
� Na simulação de sistemas físicos deve-se ter uma clara distinção 
entre problemas mal-condicionados e algoritmos numericamente 
instáveis.
5
Representação de Números
� Um número N qualquer pode ser descrito numa base β
usando a seguinte forma polinomial:
� Exemplos:
�Base 10 (decimal): a mais emprega
�Base 2 ( binária): usada pelos computadores
, 
aFracionári Parte
2
2
1
1
Inteira Parte
0
0
1
1
1
1
����� upcurlybracketright����� upcurlybracketmidupcurlybracketleft
…
������ upcurlybracketright������ upcurlybracketmidupcurlybracketleft
… nn
m
m
m
m aaaaaaaN
−
−
−
−
−
−
−
− ++++++++= βββββββ , 
aFracionári Parte
2
2
1
1
Inteira Parte
0
0
1
1
1
1
����� upcurlybracketright����� upcurlybracketmidupcurlybracketleft
…
������ upcurlybracketright������ upcurlybracketmidupcurlybracketleft
… nn
m
m
m
m aaaaaaaN
−
−
−
−
−
−
−
− ++++++++= βββββββ
10 :onde −≤≤ βka 10 :onde −≤≤ βka
012
10 107104103)347( ∗+∗+∗=
012
10 107104103)347( ∗+∗+∗=
10
01234
2 )23(124016 2121212021)10111( =++++=∗+∗+∗+∗+∗= 10
01234
2 )23(124016 2121212021)10111( =++++=∗+∗+∗+∗+∗=
Os algarismos que representam o número na base β são os coeficientes do 
polinômio. 6
Conversão de Bases
� Base β base decimal:
� Levar os coeficientes à expressão polinomial e calcular o valor
� Base decimal base β - números inteiros
� Dividir o número sucessivamente pela base β até que o último 
quociente seja maior que zero e menor que β. O número é 
representado pelo último quociente e os restos, na ordem inversa.
10
321
2 )875.0(212121)111.0( =∗+∗+∗=
−−−
10
321
2 )875.0(212121)111.0( =∗+∗+∗=
−−−
210 )1101()13( = 210 )1101()13( =
7
Conversão de Bases
� Base decimal base β - números fracionários:
� Multiplicar o número fracionário por β. A parte inteira deste resultado 
é o primeiro dígito do número na base β . 
� A parte fracionária restante é novamente multiplicada por β para se 
obter o próximo dígito do número na base β.
� Repetir o passo anterior até que a parte fracionária do último produto 
seja nula, caso de representações exatas.
� No caso da representação não ser exata haverá uma seqüência
infinita da parte fracionária, sendo o número representado pelas 
partes inteiras resultantes.
� Ex. 1:
� Ex. 2:
210 )111.0()875.0( =
210 )0110001100110.0()1.0( …= 210 )0110001100110.0()1.0( …=
Este e muitos outros números não tem representação finita na base 2.
 
 00.1)250.0(
50.1)2750.0(
750.1)2875.0(










=∗
=∗
=∗
⇔
8
Outros exemplos de Conversão de Bases
� Converter (13.25)10 base 2:
� Parte inteira:
� Parte fracionária 
210 )01.0()25.0( = 210 )01.0()25.0( = 
 00.1)250.0(
50.0)225.0(






=∗
=∗⇔
101010 )25.0()13()25.13( +=
210 )1101()13( = 210 )1101()13( =
� Converter (-111.001)2 base decimal:
]212020212121[)001.111( 3210122
−−− ∗+∗+∗+∗+∗+∗−=− ]212020212121[)001.111( 3210122
−−− ∗+∗+∗+∗+∗+∗−=−
102 )125,7(]125.0124[)001.111( −=+++−=− 102 )125,7(]125.0124[)001.111( −=+++−=−
9
Sistema de Ponto Flutuante
� Aspectos gerais:
� Os números reais são aproximados por números racionais em 
máquinas digitais de precisão finita (número de dígitos 
limitados), incorrendo em erros que podem ser amplificados à 
medida que as operações aritméticas são executadas.
10
� - conjuntos dos números naturais e inteiros, respectivamente;
� β é denominada de base, β≥2;
� é denominado de expoente;
� m é denominado de mantissa;
� n é o máximo de dígitos usados;
� , são os dígitos do número.
Sistema de Ponto Flutuante
� Definição 1: 
� Um é dito um número de ponto flutuante normalizado se:Rx∈
 Z , ,1 ,0 ; )
,,2 ; 10 e 11 )
N ;.0 )
 )
maxminmaxminmaxmin
1
21
∈≥≤≤≤
=−≤≤−≤≤
∈±=
∗=
eeeeeeed
njddc
ndddmb
mxa
j
n
e
⋯
⋯
ββ
β
 Z , ,1 ,0 ; )
,,2 ; 10 e 11 )
N ;.0 )
 )
maxminmaxminmaxmin
1
21
∈≥≤≤≤
=−≤≤−≤≤
∈±=
∗=
eeeeeeed
njddc
ndddmb
mxa
j
n
e
⋯
⋯
ββ
β
2
2 )2100.0(
 :Exemplo
∗=x 2
2 )2100.0(
 :Exemplo
∗=x
onde:
maxmin eee ≤≤
njd j ,,2,1 ; ⋯=
ZN e 
11
Sistema de Ponto Flutuante
precisão. a é e base a é expoente,maior o emenor o
 mente,respectiva são, e onde ),,,,( maxminmaxmin
n
eeeenFF
β
β=
precisão. a é e base a é expoente,maior o emenor o
 mente,respectiva são, e onde ),,,,( maxminmaxmin
n
eeeenFF
β
β=
� Definição 2:
� A união de todos os números de ponto flutuante com o ZERO, 
representado na forma é chamado de sistema 
de ponto flutuante (SPF) e representado por: 
min00000.00
eβ∗= …
� Características:
� Os sistemas de ponto flutuante são caracterizados pelos 
seguintes elementos:
�base β (binária, decimal, hexadecimal, etc.)
�precisão n (número de algarismos da mantissa)
� limites do expoente e )( maxmin eee ≤≤
12
Sistema de Ponto Flutuante
� Exemplo:
� Representar 25 num SPF com n=10, β=2, emin=-15 e emax=15
101
10
5
210
211001.0)25(
 
211001.0)11001()25(
∗=
⇓
∗==
101
10
5
210
211001.0)25(
 
211001.0)11001()25(
∗=
⇓
∗== �
expoente do Sinalmantissa da Sinal
expoentemantissa
 
01010 1100100000 0
↑↑
�upcurlybracketright�upcurlybracketmidupcurlybracketleft �
expoente do Sinalmantissa da Sinal
expoentemantissa
 
01010 1100100000 0
↑↑
�upcurlybracketright�upcurlybracketmidupcurlybracketleft
13
Sistemas de Ponto Flutuante
� Propriedades:
� Menor número em módulo:
� Maior número:
� Cardinalidade de :� Cardinalidade pode ser determinada como segue:
� número de mantissas positivas: 
�Número de expoentes possíveis:
�Números possíveis: 
� Incluindo-se os negativos e o zero, resulta:
min1.0
eβ∗ min1.0 eβ∗
max]1[]1][1.[0
eββββ ∗−−− ⋯ max]1[]1][1.[0 eββββ ∗−−− ⋯
),,,( maxmin eenFF β=
1)1)()(1(2# minmax
1 ++−−= − eeF nββ 1)1)()(1(2# minmax
1 ++−−= − eeF nββ
))(1( 1−− nββ ))(1( 1−− nββ
)1( minmax +− ee )1( minmax +− ee
)1)()(1( minmax
1 +−− − eenββ )1)()(1( minmax
1 +−− − eenββ
1)1)()(1(2# minmax
1 ++−−= − eeF nββ 1)1)()(1(2# minmax
1 ++−−= − eeF nββ 14
Sistemas de Ponto Flutuante
� Exemplo: Seja 
� Mantissas: 0.100, 0.101, 0.110, 0.111
� Expoentes admissíveis: -1, 0, 1, 2
� Números positivos: 
)2,1,3,2(),,,( maxmin −== FeenFF β
2/7212121)1.11()2(0.111
 
22021)10()2100.0(
1)1()2100.0(
2/12120)1.0()2100.0(
4/1212020)01.0()2100.0(
101
22
2
01
22
2
22
1
10
22
0
210
22
1
=∗+∗+∗==∗
=∗+∗==∗
==∗
=∗+∗==∗
=∗+∗+∗==∗
−
−−
−−−
⋮
2/7212121)1.11()2(0.111
 
22021)10()2100.0(
1)1()2100.0(
2/12120)1.0()2100.0(
4/1212020)01.0()2100.0(
101
22
2
01
22
2
22
1
10
22
0
210
22
1
=∗+∗+∗==∗
=∗+∗==∗
==∗
=∗+∗==∗
=∗+∗+∗==∗
−
−−
−−−
⋮
15
Sistemas de Ponto Flutuante
� Exemplo: Elementos do SPF )2,1,3,2(),,,( maxmin −== FeenFF β
16
Sistemas de Ponto Flutuante
� Limites de representação: 
� Região de Underflow: 
�Região situada entre o maior número de ponto flutuante negativo 
e o ZERO e, simetricamente, entre o menor número de ponto 
flutuante positivo e o ZERO.
� Região de Overflow: 
�Regiões situadas aquém do menor número de ponto flutuante 
negativo e além do maior número de ponto flutuante positivo.
17
Sistemas de Ponto Flutuante
� Exemplo de aplicação para o SPF : 
� Suponha x=5/4 e y=3/8 em F e note que:
)2,1,3,2( −= FF
Fzyxz ; 
8
13
8
3
4
5
∉=+=+= Fzyxz ; 
8
13
8
3
4
5
∉=+=+=
� Na representação deve-se escolher entre:
2
1)2110.0(
2
3
∗= 2
1)2110.0(
2
3
∗= 2
1)2111.0(
4
7
∗= 2
1)2111.0(
4
7
∗=ou
Esse tipo de escolha dá origem a diferentes tipos de arredondamento
2
1
10
10
)21101.0()625.1(
8
13
∗==





2
1
10
10
)21101.0()625.1(
8
13
∗==





18
Sistemas de Ponto Flutuante
� Exemplo de aplicação para o SPF: 
� Considere os números:
)100,98,5,2( −= FF
F∉= 210 )0110001100110.0()1.0( … F∉= 210 )0110001100110.0()1.0( …
� Somando-se cada um dos números sucessivamente 10 vezes, 
resulta:
10
10
1
10 )0.1()1.0( =∑ 10
10
1
10 )0.1()1.0( =∑102
10
1
2
3 )96875.0()11111.0()211001.0( ==∗∑ − 102
10
1
2
3 )96875.0()11111.0()211001.0( ==∗∑ −
F∈∗≅ − 2
3
10 )211001.0()1.0( F∈∗≅
−
2
3
10 )211001.0()1.0(e
≠
Truncamento
19
Sistemas de Ponto Flutuante
� Exemplo de aplicação para o SPF: 
� Considere:
� Determinar: 
2
0
2
1
2
0 )2110.0(
4
3
 e )2110.0( 
8
3
 ;)2101.0(
8
5
∗==∗==∗== − zyx 2
0
2
1
2
0 )2110.0(
4
3
 e )2110.0( 
8
3
 ;)2101.0(
8
5
∗==∗==∗== − zyx
)2,1,3,2( −= FF
zyxs ++= )(1 zyxs ++= )(1 e )(2 zyxs ++= )(2 zyxs ++=
11.1110.0.1
110.0)011.0101.0( 
)2110.0())2110.0()2101.0((
1
010
1
=+=
++=
∗+∗+∗= −
s
s
10.1
101.1001.1101.0 
)110.0011.0(101.0 
2
2
=
=+=
++=
s
s
21 ss ≠
20
Sistemas de Ponto Flutuante
Máquina e Aritmética β m emin emax Precisão
Cray-1 Precisão Simples 2 48 -8192 8191 4 x 10-15
Cray-1 Precisão Dupla 2 96 -8192 8191 1 x 10-29
DEC VAX formato G Dupla 2 53 -1023 1023 1 x 10-16
DEC VAX formato D Dupla 2 56 -127 127 1 x 10-17
Calculadoras HP 28 e 48G 10 12 -499 499 5 x 10-12
IBM 3090 Precisão Simples 16 6 -64 63 5 x 10-07
IBM 3090 Precisão Dupla 16 14 -64 63 1 x 10-16
IBM 3090 Precisão Estendida 16 28 -64 63 2 x 10-33
IEEE Precisão Simples 2 24 -126 127 6 x 10-8
IEEE Precisão Dupla 2 53 -1022 1023 1 x 10-16
IEEE Precisão Extendida 2 64 -16381 16384 5 x 10-20
PDP 11 2 24 -128 127 1.19 x 10-7
Control Data 6600 2 48 -976 1070 7.11 x 10-13
Parâmetros de Aritmética de Ponto Flutuante
21
Exercícios Propostos
� Considere os sistemas de ponto flutuante abaixo: 
a) HP25: F(10,9,-98,100)
b) IBM360.370: F(16,6,-64,63)
c) B6700: F(8,13,-51,77)
� Determinar para cada um destes sistemas:
� A cardinalidade;
� O maior e o menor número em módulo que podem ser representados;
� As regiões de overflow e underflow.
� Considere o SPF :
� Calcule, usando truncamento,
para:
)2,1,3,2( −= FF
 )( e )( 21 yzxczyxc +−=−+= )( e )( 21 yzxczyxc +−=−+=
111 2100.0 e 2101.0 ;2110.0 ∗=∗=∗= − zyx 111 2100.0 e 2101.0 ;2110.0 ∗=∗=∗= − zyx
22
Arredondamentos
� Aspectos gerais: 
� Há diferentes maneiras de se aproximar um número real para um 
número de ponto flutuante e, então, a questão principal é como 
realizar tal aproximação.
� Definição:
� Seja um sistema de ponto flutuante. Uma 
função é considerada um arredondamento se valer:
),,,( maxmin eenFF β=
F→ℜΓ :
xxFx =Γ∈∀ )(, xxFx =Γ∈∀ )(,
� Tipos de arredondamento: 
� Arredondamento para cima ou excesso:
� Arredondamento para baixo ou por falta:
� Arredondamento para o número de máquina mais próximo: 
x∆x∆
x∇x∇
oxox
23
Arredondamentos
� Exemplo 1: 
� Seja o sistema de ponto flutuante. 
� O número , pois:
� Podemos realizar o arredondamento nas seguintes formas:
)2,1,3,2( −= FF
F∉
8
9
2
1
10 )21001.0()125.1(
8
9
∗== 2
1
10 )21001.0()125.1(
8
9
∗==
102
1 )0.1()2100.0(
8
9
=∗=




∇ 102
1 )0.1()2100.0(
8
9
=∗=




∇ou
10
10
2
1 )25.1(
4
5
)2101.0(
8
9
=




=∗=




∆ 10
10
2
1 )25.1(
4
5
)2101.0(
8
9
=




=∗=




∆
24
Arredondamentos
� Definições 1: 
� Um arredondamento é dito por falta se:
� Um arredondamento é dito por excesso se:
� Um arredondamento é dito monotônico se valer: 
F→ℜΓ : xxx ≤Γℜ∈∀ )(,
F→ℜΓ : xxx ≥Γℜ∈∀ )(,
)()(,, yTxyxyx ≤Γ⇒≤ℜ∈∀ )()(,, yTxyxyx ≤Γ⇒≤ℜ∈∀
� Exemplo: 
� Seja o sistema de ponto flutuante, e sejam: 
� Então, obtém-se os seguintes resultados para os diferentes 
arredondamentos.
)10,98,4,10( −= FF
666666.0 e 348436.0 ;333333.0 === zyx 666666.0 e 348436.0 ;333333.0 === zyx
6667.03484.03333.0
6667.0)(3485.0)(3334.0)(
6666.0)(3484.0)(3333.0)(
===
=∆=∆=∆
=∇=∇=∇
ozoyox
zyx
zyx
6667.03484.03333.0
6667.0)(3485.0)(3334.0)(
6666.0)(3484.0)(3333.0)(
===
=∆=∆=∆
=∇=∇=∇
ozoyox
zyx
zyx
excessopor monotônico entoarredondam :)(
faltapor monotônico entoarredondam :)(
x
x
∆
∇
excessopor monotônico entoarredondam :)(
faltapor monotônico entoarredondam :)(
x
x
∆
∇
25
Erros
� Aspetos gerais 
� Erros são cometidos toda vez que não for possível uma representação 
exata em F, ou seja, toda vez em que for necessário algum tipo de 
arredondamento.
� Tipos de erros:
� Erros Inerentes: surgem no processo de elaboração ou simplificação 
do modelo matemática de um sistema físico.
� Erros de Discretização: erros cometidos quando se substitui qualquer 
processo infinito por um processo finito oudiscreto.
� Erros de Aredondamento: sugerem na representação de números 
reais em máquinas digitais. Em geral, é utilizado o arredondamento 
para o número de ponto flutuante mais próximo ou o arredondamento 
por falta.
∑∑
=
∞
=
≅=
N
ii ii
z
00 !
1
!
1
∑∑
=
∞
=
≅=
N
ii ii
z
00 !
1
!
1
26
Cálculo de Erros
� Definição geral 
� A diferença entre o valor arredondado e o valor exato pode ser medida 
pelo erro absoluto ou pelo erro relativo, definidos a seguir.
� Erro absoluto:
� O erro absoluto é dado por: 
� Erro relativo:
� O erro relativo de é dado por:
� Exemplo:
AE
Não é possível exibir esta imagem no momento.Não é possível exibir esta imagem no momento.
RE
x
xx
ER
−Γ
=
)(
x
xx
ER
−Γ
=
)(
)(
)(
x
xx
ER Γ
−Γ
=
)(
)(
x
xx
ER Γ
−Γ
=ou
00005.0)(
00006.0
=Γ
=
x
x
00005.0)(
00006.0
=Γ
=
x
x
00001.0=AE 2.0
00005.0
00001.0
==RE
27
Dígitos Significativos Exatos -DSE
� Aspectos gerais:
� O erros absoluto e relativo em máquinas digitais somente podem ser 
calculados se for conhecido o valor exato, fato incomum na prática. A 
alternativa é trabalhar com o conceito de dígitos significativos.
� Definição 1: 
� Um dígito é significativo, em um sistema decimal, se for 1,2,...,9. O 
dígito 0 é significante, exceto quando for usado para fixar a vírgula, 
ou o ponto decimal, ou preencher o lugar de dígitos descartados.
ivossignificat dígitos 2 23.000 
ivos;significat dígitos 5 30.357 ivos;significat dígitos 4 008735.0
→
→→
ivossignificat dígitos 2 23.000 
ivos;significat dígitos 5 30.357 ivos;significat dígitos 4 008735.0
→
→→
� Definição 2: 
� Um dígito significativo é exato se, arredondando-se o número 
aproximado para uma posição imediatamente após aquela posição 
do dígito, isso fizer com que o erro absoluto não seja maior do que a 
meia unidade naquela posição do dígito. 28
Dígitos Significativos Exatos - DSE
� Considere as seguintes aproximações para 2/3: 
� Primeiro caso: 0.66667 (determinar o erro absoluto em relação a 2/3)
000005.000000333.06666666.0666670.0:dígito 5
 
0005.000006666.06666666.06666.0 :dígito 3
005.00006666.06666.0666.0 :dígito 2
05.0006666.06666.066.0 :dígito 1
0
0
0
0
<+=−
<−=−
<−=−
<−=−
……
⋮
……
……
……
000005.000000333.06666666.0666670.0:dígito 5
 
0005.000006666.06666666.06666.0 :dígito 3
005.00006666.06666.0666.0 :dígito 2
05.0006666.06666.066.0 :dígito 1
0
0
0
0
<+=−
<−=−
<−=−
<−=−
……
⋮
……
……
……
Todos os dígitos significativos de 0.66667 são exatos.
29
Dígitos Significativos Exatos - DSE
� Exemplo (cont.):
� Segundo caso: 0.666998 (determinar o erro absoluto em relação a 2/3)
00005.0000323.066666.066699.0 :dígito 4
05.0006666.06666.066.0 :dígito 1
0
0
>−=−
<−=−
……
……
00005.0000323.066666.066699.0 :dígito 4
05.0006666.06666.066.0 :dígito 1
0
0
>−=−
<−=−
……
……
� Teorema:
� Se , então o número é correto em m dígitos 
significativos exatos.
m
RE
−≤ β
2
1
O quarto dígito significativo (9) não é exato
30
Dígitos Significativos Exatos - DSE
� Fórmulas de aplicação prática:
� Caso 1- Valor exato conhecido:
� Caso 2 – Valor exato desconhecido:
�Nas situações em que , então o número de dígitos 
significativos de xj em relação xj+1 é dado por:
;
)(
log3.0( 10 






 Γ−
++−=
x
xx
DSE µ ;
)(
log3.0( 10 






 Γ−
++−=
x
xx
DSE µ
jj xx ∞→= lim















 −
++−=
+
+
j
jj
jj
x
xx
xxDSE
1
1 log3.0),( µ















 −
++−=
+
+
j
jj
jj
x
xx
xxDSE
1
1 log3.0),( µ
onde µ é a unidade de erro de arredondamento.
Dígitos significativos exatos de xj em relação xj+1
31
Precisão e Exatidão
� Aspectos gerais:
� A precisão de uma máquina digital é definida automaticamente pelo 
sistema de ponto flutuante associado.
� Definição 1 – Épsilon de máquina:
� O épsilon da máquina é o menor número de ponto flutuante tal que
� Definição 2 – Precisão:
� A precisão de uma máquina digital é definida como o número de 
dígitos da mantissa dessa máquina.
� Definição 3 - Exatidão:
� A exatidão é uma medida de perfeição do resultado e depende da 
precisão da máquina e do método utilizado para a obtenção do 
resultado.
11 >+ ε 11 >+ ε
32
Precisão e Exatidão
� Exemplo:
� Considere as aproximações para π da tabela ao abaixo.
Todas as aproximações possuem a 
mesma precisão ( 5 casas decimais), 
mas somente uma delas possui 5 
dígitos significativos exatos.
Aproximação x j DSE (x j ,ππππ)
3.1410 3.4
3.1411 3.5
3.1412 3.6
3.1413 3.7
3.1414 3.9
3.1415 4.2
3.1416 5.3
3.1417 4.2
3.1418 3.7
3.1419 3.6
33
Precisão e Exatidão
� Exemplo: Seja o número racional 
� 1,4142 é mais preciso e mais exato que 1.41, pois o primeiro tem 
maior número de casas decimais e aproxima melhor 
� 1,4149 é mais preciso que 1.414, pois tem mais casas decimais, 
porém, é menos exato do que 1.414, já que o dígito 9 do primeiro não 
é exato.
…414213562.12 = …414213562.12 =
22
34
Instabilidade
� Aspectos gerais:
� Instabilidade pode ser entendida como uma sensibilidade a 
perturbações e pode ocorrer tanto no problema em si (modelo 
matemático) como no algoritmo, isto é, na maneira de resolvê-lo.
� Indutores de erros:
� Modelos ou entrada de dados (erros inerentes)
� Arredondamento ou truncamento 
35
Instabilidade dos Algoritmos
� Exemplo 1- Função exponencial:
� A instabilidade de algoritmos pode ser ilustrada através do exemplo 
de se calcular a constante de Euler por série de Taylor.
� Para x = 1 e x = -5.5, tem-se: (para um determinado truncamento)
� Comparação com os resultados fornecidos por uma calculadora:
⋯+++++=
!4!32
1
432 xxx
xex ⋯+++++=
!4!32
1
432 xxx
xex
7183.25E 4801.25.0111 =+−++++≅ ……e 7183.25E 4801.25.0111 =+−++++≅ ……e
718281828.21 =calce 718281828.2
1 =calce
6
1 1068.6
718281828.2
7183.2718281828.2 −∗=
−
=RE
6
1 1068.6
718281828.2
7183.2718281828.2 −∗=
−
=RE
90040867143.05.5 =−calce 90040867143.0
5.5 =−calce 35.0
0026363.0
0026363.090040867143.0
2 =
−
=RE 35.0
0026363.0
0026363.090040867143.0
2 =
−
=RE
0026363.0942.41129.38730.27125.155.515.5 =−+−+−≅− …e 0026363.0942.41129.38730.27125.155.515.5 =−+−+−≅− …e
36
Instabilidade dos Algoritmos
� Causas da elevada diferença: 
� A causa do erro é uma combinação de dois fatores:
�somas de grandezas de diferentes ordens; e
�subtração de grandezas quase iguais.
� Tal fenômeno é conhecido como cancelamento subtrativo ou 
cancelamento catastrófico, bastante comum em cálculos.
� Cancelamento subtrativo
� O cancelamento subtrativo não é a real causa do erro final da soma, 
ele apenas aumentou o efeito do erro final.
� Note que na primeira soma (para e), não houve tal aumento.
� Se mudarmos o cálculo de e−5.5 para 1/e5.5 e utilizarmos as mesmas 
parcelas obteremos 0.0040865, com erro relativo de 6.6 × 10−5.
21 RR EE ≠
A série de Taylor pode ser utilizada para argumentos positivos
37
Instabilidade dos Algoritmos
� Exemplo 2- Função exponencial:
� Valores obtidos para usando e ∑
=
=
T
j
j
j
x
xf
0 !
)(xe 0 qdo )(/1 <− xxf
Note que o erro resultante da aproximação f(x) é elevado para x<0
x f(x) 1/f(-x) e
x(Matlab) |e
x
-f(x)|/e
x
|e
x
-1/f(-x)|/e
x
-40 50.810 4.2484e-018 4.2484e-0.18 10e020 5.4400e-016
-20 4.1736e-009 2.0612e-009 2.0612e-009 102.48 2.0066e-016
-10 4.5400e-005 4.5400e-005 4.5400e-005 7.2342e-007 2.9851e-016
-5 6.7379e-003 6.7379e-003 6.7379e-003 2.1369e-011 2.5746e-016
-2 0.13534 0.13534 0.13534 4.1018e-014 2.0509e-016
-1 0.36788 0.36788 0.36788 3.0179e-014 1.5089e-016
0 1.0000 1.0000 0.0000
1 2.7183 2.7183 0.0000
2 7.3891 7.3891 2.4040e-014
5 1.4841e+002 1.4841e+002 1.9150e-014
10 2.2026e+004 2.2026e+004 3.3033e-014
20 4.8517e+008 4.8517e+008 2.4571e-014
38
Instabilidade dos Algoritmos
� Exemplo 3 – Calcular 
� Integrando por partes resulta: 
� Usando , tem-se os seguintes valores: 
…,2,1 para ;1
1
0
== −∫ ndxexy xnn
e
ynnyy nn
1
 onde ;,3,2 ,1 11 ==−= − …
e
ynnyy nn
1
 onde ;,3,2 ,1 11 ==−= − …
068480.0127120.0207274.0
118720.0145480.0264242.0
110160.0170904.0367879.0
963
852
741
−≅≅≅
≅≅≅
≅≅≅
yyy
yyy
yyy
068480.0127120.0207274.0
118720.0145480.0264242.0
110160.0170904.0367879.0
963
852
741
−≅≅≅
≅≅≅
≅≅≅
yyy
yyy
yyy
)99,98,6,10( −= FF
Note que o integrando é sempre positivo no intervalo [0,1]
� Causas do erro: 
� foi feito somente um erro de arredondamento em y1 quando 1/e foi 
tomado como 0.367879 em vez de 0.367879442.
� O erro final é devido somente a este erro, pois a fórmula está correta.
39
Instabilidade dos Algoritmos
� Exemplo 3 – Análise
� Note pelo algoritmo que em y2 o erro foi multiplicado por 
(-2), em y3 por (-3) e assim sucessivamente.
� Então, o erro em y9 é o erro em y1 multiplicado por (-2)(-3)...(-9)=9!
� Sendo: 
11 −−= nn nyy
7
1 10412.4367879.0
1 −∗=−=
e
E 71 10412.4367879.0
1 −∗=−=
e
E
Note que embora a fórmula esteja correta ela é instável
1601.0!*9 19 ≅= EE 1601.0!*9 19 ≅= EE
40
Instabilidade dos Algoritmos
� Exemplo 3 – Algoritmo Estável
� Um algoritmo alternativo estável é dado por
� Nesta fórmula, a cada passo, o valor do erro em yn é decrescido por 
1/n (em vez de multiplicado por n).
� Se começarmos com n ≫ 1 voltaremos e então o erro inicial ou erros 
de arredondamento diminuirão a cada passo.
� Resta-nos saber qual será o valor inicial para yn.
� Observamos que:
� Logo, yn tende a zero quando n tende para o infinito.
2,3,4 ,
1
1 …=
−
=− n
n
y
y nn
1
1
1
1
0
11
0
1
1
0
+
=





+
=≤=
+
− ∫∫ nn
x
dxxdxexy
n
nxn
n
1
1
1
1
0
11
0
1
1
0
+
=





+
=≤=
+
− ∫∫ nn
x
dxxdxexy
n
nxn
n
41
Instabilidade dos Algoritmos
� Exemplo 3 – Algoritmo Estável (cont.)
� Aproximando y20 por zero, obtém-se:
0916123.00669477.00527778.0
0838771.00627322.00500000.0
0773523.00590176.00500000.0
0717733.00557190.00
91317
101418
111519
121620
≅≅≅
≅≅≅
≅≅≅
≅≅≅
yyy
yyy
yyy
yyy
0916123.00669477.00527778.0
0838771.00627322.00500000.0
0773523.00590176.00500000.0
0717733.00557190.00
91317
101418
111519
121620
≅≅≅
≅≅≅
≅≅≅
≅≅≅
yyy
yyy
yyy
yyy
� Majorando o erro em y20 por 1/21, tem-se:
8
15
18
19
104
 
00012.0
21
1
20
1
19
1
0024.0
21
1
20
1
−∗≅
≅∗∗=
≅∗=
E
E
E
⋮ 3678795.01455329.0
2642411.01268024.0
2072767.01123835.0
1708934.01009320.0
15
26
37
48
==
==
==
==
yy
yy
yy
yy
3678795.01455329.0
2642411.01268024.0
2072767.01123835.0
1708934.01009320.0
15
26
37
48
==
==
==
==
yy
yy
yy
yy
42
Instabilidade dos Algoritmos
� Outras fontes de erros:
� Calculo da média aritmética de dois números a e b:
{ }
{ }m
sm
bas
ba
 saida .4
2/ .3
 .2
, entrada .1
:1 Algoritmo
←
+←
{ }
{ }m
SSm
bS
aS
ba
 saida .5
 .4
2/ .3
2/ .2
, entrada .1
:2 Algoritmo
21
2
1
+←
=
=
{ }
{ }m
dbm
dd
bad
ba
 saida .5
 .4
2/ .3
 .2
, entrada .1
:3 Algoritmo
1
11
1
+←
=
−=
� Análise:
� Para um dado F=F(β, n, emim, emax) podemos ter, conforme a, b Є F, 
os seguintes problemas:
� Algoritmo 1: overflow em 2
� Algoritmo 2: underflow em 2 e 3
� Algoritmo 3: não haverá erro operacional, mas poderá ocorrer erro no 
comando 2 se houver cancelamento subtrativo.
43
Instabilidade de Problemas ou Modelos
� Aspectos gerais:
� Os sistemas físicos bem como os seus respectivos modelos 
matemáticos apresentam comportamentos instáveis denominados de 
instabilidade intrínseca. 
� Exemplo Ilustrativo:
� Na figura abaixo observam-se 2 lápis colocados em posição de 
equilíbrio, respectivamente, estável e instável. No caso estável, uma 
pequena perturbação não acarretará a queda, voltando o lápis a 
posição de equilíbrio. O mesmo não ocorrerá no caso instável
44
Instabilidade de Problemas ou Modelos
� Comentários:
�Há problemas que, quando sofrem alterações nos dados 
de entrada, apresentam uma pequena diferença 
proporcional na sua respostas e são denominados bem 
condicionados.
�Outros problemas apresentam grande variação no 
resultado, mesmo para uma pequena alteração nos 
dados, de entrada e são denominados mal 
condicionados.
45
Considerações Finais
� Aspectos gerais:
� Não existe receita simples para o desenvolvimento de algoritmos 
estáveis. É importante considerar, além dos aspectos relacionados 
ao custo computacional e rapidez de convergência da solução, 
aqueles relacionados a preservação da estabilidade numérica.
� Recomendações:
� Evitar, sempre que possível, subtrações com quantidades 
contaminadas por erros.
� Minimizar o tamanho de quantidades intermediárias, relativo à 
solução final.
� Atentar para formulações que são matematicamente, mas não 
numericamente equivalentes.
� É vantajoso expressar atualizações do tipo: valor novo=valor 
velho+pequena correção, se essas pequenas correções forem 
calculadas com muitos dígitos significativos.
� Tome precauções para evitar underflow e overflow.