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+1p_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_jp_j^T (p_j,M^TMp_j)g_j = _j=1^n-1 p_jp_j^T (p_j,M^TMp_j)M^Tt for this scheme. The resulting approximate inverse operator is therefore
(M^TM)^ _j=1^n-1 p_jp_j^T (p_j,M^TMp_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^TM)^ P_nD_P^-1P_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^TM^TMP_n, because of the conjugacy of the 's composing .Now equation (pn) shows that
P_nB_n = G_n, where
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^TM)^ G_nB_n^-1D_P^-1(B_n^T)^-1G_n^T. Thus, the approximate inverse is seen to have the general form
(M^TM)^ G_nT_n^-1G_n^T, where is the tridiagonal matrix
T_n = B_n^TD_PB_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.