Conjugate Gradient


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 xf(x)=12xTAxbTx+c
  1. Gradient of f(x) isf(x)=12ATx+12Axb
  2. If A is symmetricf(x)=AxbTherefore, Ax=b is critical point of f(x). (f(x)=0)
  3. If A is positive-define, that is for every nonzero vector x, xTAx>0, f(x) is an increasing function and Ax=b can be solved by finding an x that minimizes f(x).

Different Situations w.r.t. positive or not
![Pasted image 20221225214120.png](/img/user/attachment/Pasted image 20221225214120.png)

Final procedure

![Pasted image 20221225220257.png](/img/user/attachment/Pasted image 20221225220257.png)

The Method of Conjugate Gradients

High level idea

In CG -- The Method of Conjugate Directions we can set ui=ri.


Pasted image 20230102165650.png
Pasted image 20230102165728.png
Pasted image 20230102170903.png

Compute \beta

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

CG procedure

Pasted image 20230102171046.png

HPCG (Understand the preconditioned conjugate gradient method )