روش گرادیان مزدوج:
روش گرادیان مزدوج، یک روش تکراری برای حل دستگاه معادلات خطی $Ax=b$ می‌باشد که در آن $A$ ماتریسی $n\times n$ متقارن و معین مثبت است. به سادگی دیده می‌شود که حل دستگاه فوق، هم‌ارز با حل مسئله‌ی بهینه‌سازی درجه دوم زیر است:
$$\min f\left( x \right)=\frac{1}{2}{{x}^{t}}Ax-{{b}^{t}}x$$
این هم‌ارزی موجب می‌شود که روش گرادیان مزدوج به‌عنوان روشی برای یافتن کمینه‌ی توابع محدب درجه دوم مورد استفاده قرار گیرد. البته همانند بخش قبل می‌توان آن را برای توابع غیر درجه دوم نیز به‌کار برد. توجه کنید که: $$\nabla f\left( x \right)=Ax-b=r\left( x \right).$$ از آن‌جا که روش گرادیان مزدوج، بر پایه‌ی جهت‌های مزدوج بنا شده است، بنابراین ابتدا شرح مختصری از جهت‌های مزدوج می‌آوریم.
تعریف: فرض کنید $A$ یک ماتریس متقارن باشد. بردارهای ${{p}_{1}}$ و ${{p}_{2}}$ را $A$-متعامد یا مزدوج نسبت به $A$ می‌نامیم هرگاه $p_{1}^{t}A{{p}_{2}}=0$. یک مجموعه‌ی متناهی از بردارها مانند $\left\{ {{p}_{1}},{{p}_{2}},\ldots ,{{p}_{l}} \right\}$ را یک مجموعه‌ی $A$-متعامد یا مزدوج نسبت به $A$ می‌نامیم هرگاه به‌ازای هر $i\ne j$ داشته باشیم $p_{i}^{t}A{{p}_{j}}=0$.
مثال: بردارهای ${{p}_{1}}=\left(\begin{matrix}-7\\4\\\end{matrix}\right)$ و ${{p}_{2}}=\left(\begin{matrix}5\\-2 \\\end{matrix} \right)$ نسبت به ماتریس $A=\left( \begin{matrix}2 & 3\\ 3 & 4 \\\end{matrix} \right)$ مزدوج هستند. اگر $A=0$ آن‌گاه هر دو بردار دلخواه، مزدوج هستند و اگر $A=I$ آن‌گاه بردارهای مزدوج بر هم عمودند.
قضیه: فرض کنید $A$ یک ماتریس معین مثبت باشد. اگر مجموعه بردارهای ناصفر $\left\{ {{p}_{1}},{{p}_{2}},\ldots ,{{p}_{l}} \right\}$ ،$A$-متعامد باشند، آن‌گاه این بردارها مستقل خطی هستند.
اثبات: فرض کنید ثابت‌های ${{\lambda }_{1}},{{\lambda }_{2}},\ldots ,{{\lambda }_{l}}$ موجود باشند به‌طوری که:\[{{\lambda }_{1}}{{p}_{1}}+{{\lambda }_{2}}{{p}_{2}}+\ldots+{{\lambda }_{l}}{{p}_{l}}=0\]
چون برای $i\ne j$ ، $p_{i}^{t}A{{p}_{j}}=0$ ، پس با ضرب رابطه‌ی فوق در $A$ و تشکیل ضرب داخلی با ${{p}_{i}}$ داریم ${{\lambda }_{i}}p_{i}^{t}A{{p}_{i}}=0$ و از آن‌جا که $A$ معین مثبت است، پس ${{\lambda }_{i}}=0$.
در ادامه، روش جهت‌های مزدوج را بیان می‌کنیم. این روش به‌خوبی اهمیت جهت‌های مزدوج را نشان می‌دهد.
