Derivation of the conjugate gradient method
عددی لکیری الجبرا میں، کنجوگیٹ گریڈیئنٹ طریقہ عددی طور پر لکیری نظام کو حل کرنے کے لیے ایک تکراری طریقہ ہے جہاں سمیٹرک مثبت-یقینی ہے۔ کنجوگیٹ گریڈینٹ طریقہ کئی مختلف نقطہ نظر سے اخذ کیا جا سکتا ہے، بشمول اصلاح کے لیے کنجوگیٹ سمت کے طریقہ کار کی تخصص، اور آئجین ویلیو کے مسائل کے لیے آرنلڈی/لینکزوس تکرار کی تغیر۔ اس مضمون کا مقصد ان مشتقات میں اہم اقدامات کو دستاویز کرنا ہے۔ کنجوگیٹ سمت کے طریقہ کار سے ماخوذ کنجوگیٹ گریڈینٹ طریقہ کو کنجوگیٹ سمت کے طریقہ کار کے ایک خاص معاملے کے طور پر دیکھا جا سکتا ہے جس کا اطلاق کواڈریٹک فنکشن کو کم سے کم کرنے کے لیے کیا جاتا ہے۔ کنجوگیٹ سمت کا طریقہ کنجوگیٹ سمت کے طریقہ کار میں کسی کو کم کرنے کے لیے ابتدائی اندازے اور متعلقہ بقایا سے شروع ہوتا ہے، اور فارمولوں کے ذریعے تکرار اور بقایا کا حساب لگاتا ہے جہاں باہمی طور پر مربوط سمتوں کا ایک سلسلہ ہوتا ہے، یعنی کسی کے لیے۔ کنجوگیٹ ڈائرکشن کا طریقہ اس لحاظ سے غیر واضح ہے کہ سمتوں کے انتخاب کے لیے کوئی فارمولا نہیں دیا گیا ہے۔ مخصوص انتخاب مختلف طریقوں کا باعث بنتے ہیں جن میں کنجوگیٹ گریڈینٹ طریقہ اور گوسیائی خاتمہ شامل ہیں۔ آرنلڈی/لینکزوس تکرار سے ماخوذ کنجوگیٹ گریڈینٹ طریقہ کو آرنلڈی/لینکزوس تکرار کی ایک قسم کے طور پر بھی دیکھا جا سکتا ہے جو لکیری نظاموں کو حل کرنے کے لیے لاگو ہوتا ہے۔ عام آرنلڈی طریقہ آرنلڈی تکرار میں، ایک ویکٹر سے شروع ہوتا ہے اور آہستہ آہستہ کریلوف سب اسپیس کی ایک آرتھونورمل بنیاد بناتا ہے جس کی وضاحت کرتے ہوئے کہ دوسرے الفاظ میں، کے لیے، گرام-شمڈٹ آرتھوگنالائزنگ کے خلاف اس کے بعد نارملائزیشن کے ذریعے پایا جاتا ہے۔ میٹرکس کی شکل میں ڈالیں تو، تکرار کو مساوات کے ذریعے پکڑا جاتا ہے جہاں لکیری سسٹمز کو حل کرنے کے لیے آرنلڈی تکرار کا اطلاق کرتے وقت، ایک ابتدائی اندازے کے مطابق بقایا کے ساتھ شروع ہوتا ہے۔ تکرار کے ہر مرحلے کے بعد، ایک حساب لگاتا ہے اور نیا تکرار کرتا ہے۔ براہ راست لینکزوس طریقہ باقی بحث کے لیے، ہم فرض کرتے ہیں کہ یہ ہم آہنگ مثبت-یقینی ہے۔ کی ہم آہنگی کے ساتھ، اوپری ہیسنبرگ میٹرکس ہم آہنگ ہو جاتا ہے اور اس طرح سہ رخی ہو جاتا ہے۔ اس کے بعد اسے مزید واضح طور پر اس کے ذریعے ظاہر کیا جا سکتا ہے۔ یہ تکرار میں ایک مختصر تین مدتی تکرار کو قابل بناتا ہے، اور آرنلڈی تکرار کو لینکزوس تکرار تک کم کر دیا جاتا ہے۔ چونکہ ہم آہنگی مثبت-یقینی ہے، اسی طرح ہے۔ لہذا، LU کو فیکٹرائز کیا جا سکتا ہے جس میں جزوی محور کے بغیر آسان تکرار کے ساتھ اور: جیسا کہ دوبارہ لکھیں۔ اب یہ مشاہدہ کرنا ضروری ہے کہ درحقیقت، اس کے لیے مختصر تکرار بھی ہیں: اس تشکیل کے ساتھ، ہم اس کے لیے ایک سادہ تکرار پر پہنچتے ہیں: اوپر کے تعلقات براہ راست لینکزوس طریقہ کار کی طرف لے جاتے ہیں، جو قدرے زیادہ پیچیدہ ثابت ہوتا ہے۔ آرتھوگونالیٹی اور کنجوگیسی کو مسلط کرنے سے کنجوگیٹ گریڈینٹ کا طریقہ اگر ہم مستقل عنصر میں اسکیلنگ کو پیمانے اور معاوضہ دینے کی اجازت دیتے ہیں، تو ہم ممکنہ طور پر شکل کے آسان تکرار حاصل کر سکتے ہیں: آسان بنانے کے لیے احاطے کے طور پر، اب ہم آرتھوگونالیٹی اور کنجوگیسی حاصل کرتے ہیں، یعنی، کے لیے، بقایا باہمی طور پر آرتھوگونل ہیں کیونکہ بنیادی طور پر اس کے بعد سے ایک ملٹیپل ہے، کیونکہ، اس کی کنجوگیسی کو دیکھنے کے لیے، یہ ظاہر کرنے کے لیے کافی ہے کہ یہ ڈائیگنل ہے: سمٹرک اور نچلا مثلث بیک وقت ہے اور اس طرح اسے ڈائیگنل ہونا چاہیے۔ اب ہم مستقل عوامل کو حاصل کر سکتے ہیں اور پیمانے کے حوالے سے صرف کی آرتھوگونالیٹی اور کنجگسی کو مسلط کر کے۔ کی آرتھوگونالیٹی کی وجہ سے، یہ ضروری ہے کہ۔ نتیجے کے طور پر، اسی طرح، کے امتزاج کی وجہ سے، یہ ضروری ہے کہ۔ نتیجے کے طور پر، یہ مشتق کو مکمل کرتا ہے۔ حوالہ جات عددی لکیری الجبرا آپٹیمائزیشن الگورتھم اور طریقے گریڈینٹ طریقے ثبوت پر مشتمل مضامین