or second stage. The preconditioned conjugate gradient method In most cases, preconditioning is necessary to ensure fast convergence of the conjugate gradient method. If is symmetric positive-definite and has a better condition number than , a preconditioned conjugate gradient method can be used. It takes the following form: repeat if rk+1 is sufficiently small then exit loop end if end repeat The result is xk+1 The above formulation is equivalent to applying the regular conjugate gradient method to the preconditioned system where The Cholesky decomposition of the preconditioner must be used to keep the symmetry (and positive definiteness) of the system. However, this decomposition does not need to be computed, and it is sufficient to know . It can be shown that has the same spectrum as . The preconditioner matrix M has to be symmetric positive-definite and fixed, i.e., cannot change from iteration to iteration. If any of these assumptions on the preconditioner is violated, the behavior of the preconditioned conjugate gradient method may become unpredictable. An example of a commonly used preconditioner is the incomplete Cholesky factorization. The flexible preconditioned conjugate gradient method In numerically challenging applications, sophisticated preconditioners are used, which may lead to variable preconditioning, changing between iterations. Even if the preconditioner is symmetric positive-definite on every iteration, the fact that it may change makes the arguments above invalid, and in practical tests leads to a significant slow down of the convergence of the algorithm presented above. Using the Polak–Ribière formula instead of the Fletcher–Reeves formula may dramatically improve the convergence in this case. This version of the preconditioned conjugate gradient method can be called flexible, as it allows for variable preconditioning. The flexible version is also shown to be robust even if the preconditioner is not symmetric positive definite (SPD). The implementation of the flexible version requires storing an extra vector. For a fixed SPD preconditioner, so both formulas for are equivalent in exact arithmetic, i.e., without the round-off error. The mathematical explanation of the better convergence behavior of the method with the Polak–Ribière formula is that the method is locally optimal in this case, in particular, it does not converge slower than the locally optimal steepest descent method. Vs. the locally optimal steepest descent method In both the original and the preconditioned conjugate gradient methods one only needs to set in order to make them locally optimal, using the line search, steepest descent methods.