From (iterationons), it follows easily that the model estimate at the
*n*-th iteration must be of the form

**s**_n = _i=1^n-1 _i+1**p**_i,
where we assume for simplicity that .Then substituting (optimumalpha) -- or more directly the first ratio
in (cgalpha) -- for the 's shows that
the *n*-th iterate is given explicitly by

**s**_n = _j=1^n-1 **p**_j**p**_j^T
(**p**_j,**M**^T**Mp**_j)**g**_j =
_j=1^n-1 **p**_j**p**_j^T
(**p**_j,**M**^T**Mp**_j)**M**^T**t**
for this scheme. The resulting approximate inverse operator is therefore

(**M**^T**M**)^
_j=1^n-1 **p**_j**p**_j^T
(**p**_j,**M**^T**Mp**_j),
which form we now want to study. We use the dagger notation to indicate
that the expression in (inversionop) is approximating a
pseudoinverse, because it may happen that the normal matrix is singular
in which case the standard inverse does not exist.

First, note that although (inversionop) might appear to be in
the form of a singular value decomposition, it definitely is not.
The 's are not orthogonal and the
denominators of these terms are not eigenvalues.
If we define the matrix composed of direction
vectors at the *n*-th iteration to be

**P**_n = **p**_1 & **p**_2 & & **p**_n ,
then the approximate inverse operator can be rewritten as

(**M**^T**M**)^
**P**_n**D_P**^-1**P**_n^T,
where the matrix is a diagonal matrix whose diagonal elements are
given by .In fact the entire matrix is given directly by

**D_P** **P**_n^T**M**^T**MP**_n,
because of the conjugacy of the 's composing .Now equation (pn) shows that

**G**_n = **g**_1 & **g**_2 & & **g**_n ,
and the matrix is bidiagonal with units along the main diagonal
and 's along the upper diagonal:

**B**_n = [

]
Multiplying
(PBG) on the right by the inverse of and then
substituting into (inverse2), we find that

(**M**^T**M**)^
**G**_n**B**_n^-1**D_P**^-1(**B**_n^T)^-1**G**_n^T.
Thus, the approximate inverse is seen to have the general form

(**M**^T**M**)^
**G**_n**T**_n^-1**G**_n^T,
where is the tridiagonal matrix

**T**_n = **B**_n^T**D_P****B**_n.
This result highlights the similarities between the CG method
and that of other iterative methods
such as Lanczos 1950 and LSQR Paige and Saunders (1982),
also producing tridiagonal respresentations of the matrix
to be inverted.

11/11/1997