Orden de operaciones, algoritmos numéricos

He leido eso

(1) Las operaciones mal condicionadas deben realizarse antes que las bien condicionadas.

Como ejemplo, uno debe calcular $xz-yz$ como $(x-y)z$ ya que la resta está mal condicionada mientras que la multiplicación no.

Sin embargo, un análisis de error de primer orden de ambos algoritmos revela que difieren solo por un factor de tres (*), y no veo por qué uno puede generalizar esto a la declaración (1), ni entiendo intuitivamente la importancia de Orden de operaciones. ¿Crees que la declaración es (1) es una regla aceptada, y tienes otras explicaciones para ello?

*: más específicamente, la primera versión tiene un error relativo delimitado por

$$\text{eps}+3\frac{|x|+|y|}{|x|-|y|}\text{eps}$$ mientras que el error relativo de la segunda versión está delimitado por

$$3\text{eps}+\frac{|x|+|y|}{|x|-|y|}\text{eps}$$

donde $\text{eps}$ es la precisión de la máquina.

Este análisis se basa en la suposición de que el $i$ -ésimo resultado intermedio se multiplica por $(1+\varepsilon_i)$ (debido a errores de redondeo), donde $\varepsilon_i$ es iid variables aleatorias limitadas por $\text{eps}$ . "Primer orden" significa que los términos de orden superior, como $\epsilon_i\epsilon_jx$ , se descuidan.

Denotemos por (era flojo tratando de obtener una versión en círculo del operador de división) los análogos de coma flotante de multiplicación exacta ( × ), suma ( + ) y resta ( - ), respectivamente. Asumiremos (IEEE-754) que para todos ellos [ x ⊕ y ] = ( x + y ) ( 1 + δ ⊕ ) $\otimes,\oplus,\ominus$$\times$$+$$-$ donde ϵ m a c h es la máquina épsilon que da un límite superior al error relativo debido al redondeo. También usaremos el siguiente lema (suponiendo que todos | δ i | ≤ ϵ m a c h , ym no es demasiado grande) que se puede probar fácilmente: m ∏ i = 1 ( 1 + δ i ) = 1 + θ

$$[x\oplus y]=(x+ y)(1+\delta_\oplus),\quad |\delta_\oplus|\le\epsilon_\mathrm{mach},$$ $\epsilon_\mathrm{mach}$$|\delta_i|\le\epsilon_\mathrm{mach}$$m$ $$\prod\limits_{i=1}^{m}(1+\delta_i)=1+\theta(m),\quad |\theta(m)|\le\frac{m\epsilon_\mathrm{mach}}{1-m\epsilon_\mathrm{mach}}$$

Definamos la verdadera función que opera en números reales x , y , z como$f$$x,y,z$

$$f(x,y,z)=(x\times z)-(y\times z)$$

y dos versiones de la implementación de la función en aritmética de coma flotante compatible con IEEE como y ~ f 2 que operan en representaciones de coma flotante ˜ x = x ( 1 + δ x ) , ˜ y , ˜ z , como sigue:$\tilde{f_1}$$\tilde{f_2}$$\tilde{x}=x(1+\delta_x),\tilde{y},\tilde{z}$

$$\tilde{f_1}(\tilde{x},\tilde{y},\tilde{z})=(\tilde{x}\otimes\tilde{z})\ominus(\tilde{y}\otimes\tilde{z}),$$

$$\tilde{f_2}(\tilde{x},\tilde{y},\tilde{z})=(\tilde{x}\ominus\tilde{y})\otimes\tilde{z}.$$

Análisis de error para :$\tilde{f_1}$

$$\begin{aligned} \tilde{f_1}&=\Big(\underbrace{\big(x(1+\delta_x)\times z(1+\delta_z)\big)\big(1+\delta_{\otimes_{xz}}\big)}_{(\tilde{x}\otimes\tilde{z})}-\underbrace{\big(y(1+\delta_y)\times z(1+\delta_z)\big)\big(1+\delta_{\otimes_{yz}}\big)}_{(\tilde{y}\otimes\tilde{z})}\Big)\Big(1+\delta_{\ominus}\Big)\\ &=xz(1+\delta_x)(1+\delta_z)(1+\delta_{\otimes_{xz}})(1+\delta_\ominus)-yz(1+\delta_y)(1+\delta_z)(1+\delta_{\otimes_{yz}})(1+\delta_\ominus)\\ &=xz(1+\theta_{xz,1})-yz(1+\theta_{yz,1}). \end{aligned}$$ $|\theta_{xz,1}|,|\theta_{yz,1}|\le\frac{4\epsilon_\mathrm{mach}}{1-4\epsilon_\mathrm{mach}}$

$\tilde{f_2}$

$$\begin{aligned} \tilde{f_2}&=\Bigg(\Big(\big( x(1+\delta_x)-y(1+\delta_y \big)\big(1+\delta_{\ominus_{xy}}\big)\Big)\times \Big(z(1+\delta_z)\Big)\Bigg)\Bigg(1+\delta_{\otimes}\Bigg)\\ &=xz(1+\delta_x)(1+\delta_z)(1+\delta_{\ominus_{xy}})(1+\delta_\otimes)-yz(1+\delta_y)(1+\delta_z)(1+\delta_{\ominus_{xy}})(1+\delta_\otimes)\\ &=xz(1+\theta_{x,2})-yz(1+\theta_{y,2}). \end{aligned}$$ $|\theta_{x,2}|,|\theta_{y,2}|\le\frac{4\epsilon_\mathrm{mach}}{1-4\epsilon_\mathrm{mach}}$

$\tilde{f_1}$$\tilde{f_2}$$\tilde{f_2}$$\tilde{f_1}$

$x$$y$

$$\begin{aligned} \frac{|\tilde{f_1}-f|}{|f|}&=\frac{|xz+xz\theta_{xz,1}-yz-yz\theta_{yz,1}-(xz-yz)|}{|xz-yz|}=\frac{|x\theta_{xz,1}-y\theta_{yz,1}|}{|x-y|}\\ &\le\frac{|x|+|y|}{|x-y|}\frac{4\epsilon_\mathrm{mach}}{1-4\epsilon_\mathrm{mach}}, \end{aligned}$$ $$\begin{aligned} \frac{|\tilde{f_2}-f|}{|f|}&=\frac{|xz+xz\theta_{x,2}-yz-yz\theta_{y,2}-(xz-yz)|}{|xz-yz|}=\frac{|x\theta_{x,2}-y\theta_{y,2}|}{|x-y|}\\ &\le\frac{|x|+|y|}{|x-y|}\frac{4\epsilon_\mathrm{mach}}{1-4\epsilon_\mathrm{mach}}. \end{aligned}$$

$\theta$$x,y,z$$(x-y)$$x$$y$

$x,y,z,f(x,y,z)\in\mathbb F_0$$\mathbb F_0$