Conjugate Gradient

Motivation

Solve large systems of linear equations

where $x$ is an unknown vector, $b$ is a known vector, and $A$ is a known, square, symmetric, positive-definite (or positive-indefinite) matrix.

Why symmetric and Why positive

In short, if $A$ is symmetric and positive-definite, a quadratic function is minimized by the solution to $Ax=b$ .

This linear system problem can be transfer to an optimization problem

1. We have a quadratic function of vector $x$$$f(x)=\frac{1}{2}{x}^{T}Ax-b^{T}x+c$$

1. Gradient of $f^{\prime }(x)$ is$$f^{\prime }(x)=\frac{1}{2}{A}^{T}x+\frac{1}{2}Ax-b$$
2. If $A$ is symmetric$$f^{\prime }(x)=Ax-b$$Therefore, $Ax=b$ is critical point of $f(x)$. ($f^{\prime }(x)=0$)
3. If $A$ is positive-define, that is for every nonzero vector $x$, $x^{T}Ax>0$, $f(x)$ is an increasing function and $Ax=b$ can be solved by finding an $x$ that minimizes $f(x)$.

CG -- The Method of Steepest Descent

CG -- The Method of Conjugate Directions

The Method of Conjugate Gradients

High level idea

In CG -- The Method of Conjugate Directions we can set $u_i=r_i$.

Reason

Compute \beta

We don't need to memory all previous vectors like CG -- Gram-Schmidt Conjugation#Difficulties.

CG procedure

HPCG (Understand the preconditioned conjugate gradient method )