Pivot element
محور یا محور عنصر میٹرکس، یا ایک صف کا عنصر ہے، جسے پہلے الگورتھم کے ذریعے منتخب کیا جاتا ہے (مثال کے طور پر۔ گوسیائی خاتمہ، سمپلیکس الگورتھم، وغیرہ۔ )، کچھ حساب کتاب کرنے کے لیے۔ میٹرکس الگورتھم کے معاملے میں، ایک محور اندراج عام طور پر کم از کم صفر سے الگ ہونا ضروری ہے، اور اکثر اس سے دور ہونا ضروری ہے۔ اس صورت میں اس عنصر کو تلاش کرنا پیوٹنگ کہلاتا ہے۔ پیوٹنگ کے بعد قطاریں یا کالموں کا تبادلہ کیا جا سکتا ہے تاکہ محور کو ایک مقررہ پوزیشن پر لایا جا سکے اور الگورتھم کو کامیابی کے ساتھ آگے بڑھنے دیا جا سکے، اور ممکنہ طور پر راؤنڈ آف ایرر کو کم کیا جا سکے۔ یہ اکثر قطار کی ایکلون شکل کی تصدیق کے لیے استعمال ہوتا ہے۔ پیوٹنگ کو میٹرکس میں قطاروں یا کالموں کو تبدیل کرنے یا ترتیب دینے کے طور پر سوچا جا سکتا ہے، اور اس طرح اسے تعدد میٹرکس کے ذریعے ضرب کے طور پر پیش کیا جا سکتا ہے۔ تاہم، الگورتھم شاذ و نادر ہی میٹرکس عناصر کو منتقل کرتے ہیں کیونکہ اس میں بہت زیادہ وقت لگتا ہے ؛ اس کے بجائے، وہ صرف ترتیبات پر نظر رکھتے ہیں۔ مجموعی طور پر، پیوٹنگ ایک الگورتھم کی کمپیوٹیشنل لاگت میں مزید کارروائیوں کا اضافہ کرتی ہے۔ یہ اضافی کارروائیاں بعض اوقات الگورتھم کے بالکل کام کرنے کے لیے ضروری ہوتی ہیں۔ دوسرے اوقات یہ اضافی کارروائیاں قابل قدر ہوتی ہیں کیونکہ وہ حتمی نتیجہ میں عددی استحکام کا اضافہ کرتی ہیں۔ ان نظاموں کی مثالیں جن میں پیوٹنگ کی ضرورت ہوتی ہے۔ گوسیائی خاتمے کے معاملے میں، الگورتھم کے لیے ضروری ہے کہ پیوٹ عناصر صفر نہ ہوں۔ صفر محور عنصر کی صورت میں قطاروں یا کالموں کا تبادلہ ضروری ہے۔ نیچے دیے گئے نظام کو ختم کرنے کے لیے قطاریں 2 اور 3 کے تبادلے کی ضرورت ہوتی ہے۔ پیوٹنگ کے نتیجے میں آنے والا نظام مندرجہ ذیل ہے اور یہ ایلیمینیشن الگورتھم اور بیکورڈ سبسٹیوشن کو سسٹم کے حل کو آؤٹ پٹ کرنے کی اجازت دے گا۔ مزید برآں، گوسیائی خاتمے میں عام طور پر بڑے مطلق قدر والے محور عنصر کا انتخاب کرنا مطلوب ہے۔ یہ عددی استحکام کو بہتر بناتا ہے۔ مندرجہ ذیل نظام راؤنڈ آف ایرر سے ڈرامائی طور پر متاثر ہوتا ہے جب گوسیئن کا خاتمہ اور بیکورڈ متبادل انجام دیا جاتا ہے۔ اس نظام میں x1 = 10.00 اور x2 = 1.000 کا صحیح حل ہے، لیکن جب ایلیمینیشن الگورتھم اور بیکورڈ سبسٹیوشن کو چار ہندسوں کے ریاضی کا استعمال کرتے ہوئے انجام دیا جاتا ہے، تو a11 کی چھوٹی قدر چھوٹی راؤنڈ آف غلطیوں کا سبب بنتی ہے۔ محور کے بغیر الگورتھم x1 ≈ 9873.3 اور x2 ≈ 4 کا تخمینہ پیدا کرتا ہے۔ اس صورت میں یہ مطلوب ہے کہ ہم دونوں قطاروں کا تبادلہ کریں تاکہ a21 محور کی پوزیشن میں ہو۔ اس نظام کو مدنظر رکھتے ہوئے، چار ہندسوں کے ریاضی کا استعمال کرتے ہوئے ایلیمینیشن الگورتھم اور بیکورڈ متبادل سے صحیح اقدار x1 = 10.00 اور x2 = 1.000 حاصل ہوتی ہیں۔ جزوی، روک، اور مکمل پیوٹنگ جزوی پیوٹنگ میں، الگورتھم میٹرکس کے کالم سے سب سے بڑی مطلق قیمت کے ساتھ اندراج کا انتخاب کرتا ہے جسے فی الحال پیوٹ عنصر سمجھا جا رہا ہے۔ مزید خاص طور پر، جب کسی میٹرکس کو قطار کی ایکلون شکل میں کم کیا جاتا ہے، تو کالم کی قطار میں کمی سے پہلے جزوی پیوٹنگ تبدیلیاں قطاریں بناتی ہیں تاکہ محور عنصر کی اسی کالم میں نیچے دیے گئے عناصر کے مقابلے میں سب سے بڑی مطلق قیمت ہو۔ جزوی پیوٹنگ عام طور پر راؤنڈ آف کی غلطی کو مناسب طریقے سے کم کرنے کے لیے کافی ہوتی ہے۔ تاہم، بعض نظاموں اور الگورتھم کے لیے، قابل قبول درستگی کے لیے مکمل پیوٹنگ (یا زیادہ سے زیادہ پیوٹنگ) کی ضرورت پڑ سکتی ہے۔ مکمل پیوٹنگ میٹرکس میں سب سے بڑے (مطلق قدر کے لحاظ سے) عنصر کو محور کے طور پر استعمال کرنے کے لیے قطاریں اور کالم دونوں کا تبادلہ کرتی ہے۔ عددی استحکام کو یقینی بنانے کے لیے عام طور پر مکمل پیوٹنگ ضروری نہیں ہے اور زیادہ سے زیادہ عنصر کی تلاش کی اضافی لاگت کی وجہ سے، عددی استحکام میں بہتری جو یہ فراہم کرتا ہے عام طور پر سب کے لیے اس کی کم کارکردگی سے زیادہ ہوتی ہے لیکن سب سے چھوٹے میٹرکس کے لیے۔ اس لیے یہ شاذ و نادر ہی استعمال ہوتا ہے۔ ایک اور حکمت عملی، جسے روک پیوٹنگ کے نام سے جانا جاتا ہے، دونوں قطاروں اور کالموں کو آپس میں بدلتا ہے لیکن صرف اس بات کی ضمانت دیتا ہے کہ منتخب کردہ محور بیک وقت اس کی قطار میں سب سے بڑا ممکنہ اندراج اور اس کے کالم میں سب سے بڑا ممکنہ اندراج ہے، جیسا کہ پورے بقیہ ذیلی میٹرکس میں سب سے بڑا ممکن ہے۔ جب سیریل کمپیوٹرز پر لاگو کیا جاتا ہے تو اس حکمت عملی کی لاگت جزوی پیوٹنگ سے صرف تین گنا زیادہ ہونے کی توقع کی جاتی ہے اور اس وجہ سے یہ مکمل پیوٹنگ سے سستی ہے۔ روک پیوٹنگ نظریاتی اور عملی طور پر جزوی پیوٹنگ سے زیادہ مستحکم ثابت ہوئی ہے۔ اسکیلڈ پیوٹنگ جزوی پیوٹنگ حکمت عملی کی ایک تغیر کو اسکیلڈ پیوٹنگ کہا جاتا ہے۔ اس نقطہ نظر میں، الگورتھم محور عنصر کے طور پر اس اندراج کا انتخاب کرتا ہے جو اس کی صف میں اندراجات کے مقابلے میں سب سے بڑا ہے۔ یہ حکمت عملی تب مطلوب ہوتی ہے جب اندراجات کی شدت میں بڑے فرق راؤنڈ آف غلطی کے پھیلاؤ کا باعث بنتے ہیں۔ اسکیلڈ پیوٹنگ کو ایسے نظام میں استعمال کیا جانا چاہیے جیسے نیچے والے نظام میں جہاں قطار کی اندراجات شدت میں بہت مختلف ہوتی ہیں۔ نیچے دی گئی مثال میں، دونوں قطاروں کا تبادلہ کرنا مطلوب ہوگا کیونکہ موجودہ محور عنصر 30 5.291 سے بڑا ہے لیکن یہ اس کی قطار میں موجود دیگر اندراجات کے مقابلے میں نسبتا چھوٹا ہے۔ اس معاملے میں قطار کے تبادلے کے بغیر، راؤنڈنگ کی غلطیوں کو پچھلی مثال کی طرح پھیلایا جائے گا۔ محور پوزیشن ایک میٹرکس میں ایک محور پوزیشن، A، میٹرکس میں ایک پوزیشن ہے جو A کی کم شدہ قطار ایکلون شکل میں صف میں سرفہرست 1 سے مطابقت رکھتی ہے۔ چونکہ اے کی کم شدہ قطار ایکلون شکل منفرد ہے، اس لیے محور کی پوزیشنوں کا منفرد طور پر تعین کیا جاتا ہے اور اس کا انحصار اس بات پر نہیں ہوتا ہے کہ کمی کے عمل میں قطار کے تبادلے کیے جاتے ہیں یا نہیں۔ اس کے علاوہ، ایک قطار کا محور اوپر کی صف میں محور کے دائیں طرف قطار ایکلون کی شکل میں ظاہر ہونا چاہیے۔ حوالہ جات آر۔ ایل۔ برڈن، جے۔ ڈی۔ فیئر، عددی تجزیہ، 8 واں ایڈیشن، تھامسن بروکس/کول، 2005۔ جی ایچ گولب، سی ایف لون، میٹرکس کمپیوٹیشنز، تیسرا ایڈیشن، جانز ہاپکنز، 1996۔ عددی لکیری الجبرا ایکسچینج الگورتھم ایس وی: اہم عنصر