5,321
edits
Numerical Optimization: Difference between revisions
→Conjugate Gradient Methods
| Line 49: | Line 49: | ||
==Conjugate Gradient Methods== | ==Conjugate Gradient Methods== | ||
The goal is to solve <math>Ax=b</math> or equivalently <math>\min \phi(x)</math> where <math>\phi(x)=(1/2)x^T A x - b^Tx</math> | The goal is to solve <math>Ax=b</math> or equivalently <math>\min \phi(x)</math> where <math>\phi(x)=(1/2)x^T A x - b^Tx</math><br>. | ||
The practical CG algorithm will converge in at most <math>n</math> steps. | |||
===Definitions=== | ===Definitions=== | ||
Vectors <math>\{p_i\}</math> are conjugate w.r.t SPD matrix <math>A</math> if <math>p_i^T A p_j = 0</math> for <math>i \neq j</math> | Vectors <math>\{p_i\}</math> are conjugate w.r.t SPD matrix <math>A</math> if <math>p_i^T A p_j = 0</math> for <math>i \neq j</math> | ||