Urutan operasi, algoritma numerik

Saya sudah membaca itu

(1) Operasi yang terkondisi harus dilakukan sebelum yang terkondisi dengan baik.

Sebagai contoh, seseorang harus menghitung $xz-yz$ sebagai$(x-y)z$ karena pengurangan tidak dikondisikan sedangkan multiplikasi tidak.

Namun, analisis kesalahan orde pertama dari kedua algoritma mengungkapkan bahwa mereka hanya berbeda oleh faktor tiga (*), dan saya tidak melihat mengapa orang dapat menggeneralisasikan ini ke pernyataan (1), dan saya juga tidak secara intuitif memahami pentingnya urutan operasi. Apakah menurut Anda pernyataan itu (1) adalah aturan yang diterima, dan apakah Anda punya penjelasan lain untuk itu?

*: lebih khusus, versi pertama memiliki kesalahan relatif yang dibatasi oleh

$$\text{eps}+3\frac{|x|+|y|}{|x|-|y|}\text{eps}$$ sementara kesalahan relatif dari versi kedua dibatasi oleh

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

dimana$\text{eps}$ adalah presisi mesin.

Analisis ini didasarkan pada asumsi bahwa hasil menengah ke- dikalikan dengan (karena kesalahan pembulatan), di mana adalah variabel acak pertama yang dibatasi oleh . "Urutan pertama" berarti bahwa istilah dengan tingkat lebih tinggi, seperti , diabaikan.$i$$(1+\varepsilon_i)$$\varepsilon_i$$\text{eps}$$\epsilon_i\epsilon_jx$

Mari kita tunjukkan dengan (Saya malas mencoba untuk mendapatkan versi yang dilingkari dari operator divisi) analog floating-point dari perkalian yang tepat (× ), penambahan ( + ), dan pengurangan ( - ), masing-masing. Kami akan menganggap (IEEE-754) bahwa untuk semuanya [ x ⊕ y ] = ( x + y ) ( $\otimes,\oplus,\ominus$$\times$$+$$-$ mana ϵ m a c h adalah mesin epsilon yang memberikan batas atas pada kesalahan relatif karena pembulatan. Kami juga akan menggunakan lemma berikut (dengan asumsi semua | δ i | ≤ ε m a c h , dan m tidak terlalu besar) yang dapat dengan mudah dibuktikan: m Π i = 1 ( 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}$ , sebagai berikut:

$$\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$ adalah himpunan semua angka floating-point normal.