پیاده‌ سازی روش گرادیان مزدوج

چنان که در آموزش قبل گفته شد، روش گرادیان مزدوج یک روش تکراری برای حل دستگاه معادلات خطی $Ax=b$ می‌باشد که در آن $A$ ماتریسی $n\times n$ متقارن و معین مثبت است. همچنین این روش، روشی برای حل مسئله‌ی بهینه‌سازی درجه دوم زیر است:

$$\min f\left( x \right)=\frac{1}{2}{{x}^{t}}Ax-{{b}^{t}}x$$

در این‌جا، می‌خواهیم این روش را برای یک مسئله‌ی نمونه با استفاده از نرم‌افزار Matlab پیاده‌سازی کنیم.

دستگاه معادلات خطی زیر را در نظر می‌گیریم:

$$\begin{bmatrix}3 & 0&2&0&0 \\0 & 2&0&1&-1\\2&0&2&-1&0\\0&1&-1&3&-1\\0&-1&0&-1&1 \end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3\\x_4\\x_5 \end{bmatrix}=\begin{bmatrix}9\\3\\4\\6\\-1 \end{bmatrix}$$مسئله‎ی بهینه‌سازی نامقید متناظر، پنج متغیره و ضابطه‌ی تابع هدف آن، $f({{x}_{1}},{{x}_{2}},{{x}_{3}},{{x}_{4}},{{x}_{5}})$ ، بصورت زیر است:$$\frac{3}{2}x_1^2+x_2^2+x_3^2+\frac{3}{2}x_4^2+\frac{1}{2}x_5^2+2x_1x_3+x_2x_4-x_2x_5-x_3x_4-x_4x_5-9x_1-3x_2-4x_3-6x_4+x_5$$جواب دستگاه معادلات خطی بالا، مختصات نقطه‌ی کمینه‌ی این تابع را به دست می‌دهد.

به کمک روش گرادیان مزدوج، با نقطه‌ی شروع $x_0=(0,0,0,0,0)^t$، شرط توقف $\left \| \nabla f\left( {{x}^{k}} \right)\right \|<10^{-1}$ و پارامتر فلچر-ریوز این مسئله را حل می‌کنیم.

clear
clc
A=[3 0 2 0 0;
    0 2 0 1 -1;
    2 0 2 -1 0;
    0 1 -1 3 -1;
    0 -1 0 -1 1]
b=[9;3;4;6;-1]
x0=[0;0;0;0;0]
r0=A*x0-b;
p0=-r0;
k=0;
xk=x0;
rk=r0;
pk=p0;
iteration=0;
while norm(rk)>10^-1
    alphak=(rk'*rk)/(pk'*A*pk);
    xk=xk+alphak*pk
    rk1=rk+alphak*A*pk;
    betak1=(rk1'*rk1)/(rk'*rk);
    pk=-rk1+betak1*pk;
    rk=rk1;
    iteration=iteration+1;
end
disp('iteration='), disp(iteration)

با اجرای این برنامه ملاحظه می‌کنیم که جواب مسئله (دستگاه) عبارتست از $x^*=(x_1,x_2,x_3,x_4,x_5)^t=(1,2,3,4,5)^t$ و روش گرادیان مزدوج طی 5 گام به این جواب می‌رسد.