Pairwise summation
संख्यात्मक विश्लेषण में, जोड़ीदार योग, जिसे कैस्केड योग भी कहा जाता है, सीमित-परिशुद्धता फ्लोटिंग-पॉइंट संख्याओं के अनुक्रम को जोड़ने की एक तकनीक है जो अनुक्रम में सरलता से योग को जमा करने की तुलना में संचित राउंड-ऑफ त्रुटि को काफी कम कर देती है। यद्यपि काहन योग जैसी अन्य तकनीकें हैं जिनमें आम तौर पर और भी छोटी राउंड-ऑफ त्रुटियां होती हैं, जोड़ीदार योग लगभग उतना ही अच्छा है (केवल एक लघुगणक कारक द्वारा भिन्न) जबकि बहुत कम कम्प्यूटेशनल लागत होती है-इसे लागू किया जा सकता है ताकि लगभग समान लागत हो (और अंकगणितीय संचालन की बिल्कुल समान संख्या) सरल योग के रूप में। विशेष रूप से, n संख्याओं xn के अनुक्रम का जोड़ीदार योग अनुक्रम को दो हिस्सों में पुनरावर्ती रूप से तोड़कर, प्रत्येक आधे को जोड़कर और दो योग जोड़कर काम करता हैः एक विभाजन और विजय एल्गोरिथ्म। इसकी सबसे खराब स्थिति राउंडऑफ़ त्रुटियाँ अधिकतम ओ (ε लॉग एन) के रूप में स्पर्शोन्मुख रूप से बढ़ती हैं, जहाँ ε मशीन की परिशुद्धता है (एक निश्चित स्थिति संख्या मानते हुए, जैसा कि नीचे चर्चा की गई है)। इसकी तुलना में, अनुक्रम में योग को जमा करने की सरल तकनीक (i = 1,., n के लिए एक समय में प्रत्येक xi को जोड़ने) में राउंडऑफ़ त्रुटियाँ होती हैं जो O (εn) के रूप में सबसे खराब होती हैं। काहन योग में लगभग ओ (ε) की सबसे खराब स्थिति त्रुटि है, जो एन से स्वतंत्र है, लेकिन इसके लिए कई गुना अधिक अंकगणितीय संचालन की आवश्यकता होती है। यदि राउंडऑफ़ त्रुटियाँ यादृच्छिक हैं, और विशेष रूप से यादृच्छिक संकेत हैं, तो वे एक यादृच्छिक चाल बनाते हैं और त्रुटि वृद्धि जोड़ीदार योग के लिए औसत तक कम हो जाती है। योग की एक बहुत ही समान पुनरावर्ती संरचना कई तेज फूरियर परिवर्तन (एफ. एफ. टी.) एल्गोरिदम में पाई जाती है, और उन एफ. एफ. टी. के समान धीमे राउंडऑफ़ संचय के लिए जिम्मेदार है। एल्गोरिथ्म सूडोकोड में, लंबाई ≤ 0 की एक सरणी के लिए युग्मवार योग एल्गोरिथ्म लिखा जा सकता हैः s = युग्मवार (x [1. n]) यदि n ≤ N आधार मामलाः पर्याप्त रूप से छोटे सरणी के लिए सरल योग s = 0 के लिए i = 1 से n s = s + x [i] अन्यथा विभाजित करें और जीतेंः सरणी के दो हिस्सों को पुनरावर्ती रूप से जोड़ें m = मंजिल (n/2) s = युग्मवार (x [1. m]) + युग्मवार (x [m + 1. n]) समाप्त होता है यदि कुछ पर्याप्त रूप से छोटे के लिए, यह एल्गोरिथ्म एक सरल लूप-आधारित योग में बदल जाता है एक आधार मामले के रूप में, जिसकी त्रुटि सीमा O (Nε) है। पूरे योग में एक सबसे खराब स्थिति त्रुटि होती है जो किसी दिए गए शर्त संख्या (नीचे देखें) के लिए बड़े n के लिए O (ε लॉग n) के रूप में लक्षणहीन रूप से बढ़ती है। इस प्रकार के एल्गोरिदम में (सामान्य रूप से एल्गोरिदम को विभाजित करने और जीतने के लिए), पुनरावृत्ति के ऊपरी हिस्से का परिशोधन करने के लिए एक बड़े आधार मामले का उपयोग करना वांछनीय है। यदि एन = 1 है, तो प्रत्येक इनपुट के लिए लगभग एक पुनरावर्ती सबरूटीन कॉल होती है, लेकिन अधिक सामान्य रूप से प्रत्येक एन/2 इनपुट के लिए (मोटे तौर पर) एक पुनरावर्ती कॉल होती है यदि पुनरावृत्ति बिल्कुल एन = एन पर रुक जाती है। एन को पर्याप्त रूप से बड़ा बनाकर, पुनरावर्तन के ऊपरी हिस्से को नगण्य बनाया जा सकता है (सटीक रूप से पुनरावर्ती योग के लिए एक बड़े आधार मामले की इस तकनीक को उच्च प्रदर्शन वाले एफ. एफ. टी. कार्यान्वयन द्वारा नियोजित किया जाता है)। एन के बावजूद, बिल्कुल एन-1 जोड़ कुल मिलाकर किए जाते हैं, जो कि सरल योग के लिए समान है, इसलिए यदि पुनरावृत्ति ओवरहेड को नगण्य बनाया जाता है तो जोड़ीदार योग में अनिवार्य रूप से सरल योग के लिए समान कम्प्यूटेशनल लागत होती है। इस विचार पर एक भिन्नता यह है कि प्रत्येक पुनरावर्ती चरण में योग को बी ब्लॉकों में विभाजित किया जाए, प्रत्येक ब्लॉक को पुनरावर्ती रूप से जोड़ा जाए, और फिर परिणामों का योग किया जाए, जिसे इसके प्रस्तावकों द्वारा "सुपरब्लॉक" एल्गोरिदम कहा गया था। उपरोक्त जोड़ीदार एल्गोरिथ्म अंतिम चरण को छोड़कर प्रत्येक चरण के लिए b = 2 से मेल खाता है जो b = N है। सटीकता मान लीजिए कि एक n मान xi का योग कर रहा है, i = 1,., n के लिए। सटीक योग हैः (अनंत सटीकता के साथ गणना की गई)। एक आधार मामले N = 1 के लिए जोड़ीदार योग के साथ, एक इसके बजाय प्राप्त करता है, जहां त्रुटि ऊपर से घिरी हुई हैः जहां ε नियोजित किए जा रहे अंकगणित की मशीन परिशुद्धता है (जैसे। मानक दोहरे परिशुद्धता वाले तैरते बिंदु के लिए ε ≈ 10−16)। आम तौर पर, ब्याज की मात्रा सापेक्ष त्रुटि होती है, जो इसलिए ऊपर इस प्रकार बंधी होती हैः सापेक्ष त्रुटि बाध्य के लिए अभिव्यक्ति में, अंश (‡ |xi।/|Σxi।) योग समस्या की शर्त संख्या है। अनिवार्य रूप से, स्थिति संख्या त्रुटियों के लिए योग समस्या की आंतरिक संवेदनशीलता का प्रतिनिधित्व करती है, भले ही इसकी गणना कैसे की जाए। निश्चित परिशुद्धता में एक निश्चित एल्गोरिथ्म द्वारा प्रत्येक (पीछे की ओर स्थिर) योग विधि की सापेक्ष त्रुटि। वे नहीं जो मनमाने-सटीक अंकगणित का उपयोग करते हैं, और न ही एल्गोरिदम जिनकी स्मृति और समय की आवश्यकताएँ डेटा के आधार पर बदलती हैं), इस स्थिति संख्या के समानुपाती हैं। एक गैर-वातानुकूलित योग समस्या वह है जिसमें यह अनुपात बड़ा होता है, और इस मामले में जोड़ीदार योग में भी एक बड़ी सापेक्ष त्रुटि हो सकती है। उदाहरण के लिए, यदि योग xi शून्य माध्य के साथ असंबद्ध यादृच्छिक संख्याएँ हैं, तो योग एक यादृच्छिक चाल है और स्थिति संख्या इसके समानुपाती होगी। दूसरी ओर, गैर-शून्य के साथ यादृच्छिक निवेश के लिए एक परिमित स्थिरांक के लिए स्थिति संख्या एसिम्प्टोट्स का अर्थ है। यदि सभी इनपुट गैर-नकारात्मक हैं, तो शर्त संख्या 1 है। ध्यान दें कि व्यवहार में भाजक प्रभावी रूप से 1 है, क्योंकि 1 से बहुत छोटा है जब तक कि n 21/ε क्रम का नहीं हो जाता है, जो कि दोगुनी सटीकता में लगभग 101015 है। इसकी तुलना में, सरल योग के लिए बाध्य सापेक्ष त्रुटि (बस अनुक्रम में संख्याओं को जोड़ना, प्रत्येक चरण में गोल करना) स्थिति संख्या से गुणा के रूप में बढ़ती है। व्यवहार में, यह बहुत अधिक संभावना है कि गोल त्रुटियों में एक यादृच्छिक संकेत होता है, शून्य माध्य के साथ, ताकि वे एक यादृच्छिक चलना बना सकें; इस मामले में, सरल योग में एक मूल माध्य वर्ग सापेक्ष त्रुटि होती है जो बढ़ती है और जोड़ीदार योग में एक त्रुटि होती है जो औसतन बढ़ती है। सॉफ़्टवेयर कार्यान्वयन जोड़ीदार योग NumPy और जूलिया तकनीकी-कम्प्यूटिंग भाषा में डिफ़ॉल्ट योग एल्गोरिथ्म है, जहाँ दोनों मामलों में यह सरल योग के लिए तुलनीय गति पाया गया था (एक बड़े आधार मामले के उपयोग के लिए धन्यवाद)। अन्य सॉफ्टवेयर कार्यान्वयनों में सी #भाषा के लिए एच. पी. सी. शार्प लाइब्रेरी और डी. में मानक लाइब्रेरी योग शामिल हैं।