may not need all of them to obtain a good approximation to the solution . So, we want to regard the conjugate gradient method as an iterative method. This also allows us to approximately solve systems where n is so large that the direct method would take too much time. We denote the initial guess for by (we can assume without loss of generality that , otherwise consider the system Az = b − Ax0 instead). Starting with x0 we search for the solution and in each iteration we need a metric to tell us whether we are closer to the solution (that is unknown to us). This metric comes from the fact that the solution is also the unique minimizer of the following quadratic function The existence of a unique minimizer is apparent as its Hessian matrix of second derivatives is symmetric positive-definite and that the minimizer (use Df(x)=0) solves the initial problem follows from its first derivative This suggests taking the first basis vector p0 to be the negative of the gradient of f at x = x0. The gradient of f equals . Starting with an initial guess x0, this means we take p0 = b − Ax0. The other vectors in the basis will be conjugate to the gradient, hence the name conjugate gradient method. Note that p0 is also the residual provided by this initial step of the algorithm. Let rk be the residual at the kth step: As observed above, is the negative gradient of at , so the gradient descent method would require to move in the direction rk. Here, however, we insist that the directions must be conjugate to each other. A practical way to enforce this is by requiring that the next search direction be built out of the current residual and all previous search directions. The conjugation constraint is an orthonormal-type constraint and hence the algorithm can be viewed as an example of Gram-Schmidt orthonormalization. This gives the following expression: (see the picture at the top of the article for the effect of the conjugacy constraint on convergence). Following this direction, the next optimal location is given by with where the last equality follows from the definition of . The expression for can be derived if one substitutes the expression for xk+1 into f and minimizing it with respect to The resulting algorithm The above algorithm gives the most straightforward