Порядок операций, численные алгоритмы

Я прочитал это

(1) Плохо обусловленные операции должны выполняться до хорошо подготовленных.

Например, нужно вычислить как (xy) z, поскольку вычитание плохо обусловлено, а умножение - нет.$xz-yz$$(x-y)z$

Однако анализ ошибок первого порядка обоих алгоритмов показывает, что они различаются только в три раза (*), и я не понимаю, почему можно обобщить это в утверждении (1), и при этом я интуитивно не понимаю значение порядок действий. Как вы думаете, утверждение (1) является принятым правилом, и есть ли у вас другие объяснения для него?

*: более конкретно, первая версия имеет относительную ошибку, ограниченную

$$\text{eps}+3\frac{|x|+|y|}{|x|-|y|}\text{eps}$$ тогда как относительная ошибка второй версии ограничена

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

где $\text{eps}$ - точность машины.

Этот анализ основан на предположении, что $i$ промежуточный результат умножается на $(1+\varepsilon_i)$ (из-за ошибок округления), где $\varepsilon_i$ - это случайные переменные iid, ограниченные $\text{eps}$ . «Первый порядок» означает, что членами высшего порядка, такими как $\epsilon_i\epsilon_jx$ , пренебрегают.

Обозначим через (мне было лень пытаться получить обведенную версию оператора деления) аналоги с плавающей запятой точного умножения ( ), сложения ( ) и вычитания ( ) соответственно. Предположим (IEEE-754), что для всех них где - машинный эпсилон, дающий верхнюю границу относительной ошибки из-за округления. Мы также будем использовать следующую лемму (при условии, что все , а не слишком велика), которую легко доказать: × + - [ x ⊕ y ] = ( $\otimes,\oplus,\ominus$$\times$$+$$-$ϵ m a c h | δ я | ≤ ϵ m a c h m 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)$$

и две версии реализации функции в IEEE-совместимой арифметике с плавающей точкой, такие как и которые работают с представлениями с плавающей точкой , следующим образом:$\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}}$

Итак, для и мы получили выражения одного типа, поэтому я не понимаю, почему одна реализация предпочтительнее другой с числовой точки зрения (за исключением того факта, что выполняет только 2 операции с плавающей точкой по сравнению с ).$\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}$$

Незначительные различия между могут сделать одну из двух числовых реализаций незначительно лучше или хуже в зависимости от . Однако я сомневаюсь, что это может иметь какое-либо значение. Результат полностью имеет смысл, потому что, независимо от того, что, если вам нужно вычислить , когда и достаточно близки по значениям (для точности, с которой вы работаете), используя арифметику с плавающей точкой, никакое масштабирование не поможет вам: ты уже в беде.x , y , z ( x - y ) x $\theta$$x,y,z$$(x-y)$$x$$y$

NB: Все обсуждения выше предполагают, что нет переполнения или недостаточного значения, то есть , - набор всех нормальных чисел с плавающей точкой.F$x,y,z,f(x,y,z)\in\mathbb F_0$$\mathbb F_0$