A Completed Theory of the Unsymmetric Lanczos Process and Related Algorithms. Part II

作     者：Martin H. Gutknecht 

出 版 物：《SIAM Journal on Matrix Analysis and Applications》 

年 卷 期：1994年第15卷第1期

页      面：15-58页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：65F10 30E05 41A21 65F15 Lanczos algorithm biconjugate gradient algorithm BIOMIN BIODIR breakdown formal orthogonal polynomial recurrence Padé approximation staircase quotient difference algorithm qd algorithm 

摘      要：This paper is a continuation of Part I [M. H. Gutknecht, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 594–639], where the theory of the “unsymmetric Lanczos biorthogonalization (BO) algorithm and the corresponding iterative method BIORES for non-Hermitian linear systems was extended to the nongeneric case. The analogous extension is obtained here for the biconjugate gradient (or BIOMIN) method and for the related BIODIR method. Here, too, the breakdowns of these methods can be cured. As a preparation, mixed recurrence formulas are derived for a pair of sequences of formal orthogonal polynomials belonging to two adjacent diagonals in a nonnormal Padé table, and a matrix interpretation of these recurrences is developed. This matrix interpretation leads directly to a completed formulation of the progressive qd algorithm, valid also in the case of a nonnormal Padé table. Finally, it is shown how the cure for exact breakdown can be extended to near-breakdown in such a way that (in exact arithmetic) the well-conditioned formal orthogonal polynomials and the corresponding Krylov space vectors do not depend on the threshold specifying the near-breakdown.