next up previous
Next: Computational Environments Up: The CSI-MSVD Algorithm Previous: Singular Vector Calculation

3.5 Error Estimation for Singular Triplets

  As the Chebyshev semi-iterative method proceeds, iterates of the form

are generated. Approximations to the left singular vector corresponding to the largest singular value are generated by the sequence , while the corresponding right singular vector is approximated by the sequence . An estimate of the error in these singular vector approximations is desired. Let

 

and consider the error vectors defined by

 

These vectors measure the error in the singular vector approximations but do not reflect the error in the singular triplet, i.e., and . The vectors and are generated as part of the solution of the system of equations defined by Equation (4) with b=0 and is approximating the singular value of A (now scaled by ) closest to 1.

The vectors and are generated by substituting m=k+1 in Equation (26) and m=k+2 in Equation (27) (with ) to obtain

 

 

Hence, the quantity is calculated as an intermediate result in the calculation of , and can be calculated at step k+2.

An analogous result for is harder to derive since the right multiplication of is by which is calculated in Equation (33) (rather than ). Consider the intermediate product

From Equation (31), and so

 

Since by definition, it follows that . Substituting this expression for into Equation (35) yields

 

where , , and hence is a perturbation of a vector in the desired direction . If this perturbation is suitably small, i.e. 0, then may be approximated (see [22]) by

 

where is the normalized version of . A pseudo-code for the two-pass CSI-MSVD algorithm to approximate singular values and corresponding singular vectors with implicit error estimation is provided in Figures 4 and 5.

  
Figure 4: Pseudo-code for one PASS of the CSI-MSVD algorithm.

    

 
Figure 5: Pseudo-code for two-pass CSI-MSVD algorithm with implicit error estimation. 



next up previous
Next: Computational Environments Up: The CSI-MSVD Algorithm Previous: Singular Vector Calculation



Michael W. Berry (berry@cs.utk.edu)
Sun May 19 11:34:27 EDT 1996