Conjugate gradient methods

Author: Alexandra Roberts, Anye Shi, Yue Sun (SYSEN6800 Fall 2021)

Introduction

The conjugate gradient method (CG) was originally invented to minimize a quadratic function:
$F({\textbf {x}})={\frac {1}{2}}{\textbf {x}}^{T}{\textbf {A}}{\textbf {x}}-{\textbf {b}}{\textbf {x}}$
where A is an n × n symmetric positive definite matrix, x and b are n × 1 vectors.
The solution to the minimization problem is equivalent to solving the linear system, i.e. determining x when $\nabla F(x)=0$
${\textbf {A}}{\textbf {x}}-{\textbf {b}}={\textbf {0}}$