Conjugate gradient method
ریاضی میں، کنجوگیٹ گریڈینٹ طریقہ لکیری مساوات کے مخصوص نظاموں کے عددی حل کے لیے ایک الگورتھم ہے، یعنی وہ جن کا میٹرکس مثبت-یقینی ہے۔ کنجوگیٹ گریڈینٹ طریقہ اکثر ایک تکراری الگورتھم کے طور پر لاگو کیا جاتا ہے، جو غیر معمولی نظاموں پر لاگو ہوتا ہے جو براہ راست نفاذ یا دوسرے براہ راست طریقوں جیسے کہ چولسکی سڑنے کے ذریعے سنبھالے جانے کے لیے بہت بڑے ہوتے ہیں۔ بڑے غیر معمولی نظام اکثر اس وقت پیدا ہوتے ہیں جب عددی طور پر جزوی تفریقی مساوات یا اصلاح کے مسائل کو حل کیا جاتا ہے۔ کنجوگیٹ گریڈینٹ کا طریقہ غیر محدود اصلاح کے مسائل جیسے توانائی کو کم سے کم کرنے کے لیے بھی استعمال کیا جا سکتا ہے۔ اسے عام طور پر میگنس ہیسٹینس اور ایڈورڈ سٹیفل سے منسوب کیا جاتا ہے، جنہوں نے اسے زیڈ 4 پر پروگرام کیا، اور اس پر بڑے پیمانے پر تحقیق کی۔ بائیکونجوگیٹ گریڈینٹ طریقہ غیر ہم آہنگی میٹرکس کو عمومی شکل فراہم کرتا ہے۔ مختلف غیر لکیری کنجوگیٹ گریڈینٹ طریقے غیر لکیری اصلاح کے مسائل کو کم سے کم تلاش کرتے ہیں۔ کنجوگیٹ گریڈینٹس کے ذریعے حل کیے گئے مسئلے کی تفصیل فرض کریں کہ ہم ویکٹر کے لیے لکیری مساوات کے نظام کو حل کرنا چاہتے ہیں، جہاں معروف میٹرکس سمیٹرک (یعنی، اے ٹی = اے)، مثبت-یقینی (یعنی۔ xTAx> 0 Rn میں تمام غیر صفر ویکٹروں کے لیے)، اور حقیقی، اور یہ بھی جانا جاتا ہے۔ ہم اس نظام کے منفرد حل کی نشاندہی کرتے ہیں۔ کنجوگیٹ گریڈینٹ طریقہ کئی مختلف نقطہ نظر سے اخذ کیا جا سکتا ہے، بشمول اصلاح کے لیے کنجوگیٹ سمت کے طریقہ کار کی تخصص، اور آئجین ویلیو کے مسائل کے لیے آرنلڈی/لینکزوس تکرار کی تغیر۔ ان کے نقطہ نظر میں اختلافات کے باوجود، یہ مشتقات ایک مشترکہ موضوع کا اشتراک کرتی ہیں-بقایا کی آرتھوگونالیٹی اور تلاش کی سمتوں کی ہم آہنگی کو ثابت کرتی ہیں۔ یہ دونوں خصوصیات طریقہ کار کی معروف مختصر تشکیل کو تیار کرنے کے لیے اہم ہیں۔ ہم کہتے ہیں کہ دو غیر صفر ویکٹر u اور v کنجوگیٹ ہیں (کے حوالے سے) اگر ہم آہنگی اور مثبت-یقینی ہے، تو بائیں ہاتھ کی طرف ایک اندرونی پروڈکٹ کی وضاحت کرتا ہے۔ دو ویکٹر اس صورت میں کنجوگیٹ ہوتے ہیں جب وہ اس اندرونی پروڈکٹ کے حوالے سے آرتھوگنل ہوں۔ کنجوگیٹ ہونا ایک سمیٹرک رشتہ ہے: اگر کنجوگیٹ ہے، تو کنجوگیٹ ہے۔ فرض کریں کہ یہ باہمی طور پر کنجوگیٹ ویکٹروں کا ایک مجموعہ ہے، یعنی۔ سب کے لیے۔ پھر اس کے لیے ایک بنیاد بنتی ہے، اور ہم اس بنیاد پر اس کے حل کا اظہار کر سکتے ہیں: ویکٹر کی پیداوار کے ساتھ مسئلے کو بائیں سے ضرب دینا اور اس طرح یہ مساوات کو حل کرنے کے لیے درج ذیل طریقہ فراہم کرتا ہے: کنجوگیٹ سمتوں کی ترتیب تلاش کریں، اور پھر کوفشنٹس کا حساب لگائیں۔ ایک تکراری طریقہ کے طور پر اگر ہم کنجوگیٹ ویکٹر کو احتیاط سے منتخب کرتے ہیں، تو ہمیں حل کا اچھا تخمینہ حاصل کرنے کے لیے ان سب کی ضرورت نہیں ہوگی۔ لہذا، ہم کنجوگیٹ گریڈینٹ طریقہ کو ایک تکراری طریقہ سمجھنا چاہتے ہیں۔ یہ ہمیں ان نظاموں کو تقریبا حل کرنے کی بھی اجازت دیتا ہے جہاں n اتنا بڑا ہے کہ براہ راست طریقہ کار میں بہت زیادہ وقت لگے گا۔ ہم by کے لیے ابتدائی اندازے کی نشاندہی کرتے ہیں (ہم عامیت کے نقصان کے بغیر فرض کر سکتے ہیں کہ، بصورت دیگر اس کے بجائے نظام Az = b − Ax0 پر غور کریں)۔ x0 سے شروع کرتے ہوئے ہم حل تلاش کرتے ہیں اور ہر تکرار میں ہمیں یہ بتانے کے لیے ایک میٹرک کی ضرورت ہوتی ہے کہ آیا ہم حل کے قریب ہیں (جو ہمیں معلوم نہیں ہے)۔ یہ میٹرک اس حقیقت سے آتا ہے کہ حل مندرجہ ذیل کواڈریٹک فنکشن کا منفرد منیائزر بھی ہے۔ ایک منفرد منیائزر کا وجود واضح ہے کیونکہ اس کا دوسرے مشتقات کا ہیسیئن میٹرکس سمیٹرک مثبت-یقینی ہے اور یہ کہ منیائزر (Df (x) = 0 استعمال کرتا ہے) ابتدائی مسئلے کو حل کرتا ہے جو اس کے پہلے مشتق سے آتا ہے۔ اس سے پہلے بیس ویکٹر p0 کو x = x0 پر f کے میلان کا منفی لینے کا مشورہ ملتا ہے۔ f کا میلان برابر ہے۔ ابتدائی اندازے x0 سے شروع کرتے ہوئے، اس کا مطلب ہے کہ ہم p0 = b − Ax0 لیتے ہیں۔ بیس میں موجود دوسرے ویکٹر گریڈیئنٹ کے ساتھ کنجوگیٹ ہوں گے، اس لیے اس کا نام کنجوگیٹ گریڈیئنٹ طریقہ ہے۔ نوٹ کریں کہ p0 الگورتھم کے اس ابتدائی مرحلے کے ذریعہ فراہم کردہ بقایا بھی ہے۔ k ویں مرحلے پر rk کو بقایا مان لیں: جیسا کہ اوپر مشاہدہ کیا گیا ہے، یہ at کا منفی میلان ہے، لہذا میلان نزول کے طریقہ کار کو rk کی سمت میں منتقل کرنے کی ضرورت ہوگی۔ تاہم، یہاں ہم اس بات پر اصرار کرتے ہیں کہ ہدایات ایک دوسرے سے مربوط ہونی چاہئیں۔ اس کو نافذ کرنے کا ایک عملی طریقہ یہ ہے کہ اگلی تلاش کی سمت موجودہ بقایا اور تمام پچھلی تلاش کی سمتوں سے بنائی جائے۔ کنجگیشن رکاوٹ ایک آرتھونورمل قسم کی رکاوٹ ہے اور اس لیے الگورتھم کو گرام-شمٹ آرتھونورملائزیشن کی مثال کے طور پر دیکھا جا سکتا ہے۔ یہ مندرجہ ذیل اظہار دیتا ہے: (کنورجنس پر کنجوگیسی رکاوٹ کے اثر کے لیے مضمون کے اوپری حصے میں موجود تصویر دیکھیں)۔ اس سمت کی پیروی کرتے ہوئے، اگلا بہترین مقام اس کے ذریعہ دیا جاتا ہے جہاں کی تعریف سے آخری مساوات کی پیروی ہوتی ہے۔ کے لیے اظہار اس صورت میں اخذ کیا جا سکتا ہے جب کوئی xk + 1 کے لیے اظہار کو f میں تبدیل کرے اور اس کے نتیجے میں الگورتھم کے حوالے سے اسے کم سے کم کرے۔ مندرجہ بالا الگورتھم کنجوگیٹ گریڈینٹ طریقہ کار کی سب سے سیدھی وضاحت دیتا ہے۔ بظاہر، جیسا کہ بیان کیا گیا ہے کہ الگورتھم میں تمام پچھلی تلاش کی سمتوں اور بقیہ ویکٹروں کے ساتھ ساتھ بہت سے میٹرکس ویکٹر ضرب کو ذخیرہ کرنے کی ضرورت ہوتی ہے، اور اس طرح یہ کمپیوٹیشنل طور پر مہنگا ہو سکتا ہے۔ تاہم، الگورتھم کے قریبی تجزیے سے پتہ چلتا ہے کہ یہ آرتھوگنل ہے، یعنی۔ ، i  ऒत्त ج کے لیے۔ اور-orthogonal ہے، یعنی۔ ، کے لیے۔ یہ سمجھا جا سکتا ہے کہ جیسے جیسے الگورتھم ترقی کرتا ہے، اور اسی کریلوف سب اسپیس میں پھیلا ہوا ہے۔ جہاں معیاری اندرونی پروڈکٹ کے حوالے سے آرتھوگنل بنیاد بنتی ہے، اور اندرونی پروڈکٹ کے حوالے سے آرتھوگنل بنیاد بناتی ہے۔ لہذا، کریلوف سب اسپیس پر کے پروجیکشن کے طور پر سمجھا جا سکتا ہے۔ Ax = b کو حل کرنے کے لیے الگورتھم ذیل میں تفصیلی ہے جہاں ایک حقیقی، ہم آہنگ، مثبت-یقینی میٹرکس ہے۔ ان پٹ ویکٹر ایک لگ بھگ ابتدائی حل یا 0 ہو سکتا ہے۔ یہ اوپر بیان کردہ عین طریقہ کار کی ایک مختلف تشکیل ہے۔ یہ سب سے زیادہ استعمال ہونے والا الگورتھم ہے۔ یہی فارمولا فلیچر-ریوز غیر لکیری کنجوگیٹ گریڈینٹ طریقہ کار میں بھی استعمال ہوتا ہے۔ دوبارہ شروع کریں ہم نوٹ کرتے ہیں کہ اس کا حساب گریڈینٹ ڈیسنٹ کے طریقہ کار سے لگایا جاتا ہے۔ ترتیب اسی طرح گریڈیئنٹ نزول کے طریقہ کار کے ذریعے شمار کی جائے گی، یعنی، کنجوگیٹ گریڈیئنٹ تکرار کے دوبارہ شروع کرنے کے آسان نفاذ کے طور پر استعمال کیا جا سکتا ہے۔ دوبارہ شروع کرنا کنورجنس کو سست کر سکتا ہے، لیکن استحکام کو بہتر بنا سکتا ہے اگر کنجوگیٹ گریڈینٹ طریقہ غلط سلوک کرتا ہے، مثال کے طور پر، راؤنڈ آف غلطی کی وجہ سے۔ واضح بقایا حساب فارمولے اور، جو دونوں عین حساب میں رکھتے ہیں، فارمولوں اور ریاضیاتی طور پر مساوی بناتے ہیں۔ سابقہ کو الگورتھم میں اضافی ضرب سے بچنے کے لیے استعمال کیا جاتا ہے کیونکہ ویکٹر کا اندازہ کرنے کے لیے پہلے ہی شمار کیا جا چکا ہوتا ہے۔ مؤخر الذکر زیادہ درست ہو سکتا ہے، جس میں مضمر کے لیے واضح حساب کو راؤنڈ آف ایرر جمع کرنے کے تابع ریکرشن کے ذریعے تبدیل کیا جاتا ہے، اور اس طرح کبھی کبھار تشخیص کے لیے تجویز کیا جاتا ہے۔ بقایا کا ایک معیار عام طور پر معیار کو روکنے کے لیے استعمال ہوتا ہے۔ واضح بقایا کا معیار درست ریاضی اور گول غلطیوں کی موجودگی دونوں میں درستگی کی ایک ضمانت شدہ سطح فراہم کرتا ہے، جہاں کنورجنس قدرتی طور پر جمود کا شکار ہوتی ہے۔ اس کے برعکس، مضمر بقایا گول غلطیوں کی سطح سے نیچے طول و عرض میں چھوٹا ہوتا رہتا ہے اور اس طرح کنورجنس کے جمود کا تعین کرنے کے لیے استعمال نہیں کیا جا سکتا۔ الفا اور بیٹا کی گنتی الگورتھم میں، اس طرح کا انتخاب کیا جاتا ہے جو اس کے لیے آرتھوگنل ہو۔ تب سے ڈینومینیٹر کو آسان بنایا گیا ہے۔ اس کا انتخاب اس طرح کیا جاتا ہے جو اس سے منسلک ہوتا ہے۔ ابتدائی طور پر، استعمال کر رہا ہے اور مساوی طور پر کے عدد کو اس لیے دوبارہ لکھا جاتا ہے کیونکہ اور ڈیزائن کے لحاظ سے آرتھوگنل ہوتے ہیں۔ ڈینومینیٹر کو اس طرح دوبارہ لکھا جاتا ہے کہ تلاش کی سمتوں pk کو مربوط کیا جاتا ہے اور پھر یہ کہ بقایا آرتھوگنل ہیں۔ یہ منسوخ کرنے کے بعد الگورتھم میں دیتا ہے۔ جولیا (پروگرامنگ زبان) میں مثال کوڈ "" "کنجوگیٹ _ گریڈیئنٹ! (A, b, x) کنجوگیٹ گریڈینٹ طریقہ استعمال کرتے ہوئے حل کو 'A * x = b' پر واپس کریں۔ فنکشن کنجوگیٹ _ گریڈیئنٹ! (اے:: خلاصہ میٹرکس، بی:: خلاصہ ویکٹر، ایکس:: خلاصہ ویکٹر ؛ ٹول = ای پی ایس (ایل ٹائپ (بی))) #بقایا ویکٹر بقایا کو شروع کریں = بی-اے * ایکس #تلاش کی سمت ویکٹر تلاش کی سمت کو شروع کریں = بقایا #ابتدائی مربع بقایا معیار پرانے _ مربع _ بقایا _ معیار = بقایا '* بقایا #متغیر تک کنورجنس جبکہ پرانا _ مربع _ بقایا _ معیار> ٹول اے _ سرچ _ سمت = اے * سرچ _ سمت مرحلہ _ سائز = پرانا _ مربع _ بقایا _ معیار 2/(تلاش _ سمت' * اے _ سرچ _ سمت) #اپ ڈیٹ حل @ x = x + قدم _ سائز * تلاش _ سمت #بقایا @کو اپ ڈیٹ کریں۔ بقایا = بقایا-مرحلہ _ سائز * A _ تلاش _ سمت نیا _ sqr _ بقایا _ معیار = ڈاٹ (بقایا، بقایا) #تلاش کی سمت ویکٹر کو اپ ڈیٹ کریں @۔ سرچ _ ڈائرکشن = بقایا + (نیا _ sqr _ ریسائڈ _ نارم/پرانا _ sqr _ ریسائڈ _ نارم) ^ 2 * سرچ _ ڈائرکشن #اگلی تکرار کے لیے مربع بقایا معیار کو اپ ڈیٹ کریں پرانا _ sqr _ ریسائڈ _ نارم = نیا _ sqr _ ریسائڈ _ نارم اینڈ ریٹرن x اینڈ عددی مثال لکیری سسٹم Ax = b پر غور کریں جس کے ذریعے ہم نظام کا تخمینہ حل تلاش کرنے کے لیے ابتدائی اندازے سے شروع ہونے والے کنجوگیٹ گریڈینٹ طریقہ کے دو مراحل انجام دیں گے۔ حل حوالہ کے لیے، صحیح حل یہ ہے کہ ہمارا پہلا قدم x0 سے وابستہ بقایا ویکٹر r0 کا حساب لگانا ہے۔ یہ بقایا فارمولا r0 = b-Ax0 سے شمار کیا جاتا ہے، اور ہمارے معاملے میں اس کے برابر ہے۔ چونکہ یہ پہلی تکرار ہے، ہم بقایا ویکٹر r0 کو اپنی ابتدائی تلاش کی سمت p0 کے طور پر استعمال کریں گے۔ pk کو منتخب کرنے کا طریقہ مزید تکرار میں تبدیل ہو جائے گا۔ اب ہم اس رشتے کا استعمال کرتے ہوئے اسکیلر کا حساب لگاتے ہیں۔ اب ہم فارمولہ کا استعمال کرتے ہوئے x1 کا حساب لگا سکتے ہیں۔ یہ نتیجہ پہلی تکرار کو مکمل کرتا ہے، جس کا نتیجہ نظام کا "بہتر" تخمینہ حل ہوتا ہے، x1۔ اب ہم آگے بڑھ سکتے ہیں اور فارمولے کا استعمال کرتے ہوئے اگلے بقایا ویکٹر r1 کا حساب لگا سکتے ہیں۔ اس عمل میں ہمارا اگلا مرحلہ اسکیلر کا حساب لگانا ہے جو بالآخر اگلی تلاش کی سمت p1 کا تعین کرنے کے لیے استعمال ہوگا۔ اب، اس اسکیلر کا استعمال کرتے ہوئے، ہم اس رشتے کا استعمال کرتے ہوئے اگلی تلاش کی سمت p1 کا حساب لگا سکتے ہیں۔ اب ہم اپنے نئے حاصل کردہ p1 کا استعمال کرتے ہوئے اسی طریقہ کا استعمال کرتے ہوئے اسکیلر کا حساب لگاتے ہیں جس کے لیے استعمال کیا گیا تھا۔ آخر میں، ہم x2 کو اسی طریقہ کا استعمال کرتے ہوئے تلاش کرتے ہیں جو x1 کو تلاش کرنے کے لیے استعمال ہوتا تھا۔ نتیجہ، x2، x1 اور x0 کے مقابلے میں نظام کے حل کا "بہتر" تخمینہ ہے۔ اگر اس مثال میں محدود درستگی کے بجائے عین حساب کا استعمال کیا جائے، تو نظریاتی طور پر عین حل n = 2 تکرار کے بعد پہنچ جاتا (n نظام کی ترتیب ہے)۔ کنورجنس کی خصوصیات کنجوگیٹ گریڈینٹ طریقہ کو نظریاتی طور پر ایک براہ راست طریقہ کے طور پر دیکھا جا سکتا ہے، کیونکہ راؤنڈ آف ایرر کی عدم موجودگی میں یہ ایک محدود تعداد میں تکرار کے بعد درست حل پیدا کرتا ہے، جو میٹرکس کے سائز سے بڑا نہیں ہوتا ہے۔ عملی طور پر، عین مطابق حل کبھی حاصل نہیں کیا جاتا ہے کیونکہ کنجوگیٹ گریڈینٹ طریقہ یہاں تک کہ چھوٹی پریشانیوں کے حوالے سے غیر مستحکم ہے، مثال کے طور پر، کریلوف سب اسپیس پیدا کرنے کی انحطاطی نوعیت کی وجہ سے زیادہ تر سمتیں عملی طور پر کنجوگیٹ نہیں ہوتی ہیں۔ ایک تکراری طریقہ کے طور پر، کنجوگیٹ گریڈینٹ طریقہ یکسانیت سے (توانائی کے معیار میں) عین حل کے تخمینوں کو بہتر بناتا ہے اور تکرار کی نسبتا کم (مسئلہ کے سائز کے مقابلے میں) تعداد کے بعد مطلوبہ رواداری تک پہنچ سکتا ہے۔ بہتری عام طور پر لکیری ہوتی ہے اور اس کی رفتار کا تعین سسٹم میٹرکس کے کنڈیشن نمبر سے ہوتا ہے: بہتری جتنی بڑی ہوگی، اتنی ہی سست ہوگی۔ اگر بڑا ہے، تو پری کنڈیشننگ عام طور پر اصل نظام کو اس سے چھوٹا تبدیل کرنے کے لیے استعمال کیا جاتا ہے، نیچے دیکھیں۔ کنورجنس تھیوریم کثیر الجہتی کے ذیلی سیٹ کی وضاحت کریں جہاں زیادہ سے زیادہ ڈگری کے کثیر الجہتی کا سیٹ ہے۔ عین مطابق حل کے تکراری تخمینے ہونے دیں، اور غلطیوں کی وضاحت اس طرح کریں۔ اب، کنورجنس کی شرح کا تخمینہ لگایا جا سکتا ہے جہاں سپیکٹرم کی نشاندہی ہوتی ہے، اور کنڈیشن نمبر کی نشاندہی ہوتی ہے۔ نوٹ کریں، اہم حد جب اس حد کی طرف مائل ہوتی ہے تو یہ حد جیکوبی یا گاؤس سیڈل کے تکراری طریقوں کے مقابلے میں تیز ارتکاز کی شرح کو ظاہر کرتی ہے جو اس کے پیمانے پر ہے۔ کنورجنس تھیوریم میں کوئی راؤنڈ آف ایرر نہیں فرض کی گئی ہے، لیکن کنورجنس باؤنڈ عام طور پر عملی طور پر درست ہے جیسا کہ نظریاتی طور پر این گرین بوم نے وضاحت کی ہے۔ عملی کنورجنس اگر تصادفی طور پر شروع کیا جائے تو، تکرار کا پہلا مرحلہ اکثر تیز ترین ہوتا ہے، کیونکہ کریلوف سب اسپیس کے اندر غلطی ختم ہو جاتی ہے جو ابتدائی طور پر ایک چھوٹے موثر کنڈیشن نمبر کی عکاسی کرتی ہے۔ کنورجنس کے دوسرے مرحلے کو عام طور پر نظریاتی کنورجنس کے ساتھ اچھی طرح سے بیان کیا جاتا ہے، لیکن میٹرکس کے سپیکٹرم کی تقسیم اور غلطی کی سپیکٹرم کی تقسیم کے لحاظ سے یہ انتہائی لکیری ہو سکتا ہے۔ آخری مرحلے میں، سب سے چھوٹی قابل حصول درستگی تک پہنچ جاتی ہے اور کنورجنس اسٹال یا طریقہ کار بھی موڑنا شروع کر سکتا ہے۔ بڑے سائز کے میٹرکس کے لیے ڈبل صحت سے متعلق فلوٹنگ پوائنٹ فارمیٹ میں عام سائنسی کمپیوٹنگ ایپلی کیشنز میں، کنجوگیٹ گریڈینٹ طریقہ رواداری کے ساتھ رکنے کے معیار کا استعمال کرتا ہے جو پہلے یا دوسرے مرحلے کے دوران تکرار کو ختم کرتا ہے۔ پری کنڈیشنڈ کنجوگیٹ گریڈینٹ طریقہ زیادہ تر معاملات میں، کنجوگیٹ گریڈینٹ طریقہ کے تیز ارتکاز کو یقینی بنانے کے لیے پری کنڈیشننگ ضروری ہے۔ اگر سمیٹرک مثبت-ڈیفائنٹ ہے اور اس سے بہتر کنڈیشن نمبر ہے، تو ایک پری کنڈیشنڈ کنجوگیٹ گریڈینٹ طریقہ استعمال کیا جا سکتا ہے۔ یہ مندرجہ ذیل شکل اختیار کرتا ہے: دہرائیں اگر rk + 1 کافی چھوٹا ہے تو ایگزٹ لوپ ختم ہو جاتا ہے اگر آخر میں دہرایا جاتا ہے۔ نتیجہ xk + 1 ہے۔ مندرجہ بالا تشکیل پہلے سے طے شدہ نظام پر باقاعدہ کنجوگیٹ گریڈینٹ طریقہ کو لاگو کرنے کے مترادف ہے جہاں نظام کی ہم آہنگی (اور مثبت تعریف) کو برقرار رکھنے کے لیے پری کنڈیشنر کا چولسکی سڑنا استعمال کیا جانا چاہیے۔ تاہم، اس سڑنے کا حساب لگانے کی ضرورت نہیں ہے، اور یہ جاننا کافی ہے۔ یہ دکھایا جا سکتا ہے کہ اس کا سپیکٹرم ویسا ہی ہے جیسا کہ۔ پری کنڈیشنر میٹرکس M کو سمیٹرک مثبت-یقینی اور فکسڈ ہونا چاہیے، یعنی، تکرار سے تکرار میں تبدیل نہیں ہو سکتا۔ اگر پری کنڈیشنر پر ان میں سے کسی بھی مفروضے کی خلاف ورزی کی جاتی ہے، تو پری کنڈیشنڈ کنجوگیٹ گریڈینٹ طریقہ کار کا طرز عمل غیر متوقع ہو سکتا ہے۔ عام طور پر استعمال ہونے والے پری کنڈیشنر کی ایک مثال نامکمل چولسکی فیکٹرائزیشن ہے۔ لچکدار پری کنڈیشنڈ کنجوگیٹ گریڈینٹ طریقہ عددی طور پر چیلنجنگ ایپلی کیشنز میں، نفیس پری کنڈیشنرز استعمال کیے جاتے ہیں، جو تکرار کے درمیان بدلتے ہوئے متغیر پری کنڈیشننگ کا باعث بن سکتے ہیں۔ یہاں تک کہ اگر پری کنڈیشنر ہر تکرار پر سمیٹرک مثبت-یقینی ہے، تو یہ حقیقت کہ یہ تبدیل ہو سکتا ہے اوپر کے دلائل کو غلط بنا دیتا ہے، اور عملی ٹیسٹوں میں اوپر پیش کردہ الگورتھم کے کنورجنس کی نمایاں سست روی کا باعث بنتا ہے۔ فلیچر-ریوز فارمولے کے بجائے پولک-ربیر فارمولے کا استعمال اس معاملے میں کنورجنس کو ڈرامائی طور پر بہتر بنا سکتا ہے۔ پری کنڈیشنڈ کنجوگیٹ گریڈینٹ طریقہ کار کے اس ورژن کو لچکدار کہا جا سکتا ہے، کیونکہ یہ متغیر پری کنڈیشننگ کی اجازت دیتا ہے۔ لچکدار ورژن بھی مضبوط دکھایا گیا ہے یہاں تک کہ اگر پری کنڈیشنر سمیٹرک مثبت ڈیفینیٹ (ایس پی ڈی) نہیں ہے۔ لچکدار ورژن کے نفاذ کے لیے ایک اضافی ویکٹر کو ذخیرہ کرنے کی ضرورت ہوتی ہے۔ ایک فکسڈ ایس پی ڈی پری کنڈیشنر کے لیے، اس لیے دونوں فارمولے عین حساب میں مساوی ہیں، یعنی راؤنڈ آف ایرر کے بغیر۔ پولک-ربیر فارمولے کے ساتھ طریقہ کار کے بہتر کنورجنس رویے کی ریاضیاتی وضاحت یہ ہے کہ یہ طریقہ اس معاملے میں مقامی طور پر بہترین ہے، خاص طور پر، یہ مقامی طور پر بہترین اسٹپیسٹ نزول کے طریقہ سے آہستہ نہیں ملتا ہے۔ بمقابلہ مقامی طور پر زیادہ سے زیادہ سیدھا نزول کا طریقہ اصل اور قبل از وقت کنجوگیٹ گریڈینٹ دونوں طریقوں میں لائن سرچ، سب سے زیادہ سیدھا نزول کے طریقوں کا استعمال کرتے ہوئے انہیں مقامی طور پر زیادہ سے زیادہ بہتر بنانے کے لیے صرف سیٹ کرنے کی ضرورت ہوتی ہے۔ اس متبادل کے ساتھ، ویکٹر ہمیشہ ویکٹر کی طرح ہوتے ہیں، اس لیے ویکٹر کو ذخیرہ کرنے کی ضرورت نہیں ہے۔ اس طرح، ان تیز ترین نزول کے طریقوں کی ہر تکرار کنجوگیٹ گریڈینٹ طریقوں کے مقابلے میں تھوڑی سستی ہے۔ تاہم، مؤخر الذکر تیزی سے یکجا ہوتا ہے، جب تک کہ (انتہائی) متغیر اور/یا غیر ایس پی ڈی پری کنڈیشنر استعمال نہ کیا جائے، اوپر دیکھیں۔ ڈبل انٹیگریٹر کے لیے بہترین فیڈ بیک کنٹرولر کے طور پر کنجوگیٹ گریڈیئنٹ طریقہ کنجوگیٹ گریڈیئنٹ طریقہ بھی بہترین کنٹرول تھیوری کا استعمال کرتے ہوئے اخذ کیا جا سکتا ہے۔ اس نقطہ نظر میں، کنجوگیٹ گریڈینٹ طریقہ ایک بہترین فیڈ بیک کنٹرولر کے طور پر سامنے آتا ہے، ڈبل انٹیگریٹر سسٹم کے لیے، مقدار اور متغیر فیڈ بیک فوائد ہیں۔ عام مساوات پر کنجوگیٹ گریڈیئنٹ کنجوگیٹ گریڈیئنٹ طریقہ کار کو عام مساوات اے ٹی اے اور رائٹ ہینڈ سائیڈ ویکٹر اے ٹی بی پر لاگو کرکے صوابدیدی این-بائی-ایم میٹرکس پر لاگو کیا جا سکتا ہے، کیونکہ اے ٹی اے کسی بھی اے کے لیے ایک سمیٹرک مثبت-سیمیڈفائنٹ میٹرکس ہے۔ نتیجہ عام مساوات (سی جی این آر) پر کنجوگیٹ گریڈیئنٹ ہے۔ اے ٹی اے ایکس = اے ٹی بی ایک تکراری طریقہ کے طور پر، میموری میں واضح طور پر اے ٹی اے بنانا ضروری نہیں ہے بلکہ صرف میٹرکس ویکٹر انجام دینے اور میٹرکس ویکٹر ضرب کو منتقل کرنے کے لیے ضروری ہے۔ لہذا، سی جی این آر خاص طور پر مفید ہوتا ہے جب اے ایک غیر معمولی میٹرکس ہوتا ہے کیونکہ یہ کارروائیاں عام طور پر انتہائی موثر ہوتی ہیں۔ تاہم نارمل مساوات بنانے کا منفی پہلو یہ ہے کہ کنڈیشن نمبر κ (ATA) κ2 (A) کے برابر ہے اور اس لیے CGNR کے کنورجنس کی شرح سست ہو سکتی ہے اور لگ بھگ حل کا معیار راؤنڈ آف کی غلطیوں کے لیے حساس ہو سکتا ہے۔ ایک اچھا پری کنڈیشنر تلاش کرنا اکثر سی جی این آر طریقہ استعمال کرنے کا ایک اہم حصہ ہوتا ہے۔ کئی الگورتھم تجویز کیے گئے ہیں (مثال کے طور پر سی جی ایل ایس، ایل ایس کیو آر)۔ ایل ایس کیو آر الگورتھم میں واضح طور پر بہترین عددی استحکام ہوتا ہے جب اے غیر مشروط ہوتا ہے، یعنی اے کا ایک بڑا کنڈیشن نمبر ہوتا ہے۔ پیچیدہ ہرمیٹین میٹرکس کے لیے کنجوگیٹ گریڈینٹ طریقہ ایک معمولی ترمیم کے ساتھ کنجوگیٹ گریڈینٹ طریقہ حل کرنے کے لیے قابل توسیع ہے، پیچیدہ قیمت والے میٹرکس A اور ویکٹر b کو دیکھتے ہوئے، پیچیدہ قیمت والے ویکٹر x کے لیے لکیری مساوات کا نظام، جہاں A ہرمیٹین (یعنی، A '= A) اور مثبت-یقینی میٹرکس ہے، اور علامت' کنجوگیٹ ٹرانسپوز کی نشاندہی کرتی ہے۔ معمولی ترمیم صرف ہر جگہ حقیقی ٹرانسپوز کے لیے کنجوگیٹ ٹرانسپوز کو تبدیل کرنا ہے۔ یہ بھی دیکھیں کہ بائیکونجوگیٹ گریڈینٹ میتھڈ (بی آئی سی جی) کنجوگیٹ گریڈینٹ اسکوائرڈ میتھڈ (سی جی ایس) کنجوگیٹ بقایا طریقہ گاؤسیائی عقیدے کی تشہیر تکراری طریقہ: لکیری سسٹم کریلوف سب اسپیس نان لائنر کنجوگیٹ گریڈینٹ میتھڈ پری کنڈیشنگ اسپارس میٹرکس ویکٹر ضرب حوالہ جات مزید پڑھنے کے لیے جیرارڈ میورینٹ: "کنجوگیٹ گریڈینٹ الگورتھم میں خاموش غلطیوں کا پتہ لگانا اور ان کی اصلاح"، عددی الگورتھم، vol.92 (2023)، pp.869-891۔ یو آر ایل = https://doi.org/10.1007/s11075-022-01380-1 بیرونی روابط عددی لکیری الجبرا گریڈینٹ طریقے مضامین مثال کے طور پر میٹ لیب/آکٹیو کوڈ