روش گرادیان مزدوج (Conjugate Gradient Method)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش گرادیان مزدوج (Conjugate Gradient Method) :
برای حل
\[ Ax = b \]با A متقارن مثبت معین
توضیح ساده: روش گرادیان مزدوج یک روش تکراری بسیار هوشمندانه برای حل دستگاه های خطی با ماتریس های متقارن و مثبت معین است. این روش ترکیبی از ایده های بهینه سازی و جبر خطی است. تصور کنید می خواهیم به پایین ترین نقطه یک دره برسیم. روش گرادیان کاهشی (بعدا توضیح داده می شود) مستقیم به سمت پایین ترین شیب حرکت می کند، اما ممکن است زیگزاگ کند. روش گرادیان مزدوج جهت های حرکت را طوری انتخاب می کند که هر جهت با جهت های قبلی "مزدوج" باشد، یعنی در مسیر درست حرکت کرده و مستقیما به جواب برسیم.
شرح گام به گام: با یک حدس اولیه x₀ شروع می کنیم. جهت جستجوی اولیه را برابر با باقیمانده (r₀ = b - Ax₀) قرار می دهیم. در هر تکرار، یک گام بهینه در جهت فعلی برمی داریم تا تابع f(x) = ½ xᵀAx - bᵀx را کمینه کنیم. سپس جهت جدید را طوری محاسبه می کنیم که نسبت به همه جهت های قبلی A-مزدوج باشد (یعنی d_iᵀ A d_j = 0 برای i≠j). این خاصیت باعث می شود روش در نهایت (حداکثر بعد از n تکرار) به جواب دقیق برسد، اما در عمل به دلیل خطای گرد کردن ممکن است به تکرار بیشتری نیاز باشد.
مثال عددی: دستگاه ساده ۲×۲:
\[ A = \begin{bmatrix} 3 & 1 \\ 1 & 2 \end{bmatrix}, \quad b = \begin{bmatrix} 5 \\ 5 \end{bmatrix} \]جواب دقیق x = [1, 2]ᵀ است. با x₀ = [0,0]ᵀ شروع می کنیم. r₀ = [5,5]ᵀ، d₀ = r₀. α₀ = (r₀ᵀr₀)/(d₀ᵀAd₀) = (25+25)/( (5,5)ᵀA(5,5) ) = 50/(5*3*5 + 2*5*1*5 + ...) = 50/ (75+20+20)?? بهتر است دقیق محاسبه کنیم: d₀ᵀAd₀ = [5,5] * ( [3*5+1*5, 1*5+2*5] ) = [5,5] * [20,15] = 5*20+5*15=100+75=175. پس α₀ = 50/175 = 2/7 ≈ 0.2857. x₁ = x₀ + α₀ d₀ = [0,0] + 0.2857*[5,5] = [1.4285, 1.4285]. r₁ = r₀ - α₀ A d₀ = [5,5] - 0.2857*[20,15] = [5-5.714, 5-4.2855] = [-0.714, 0.7145]. β₁ = (r₁ᵀr₁)/(r₀ᵀr₀) = (0.51+0.51)/50 ≈ 1.02/50=0.0204. d₁ = r₁ + β₁ d₀ = [-0.714,0.7145] + 0.0204*[5,5] = [-0.714+0.102, 0.7145+0.102] = [-0.612, 0.8165]. تکرار بعدی به جواب نزدیک می شود.
مزایا: همگرایی سریع (برای ماتریس های خوش حالت)، حافظه کم (فقط چند بردار ذخیره می کند)، مناسب برای ماتریس های بزرگ و تنک.
معایب: فقط برای ماتریس های متقارن مثبت معین کاربرد دارد. برای ماتریس های بدحالت ممکن است کند شود.
کاربردها: در روش عناصر محدود، در بهینه سازی، در یادگیری ماشین، در حل مسائل بزرگ مقیاس.
نکته: این روش توسط هستینگز و استیفل در دهه ۱۹۵۰ برای حل مسائل مهندسی توسعه یافت و یکی از مهم ترین پیشرفت ها در آنالیز عددی است.
