The generalized Newton shift is a generalization of the Newton shift for computing the singular values of a bidiagonal matrix with the dqds or mdLVs algorithm and is defined as \(\left( \textrm{Tr}\left( \left( B^{(n)}\right) ^{\top } B^{(n)}\right) ^{-p}\right) ^{-1/p}\) , where \(B^{(n)}\) is the bidiagonal matrix at the n-th iteration and p is some positive integer. This quantity can be computed in O(pm) work, where m is the order of the matrix, and another \(O(p^2 m)\) subtraction-free algorithm is also available for higher accuracy. We analyze the asymptotic convergence property of the dqds algorithm with the generalized Newton shift and show that its order of convergence is \(p+1-\epsilon \) for any \(\epsilon >0\) . This result is confirmed by numerical experiments. Since the generalized Newton shift can achieve arbitrarily high order of convergence, it should be useful as a building block for constructing an efficient shifting strategy for the dqds algorithm.
