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

Точная теорема о вычитании чисел с плавающей точкой

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

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

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

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

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

вычисляется точно.

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

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

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

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

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

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

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

• Если , то мы можем записать с помощью , поэтому результат следует из теоремы, ограниченной . ${\displaystyle x\leq y}$ ${\displaystyle x-y=-(y-x)}$ ${\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{aligned}x&=s_{x}\cdot \beta ^{e_{x}-p+1}\\y&=s_{y}\cdot \beta ^{e_{y}-p+1}\end{aligned}}}$$

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

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

$${\displaystyle {\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}}}$$

Пусть . Так как имеем: ${\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 x-y>0}$, так . ${\displaystyle s'>0}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Лемма Стербенца играет важную роль в доказательстве теорем о границах ошибок в численном анализе алгоритмов с плавающей точкой. Например, формула Герона для площади треугольника со сторонами длиной , и , где — полупериметр, может давать плохую точность для длинных узких треугольников, если вычислять ее непосредственно в арифметике с плавающей точкой. Однако для можно доказать , что альтернативная формула с помощью леммы Стербенца имеет низкую прямую ошибку для всех входных данных. ^{[3] [4] [5]} $${\displaystyle A={\sqrt {s(s-a)(s-b)(s-c)}}}$$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\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-(a-b){\bigr )}{\bigl (}c+(a-b){\bigr )}{\bigl (}a+(b-c){\bigr )}}}}$$

Ссылки

1. Мюллер, Жан-Мишель; Бруни, Николас; де Динешен, Флоран; Жаннерод, Клод-Пьер; Джолдес, Миоара; Лефевр, Винсент; Мелькионд, Гийом; Револь, Натали ; Торрес, Серж (2018). Справочник по арифметике с плавающей запятой (2-е изд.). Gewerbestrasse 11, 6330 Хам, Швейцария: Биркхойзер. Лемма 4.1, с. 101. дои : 10.1007/978-3-319-76526-6. ISBN 978-3-319-76525-9.{{cite book}}: CS1 maint: местоположение ( ссылка )
2. Sterbenz, Pat H. (1974). Вычисления с плавающей точкой. Englewood Cliffs, NJ, США: Prentice-Hall. Теорема 4.3.1 и следствие, стр. 138. ISBN 0-13-322495-3.
3. Кахан, В. (2014-09-04). "Неверный расчет площади и углов игольчатого треугольника" (PDF) . Конспект лекций для вводных занятий по численному анализу . Получено 17 сентября 2020 г.
4. Голдберг, Дэвид (март 1991 г.). «Что каждый специалист по информатике должен знать об арифметике с плавающей точкой». ACM Computing Surveys . 23 (1). Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники: 5–48. doi :10.1145/103162.103163. ISSN  0360-0300. S2CID  222008826. Получено 17 сентября 2020 г.
5. Boldo, Sylvie (апрель 2013 г.). Nannarelli, Alberto; Seidel, Peter-Michael; Tang, Ping Tak Peter (ред.). How to Compute the Area of ​​a Triangle: a Formal Revisit. 21st IEEE Symposium on Computer Arithmetic. IEEE Computer Society. стр. 91–98. doi :10.1109/ARITH.2013.29. ISBN 978-0-7695-4957-6. ISSN  1063-6889.