Умирающая лемма

В арифметике с плавающей запятой или лемма Стербенца лемма Стербенца — это теорема, определяющая условия, при которых разности с плавающей запятой вычисляются точно.Он назван в честь Пэта Х. Стербенса, опубликовавшего его вариант в 1974 году.

Лемма Штербенца — В системе счисления с плавающей запятой с субнормальными числами , если $x$ и $y$ являются числами с плавающей запятой, такими что

$${\frac {y}{2}}\leq x\leq 2y,$$

затем $x-y$ также является числом с плавающей запятой.Таким образом, правильно округленное вычитание с плавающей запятой

$$x\ominus y=\operatorname {fl} (x-y)=x-y$$

рассчитывается точно.

Лемма Штербенца применима к IEEE 754 , наиболее широко используемой системе счисления с плавающей запятой в компьютерах.

Доказательство

Позволять $\beta$ быть основанием системы с плавающей запятой и $p$ точность.

Сначала рассмотрим несколько простых случаев:

• Если $x$ тогда равен нулю $x-y=-y$, и если $y$ тогда равен нулю $x-y=x$, поэтому результат тривиален, поскольку отрицание с плавающей запятой всегда точно.

• Если $x=y$ результат равен нулю и, следовательно, точен.

• Если $x<0$ тогда мы также должны иметь $y/2\leq x<0$ так $y<0$. В этом случае, $x-y=-(-x--y)$, поэтому результат следует из теоремы, ограниченной $x,y\geq 0$.

• Если $x\leq y$, мы можем написать $x-y=-(y-x)$ с $x/2\leq y\leq 2x$, поэтому результат следует из теоремы, ограниченной $x\geq y$.

Для дальнейшего доказательства предположим, что $0<y<x\leq 2y$ без потери общности.

Писать $x,y>0$ с точки зрения их положительных целочисленных значений $s_{x},s_{y}\leq \beta ^{p}-1$ и минимальные показатели $e_{x},e_{y}$:

$${\begin{aligned}x&=s_{x}\cdot \beta ^{e_{x}-p+1}\\y&=s_{y}\cdot \beta ^{e_{y}-p+1}\end{aligned}}$$

Обратите внимание, что $x$ и $y$ может быть субнормальным — мы не предполагаем $s_{x},s_{y}\geq \beta ^{p-1}$.

Вычитание дает:

$${\begin{aligned}x-y&=s_{x}\cdot \beta ^{e_{x}-p+1}-s_{y}\cdot \beta ^{e_{y}-p+1}\\&=s_{x}\beta ^{e_{x}-e_{y}}\cdot \beta ^{e_{y}-p+1}-s_{y}\cdot \beta ^{e_{y}-p+1}\\&=(s_{x}\beta ^{e_{x}-e_{y}}-s_{y})\cdot \beta ^{e_{y}-p+1}.\end{aligned}}$$

Позволять $s'=s_{x}\beta ^{e_{x}-e_{y}}-s_{y}$.С $0<y<x$ у нас есть:

• $e_{y}\leq e_{x}$, так $e_{x}-e_{y}\geq 0$, из чего мы можем сделать вывод $\beta ^{e_{x}-e_{y}}$ является целым числом и, следовательно, таковым является $s'=s_{x}\beta ^{e_{x}-e_{y}}-s_{y}$; и
• $x-y>0$, так $s'>0$.

Далее, поскольку $x\leq 2y$, у нас есть $x-y\leq y$, так что

$$s'\cdot \beta ^{e_{y}-p+1}=x-y\leq y=s_{y}\cdot \beta ^{e_{y}-p+1}$$

что подразумевает, что

$$0<s'\leq s_{y}\leq \beta ^{p}-1.$$

Следовательно

$$x-y=s'\cdot \beta ^{e_{y}-p+1},\quad {\text{for}}\quad 0<s'\leq \beta ^{p}-1,$$

так $x-y$ является числом с плавающей запятой.◻

Примечание: Даже если $x$ и $y$ являются нормальными т.е. , $s_{x},s_{y}\geq \beta ^{p-1}$, мы не можем доказать, что $s'\geq \beta ^{p-1}$ и поэтому не может доказать, что $x-y$ это тоже нормально.Например, разница двух наименьших положительных нормальных чисел с плавающей запятой $x=(\beta ^{p-1}+1)\cdot \beta ^{e_{\mathrm {min} }-p+1}$ и $y=\beta ^{p-1}\cdot \beta ^{e_{\mathrm {min} }-p+1}$ является $x-y=1\cdot \beta ^{e_{\mathrm {min} }-p+1}$ что обязательно субнормально.В системах счисления с плавающей запятой без субнормальных чисел , таких как процессоры в нестандартном режиме сброса до нуля вместо стандартного постепенного опустошения, лемма Штербенца не применяется.

Отношение к катастрофической отмене

Лемме Штербенца можно противопоставить явление катастрофического сокращения :

• Лемма Штербенца утверждает, что если $x$ и $y$ являются достаточно близкими числами с плавающей запятой, то их разница $x-y$ вычисляется точно с помощью арифметики с плавающей запятой $x\ominus y=\operatorname {fl} (x-y)$, без округления.
• Феномен катастрофической отмены заключается в том, что если ${\tilde {x}}$ и ${\tilde {y}}$ являются приближениями к истинным числам $x$ и $y$- возникают ли аппроксимации из-за предшествующей ошибки округления, или из-за усечения ряда, или из-за физической неопределенности, или из-за чего-то еще - ошибка разности ${\tilde {x}}-{\tilde {y}}$ от желаемой разницы $x-y$ обратно пропорциональна $x-y$. Таким образом, чем ближе $x$ и $y$ есть, тем хуже ${\tilde {x}}-{\tilde {y}}$ может быть приближением к $x-y$, даже если само вычитание вычисляется точно.

Другими словами, лемма Штербенца показывает, что вычитание соседних чисел с плавающей запятой является точным, но если имеющиеся числа являются приближениями, то даже их точная разность может быть далека от разности чисел, которые вы хотели вычесть.

Использование в численном анализе

Лемма Штербенца играет важную роль в доказательстве теорем об границах погрешности при численном анализе алгоритмов с плавающей запятой.Например, формула Герона $$A={\sqrt {s(s-a)(s-b)(s-c)}}$$для площади треугольника с длинами сторон $a$, $b$, и $c$, где $s=(a+b+c)/2$ является полупериметром, может дать плохую точность для длинных узких треугольников, если вычисляется непосредственно в арифметике с плавающей запятой.Однако для $a\geq b\geq c$, альтернативная формула $$A={\frac {1}{4}}{\sqrt {{\bigl (}a+(b+c){\bigr )}{\bigl (}c-(a-b){\bigr )}{\bigl (}c+(a-b){\bigr )}{\bigl (}a+(b-c){\bigr )}}}$$с помощью леммы Стербенца можно доказать, что он имеет низкую прямую ошибку для всех входов.