A Convergence Analysis of Gmres and Fom Methods for Sylvester Equations

Numerical Algorithms - 2002
Mickaël Robbé1, Miloud Sadkane2
1Free Field Technologies, Louvain-la-Neuve, Belgium
2Département de Mathématiques, Université de Bretagne Occidentale, Brest Cedex, France

Tóm tắt

We discuss convergence properties of the GMRES and FOM methods for solving large Sylvester equations of the form AX−XB=C. In particular we show the importance of the separation between the fields of values of A and B on the convergence behavior of GMRES. We also discuss the stagnation phenomenon in GMRES and its consequence on FOM. We generalize the issue of breakdown in the block-Arnoldi algorithm and explain its consequence on FOM and GMRES methods. Several numerical tests illustrate the theoretical results.

Từ khóa


Tài liệu tham khảo

R. Bartels and G.W. Stewart, Algorithm 432: Solution of the matrix equation AX + XB = C, Comm. ACM 15 (1972) 820-826.

A. Björck, Numerical Methods for Least Squares Problems (SIAM, Philadelphia, PA, 1996).

D. Calvetti, B. Lewis and L. Reichel, On the solution of large Sylvester-obesrver equations, Numer. Linear Algebra Appl. 8 (2001) 435-451.

B. Datta, Numerical linear algebra in control theory, Linear Algebra Appl. 198 (1994) 755-790.

B. Datta and Y. Saad, Arnoldi methods for large Sylvester-like observer matrix equations, and an associated algorithm for partial spectrum assignment, Linear Algebra Appl. 154-156 (1991) 225-244.

M. Eiermann, Fields of values and iterative methods, Linear Algebra Appl. 180 (1993) 167-197.

A. El Guennouni, K. Jbilou and J. Riquet, Block Krylov subspace methods for solving large Sylvester equations, Preprint LMPA, No. 132 (2000), Université du Littoral, to appear in Numer. Algorithms.

G.H. Golub, S. Nash and C. Van Loan, A Hessenberg-Schur method for the problem AX+XB = C, IEEE Trans. Automat. Control 24 (1979) 909-913.

G.H. Golub and C.F. Van Loan, Matrix Computation, 2nd edn (Johns Hopkins Univ. Press, Baltimore, MD, 1989).

D.Y. Hu and L. Reichel, Krylov subspace methods for the Sylvester equations, Linear Algebra Appl. 174 (1992) 283-314.

I.M. Jaimoukha and E.M. Kasenally, Krylov subspace method for solving large Lyapunov equation, SIAM J. Numer. Anal. 31 (1994) 227-251.

M. Robbé and M. Sadkane, Breakdown and stagnation in block FOM and block GMRES methods, Manuscript (2001).

Y. Saad, Numerical solution of large Lyapunov equation, in: Signal Processing, Scattering, Operator Theory and Numerical Methods (Birkhäuser, Boston, 1990) pp. 503-511.

Y. Saad, Iterative Methods for Sparse Linear Systems (PWS, Boston, 1996).

Y. Saad and M.H. Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput. 7 (1986) 856-869.

M. Sadkane, A block Arnoldi-Chebyshev method for computing the leading eigenpairs of large sparse unsymmetric matrices, Numer. Math. 64 (1993) 181-193.

V. Simoncini, On the numerical solution of AX - XB = C, BIT 36 (1996) 814-830.

G. Stewart and J. Sun, Matrix Perturbation Theory (Academic Press, San Diego, CA, 1990).

Thông tin
Thông tin xuất bản

Numerical Algorithms

Thông tin tác giả