Analysis of the convergence of the minimal and the orthogonal residual methods
Tóm tắt
We consider two Krylov subspace methods for solving linear systems, which are the minimal residual method and the orthogonal residual method. These two methods are studied without referring to any particular implementations. By using the Petrov–Galerkin condition, we describe the residual norms of these two methods in terms of Krylov vectors, and the relationship between there two norms. We define the Ritz singular values, and prove that the convergence of these two methods is governed by the convergence of the Ritz singular values.
Tài liệu tham khảo
P.N. Brown, A theoretical comparison of the Arnoldi and the GMRES algorithms, SIAM J. Sci. Statist. Comput. 12 (1991) 58–78.
J. Cullum and A. Greenbaum, Relations between Galerkin and norm-minimizing iterative methods for solving linear systems, SIAM J. Matrix Anal. Appl. 17 (1996) 223–248.
S.C. Eisenstat, H.C. Elman and M.H. Schultz, Variational iterative methods for nonsymmetric systems of linear equations, SIAM J. Numer. Anal. 20 (1983) 345–357.
H.C. Elman, Iterative methods for large sparse nonsymmetric systems of linear equations, Ph.D. thesis, Computer Science Department, Yale University, New Haven, CT (1982).
F.R. Gantmacher, The Theory of Matrices, Vol. 1 (Chelsea, New York, 1959).
A. Greenbaum and L.N. Trefethen, GMRES/CR and ARNOLDI/LANCZOS as matrix approximation problems, SIAM J. Sci. Statist. Comput. 15 (1994) 357–368.
M.R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards 49 (1952) 409–436.
G. Golub and C.F. van Loan, Matrix Computations, 2nd ed. (Johns Hopkins Univ. Press, Baltimore, MD, 1989).
Y. Huang and H.A. van der Vorst, Some observations on the convergence behaviour of GMRES, Delft University of Technology, Report 89–09 (1989).
T. Huckle, The Arnoldi method for normal matrices, SIAM J. Matrix Anal. Appl. 15 (1994) 479–489.
K. Jbilou and H. Sadok, Analysis of some vector extrapolation methods for solving systems of linear equations, Numer. Math. 70 (1995) 73–89.
N.M. Nachtigal, S.C. Reddy and L.N. Trefethen, How fast are nonsymmetric matrix iterations, SIAM J. Matrix Anal. Appl. 13 (1992) 778–795.
C.C. Paige, B.N. Parlett and H.A. van der Vorst, Approximate solutions and eigenvalue bounds from Krylov subspaces, Numer. Linear Algebra Appl. 2 (1995) 115–134.
C.C. Paige and M.A. Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal. 12 (1975) 617–629.
Y. Saad, Variations on Arnoldi's method for computing eigenelements of large unsymmetric, Linear Algebra Appl. 34 (1980) 269–295.
Y. Saad, Krylov subspace methods for solving large unsymmetric linear systems, Math. Comp. 37 (1981) 105–126.
Y. Saad and M.H. Schultz, Conjugate gradient-like algorithms for solving nonsymmetric linear systems, Math. Comp. 44 (1985) 417–424.
Y. Saad and M.H. Schultz, GMRES: a generalized minimal residual algorithm for solving non-symmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986) 856–869.
G.W. Stewart and J.G. Sun, Matrix Perturbation Theory (Academic Press, New York, 1990).
R.C. Thompson, Principal submatrices IX: interlacing inequalities for singular values of submatrices, Linear Algebra Appl. 5 (1972) 1–12.
A. van der Sluis and H.A. van der Vorst, The rate of convergence of conjugate gradients, Numer. Math. 48 (1986) 543–560.
H.A. van der Vorst and C. Vuik, The rate of convergence of the GMRES method, J. Comput. Appl. Math. 48 (1993) 327–341.