Editing Conjugate gradient method (section)

==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 [[nonlinear conjugate gradient method|Polak–Ribière]] formula

:<math>\beta_k := \frac{\mathbf{r}_{k+1}^\mathsf{T} \left(\mathbf{z}_{k+1}-\mathbf{z}_{k}\right)}{\mathbf{r}_k^\mathsf{T} \mathbf{z}_k}</math>

instead of the [[nonlinear conjugate gradient method|Fletcher–Reeves]] formula

:<math>\beta_k := \frac{\mathbf{r}_{k+1}^\mathsf{T} \mathbf{z}_{k+1}}{\mathbf{r}_k^\mathsf{T} \mathbf{z}_k}</math>

may dramatically improve the convergence in this case.<ref>{{cite journal |doi=10.1137/S1064827597323415 |title=Inexact Preconditioned Conjugate Gradient Method with Inner-Outer Iteration |year=1999 |last1=Golub |first1=Gene H. |last2=Ye |first2=Qiang |journal=SIAM Journal on Scientific Computing |volume=21 |issue=4 |page=1305|citeseerx=10.1.1.56.1755 }}</ref> This version of the preconditioned conjugate gradient method can be called<ref>{{cite journal|doi=10.1137/S1064827599362314|title=Flexible Conjugate Gradients|year=2000|last1=Notay|first1=Yvan|journal=SIAM Journal on Scientific Computing|volume=22|issue=4|pages=1444–1460|citeseerx=10.1.1.35.7473}}</ref> '''flexible''', as it allows for variable preconditioning. 
The flexible version is also shown<ref>{{Cite journal|doi=10.1016/j.procs.2015.05.241|title=Nonsymmetric Preconditioning for Conjugate Gradient and Steepest Descent Methods 1|year=2015|last1=Bouwmeester|first1=Henricus|last2=Dougherty|first2=Andrew|last3=Knyazev|first3=Andrew V.|journal=Procedia Computer Science|volume=51|pages=276–285|s2cid=51978658|doi-access=free|arxiv=1212.6680}}</ref> 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, <math>\mathbf{r}_{k+1}^\mathsf{T} \mathbf{z}_{k}=0,</math> so both formulas for {{mvar|β<sub>k</sub>}} 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 [[nonlinear conjugate gradient method|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.<ref>{{cite journal|doi=10.1137/060675290|title=Steepest Descent and Conjugate Gradient Methods with Variable Preconditioning| year=2008| last1=Knyazev|first1=Andrew V.|last2=Lashuk|first2=Ilya|journal=SIAM Journal on Matrix Analysis and Applications|volume=29|issue=4|page=1267|arxiv=math/0605767|s2cid=17614913}}</ref>