- Seja
Descreve o algoritmo para calcular valor da função
utilizando um sistema de ponto flutuante, tal que o erro relativo do resultado será da ordem do erro da representação.
Passo 1
O enunciado dá a função
e pede: descrever um algoritmo para calcular
num sistema de ponto flutuante de forma que o erro relativo do resultado seja da ordem do erro da representação (ou seja, da ordem do unit roundoff
).
Informações relevantes do enunciado: a função é dada para todo ; não foi imposta nenhuma restrição adicional sobre
. O objetivo é obter uma fórmula/algoritmo numericamente estável (pequeno erro relativo).
Informações relevantes do enunciado: a função é dada para todo
Passo 2
Por que o método direto pode ser ruim (no bom e velho português): calcular diretamente
e depois fazer a subtração pode causar cancelamento catastrófico quando
é grande. Vou explicar isso devagar.
O que é cancelamento: se dois números grandes e muito próximos são subtraídos, a diferença é pequena e muitas casas significativas se perdem devido ao arredondamento do ponto flutuante. Por exemplo, se
e
são representados com erro relativo da ordem de
e
, então
pode ter erro absoluto da ordem de
, enquanto o valor exato de
poderia ser muito menor — isto faz o erro relativo explodir.
Aplicando ao nosso caso: para
grande temos
então a diferença é da ordem de
. Subtrair dois termos da ordem de
para obter
é exatamente o cenário de cancelamento.
Passo 3
A identidade algébrica que salva o dia (e que você deve decorar para fins de prova): multiplicar e dividir pela soma (conjugado) elimina a subtração problemática. Faço o passo a passo:
Começo com
Multiplico numerador e denominador pela soma:
No numerador fica a diferença de quadrados:
Portanto obtemos a identidade exata
Essa forma não envolve subtração entre dois grandes termos; ao contrário, a resposta é o inverso de uma soma de termos do mesmo sinal — muito melhor numericamente.
Passo 4
Como calcular
de forma robusta num sistema de ponto flutuante?
Problema secundário: calcular
pode causar overflow se
for muito grande. Duas opções práticas e seguras:
- Usar a rotina padrão e confiável de bibliotecas chamada
. A função
é implementada nas boas bibliotecas de forma a evitar overflow/underflow por escalamento interno. Assim podemos obter
- Se
não estiver disponível, usar escalamento com . Defina . Se trate como caso especial (veja abaixo). Se , escreva
Como
e
são números pequenos quando
é grande, a expressão
é bem condicionada e não sofre overflow no cálculo do quadrado de
. Note que multiplicar por
não resolve overflow se
em si já é do tamanho do overflow máximo; aí a melhor escolha é usar
ou algum outro escalamento global (dividir por potências de 2 e depois restaurar). Para a maioria dos casos práticos, a fórmula com
é suficiente e evita cancelamento.
Caso especial: se
(ou
muito pequeno), a identidade também funciona; especificamente se
a forma reduz a
mas não há problema em calcular diretamente
.
Passo 5
Algoritmo prático e simples (prefira este se
estiver disponível):
- Calcule
. (Usar evita tratar sinais.) - Calcule
- Retorne
Se
não estiver disponível, use este raminho alternativo seguro:
- Calcule
. - Se
retorne . - Caso contrário calcule
- Defina
- Retorne
Esses passos evitam a subtração de números quase iguais e, salvo problemas extremos de overflow de
em si, produzem resultado com pequeno erro relativo.
Passo 6
Análise do erro (explicada devagar e sem formalismo pesado):
- Suponha que a raiz quadrada/hypot retorna um valor com erro relativo da ordem de
(unidade de arredondamento). Então os valores calculados e satisfazem
com
.
-
A soma
difere de por um termo relativo também na ordem de : com (a soma pode introduzir um pequeno erro absoluto, mas proporcional a ). -
Ao tirar o inverso numericamente, o erro relativo adicional também é da ordem de
. Em resumo o processo inteira (duas raízes/hypot, soma, inverso) acumula erros que permanecem . Não ocorre cancelamento catastrófico porque não fizemos subtração entre dois grandes e quase iguais.
Conclusão da análise: o valor retornado
satisfaz
ou seja, o erro relativo do resultado é da ordem do erro da representação.
Passo 7
Exemplo numérico ilustrativo (para sentir a diferença):
Considere
(só para ver o estrago). Pela identidade:
Se você fizer as raízes e subtrair diretamente com precisão de máquina típica (
), o arredondamento nas duas raízes (cada uma da ordem de
) pode destruir várias casas da diferença e produzir um resultado com erro relativo muito grande. O algoritmo com
ou com o escalamento acima devolve um valor com erro relativo
, isto é, uma boa aproximação de
.
Passo 8
Resumo prático e recomendações para prova/implementação:
- Memorize a fatoração/conjugado que leva a
- Na implementação, use
para calcular sem overflow/underflow. Se não houver , implemente o escalamento por e calcule . - Trate
como caso trivial (ou a identidade já funciona). - Com esses cuidados o erro relativo final fica na ordem de
.
Resposta
Algoritmo recomendado: calcular
; calcular
e
; devolver
.
Se não existir: se
devolver
, senão calcular
,
,
,
e devolver
.
Se