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

Question

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

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

Sin embargo, tengo algunos problemas para darme cuenta exactamente cuándo va a ocurrir la pérdida de precisión. Hasta ahora, lo único que sé con certeza es que cuando se restan dos números que están cerca de ser iguales, se produce una pérdida de precisión debido a que los dígitos de orden alta son significativos, y los pierdes del redondeo.

Mi pregunta es, ¿cuáles son algunas otras situaciones comunes que debería estar buscando, y qué se consideran 'buenos' métodos para abordarlas?

Por ejemplo, aquí es un problema:

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

¿Cuál es el mejor y el peor algoritmo para evaluar esto fuera 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é algunos de estos algoritmos son mejores o peores para resolver el problema.

Answer 1

Otra regla general que se suele utilizar es la siguiente: Al agregar una serie larga de números, comience a sumar desde los números más cercanos a cero y finalice con los números más grandes.

Explicar por qué esto es bueno es un poco complicado. cuando agrega números pequeños a un número grande, existe la posibilidad de que sean descartados 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 menor que el dígito mantisa más bajo, entonces el bucle no hace nada y el resultado final es un == 1.000.000 pero si lo hace 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.
Esto es por supuesto un ejemplo extremo, pero espero que entiendas la idea.

Answer 2

Tuve que tomar una clase numérica cuando era un estudiante universitario, y fue muy doloroso. De todos modos, IEEE 754 es el estándar de punto flotante implementado típicamente por las CPU modernas. Es útil entender lo básico, ya que esto te da mucha intuición sobre lo que no debes hacer. La explicación simplificada de esto es que las computadoras almacenan números en coma flotante en algo así como la 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 es el valor absoluto de un número, menos preciso 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 números de hasta 10^38 son representables con un flotador 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 por lo general quiere evitar lo siguiente:

1. que tienen valores intermedios ser grandes cuando se espera que la respuesta final a ser pequeño.

2. Sumando/restando números pequeños a/de números grandes. Por ejemplo, si escribió algo así como:

   para (índice de flotación = 17000000; índice de < 17000001; índice ++) {}

Este bucle no terminaría nunca becuase 17.000.000 + 1 se redondea hacia abajo a 17.000.000. Si tuviera algo como:

float foo = 10000000 - 10000000.0001 

El valor de foo sería 0, no -0.0001, debido a errores de redondeo.

Answer 3

Otra cosa que debe evitarse 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 restas que le gustaría evitar si es posible, entonces yo diría que (a) debería evitarse .

Answer 4

Mi pregunta es ¿cuáles son algunas otras situaciones comunes que debe buscar , y lo que se considera 'buena' métodos de acercarse a ellos?

Hay varias maneras 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 dígitos "inútiles" que no son parte de la solución pero deben almacenarse, pierde precisión.

Por ejemplo (Estamos utilizando tipos decimales para la 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 sabe que los dígitos son inútiles, está forzado a almacenarlo y crams 21 ceros después de él, desperdiciando en los 29 dígitos. Lamentablemente, no hay forma de eludir 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 cercana a 0 es casi lineal, pero impone un 1 como dígito inicial. Así, con 12 dígitos significativos exp (0.001) -1 = 1,00100050017-1 = 1.00050017e-3

Si utilizamos lugar un expm1 función(), utilice la serie de 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 los errores de redondeo antes se amplificará por el factor 50000! O tiene singularidades si, por ejemplo, el resultado se acerca a 0/0, eso significa que puede tener cualquier valor.

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

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