¿Qué algoritmo es más preciso para calcular la suma de una matriz ordenada de números?

Se da una secuencia finita creciente de números positivos . ¿Cuál de los siguientes dos algoritmos es mejor para calcular la suma de los números?$z_{1} ,z_{2},.....z_{n}$

s=0; 
for \ i=1:n 
    s=s + z_{i} ; 
end

O:

s=0; 
for \ i=1:n 
s=s + z_{n-i+1} ; 
end

En mi opinión, sería mejor comenzar a sumar los números del número más grande al más pequeño, porque el error se hace cada vez más pequeño. También sabemos que cuando agregamos un número muy grande a un número muy pequeño, el resultado aproximado puede ser el número grande.

¿Es esto correcto? ¿Qué más se puede decir?

Agregar números arbitrarios de coma flotante generalmente dará algún error de redondeo, y el error de redondeo será proporcional al tamaño del resultado. Si calcula una suma única y comienza agregando primero los números más grandes, el resultado promedio será mayor. Entonces comenzarías a sumar con los números más pequeños.

Pero obtiene un mejor resultado (y se ejecuta más rápido) si produce cuatro sumas, por ejemplo: Comience con sum1, sum2, sum3, sum4 y agregue cuatro elementos de matriz a su vez a sum1, sum2, sum3, sum4. Como cada resultado es en promedio solo 1/4 de la suma original, su error es cuatro veces menor.

Mejor aún: agregue los números en pares. Luego agrega los resultados en pares. Agregue esos resultados en pares nuevamente, y así sucesivamente hasta que le queden dos números para agregar.

Muy simple: use mayor precisión. Use el doble largo para calcular una suma de dobles. Use el doble para calcular una suma de carrozas.

Casi perfecto: busca el algoritmo de Kahan, descrito anteriormente. Mejor aún se usa agregando comenzando con el número más pequeño.

¿Son estos números enteros o de coma flotante? Suponiendo que sea punto flotante, iría con la primera opción. Es mejor sumar los números más pequeños entre sí, luego sumar los números más grandes más tarde. Con la segunda opción, que va a terminar la adición de una pequeña cantidad de un gran número que i se incrementa, lo que puede conducir a problemas. Aquí hay un buen recurso sobre aritmética de coma flotante: lo que todo informático debe saber sobre la aritmética de coma flotante

La respuesta de animal_magic es correcta: debe agregar los números de menor a mayor, sin embargo, quiero dar un ejemplo para mostrar por qué.

Supongamos que estamos trabajando en un formato de coma flotante que nos da la asombrosa precisión de 3 dígitos. Ahora queremos agregar diez números:

[1000, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Por supuesto, la respuesta exacta es 1009, pero no podemos obtener eso en nuestro formato de 3 dígitos. Redondeando a 3 dígitos, la respuesta más precisa que obtenemos es 1010. Si sumamos de menor a mayor, en cada ciclo obtenemos:

Loop Index        s
1                 1
2                 2
3                 3
4                 4
5                 5
6                 6
7                 7
8                 8
9                 9
10                1009 -> 1010

Entonces obtenemos la respuesta más precisa posible para nuestro formato. Ahora supongamos que agregamos de mayor a menor.

Loop Index        s
1                 1000
2                 1001 -> 1000
3                 1001 -> 1000
4                 1001 -> 1000
5                 1001 -> 1000
6                 1001 -> 1000
7                 1001 -> 1000
8                 1001 -> 1000
9                 1001 -> 1000
10                1001 -> 1000

Dado que los números de coma flotante se redondean después de cada operación, todas las adiciones se redondean, lo que aumenta nuestro error de 1 a 9 de la exacta. Ahora imagine si su conjunto de números para agregar tenía 1000 y luego cien 1 o un millón. Tenga en cuenta que para ser realmente exacto, desearía sumar los dos números más pequeños y luego recurrir al resultado en su conjunto de números.

Para el caso general, usaría la suma compensada (o la suma de Kahan). A menos que los números ya estén ordenados, ordenarlos será mucho más costoso que sumarlos . La suma compensada también es más precisa que la suma ordenada o la suma ingenua (vea el enlace anterior).

En cuanto a las referencias, lo que todo programador debe saber sobre la aritmética de punto flotante cubre los puntos básicos con suficiente detalle para que alguien pueda leerlo en 20 (+/- 10) minutos y comprender los conceptos básicos. "Lo que todo informático debería saber sobre la aritmética de punto flotante" de Goldberg es la referencia clásica, pero la mayoría de las personas que conozco que recomiendan ese artículo no lo han leído en detalle, porque son alrededor de 50 páginas (más que eso, en algunos impresiones), y escrito en prosa densa, por lo que tengo problemas para recomendarlo como referencia de primera línea para las personas. Es bueno para una segunda mirada al tema. Una referencia enciclopédica es la precisión y estabilidad de los algoritmos numéricos de Higham, que cubre este material, así como la acumulación de errores numéricos en muchos otros algoritmos; también tiene 680 páginas, así que tampoco miraría esta referencia primero.

Las respuestas anteriores ya discuten el asunto en general y dan buenos consejos, pero hay una peculiaridad adicional que me gustaría mencionar. En la mayoría de las arquitecturas modernas, el forbucle que ha descrito se realizaría de todos modos con una precisión extendida de 80 bits , lo que garantiza una precisión adicional, ya que todas las variables temporales se colocarán en registros. Entonces ya tiene alguna forma de protección contra errores numéricos. Sin embargo, en bucles más complicados, los valores intermedios se almacenarán en la memoria entre las operaciones y, por lo tanto, se truncarán a 64 bits. Supongo

s=0; 
for \ i=1:n 
    printf("Hello World");
    s=s + z_{i} ; 
end

es suficiente para obtener una precisión más baja en su suma (!!). Así que tenga mucho cuidado si desea imprimir-depurar su código mientras verifica la precisión.

Para los interesados, este artículo describe un problema en una rutina numérica ampliamente utilizada (factorización QR reveladora de rango de Lapack) cuya depuración y análisis fue muy difícil precisamente por este problema.

De las 2 opciones, agregar de menor a mayor producirá menos errores numéricos que luego agregar de mayor a menor.

Sin embargo, hace más de 20 años, en mi clase de "Métodos numéricos", el instructor declaró esto y se me ocurrió que todavía estaba introduciendo más error del necesario debido a la diferencia relativa en el valor entre el acumulador y los valores que se agregaban.

Lógicamente, una solución preferible es agregar los 2 números más pequeños en la lista, luego volver a insertar el valor sumado en la lista ordenada.

Para demostrarlo, elaboré un algoritmo que podría hacerlo de manera eficiente (en el espacio y el tiempo) al usar el espacio liberado a medida que los elementos se eliminaban de la matriz primaria para construir una matriz secundaria de los valores sumados que fueron ordenados inherentemente desde las adiciones eran de las sumas de valores que siempre aumentaban. En cada iteración, los "consejos" de ambas matrices se comprueban para encontrar los 2 valores más pequeños.

Como no restringió el tipo de datos que se utilizará, para lograr un resultado perfectamente preciso, simplemente use números de longitud arbitrarios ... en cuyo caso el orden no importará. Será mucho más lento, pero obtener la perfección lleva tiempo.

Use la suma del árbol binario, es decir, elija la media de la distribución (número más cercano) como la raíz del árbol binario, y cree un árbol binario ordenado agregando valores menores a la izquierda del gráfico y valores más grandes a la derecha, etc. . Agregar todos los nodos secundarios de un solo padre de forma recursiva en un enfoque ascendente. Esto será eficiente a medida que el error promedio aumente con el número de sumaciones y en un enfoque de árbol binario, el número de sumaciones está en el orden de log n en la base 2. Por lo tanto, el error promedio sería menor.

Lo que Hristo Iliev dijo anteriormente sobre los compiladores de 64 bits que prefieren las instrucciones SSE y AVX sobre la FPU (AKA NDP) es absolutamente cierto, al menos para Microsoft Visual Studio 2013. Sin embargo, para las operaciones de punto flotante de doble precisión que estaba usando, encontré en realidad es más rápido, así como en teoría más preciso, usar la FPU. Si es importante para usted, sugeriría probar varias soluciones primero, antes de elegir un enfoque final.

Cuando trabajo en Java, uso con mucha frecuencia el tipo de datos BigDecimal de precisión arbitraria. Es demasiado fácil, y generalmente no se nota la disminución de la velocidad. Calcular las funciones trascendentales con series infinitas y sqrt usando el método de Newton puede tomar un milisegundo o más, pero es factible y bastante preciso.

Solo dejé esto aquí /programming//a/58006104/860099 (cuando vaya allí, haga clic para 'mostrar fragmento de código' y ejecútelo con el botón

Es un ejemplo de JavaScript que muestra claramente que la suma comenzando desde la mayor da un error mayor

arr=[9,.6,.1,.1,.1,.1];

sum     =             arr.reduce((a,c)=>a+c,0);  // =  9.999999999999998
sortSum = [...arr].sort().reduce((a,c)=>a+c,0);  // = 10

console.log('sum:     ',sum);
console.log('sortSum:',sortSum);