Ordem das operações, algoritmos numéricos

Eu li isso

(1) Operações mal condicionadas devem ser realizadas antes das bem condicionadas.

Como exemplo, deve-se calcular $xz-yz$ como $(x-y)z$ pois a subtração está mal condicionada enquanto a multiplicação não.

Entretanto, uma análise de erro de primeira ordem de ambos os algoritmos revela que eles diferem apenas por um fator de três (*), e não vejo por que se pode generalizar isso na afirmação (1), nem compreendo intuitivamente a importância de ordem de operações. Você acha que a afirmação é (1) é uma regra aceita e você tem outras explicações para isso?

*: mais especificamente, a primeira versão possui um erro relativo delimitado por

enquanto o erro relativo da segunda versão é delimitado por

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

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

onde é a precisão da máquina.$\text{eps}$

Essa análise baseia-se no pressuposto de que o ésimo resultado intermediário é multiplicado por ( 1 + ε i ) (devido a erros de arredondamento), em que ε i são variáveis ​​aleatórias delimitadas por eps . Meios "de primeira ordem" que os termos de ordem superior, como ε i ε j x , são negligenciadas.$i$$(1+\varepsilon_i)$$\varepsilon_i$$\text{eps}$$\epsilon_i\epsilon_jx$

Vamos denotar por (eu estava com preguiça de tentar obter uma versão circulada do operador de divisão) os análogos de ponto flutuante da multiplicação exata ( × ), adição ( + ) e subtração ( - ), respectivamente. Vamos assumir (IEEE-754) que, para todos eles [ x ⊕ y ] = ( x + y ) ( 1 + δ ⊕ ) $\otimes,\oplus,\ominus$$\times$$+$$-$ onde ε m um c h é a epsilon máquina que dá um limite superior sobre o erro relativo devido ao arredondamento. Também usaremos o seguinte lema (assumindo que todos | δ i | ≤

$$[x\oplus y]=(x+ y)(1+\delta_\oplus),\quad |\delta_\oplus|\le\epsilon_\mathrm{mach},$$ $\epsilon_\mathrm{mach}$ emnão é muito grande) que pode ser facilmente comprovada: m Π i = 1 (1+ δ i )=1+θ$|\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}}$$

Vamos definir a verdadeira função que opera nos números reais x , y , z como$f$$x,y,z$

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

e duas versões da implementação da função na aritmética de ponto flutuante compatível com IEEE como e ~ f 2 que operam nas representações de ponto flutuante ˜ $\tilde{f_1}$$\tilde{f_2}$ , como se segue:$\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álise de erro 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$