Suma recursiva en pares

Aunque también hay otras técnicas, como el algoritmo de la suma de Kahan, que, por lo general, también cuentan con un error de redondeo es menor, la suma de pares recursivos es casi tan buena (que difiere solo por un factor logarítmico), mientras que tiene un costo computacional mucho menor; se puede implementar de tal manera que tenga casi el mismo costo (y exactamente el mismo número de operaciones aritméticas) simple suma En el análisis numérico, la suma por pares, también llamada suma en cascada, es una técnica para sumar una secuencia de números de coma flotante de precisión finita que reduce sustancialmente el error de redondeo acumulado en comparación con el acumulado por la suma secuencial simple. En particular, la suma recursiva en pares de una secuencia de N números x n funciona dividiendo recursivamente la secuencia en dos mitades, sumando cada mitad y sumando las dos sumas: un algoritmo de tipo divide et impera. Sus errores de redondeo en el peor de los casos crecen asintóticamente como máximo como o (elog n), donde ε es la precisión de la máquina (asumiendo un número de condicionamiento fijo, como se discute a continuación). Por otro lado, la técnica simple de acumular la suma en secuencia (agregando cada x I uno a la vez para i =1, . , n) tiene errores de redondeo que crecen en el peor de los casos como O (ε n). La suma de Kahan tiene un error en el peor de los casos de aproximadamente O (ε), independiente de n, pero requiere un número de operaciones aritméticas muchas veces mayores. Si los errores de redondeo son aleatorios y, en particular, tienen signos aleatorios, entonces dan lugar a una caminata aleatoria, y para la suma recursiva en pares, el crecimiento del error se reduce a un promedio de O ( ε registro ⁡ y ) {\displaystyle O (\varepsilon {\sqrt {\log n}})} . Una estructura recursiva de suma muy similar se encuentra en muchos algoritmos de transformada rápida de Fourier (FFT) y es responsable de la misma acumulación lenta de errores de redondeo en tales FFT. La suma recursiva por pares es el algoritmo de suma predeterminado en NumPy y el lenguaje de computación técnica Julia, donde en ambos casos se encuentra que tiene una velocidad comparable a la suma simple (gracias al uso de un modelo básico grande).

En pseudocódigo, se puede escribir el algoritmo de suma recursiva de pares para un array x de longitud n & gt; 0: para algunos N suficientemente pequeños, este algoritmo cambia a una suma de bucle simple como modelo base, cuyo límite de error es O(Ne). La suma completa tiene un error en el peor de los casos que crece asintóticamente como O (elog n) para n grande, para un número condicionante dado (Ver más abajo). En un algoritmo de este tipo (como en general para un algoritmo de tipo divide et impera), es preferible utilizar un modelo base más grande con el fin de amortizar 29/5000 la sobrecarga de recursión. SI N = 1, entonces hay aproximadamente una llamada recursiva a una subrutina para cada entrada, pero más generalmente hay una llamada recursiva (aproximadamente) para cada entrada N /2 si la recursión se detiene exactamente en n = N. Al hacer N lo suficientemente grande, la sobrecarga de recursión puede volverse insignificante (precisamente, esta técnica de un modelo base grande para una suma recursiva es empleada por implementaciones FFT de alto rendimiento). Independientemente de N, exactamente, en total se realizan adiciones n -1, tantas como para la suma simple, por lo tanto, si la sobrecarga de recursión se hace insignificante, entonces la suma recursiva en pares tiene esencialmente el mismo costo computacional que la suma simple. Una variante de esta idea es dividir la suma en bloques B en cada etapa recursiva, sumando cada bloque recursivamente y luego sumando los resultados; esta variante ha sido llamada un algoritmo de "superbloque" por sus proponentes. El algoritmo de suma recursiva en pares visto anteriormente corresponde al Caso b = 2 para cada fase, excepto para la última en la que se tiene b = N.

Supongamos que sumamos n valores x i, para i =1,. n. la suma exacta es: (calculada con precisión infinita). Con la suma recursiva en pares para un modelo base N =1, en su lugar, se obtiene S y + Y y {\displaystyle S_ {n}+e_{n}} , donde el error Y y {\displaystyle E_ {n}} está limitado por: donde ε es la precisión de la máquina de la aritmética empleada (por ejemplo, ε≈10 -16 para el formato estándar de coma flotante de doble precisión). Generalmente, la cantidad de interés es el error relativo | Y y | / | S y | {\displaystyle / E_{n} / / / s_{n} / } , que por lo tanto está limitado por: en la expresión para el límite del error relativo, la fracción (Σ / X I | / / Σ X I/) es el número de condicionamiento problema correspondiente a la suma. Esencialmente, el número de condicionamiento representa la sensibilidad intrínseca del problema correspondiente a la suma a errores, independientemente de cómo se calcule. El límite del error relativo de cada método de suma (estable hacia atrás) para un algoritmo fijo Con una precisión fija (por lo que no los que utilizan aritmética de precisión arbitraria, ni los algoritmos cuyos requisitos de memoria y tiempo cambian dependiendo de los datos), es proporcional a este número de condicionamiento. Un problema de suma mal condicionado es aquel en el que esta relación es grande y en este caso incluso la suma recursiva por pares puede tener un gran error relativo. Por ejemplo, si las adiciones x I son números aleatorios no relacionados con la media cero, la suma es una caminata aleatoria y el número de condicionamiento crecerá proporcional a y {\displaystyle {\sqrt {n}}} . Por otro lado, para entradas aleatorias con media nada el número condicionante tiende a una constante finita para y → ∞ {\displaystyle n \ to \ infty } . Si las entradas son todas no negativas, entonces el número de condicionamiento es 1. Observamos que el denominador 1 − ε registro 2 ⁡ y {\displaystyle 1 - \ varepsilon \ log _ {2}n} en la práctica es 1, ya que ε registro 2 ⁡ y {\displaystyle \varepsilon \ log _ {2}n} es mucho menor que 1 hasta que n se convierte en del orden de 2 1 / ε, que es aproximadamente 10 10 15 en doble precisión. En la práctica, es mucho más probable que los errores de redondeo tengan un signo Aleatorio, con media cero, por lo que dan lugar a una caminata y al azar; en este caso, la suma simple tiene un error relativo, mientras que la desviación estándar, que crece como O ( ε y ) {\displaystyle O (\varepsilon {\sqrt {n}})} y la suma recursiva en pares tiene un error que crece como O ( ε registro ⁡ y ) {\displaystyle O (\varepsilon {\sqrt {\log n}})} promedio En comparación, el límite de error relativo para la suma simple (adición simple de números en secuencia, redondeo con cada paso) crece como O ( ε y ) {\displaystyle O (\varepsilon n)} multiplicado por el número de condicionamiento.

Análisis numérico

Matemáticas para informática

Regla del rectángulo

Tal fórmula se aproxima a la integral (y por lo tanto el área subyacente a la función) como un rectángulo base b − a {\displaystyle b-a} y...

Cálculo Integral

Esta página se basa en el artículo de Wikipedia: Fuente, Autores, Licencia Creative Commons Reconocimiento-CompartirIgual.
This page is based on the Wikipedia article: Source, Authors, Creative Commons Attribution-ShareAlike License.
contactos
Política de privacidad , Descargos de responsabilidad