A maior rede de estudos do Brasil

Grátis
217 pág.
NotasdeAula_CN

Pré-visualização | Página 8 de 38

neste caso.
Exemplo 1.17 Se x = 1
3
= 0, 3333333, então x = 0, 3333 × 100 para uma má-
quina com precisão t = 4, com arredondamento do tipo corte.
Se x = 0, 666666.... Então, com t = 5, temos que x = 0, 66667 × 100, com
arredondamento do tipo para número mais próximo de máquina.
erros computacionais 35
Se x = −0, 0004235437, com t = 4, temos então que x = −0, 4235 × 10−3,
cujo valor do último algarismo permaneceu inalterado.
De uma forma geral, se x é um número real, este pode ser escrito, em uma
base β, da forma
x = q × βe = 0, d1 . . . , dt × βe, com 0 ≤ di < β, i = 1, . . . , t. (1.15)
Se x = q × βe, onde q é o valor de q arredondado para o dígito t + 1, temos
que:
|q − q| ≤ 1
2
β−t, (1.16)
e o limite do erro entre os valores é dado por:
|x− x| ≤ 1
2
βe−t. (1.17)
1.3.5 Erros absoluto e relativo
Sejam os valores x exato e x aproximado para uma grandeza.
De�nição 1.8 De�nimos o erro absoluto de uma grande x como:
EA = |x− x|. (1.18)
O erro relativo é de�nido como:
De�nição 1.9 O erro relativo de uma grandeza x é dado por:
ER =
EA
|x| =
|x− x|
|x| . (1.19)
Das expressões (1.17) e (1.19) podemos determinar o limite do erro relativo,
pois temos que:
ER =
|x− x|
|x| ≤
1
2
βe−t
|q|βe =
β−t
2|q| . (1.20)
Aplicando a condição de normalização 0, 1 ≤ |q| < 1, obtemos
ER =
|x− x|
|x| ≤
1
2
β1−t. (1.21)
36 cálculo numérico
De�nição 1.10 De�nimos a unidade de arredondamento de um número em ponto
�utuante como sendo a quantidade
µ =
1
2
β1−t. (1.22)
É importante chamar a atenção para o fato de que a unidade de arredonda-
mento é um valor independente da magnitude do número que está sendo apro-
ximado. A acurácia do resultado de uma grandeza pode ser estimada por seus
erros absoluto e relativo.
Exemplo 1.18 Sejam os valores x = 0, 000008 e x = 0, 000006. Então, os erros
são dados por:
EA = |x− x| = |0, 8× 10−5 − 0, 6× 10−5| = 0, 2× 10−5
ER =
EA
|x| =
0, 2× 10−5
0, 8× 10−5 = 0, 25
O erro absoluto é muito baixo, mas o erro relativo é de 25%.
Exemplo 1.19 Sejam x = 0, 435795× 10−3 e x = 0, 435210× 10−3. Então
ER =
|x− x|
|x| =
5, 85× 10−7
0, 435795× 10−3 = 0, 134237× 10
−2,
ER < 0, 5× 10−2 =⇒ t = 3.
Logo, a aproximação x possui três dígitos signi�cativos exatos; a saber, o 4, o
3 e o 5.
Veja agora que, se aplicarmos o logaritmo na base 10 da expressão (1.21), com
β = 10, temos:
m ≤ log10
(
1
2
)
− log10
( |x− x|
|x|
)
. (1.23)
O maior valor de m na expressão (1.23) representa o número de algarísmos
signi�cativos com que o valor x se aproxima do valor x.
De forma mais geral, escrevemos o valor de m como:
erros computacionais 37
m = −
[
0, 3 + log10
(
µ+
|x− x|
|x|
)]
, (1.24)
onde o termo µ representa a unidade de arredondamento de máquina.
Quando o arredondamento for para o número mais próximo de máquina, temos
que
µ =
1
2
× 101−t. (1.25)
Na prática, não sabemos o valor exato da grandeza x. Assim, o que fazemos,
ao tomar duas medidas consecutivas de x é calcular a grandeza
D(xi, xi+1) = −
[
0, 3 + log10
(
µ+
|xi+1 − xi|
|xi|
)]
, (1.26)
que nos dá o número de dígitos signi�cativos exatos de xi+1 com relação ao valor
xi.
1.4 Propagação de erros
Vejamos agora como ocorre a propagação de erros causados nas operações
aritméticas com ponto �utuante.
1.4.1 Adição
Sejam x e y os valores aproximados de duas grandezas x e y, respectivamente.
Sejam Ex e Ey os erros em x e y. Temos então que:
S = x+ y, (1.27)
S = x+ y, (1.28)
Es = S − S = (x+ y)− (x− y) = (x− x) + (y − y). (1.29)
Logo, temos que:
|Ex+y| ≤ |Ex|+ |Ey|. (1.30)
Isto é, o valor absoluto da soma dos erros absolutos é menor que a soma individual
do valor absoluto dos erros.
38 cálculo numérico
Exercício 1.10 Mostre que, para o erro relativo, a operação de adição resulta
em:
ER(x + y) = max{(ER(x),ER(y)}, (1.31)
para x, y valores com o mesmo sinal.
1.4.2 Subtração
O procedimento para subtração é similar ao da adição; temos que:
Ex−y = Ex − Ey =⇒ (1.32)
|Ex−y| ≤ |Ex|+ |Ey|. (1.33)
Exercício 1.11 Mostre que, para o erro relativo, a operação de subtração resulta
em:
ER(x− y) = ER(x) + ER(y)|x− y| , (1.34)
para quaisquer valores de x, y.
1.4.3 Multiplicação
Seguindo a mesma construção anterior, vemos que:
Ex?y ' xEy + y Ex =⇒ (1.35)
|Ex?y| ≤ |x| |Ey|+ |y| |Ex|. (1.36)
Exercício 1.12 Mostre que, para o erro relativo, a operação de multiplicação
resulta em:
ER(x · y) ≈ ER(x) + ER(y),
para quaisquer valores de x, y.
erros computacionais 39
1.4.4 Divisão
Finalmente, seguindo o mesmo procedimento, temos para a divisão:
|Ex/y| ≤ |y| |Ex|+ |x| |Ey||y|2. (1.37)
Observamos que, na divisão, se dividirmos um número em ponto �utuante
por outro número muito pequeno, temos a propagação de um erro muito grande,
já que o termo na expressão anterior está dividido pelo quadrado do valor da
grandeza aproximada.
Exercício 1.13 Mostre que para o erro relativo, a operação de divisão resulta
em:
ER(x/y) ≈ ER(x) + ER(y),
para quaisquer valores de x, y, y 6= 0.
Exemplo 1.20 Sejam x = 3, 2548, com |Ex| ≤ 0, 5 × 10−4 e y = 0, 0351, com
|Ey| ≤ 0, 5× 10−4.
Temos que:
Ex/y ≤ 0, 1335 < 0, 5× 100.
1.4.5 Operação geral
Se de�nirmos � como uma operação genérica qualquer e �∗ como uma pseu-
do-operação, vemos que para:
x = x+ Ex,
y = y + Ey,
x � y − x �∗ y = (x � y − x � y) + (x � y − x �∗ y). (1.38)
Assim, observando a equação (1.38), podemos interpretar o primeiro termo do
lado direito da equação como correspondendo a um erro introduzido pelos valores
numéricos e o segundo termo como correspondendo a um erro introduzido pela
máquina.
Teorema 1.1 Seja a operação � qualquer uma das operações aritméticas
+,−,×,÷. Então,
40 cálculo numérico
∣∣∣∣x� y − x� yx� y
∣∣∣∣ ≤ µ, (1.39)
para x� y 6= 0, ou de forma equivalente,
x� y = (x� y)(1 + ε), (1.40)
para algum ε > 0 satisfazendo à condição |ε| < µ, com µ a unidade de arredon-
damento.
Uma das conseqüências do Teorema 1.1 é que o resultado da comparação entre
dois valores reais, por meio de um teste Booleano de igualdade é, em geral, falso,
pois há o erro devido ao ε da máquina. Portanto, um teste Booleano da forma
x = y deve ser substituído pelo teste |x− y| < ε.
1.5 Complexidade computacional
Ao longo deste livro apresentaremos várias técnicas numéricas para resolu-
ção de problemas de diferentes naturezas. Em certas ocasiões veremos mais de
uma técnica, as quais podem ser empregadas para a resolução do mesmo tipo
de problema. Tais técnicas são convertidas, no formalismo computacional, em
procedimentos que chamamos de algorítmos. Assim, podemos ter vários algorít-
mos destinados à resolução de um mesmo tipo de problema.
Na Ciência da Computação é comum de�nir-se o custo computacional de um
algoritmo para a resolução de um problema. Em termos simples, o custo com-
putacional de um algoritmo está relacionado a dois fatores: primeiro ao número
de passos necessários resolver um problema, que se re�ete em um custo deno-
minado temporal e, segundo, na quantidade de memória utilizada para resolver
um problema, que é denominado custo espacial. Formalmente, o custo computa-
cional re�ete a complexidade do algoritmo. A complexidade de um algoritmo é
uma função do tamanho do problema a ser tratado. Mais adiante, na Seção 2.3,
veremos que a complexidade dos algoritmos para determinar o valor numérico de
um polinômio depende do grau, n, do polinômio, isto é, do tamanho do problema
a ser resolvido.
Em geral, no cálculo numérico estamos mais interessados na complexidade
temporal, relacionando esta ao número de operações que devem ser executadas
por um algoritmo para resolver um problema. A complexidade temporal pode
ser vista de duas formas: