Iterative computation of the smallest singular value and the corresponding singular vectors of a matrix

Influenced by some techniques used, for computing singular points of nonlinear equations, a generalized inverse iteration method is proposed for approximating the smallest singular value a, and the associated left and right singular vectors u, v of a matrix A E R-nxn. In the practically relevant case sigma(n) > 0 the method is mathematically equivalent to inverse iteralion with AA(T). However, unlike classic inverse iteration, the new method works with matrices B-k is an element of R(n+1)x(n+1) obtained by bordering A in such a way that the Bk have uniformly bounded condition numbers. This allows using iterative Krylov-type solvers for large problems. If sigma(n-1) > sigma(n) the singular vector approximations convergence linearly with factor K sigma(n)/sigma(n-1) < 1. Moreover, a certain generalized Rayleigh quotient sigma((k)) obtained as a byproduct has a relative error (sigma((k)) - sigma(n))/sigma(n) which goes to zero R-linearly with factor kappa(2). Some numerical examples confirm the theoretical results and show that the algorithm works reliable also for almost singular matrices and when using Krylov solvers. (C) 2003 Elsevier Inc. All rights reserved.