The conjugate gradient method on the normal equations applies the conjugate gradient method to a symmetric definite system obtained from a nonsymmetric or indefinite system. The CGNE and CGNR methods are variants of this approach. Since other methods for such systems are in general rather more complicated, transforming the system and then applying the conjugate gradient method is attractive for its coding simplicity.
CGNE solves the system
 |
(1)
|
for 
and then computes the solution
 |
(2)
|
CGNR solves
 |
(3)
|
for the solution vector 
, where
 |
(4)
|
If a system of linear equations 
has a nonsymmetric, possibly indefinite (but nonsingular)
coefficient matrix, one obvious attempt at a solution is to apply the conjugate
gradient method to a related symmetric positive definite system 
. While this approach is easy to understand and code,
the convergence speed of the conjugate gradient method now depends on the square
of the condition number of the original coefficient matrix. Thus the rate of convergence
of the conjugate gradient procedure on the normal equations may be slow.
Several proposals have been made to improve the numerical stability of this method. The best known is by Paige and Saunders (1982) and is based upon applying the Lanczos method to the auxiliary system
![[I A; A^T 0][r; x]=[b; 0].](/images/equations/ConjugateGradientMethodontheNormalEquations/NumberedEquation5.svg) |
(5)
|
A clever execution of this scheme delivers the factors 
and 
of the LU decomposition
of the tridiagonal matrix that would have been
computed by carrying out the Lanczos procedure with 
.
Another means for improving the numerical stability of this normal equations approach is suggested by Björck and Elfving (1979). The observation that the matrix 
is used in the construction of the iteration coefficients through an inner product
like 
leads to the suggestion that such an inner product
be replaced by 
.
