विनाशकारी रद्दीकरण

संख्यात्मक विश्लेषण में, विनाशकारी रद्दीकरण यह घटना है कि अच्छे सन्निकटन को दो पास की संख्याओं से घटाना मूल संख्याओं के अंतर के लिए बहुत खराब सन्निकटन प्राप्त कर सकता है।

उदाहरण के लिए, यदि दो स्टड हैं, तो एक $L_{1}=254.5\,{\text{cm}}$ लंबा और दूसरा $L_{2}=253.5\,{\text{cm}}$ लंबा, और वे एक शासक के साथ मापा जाता है जो केवल सेंटीमीटर के लिए अच्छा होता है, तो सन्निकटन निकल सकता है ${\tilde {L}}_{1}=255\,{\text{cm}}$ तथा ${\tilde {L}}_{2}=253\,{\text{cm}}$. ये अच्छे सन्निकटन हो सकते हैं, सापेक्ष त्रुटि में, सही लंबाई के लिए: सन्निकटन सही लंबाई के 2% से कम की त्रुटि में हैं, $|L_{1}-{\tilde {L}}_{1}|/|L_{1}|<2\%$.

हालाँकि, यदि अनुमानित लंबाई घटा दी जाए, तो अंतर होगा ${\tilde {L}}_{1}-{\tilde {L}}_{2}=255\,{\text{cm}}-253\,{\text{cm}}=2\,{\text{cm}}$, भले ही लंबाई के बीच सही अंतर है $L_{1}-L_{2}=254.5\,{\text{cm}}-253.5\,{\text{cm}}=1\,{\text{cm}}$. अनुमानों का अंतर, $2\,{\text{cm}}$, वास्तविक मानों के अंतर के परिमाण के 100% त्रुटि में है, $1\,{\text{cm}}$.

आपदाजनक रद्दीकरण तब भी हो सकता है जब अंतर की ठीक-ठीक गणना की गई हो, जैसा कि ऊपर दिए गए उदाहरण में है—यह फ्लोटिंग-पॉइंट अंकगणित की तरह किसी विशेष प्रकार के अंकगणित का गुण नहीं है; बल्कि, यह घटाव में निहित है, जब इनपुट स्वयं सन्निकटन होते हैं। वास्तव में, फ्लोटिंग-पॉइंट अंकगणित में, जब इनपुट पर्याप्त रूप से करीब होते हैं, तो फ्लोटिंग-पॉइंट अंतर की गणना ठीक से की जाती है, स्टरबेंज़ लेम्मा द्वारा - फ़्लोटिंग-पॉइंट घटाव ऑपरेशन द्वारा पेश की गई कोई राउंडिंग त्रुटि नहीं होती है।

औपचारिक विश्लेषण

औपचारिक रूप से, विनाशकारी रद्दीकरण होता है क्योंकि घटाव पास के इनपुट पर खराब स्थिति में होता है: भले ही सन्निकटन ${\tilde {x}}=x(1+\delta _{x})$ तथा ${\tilde {y}}=y(1+\delta _{y})$ छोटी सापेक्ष त्रुटि है $|\delta _{x}|=|x-{\tilde {x}}|/|x|$ तथा $|\delta _{y}|=|y-{\tilde {y}}|/|y|$ सच्चे मूल्यों से $x$ तथा $y$, क्रमशः, अनुमानित अंतर की सापेक्ष त्रुटि ${\tilde {x}}-{\tilde {y}}$ वास्तविक अंतर से $x-y$ वास्तविक अंतर के व्युत्क्रमानुपाती होता है:

$${\begin{aligned}{\tilde {x}}-{\tilde {y}}&=x(1+\delta _{x})-y(1+\delta _{y})=x-y+x\delta _{x}-y\delta _{y}\\&=x-y+(x-y){\frac {x\delta _{x}-y\delta _{y}}{x-y}}\\&=(x-y){\biggr (}1+{\frac {x\delta _{x}-y\delta _{y}}{x-y}}{\biggr )}.\end{aligned}}$$

इस प्रकार, सटीक अंतर की सापेक्ष त्रुटि ${\tilde {x}}-{\tilde {y}}$ अंतर से सन्निकटन $x-y$ की वास्तविक संख्या है

$$\left|{\frac {x\delta _{x}-y\delta _{y}}{x-y}}\right|.$$

जो सही इनपुट होने पर मनमाने ढंग से बड़ा हो सकता है $x$ तथा $y$ करीब हैं।

संख्यात्मक एल्गोरिदम में

फ्लोटिंग-पॉइंट अंकगणित में आस-पास की संख्याओं को घटाना हमेशा विपत्तिपूर्ण रद्दीकरण का कारण नहीं बनता है, या यहां तक ​​​​कि कोई भी त्रुटि - स्टरबेंज़ लेम्मा द्वारा, यदि संख्याएँ पर्याप्त रूप से पास हैं तो फ़्लोटिंग-पॉइंट अंतर सटीक है। लेकिन रद्द करने से उन इनपुट में त्रुटियां बढ़ सकती हैं जो अन्य फ्लोटिंग-पॉइंट अंकगणित में राउंडिंग से उत्पन्न हुई हैं।

उदाहरण: वर्गों का अंतर

दिए गए अंक $x$ तथा $y$, गणितीय कार्य की गणना करने का भोला प्रयास $x^{2}-y^{2}$ फ़्लोटिंग-पॉइंट अंकगणित द्वारा $\operatorname {fl} (\operatorname {fl} (x^{2})-\operatorname {fl} (y^{2}))$ विनाशकारी रद्दीकरण के अधीन है जब $x$ तथा $y$ परिमाण में करीब हैं, क्योंकि घटाव वर्ग में गोल करने की त्रुटियों को उजागर कर सकता है। वैकल्पिक फैक्टरिंग $(x+y)(x-y)$, फ़्लोटिंग-पॉइंट अंकगणित द्वारा मूल्यांकन किया गया $\operatorname {fl} (\operatorname {fl} (x+y)\cdot \operatorname {fl} (x-y))$, विपत्तिपूर्ण रद्दीकरण से बचा जाता है क्योंकि यह घटाव की ओर ले जाने वाली राउंडिंग त्रुटि को शुरू करने से बचता है।

उदाहरण के लिए, यदि $x=1+2^{-29}\approx 1.0000000018626451$ तथा $y=1+2^{-30}\approx 1.0000000009313226$, फिर अंतर का सही मूल्य $x^{2}-y^{2}$ है $2^{-29}\cdot (1+2^{-30}+2^{-31})\approx 1.8626451518330422\times 10^{-9}$. डबल-परिशुद्धता फ़्लोटिंग-पॉइंट प्रारूप अंकगणित में, वैकल्पिक फैक्टरिंग का मूल्यांकन $(x+y)(x-y)$ बिल्कुल सही परिणाम देता है (बिना गोल के), लेकिन भोली अभिव्यक्ति का मूल्यांकन करता है $x^{2}-y^{2}$ फ़्लोटिंग-पॉइंट नंबर देता है $2^{-29}=1.8626451{\underline {4923095703125}}\times 10^{-9}$, जिनमें से आधे से कम अंक सही हैं और अन्य (रेखांकित) अंक लापता पदों को दर्शाते हैं $2^{-59}+2^{-60}$, मध्यवर्ती वर्ग मानों की गणना करते समय पूर्णांकन के कारण खो गया।

उदाहरण: कॉम्प्लेक्स आर्क्सिन

व्युत्क्रम त्रिकोणमितीय कार्यों की गणना करते समय # जटिल समतल कार्य के लिए विस्तार, किसी को सीधे लघुगणकीय सूत्र का उपयोग करने के लिए लुभाया जा सकता है:

$$\arcsin(z)=i\log {\bigl (}{\sqrt {1-z^{2}}}-iz{\bigr )}.$$

हालाँकि, मान लीजिए $z=iy$ के लिये $y\ll 0$. फिर ${\sqrt {1-z^{2}}}\approx -y$ तथा $iz=-y$; उनके बीच अंतर कहते हैं $\varepsilon$—एक बहुत छोटा अंतर, लगभग शून्य। यदि ${\sqrt {1-z^{2}}}$ फ़्लोटिंग-पॉइंट अंकगणितीय देने में मूल्यांकन किया जाता है

$$\operatorname {fl} {\Bigl (}{\sqrt {\operatorname {fl} (1-\operatorname {fl} (z^{2}))}}{\Bigr )}={\sqrt {1-z^{2}}}(1+\delta )$$

किसी त्रुटि के साथ $\delta \neq 0$, कहाँ पे $\operatorname {fl} (\cdots )$ फ़्लोटिंग-पॉइंट राउंडिंग को दर्शाता है, फिर अंतर की गणना करता है

$${\sqrt {1-z^{2}}}(1+\delta )-iz$$

पास की दो संख्याएँ, दोनों बहुत करीब $-y$, त्रुटि को बढ़ा सकता है $\delta$ के एक कारक द्वारा एक इनपुट में $1/\varepsilon$—एक बहुत बड़ा कारक क्योंकि $\varepsilon$ लगभग शून्य था। उदाहरण के लिए, अगर $z=-1234567i$, का सही मूल्य $\arcsin(z)$ लगभग है $-14.71937803983977i$, लेकिन डबल-सटीक फ़्लोटिंग-पॉइंट प्रारूप अंकगणित में सहज लघुगणकीय सूत्र का उपयोग कर सकता है $-14.719{\underline {644263563968}}i$, सोलह अंकों में से केवल पाँच सही और शेष (रेखांकित) सभी कचरा।

के मामले में $z=iy$ के लिये $y<0$, पहचान का उपयोग करना $\arcsin(z)=-\arcsin(-z)$ रद्दीकरण से बचाता है क्योंकि ${\textstyle {\sqrt {1-(-z)^{2}}}={\sqrt {1-z^{2}}}\approx -y}$ लेकिन $i(-z)=-iz=y$, इसलिए घटाना प्रभावी रूप से उसी चिन्ह के साथ जोड़ है जो रद्द नहीं करता है।

उदाहरण: मूलांक रूपांतरण

सॉफ़्टवेयर प्रोग्राम में संख्यात्मक स्थिरांक अक्सर दशमलव में लिखे जाते हैं, जैसे कि C खंड में double x = 1.000000000000001; IEEE 754 बाइनरी 64 वैरिएबल को घोषित करने और आरंभ करने के लिए x. हालांकि, $1.000000000000001$ बाइनरी 64 फ़्लोटिंग-पॉइंट नंबर नहीं है; निकटतम, जो x को इस खंड में प्रारंभ किया जाएगा, है $1.0000000000000011102230246251565404236316680908203125=1+5\cdot 2^{-52}$. हालांकि दशमलव फ़्लोटिंग-पॉइंट से बाइनरी फ़्लोटिंग-पॉइंट तक रेडिक्स रूपांतरण में केवल एक छोटी सापेक्ष त्रुटि होती है, विपत्तिपूर्ण रद्दीकरण इसे बहुत बड़े में बढ़ा सकता है:

<वाक्यविन्यास लैंग = सी> डबल एक्स = 1.000000000000001; // राउंड टू 1 + 5*2^{-52} डबल वाई = 1.000000000000002; // राउंड टू 1 + 9*2^{-52} डबल जेड = वाई - एक्स; // अंतर बिल्कुल 4*2^{-52} है </वाक्यविन्यास हाइलाइट>

अंतर $1.000000000000002-1.000000000000001$ है $0.000000000000001=1.0\times 10^{-15}$. की सापेक्ष त्रुटियाँ x से $1.000000000000001$ और का y से $1.000000000000002$ दोनों नीचे हैं $10^{-15}=0.0000000000001\%$, और फ़्लोटिंग-पॉइंट घटाव y - x बिल्कुल स्टरबेंज़ लेम्मा द्वारा गणना की जाती है।

लेकिन भले ही इनपुट अच्छे सन्निकटन हों, और भले ही घटाव की गणना ठीक-ठीक की गई हो, सन्निकटन का अंतर ${\tilde {y}}-{\tilde {x}}=(1+9\cdot 2^{-52})-(1+5\cdot 2^{-52})=4\cdot 2^{-52}\approx 8.88\times 10^{-16}$ ओवर की सापेक्ष त्रुटि है $11\%$ अंतर से $1.0\times 10^{-15}$ दशमलव में लिखे गए मूल मानों में से: विनाशकारी रद्दीकरण ने मूलांक रूपांतरण में एक छोटी सी त्रुटि को आउटपुट में एक बड़ी त्रुटि में बदल दिया।

सौम्य रद्दीकरण

संख्यात्मक एल्गोरिदम में रद्दीकरण कभी-कभी उपयोगी और वांछनीय होता है। उदाहरण के लिए, 2Sum एल्गोरिदम दोनों राउंडिंग त्रुटि के बाद इस तरह के रद्दीकरण पर भरोसा करते हैं ताकि फ़्लोटिंग-पॉइंट जोड़ ऑपरेशन में फ़्लोटिंग-पॉइंट नंबर के रूप में त्रुटि की सटीक गणना की जा सके।

कार्यक्रम $\log(1+x)$, यदि बिंदुओं पर भोलेपन से मूल्यांकन किया जाए $0<x\lll 1$, के अधिकांश अंक खो देंगे $x$ गोलाई में $\operatorname {fl} (1+x)$. हालाँकि, समारोह $\log(1+x)$ पास के इनपुट पर ही अच्छी तरह से वातानुकूलित है $0$. के रूप में पुनः लिख रहा हूँ

$$\log(1+x)=x{\frac {\log(1+x)}{(1+x)-1}}$$

में रद्दीकरण का शोषण करता है ${\hat {x}}:=\operatorname {fl} (1+x)-1$ से त्रुटि से बचने के लिए $\log(1+x)$ सीधे मूल्यांकन किया।यह काम करता है क्योंकि अंश में रद्दीकरण $\log(\operatorname {fl} (1+x))={\hat {x}}+O({\hat {x}}^{2})$ और denominator में रद्दीकरण ${\hat {x}}=\operatorname {fl} (1+x)-1$ एक दूसरे का प्रतिकार करें; कार्यक्रम $\mu (\xi )=\log(1+\xi )/\xi$ शून्य के पास अच्छी तरह से वातानुकूलित है $\mu ({\hat {x}})$ का अच्छा अनुमान देता है $\mu (x)$, और इस तरह $x\cdot \mu ({\hat {x}})$ का अच्छा अनुमान देता है $x\cdot \mu (x)=\log(1+x)$.