### review of CG method:I

#### by Yi Zhang

Most popular method in solving linear system, conjugate gradient is simply a few connected elegant ideas whose geometric meanning is almost intuitive. In solving system

where is SPD matrix, it is obvious that the solution of the equation is equal to the minimizer of quadratic form

If the positive definite condition is removed, then solution of is simply one stationary point of .

Pictures below show 3D plot of a quadratic form and its contour with minus gradient . In order to solve the linear system, one need find the minimizer, and in turn** steepest descent method** is the way to follow the direction of arrow in the picture and move toward the goal, in another word, like a ball sliding on the 3D paraboloid toward the lowest point. For iteration algorithm, we obtain point in the domian by , where is the descent direction at point

and is the distance to move toward that direction, which is determined by maximizing the “profit” in present step, i.e. to move to the lowest value of in direction of . This can be achieved, intuitively, move to the “most inner” contour in that direction. Now one can see by “most inner” I mean when the contour is tangential to vector line of . One corollary of this method is that in next step we are going to move perpendicular to the direction of last move:

Another view to see this is that by “maximizing profit” we mean to minimize the value of at present step, so we are looking for step size satisfying

By this we can obtain , and algorithm of steepest descent:

[…] of unstationary methods can be formed by the solving a minimization problem. Classical CG method I wrote about before belongs to this family. Tagged with: algorithm, linear algebra, numerical leave a comment […]