Conjugate Gradient Step Explained with Worked Examples
In the conjugate gradient method for Ax=b (with A symmetric positive definite) the step length along the search direction pk is αk=pkTApkrkTrk, where rk=b−Axk is the residual.
The method minimises 21xTAx−bTx by moving along directions that are conjugate (orthogonal in the A-inner product). The first step is the same as steepest descent: p0=r0=b−Ax0. For A=(4113), b=(1,2), x0=0: r0=(1,2), Ap0=(6,7), p0TAp0=20, r0Tr0=5, so α0=0.25 and x1=(0.25,0.5).
In exact arithmetic the method reaches the exact solution in at most n steps for an n×n matrix; for a 1×1 system 5x=10, α0=10⋅5⋅10100=0.2 and x1=2 at once. For a diagonal matrix diag(2,4) and b=(2,4): α0=7220=0.2778. The products use matrix multiplication and the scalar product.
The convergence rate depends on the condition number of A, and the method is far faster than gradient descent for large sparse systems, which are also treated by Jacobi and Gauss–Seidel iterations. Newton-type methods are in Newton's method for optimisation. The slow rate of plain gradient descent that this method avoids is analysed in the gradient descent rate.
What is it used for?
The conjugate gradient method solves large linear systems with one step size per direction, which is the exact minimum along that line.