Editing Conjugate gradient method (section)

==Conjugate gradient on the normal equations==

The conjugate gradient method can be applied to an arbitrary ''n''-by-''m'' matrix by applying it to [[normal equations]] '''A'''<sup>T</sup>'''A''' and right-hand side vector '''A'''<sup>T</sup>'''b''', since  '''A'''<sup>T</sup>'''A''' is a symmetric [[Positive-definite matrix#Negative-definite.2C semidefinite and indefinite matrices|positive-semidefinite]] matrix for any '''A'''. The result is '''conjugate gradient on the normal equations''' ('''CGN''' or '''CGNR''').

: '''A'''<sup>T</sup>'''Ax''' =  '''A'''<sup>T</sup>'''b'''

As an iterative method, it is not necessary to form  '''A'''<sup>T</sup>'''A''' explicitly in memory but only to perform the matrix–vector and transpose matrix–vector multiplications. Therefore, CGNR is particularly useful when ''A'' is a [[sparse matrix]] since these operations are usually extremely efficient. However the downside of forming the normal equations is that the [[condition number]] κ('''A'''<sup>T</sup>'''A''') is equal to κ<sup>2</sup>('''A''') and so the rate of convergence of CGNR may be slow and the quality of the approximate solution may be sensitive to roundoff errors. Finding a good [[preconditioner]] is often an important part of using the CGNR method.

Several algorithms have been proposed (e.g., CGLS, LSQR). The [https://web.stanford.edu/group/SOL/software/lsqr/   LSQR] algorithm purportedly has the best numerical stability when '''A''' is ill-conditioned, i.e., '''A''' has a large [[condition number]].