Iterative Methods for Nearly Singular Linear Systems
William W. Hager · SIAM Journal on Scientific Computing · 2000
Iterative methods are developed and studied for near-singular linear systems Cx = b. Our approach, called the transformed minimal residual algorithm (TMRES), is derived from any convergent iterative scheme Sx k+1 = Tx k + b associated with a splitting C = S - T. In each step of TMRES, the transformed residual S -1 (b- Cx) is minimized over a Krylov space generated by S -1 T . The original iterative scheme typically converges slowly when C is nearly singular, while a Krylov space generated by S -1 T often contains a much better approximation to a solution. TMRES is algebraically equivalent to the generalized minimal residual algorithm (GMRES) preconditioned by S -1 , although there are numerical differences since a different matrix S -1 C is used to generate the Krylov space in preconditioned GMRES. Special attention is given to sparsity and convergence issues related to linear systems of the form $({\bf AA}\tr + \sigma{\bf I}){\bf x} =$ ${\bf b}$, where $\sigma \ge 0$.