Pregunta 1 Muestre que las sumas aritméticas de punto flotante$$s_n=\sum_{k=1}^n\frac{1}{k^2} = 1+\frac{1}{2^2}+\frac{1}{3^2}+\dotsb+\frac{1}{n^2}$ $ con precisión$\mathcal O(n)\epsilon$ de izquierda a derecha, mientras que la suma de derecha a izquierda da una precisión$\mathcal O(\log n)\epsilon$.
Hay un ejemplo de sumar 5, 10, 15$\left(\left(5+10\right)\left(1+\epsilon\right)+15\right)\left(1+\epsilon\right) =30+45\epsilon$$\left(\left(15+10\right)\left(1+\epsilon\right)+5\right)\left(1+\epsilon\right) = 30+55\epsilon$
¿De dónde viene la forma$\left(1+\epsilon\right)$? ¿Y alguna sugerencia sobre cómo abordar este problema? ¡Gracias!
Respuesta
¿Demasiados anuncios?
andy.holmes
Puntos
518
Usted obtener de $$ fl(a+b)=(a+b)(1+\delta) $$ con $|δ|\leϵ$ la cuasi aleatorio error relativo del punto flotante de ejecución de la operación.
En el cómputo de las $s_n=\sum_{k=1}^n a_k$ a través de las sumas parciales $s_{m+1}=s_m+a_{m+1}$ cada numérico paso produce un error de $Δs_m$ que se acumula como $$ s_{m+1}+Δs_{m+1}=fl(s_m+Δs_m+a_{m+1})=(s_m+Δs_m+a_{m+1})(1+\delta_m) $$ Los errores están dominados por la primera orden de los términos, de modo que hasta los términos de orden superior después de la eliminación de los términos exactos que uno obtiene $$ Δs_{m+1}=Δs_m+s_{m+1}\delta_m $$ Así que en primer orden de aproximación, el último error agrega a la suma es proporcional a la suma hasta la fecha, que en total da $$ Δs_n=s_2\delta_1+s_3\delta_2+...+s_n\delta_{n-1}. $$
El cuasi aleatorio cantidades $\delta_m$ están vinculados por una máquina constante $ϵ$. Las sumas parciales de absoluta sumas como límite superior. La combinación de ambos, uno se $$ |Δs_n|\le \sum_{k=1}^n (n+1-k)·|a_k|\,·\,ϵ $$
Para la suma de $\sum_{k=1}^n\frac1{k^2}$ suma de la parte delantera da $a_k=\frac1{k^2}$ y la de primer orden coeficiente del término de error $$ \sum_{k=1}^n (n+1-k)·|a_k|=(n+1)\sum_{k=1}^n\frac1{k^2}-\sum_{k=1}^n\frac1k\le(n+1)\frac{\pi^2}6-\ln(n+1)=O(n) $$
Recapitulación de la final se codifica como $a_k=\frac1{(n+1-k)^2}$ que da el primer fin de coeficiente del término de error como $$ \sum_{k=1}^n\frac1{n+1-k}\le 1+\ln(n)=O(\log n) $$
Las identidades utilizadas son $$ \sum_{k=1}^n\frac1{k^2}\le\sum_{k=1}^\infty\frac1{k^2}=\frac{\pi^2}6 $$ y, como consecuencia de $e^x\ge 1+x$ o límites en $\int_{k-1}^k\frac1x\,dx$, $$ \ln(k+1)-\ln(k)\le \frac1k\le \ln(k)-\ln(k-1)\\ \ln(n+1)-\ln(1)\le\sum_{k=1}^n\frac1k\le 1+\ln(n)-\ln(1) $$
