Representação de números e teoria de erros


Representação em Ponto Flutuante
Começamos por ver como representamos um qualquer número real.
Um número real é uma classe de equivalência de sucessões de Cauchy de racionais. Como tal, pode admitir várias representações, mas normalmente tomamos como representante dessa classe uma sucessão de racionais que são múltiplos de uma potência de 10 (base decimal):

Notação Científica:

x = ± 0. a1 a2 ... an ... × 10t
No caso da notação científica, um número representa-se através do sinal, da mantissa e do expoente, na base decimal. Os dígitos variam entre 0 e 9, mas o primeiro dígito da mantissa deve ser diferente de zero (o número zero é representado à parte).

Mas, a menos que estivessemos na posse de uma máquina com memória infinita (... máquina de Turing), a representação de um número deve ser finita, pelo que, consequentemente somos obrigados a considerar um número finito de dígitos na mantissa e uma limitação nos valores dos expoentes admitidos.

Sistema de Ponto Flutuante (também designado Vírgula Flutuante)
O sistema FP(ß, n, t1, t2) é o conjunto dos números

x = ± 0. a1 a2 ... an × ßt
com a1¹0, (onde t varia em { t1, ..., t2} ) e em que o zero é representado à parte.
Habitualmente usamos ß=10, e nos computadores ß=2 (neste caso os dígitos ai podem ser apenas 0 ou 1)

Overflow: Acontece se o valor do expoente t é superior a t2.
Underflow: Acontece se o valor do expoente t é inferior a t1.

Arredondamento
Dado um número, representado em notação científica
x = ± 0. a1 a2 ... an an+1 ... × 10t
ao armazená-lo num sistema FP somos obrigados a suprimir dígitos da mantissa.
Para efectuar essa conversão podemos considerar dois tipos de arredondamento:
  • Arredondamento por Corte
    • fl(x) = ± 0. a1 a2 ... an × 10t
  • Arredondamento Simétrico
    • fl(x) = ± 0. a'1 a'2 ... a'n × 10t'
    Os dígitos a'i coincidem com ai e o expoente t' coincide com t, se an+1 < 5.
    Se an+1 > 5 então os dígitos a'i e o expoente t' resultam da representação da soma de
    0. a1 a2 ... an × 10t com 0.1 × 10t - n+1.


    Definição: Consideremos x um valor exacto e x~ um valor aproximado de x. Definimos:
    Erro : ex= x - x~
    Erro Absoluto : | ex | = | x - x~ |
    Erro Relativo : |dx | = | x - x~ | / | x |   (se x¹0)


    Como em cada operação são efectuados arredondamentos, convém estabelecer um majorante u para esses erros, de forma que
    |darr | = | x - fl( x ) | / | x | < u
    O majorante u é designado unidade de arredondamento. onde ß = 10 é a base.

    Propagação de erros. Condicionamento e Estabilidade.

    Consideramos agora a propagação de erros por aplicação de uma função ou de uma operação.
    Assim, pretendemos prever o erro relativo em f(x~) face ao valor correcto f(x).
    Por aplicação da fórmula de Taylor, para uma função regular obtemos
    f(x~) = f(x)+f '(x)ex+ o(ex)
    Portanto, desprezando o termo o(ex), obtemos ef(x)»f '(x)ex
    Dividindo por f(x), obtemos então a fórmula para o erro relativo
    df(x) » x f '(x)
      f(x)    		 dx
    que nos permite avaliar a propagação do erro por aplicação de uma função.
    O valor Pf (x) = x f '(x)/f(x) é designado número de condição de f em x.
    Se este valor for elevado isso significa que há um grande incremento do erro relativo por aplicação da função. Uma situação em que isso é claro, é quando Pf (z) = ¥ e tomamos um valor z~ próximo de z.

    De forma semelhante, para funções de várias variáveis, podemos aplicar a fórmula de Taylor para várias variáveis e obter resultados análogos. Um caso que nos interessa considerar é o caso de operações elementares, como a soma ou a multiplicação, que podem ser vistas como funções de duas variáveis.
    Assim, para a soma (ou subtracção) temos

    dx+y »    x
    (x+y)    		 dx +     y
    (x+y)    		 dy
    o que nos indica imediatamente que haverá problemas quando x» -y, ou seja no caso da subtracção de quantidades semelhantes. Este caso é normalmente designado por cancelamento subtractivo e pode ser responsável pela forte propagação de erros de arredondamento, devido a um acumular de erros em sucessivas subtracções de quantidades próximas.
    No caso da multiplicação (ou divisão), esse problema já não acontece pois temos
    dxy » dx +  dy

    Propagação em Algoritmos
    Na maioria das vezes o resultado de uma função é obtido através de um algoritmo que permite decompor o seu cálculo em vários passos que nos levam a funções já programadas.
    Assim, para calcularmos os valores de f(x) = cos(x) - log(x2+cos(x)), podemos considerar o algoritmo em 5 passos:
    z1 = cos(x), z2 = x2, z3 = z1+z2, z4 = log(z3), z5 = z1-z4
    No entanto, em cada um destes passos devemos considerar um erro, já que pelo menos haverá uma representação inexacta do valor real, devido ao arredondamento para o sistema FP.
    Assim, ao analisarmos a propagação dos erros, temos

    dz1 » - x tan(x)dx +darr1
    dz2 » 2dx +darr2
    dz3 » (z1 dz1+ z2 dz2 ) /(z1+z2) + darr3 = (cos(x)dz1 + x2dz2 )/(x2+cos(x)) + darr3 =
    = (cos(x)(- x tan(x)dx +darr1) + x2(2dx +darr2))/(x2+cos(x)) + darr3 = ...
    dz4 » dz3 / log(z3) + darr4 = (...)
    dz5 » (z1 dz1 - z4 dz4 ) /(z1-z4) + darr5 = (...)
    O resultado final pode ser expresso em termos de
    dz5 » Pf(x)dx + q1darr1+...+ q4darr4+ darr5
    em que o valor Pf(x) é exactamente o número de condição, e em que os coeficientes q1, ..., q4 são valores que dependem de x e podem ser elevados mesmo quando Pf(x) não o é. Ainda que esses coeficientes estejam apenas a multiplicar pelos pequenos erros relativos de arredondamento (que serão em módulo inferiores à unidade de arredondamento), a sua acumulação num algoritmo extenso pode provocar alterações significativas no resultado.


    Condicionamento e Estabilidade
    Identificamos assim um outro tipo de problema que pode não estar relacionado com a função, mas sim com a maneira como o cálculo efectuado, através do algoritmo. Poderá acontecer que dois algoritmos diferentes, equivalentes do ponto vista algébrico, não o sejam do ponto de vista numérico, devido à propagação de erros. Distinguimos assim duas noções:

    Definição: Um problema diz-se bem condicionado se pequenos erros relativos nos dados produzem pequenos erros relativos no resultado. Caso contrário, diz-se mal condicionado.

    (O caso de mau condicionamento para cálculo de uma função corresponde a ter um número de condição Pf elevado)
     

    Definição: Um algoritmo é numericamente estável se a pequenos erros relativos dos dados, e a pequenos valores da unidade de arredondamento, corresponder um pequeno erro relativo nos resultados. Caso contrário, diz-se numericamente instável.

    (O caso de instabilidade numérica corresponde a ter um número de condição Pf elevado ou um dos coeficientes qk elevado)
    É claro que um algoritmo implementado num problema mal condicionado nunca poderá ser estável.
     

    Observação: A noção de "pequeno" pode parecer ambígua, e depende da exigência de rigor pretendida nos resultados. Normalmente deve ser encarada como uma medida comparativa entre os diversos algoritmos disponíveis. Assim, ao obtermos para um determinado algoritmo

    | d resultados | <M ( u + max { | ddados | } )
    para uma certa constante M > 0, podemos dizer que ele é estável, e através dessa constante podemos comparar a sua estabilidade com outros.