¿El mejor algoritmo para evitar la pérdida de precisión?

Question

Una asignación de tarea reciente que recibí nos pide que tomemos expresiones que puedan crear una pérdida de precisión cuando se realizan en la computadora, y las modifiquemos para evitar esta pérdida.

Desafortunadamente, las instrucciones para hacer esto no se han dejado muy claras. Al observar la realización de varios ejemplos, sé que hay ciertos métodos para hacerlo: usar series de Taylor, usar conjugados si hay raíces cuadradas involucradas, o encontrar un denominador común cuando se restan dos fracciones.

Sin embargo, estoy teniendo problemas para notar exactamente cuándo ocurrirá la pérdida de precisión. Hasta ahora, lo único que sé con certeza es que cuando restas dos números que están cerca de ser iguales, se produce una pérdida de precisión ya que los dígitos de alto orden son significativos, y los pierdes del redondeo.

Mi pregunta es ¿cuáles son otras situaciones comunes que debería estar buscando y cuáles son los métodos "buenos" para abordarlos?

Por ejemplo, aquí hay un problema:

f(x) = tan(x) − sin(x)  when x ~ 0

¿Cuál es el mejor y el peor algoritmo para evaluar esto de estas tres opciones?

(a) (1/ cos(x) − 1) sin(x),
(b) (x^3)/2
(c) tan(x)*(sin(x)^2)/(cos(x) + 1).

Entiendo que cuando x está cerca de cero, tan (x) y sin (x) son casi lo mismo. No entiendo cómo o por qué alguno de estos algoritmos es mejor o peor para resolver el problema.

Answer 1

Otra regla general que generalmente se usa es esta: cuando agregue una serie larga de números, comience a sumar desde los números más cercanos a cero y termine con los números más grandes.

Explicar por qué esto es bueno es un poco complicado. cuando agrega números pequeños a números grandes, existe la posibilidad de que se descarten por completo porque son más pequeños que el dígito más bajo en la mantisa actual de un número grande. tomemos por ejemplo esta situación:

a = 1,000,000;
do 100,000,000 time:
   a += 0.01;

si 0.01 es más pequeño que el dígito de mantisa más bajo, entonces el ciclo no hace nada y el resultado final es un == 1,000,000 pero si haces esto así:

a = 0;
do 100,000,000 time:
   a += 0.01;
a += 1,000,000;

Que el número bajo crece lentamente y es más probable que termine con algo cercano a == 2,000,000, que es la respuesta correcta.
Por supuesto, este es un ejemplo extremo, pero espero que entiendan la idea.

Answer 2

Tuve que tomar una clase de numérica cuando era estudiante universitario, y fue completamente doloroso. De todos modos, IEEE 754 es el estándar de coma flotante implementado típicamente por las CPU modernas. Es útil comprender los conceptos básicos, ya que esto le da mucha intuición sobre lo que no debe hacer. La explicación simplificada es que las computadoras almacenan números de coma flotante en una notación científica de base 2 con un número fijo de dígitos (bits) para el exponente y para la mantisa. Esto significa que cuanto mayor sea el valor absoluto de un número, menos precisamente se puede representar. Para flotantes de 32 bits en IEEE 754, la mitad de los patrones de bits posibles representan entre -1 y 1, aunque los números de hasta aproximadamente 10 ^ 38 son representables con una flotante de 32 bits. Para valores mayores a 2 ^ 24 (aproximadamente 16.7 millones) un flotante de 32 bits no puede representar todos los enteros exactamente.

Lo que esto significa para usted es que generalmente desea evitar lo siguiente:

1. Tener valores intermedios grandes cuando la respuesta final se espera que sea pequeña.

2. Sumar / restar números pequeños a / de números grandes. Por ejemplo, si escribió algo como:

   para (índice flotante = 17000000; índice < 17000001; índice ++) {}

Este ciclo nunca terminaría porque 17,000,000 + 1 se redondea a 17,000,000. Si tuviera algo como:

float foo = 10000000 - 10000000.0001

El valor para foo sería 0, no -0,0001, debido al error de redondeo.

Answer 3

  

Mi pregunta es ¿cuáles son algunos otros   situaciones comunes que debería estar buscando   para, y lo que se considera 'bueno'   métodos para acercarse a ellos?

Hay varias formas en que puede tener una pérdida de precisión severa o incluso catastrófica.

La razón más importante es que los números de coma flotante tienen un número limitado de dígitos, por ejemplo, los dobles tienen 53 bits. Eso significa que si tiene & Quot; inútil & Quot; dígitos que no son parte de la solución pero que deben almacenarse, pierde precisión.

Por ejemplo (Estamos usando tipos decimales para demostración):

2.598765000000000000000000000100 -

2.598765000000000000000000000099

La parte interesante es la respuesta 100-99 = 1. Como 2.598765 es igual en ambos casos, no cambia el resultado, pero desperdicia 8 dígitos. Mucho peor, porque la computadora no sabemos que los dígitos son inútiles, se ven obligados a almacenarlo y colocan 21 ceros después, desperdiciando los 29 dígitos. Lamentablemente, no hay forma de evitarlo por las diferencias, pero hay otros casos, p. exp (x) -1, que es una función que ocurre muy a menudo en física.

La función exp cerca de 0 es casi lineal, pero impone un 1 como dígito inicial. Entonces con 12 dígitos significantes exp (0.001) -1 = 1.00100050017 - 1 = 1.00050017e-3

Si usamos en su lugar una función expm1 (), use la serie taylor:

1 + x + x ^ 2/2 + x ^ 3/6 ... -1 =

x + x ^ 2/2 + x ^ 3/6 =: expm1 (x)

expm1 (0.001) = 1.00500166667e-3

Mucho mejor.

El segundo problema son las funciones con una pendiente muy pronunciada como la tangente de x cerca de pi / 2. tan (11) tiene una pendiente de 50000, lo que significa que cualquier pequeña desviación causada por errores de redondeo ¡antes será amplificado por el factor 50000! O tienes singularidades si p. el resultado se acerca a 0/0, eso significa que puede tener cualquier valor.

En ambos casos, crea una función sustituta, simplemente simplificando la función original. No sirve de nada resaltar los diferentes enfoques de solución porque sin entrenamiento simplemente no & "; Ver &"; el problema en primer lugar.

Un muy buen libro para aprender y entrenar: Forman S. Acton: Real Computing hecho real

Answer 4

Otra cosa a evitar es restar números que son casi iguales, ya que esto también puede conducir a una mayor sensibilidad al error de redondeo. Para valores cercanos a 0, cos (x) estará cerca de 1, por lo que 1 / cos (x) - 1 es una de esas sustracciones que le gustaría evitar si es posible, por lo que diría que (a) debe evitarse .