Ordre des opérations, algorithmes numériques

J'ai lu ça

(1) Les opérations mal conditionnées doivent être effectuées avant celles bien conditionnées.

Par exemple, on devrait calculer comme puisque la soustraction est mal conditionnée tandis que la multiplication ne l'est pas.$xz-yz$$(x-y)z$

Cependant, une analyse d'erreur de premier ordre des deux algorithmes révèle qu'ils ne diffèrent que par un facteur de trois (*), et je ne vois pas pourquoi on peut généraliser cela à l'énoncé (1), ni saisir intuitivement la signification de ordre des opérations. Pensez-vous que la déclaration est (1) est une règle acceptée, et avez-vous d'autres explications?

*: plus précisément, la première version a une erreur relative délimitée par

$$\text{eps}+3\frac{|x|+|y|}{|x|-|y|}\text{eps}$$ alors que l'erreur relative de la deuxième version est limitée par

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

où$\text{eps}$ est la précision de la machine.

Cette analyse est basée sur l'hypothèse que le $i$ ème résultat intermédiaire est multiplié par $(1+\varepsilon_i)$ (en raison d'erreurs d'arrondi), où $\varepsilon_i$ sont iid des variables aléatoires limitées par $\text{eps}$ . "Premier ordre" signifie que les termes d'ordre supérieur, comme $\epsilon_i\epsilon_jx$ , sont négligés.

Notons (j'étais paresseux en essayant d'obtenir la version encerclée de l'opérateur de division) les analogues à virgule flottante de la multiplication exacte ( × ), de l'addition ( + ) et de la soustraction ( - ), respectivement. Nous supposerons (IEEE-754) que pour chacun d'eux [ x ⊕ y ] = ( x + y ) ( 1 + δ ⊕ ) $\otimes,\oplus,\ominus$$\times$$+$$-$ où ϵ m a c h est la machine epsilon donnant une borne supérieure sur l'erreur relative due à l'arrondi. Nous utiliserons également le lemme suivant (en supposant que tout | δ i | ≤ ϵ m a c h , et m n'est pas trop grand) qui peut être facilement prouvé: 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}}$$

$f$$x,y,z$

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

$\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}.$$

$\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$