Лемма Стербенца

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

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

Пусть — основание системы счисления с плавающей точкой и точность.${\displaystyle \бета}$${\displaystyle p}$

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

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

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

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

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

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

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

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

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

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

$${\displaystyle {\begin{aligned}xy&=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}}}$$

Пусть . Так как имеем:${\displaystyle s'=s_{x}\beta ^{e_{x}-e_{y}}-s_{y}}$${\displaystyle 0<y<x}$

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

Далее, поскольку , то имеем , так что${\displaystyle x\leq 2y}$${\displaystyle xy\leq y}$

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

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

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

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

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

так же как и число с плавающей точкой. ◻${\displaystyle xy}$

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

Лемму Стербенца можно противопоставить явлению катастрофического погашения :

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

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

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