मरती हुई लेम्मा

फ्लोटिंग-पॉइंट अंकगणित में, स्टरबेंज़ लेम्मा या स्टरबेंज़ लेम्मा यह ऐसी स्थितियाँ देने वाला एक प्रमेय है जिसके अंतर्गत फ़्लोटिंग-पॉइंट अंतरों की सटीक गणना की जाती है। इसका नाम पैट एच. स्टरबेंज़ के नाम पर रखा गया है, जिन्होंने 1974 में इसका एक संस्करण प्रकाशित किया था।

Sterbenz lemma — In a floating-point number system with subnormal numbers, if $x$ and $y$ are floating-point numbers such that

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

then $x-y$ is also a floating-point number. Thus, a correctly rounded floating-point subtraction

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

is computed exactly.

स्टरबेंज़ लेम्मा आईईईई 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 )}}}$$

स्टरबेंज़ लेम्मा की मदद से सभी इनपुट के लिए कम त्रुटि विश्लेषण (गणित) साबित किया जा सकता है।