Pairwise summation
عددی تجزیے میں، جوڑی کے لحاظ سے خلاصہ، جسے کاسکیڈ خلاصہ بھی کہا جاتا ہے، محدود صحت سے متعلق فلوٹنگ پوائنٹ نمبروں کی ترتیب کا خلاصہ کرنے کی ایک تکنیک ہے جو جمع شدہ راؤنڈ آف غلطی کو بے وقوف طریقے سے ترتیب میں جمع کرنے کے مقابلے میں کافی حد تک کم کرتی ہے۔ اگرچہ کہان سمیشن جیسی دوسری تکنیکیں بھی ہیں جن میں عام طور پر راؤنڈ آف کی چھوٹی غلطیاں ہوتی ہیں، جوڑی کے لحاظ سے سمیشن تقریبا اتنی ہی اچھی ہوتی ہے (صرف ایک لوگرتھمک عنصر سے مختلف ہوتی ہے) جبکہ کمپیوٹیشنل لاگت بہت کم ہوتی ہے-اسے لاگو کیا جا سکتا ہے تاکہ لاگت تقریبا یکساں ہو (اور ریاضی کی کارروائیوں کی بالکل اتنی ہی تعداد) سادہ سمیشن کی طرح۔ خاص طور پر، n اعداد xn کی ترتیب کا جوڑی وار مجموعہ ترتیب کو بار بار دو حصوں میں توڑ کر، ہر نصف کا خلاصہ کرکے، اور دو جملوں کو شامل کرکے کام کرتا ہے: ایک تقسیم اور فتح الگورتھم۔ اس کی بدترین صورت میں راؤنڈ آف غلطیاں زیادہ سے زیادہ O (ε لاگ n) کے طور پر غیر علامتی طور پر بڑھتی ہیں، جہاں ε مشین کی درستگی ہے (ایک مقررہ حالت نمبر فرض کرتے ہوئے، جیسا کہ ذیل میں بحث کی گئی ہے)۔ اس کے مقابلے میں، مجموعہ کو ترتیب میں جمع کرنے کی بے وقوف تکنیک (i = 1,., n کے لیے ایک وقت میں ہر xi کو شامل کرنا) میں راؤنڈ آف کی غلطیاں ہوتی ہیں جو O (εn) کے طور پر بدترین ہوتی جاتی ہیں۔ کہان سمیشن میں تقریبا 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) کے طور پر غیر علامتی طور پر بڑھتی ہے (نیچے دیکھیں)۔ اس قسم کے الگورتھم میں (جہاں تک عام طور پر الگورتھم کو تقسیم کرنے اور فتح کرنے کا تعلق ہے)، ریکرشن کے اوور ہیڈ کو کم کرنے کے لیے ایک بڑا بیس کیس استعمال کرنا مطلوب ہے۔ اگر N = 1، تو ہر ان پٹ کے لیے تقریبا ایک ریکرسو سبروٹین کال ہوتی ہے، لیکن زیادہ عام طور پر ہر N/2 ان پٹ کے لیے (تقریبا) ایک ریکرسو کال ہوتی ہے اگر ریکرسن بالکل n = N پر رک جاتا ہے۔ N کو کافی بڑا بنا کر، ریکرسن کے اوور ہیڈ کو نہ ہونے کے برابر بنایا جا سکتا ہے (خاص طور پر ریکرسو سمیشن کے لیے ایک بڑے بیس کیس کی یہ تکنیک اعلی کارکردگی والے FFT نفاذ کے ذریعے استعمال کی جاتی ہے)۔ N سے قطع نظر، بالکل n−1 اضافے مجموعی طور پر کیے جاتے ہیں، جو کہ سادہ خلاصہ کے لیے ہوتے ہیں، لہذا اگر ریکرشن اوور ہیڈ کو نہ ہونے کے برابر بنایا جائے تو جوڑی کے لحاظ سے خلاصہ میں بنیادی طور پر وہی کمپیوٹیشنل لاگت ہوتی ہے جو سادہ خلاصہ کے لیے ہوتی ہے۔ اس خیال میں ایک تغیر یہ ہے کہ ہر تکراری مرحلے پر رقم کو b بلاکس میں تقسیم کیا جائے، ہر بلاک کا تکراری خلاصہ کیا جائے، اور پھر نتائج کا خلاصہ کیا جائے، جسے اس کے تجویز کنندگان نے "سپر بلاک" الگورتھم قرار دیا تھا۔ مندرجہ بالا جوڑی وار الگورتھم ہر مرحلے کے لیے b = 2 سے مطابقت رکھتا ہے سوائے آخری مرحلے کے جو کہ b = N ہے۔ درستگی فرض کریں کہ ایک n اقدار xi کا خلاصہ کر رہا ہے، i = 1،., n کے لیے۔ صحیح مجموعہ ہے: (لامحدود درستگی کے ساتھ شمار کیا گیا)۔ بیس کیس N = 1 کے لیے جوڑی کے لحاظ سے خلاصہ کے ساتھ، اس کے بجائے ایک حاصل ہوتا ہے، جہاں غلطی اوپر سے پابند ہوتی ہے: جہاں ε استعمال ہونے والے ریاضی کی مشین کی درستگی ہے (جیسے۔ ε ≈ 10−16 معیاری ڈبل صحت سے متعلق فلوٹنگ پوائنٹ کے لیے)۔ عام طور پر، سود کی مقدار رشتہ دار غلطی ہوتی ہے، جو اس لیے اوپر سے پابند ہوتی ہے: رشتہ دار غلطی کے پابند ہونے کے اظہار میں، فریکشن (ss |xi |/|Σxi |) سمیشن کے مسئلے کا کنڈیشن نمبر ہے۔ بنیادی طور پر، کنڈیشن نمبر غلطیوں کے لیے خلاصہ کے مسئلے کی اندرونی حساسیت کی نمائندگی کرتا ہے، اس سے قطع نظر کہ اس کا حساب کیسے کیا جاتا ہے۔ فکسڈ درستگی میں ایک فکسڈ الگورتھم کے ذریعہ ہر (بیکورڈ اسٹیبل) سمیشن طریقہ کار سے منسلک رشتہ دار غلطی (یعنی۔ وہ نہیں جو صوابدیدی صحت سے متعلق ریاضی استعمال کرتے ہیں، اور نہ ہی الگورتھم جن کی میموری اور وقت کی ضروریات ڈیٹا کی بنیاد پر بدلتی ہیں)، اس کنڈیشن نمبر کے متناسب ہیں۔ ایک غیر مشروط خلاصہ مسئلہ وہ ہے جس میں یہ تناسب بڑا ہوتا ہے، اور اس صورت میں جوڑی کے لحاظ سے خلاصہ بھی ایک بڑی رشتہ دار غلطی کا باعث بن سکتا ہے۔ مثال کے طور پر، اگر خلاصہ xi صفر اوسط کے ساتھ غیر مربوط بے ترتیب اعداد ہیں، تو مجموعہ ایک بے ترتیب واک ہے اور کنڈیشن نمبر اس کے متناسب بڑھے گا۔ دوسری طرف، غیر صفر کے ساتھ بے ترتیب ان پٹ کے لیے کنڈیشن نمبر کا مطلب ایک محدود مستقل کے لیے اسمیپٹوٹس ہے۔ اگر تمام ان پٹ غیر منفی ہیں، تو کنڈیشن نمبر 1 ہے۔ نوٹ کریں کہ ڈینومینیٹر عملی طور پر مؤثر طریقے سے 1 ہے، کیونکہ 1 سے بہت چھوٹا ہے جب تک کہ n ترتیب 21/ε کا نہ ہو جائے، جو کہ دوہری درستگی میں تقریبا 101015 ہے۔ اس کے مقابلے میں، بے وقوف خلاصہ کے لیے پابند رشتہ دار غلطی (صرف اعداد کو ترتیب میں شامل کرنا، ہر مرحلے پر گول کرنا) حالت نمبر سے ضرب کے طور پر بڑھتی ہے۔ عملی طور پر، اس بات کا بہت زیادہ امکان ہے کہ گول کرنے کی غلطیوں میں بے ترتیب علامت ہوتی ہے، جس میں صفر کا مطلب ہوتا ہے، تاکہ وہ بے ترتیب چہل قدمی تشکیل دیں۔ اس صورت میں، سادہ خلاصہ میں ایک جڑ کا مطلب مربع رشتہ دار غلطی ہوتی ہے جو بڑھتی ہے اور جوڑی کے لحاظ سے خلاصہ میں ایک غلطی ہوتی ہے جو اوسطا بڑھتی ہے۔ سافٹ ویئر کے نفاذ جوڑی کے لحاظ سے خلاصہ نمپی اور جولیا ٹیکنیکل کمپیوٹنگ زبان میں ڈیفالٹ سمیشن الگورتھم ہے، جہاں دونوں صورتوں میں اس کی رفتار سادہ خلاصہ سے موازنہ کرنے کے لیے پائی گئی (ایک بڑے بیس کیس کے استعمال کی بدولت)۔ سافٹ ویئر کے دیگر نفاذ میں سی #زبان کے لیے ایچ پی سی شارپ لائبریری اور ڈی میں معیاری لائبریری کا خلاصہ شامل ہے۔ حوالہ جات کمپیوٹر ریاضی عددی تجزیہ مضامین مثال کے طور پر سڈو کوڈ کے ساتھ