| Title:
|
Using successive approximations for improving the convergence of GMRES method (English) |
| Author:
|
Zítko, Jan |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
43 |
| Issue:
|
5 |
| Year:
|
1998 |
| Pages:
|
321-350 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
In this paper, our attention is concentrated on the GMRES method for the solution of the system $(I-T)x=b$ of linear algebraic equations with a nonsymmetric matrix. We perform $m$ pre-iterations $y_{l+1}=Ty_l+b $ before starting GMRES and put $y_m $ for the initial approximation in GMRES. We derive an upper estimate for the norm of the error vector in dependence on the $m$th powers of eigenvalues of the matrix $T$. Further we study under what eigenvalues lay-out this upper estimate is the best one. The estimate shows and numerical experiments verify that it is advisable to perform pre-iterations before starting GMRES as they require fewer arithmetic operations than GMRES. Towards the end of the paper we present a numerical experiment for a system obtained by the finite difference approximation of convection-diffusion equations. (English) |
| Keyword:
|
GMRES |
| Keyword:
|
iterative method |
| Keyword:
|
numerical experiments |
| Keyword:
|
solution of discretized equations |
| MSC:
|
65F10 |
| MSC:
|
65N22 |
| MSC:
|
65N35 |
| idZBL:
|
Zbl 0938.65060 |
| idMR:
|
MR1644136 |
| DOI:
|
10.1023/A:1022291601664 |
| . |
| Date available:
|
2009-09-22T17:58:35Z |
| Last updated:
|
2020-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134392 |
| . |
| Reference:
|
[A 87] O. Axelson: A generalized conjugate gradient, least square methods.Numer. Math. 51 (1987), 209–227. MR 0890033, 10.1007/BF01396750 |
| Reference:
|
[G-L] C. Brezinski, M.R. Zaglia: Extrapolation Methods—Theory and Practice.North Holland, 1991. MR 1140920 |
| Reference:
|
[E 82] H.C. Elman: Iterative Methods for Large Sparse Nonsymmetric Systems of Linear Equations.Ph. D. thesis, Computer Science Dept., Yale Univ., New Haven, CT, 1982. |
| Reference:
|
[G-L] G.H. Golub, Ch.F. Van Loan: Matrix Computation.The John Hopkins University Press, Baltimore, 1984. |
| Reference:
|
[F-F] D.K.Fadeev, V.N.Fadeeva:: Computational Methods of Linear Algebra.San Francisco: Freeman 1963. Zbl 0755.65029, MR 0158519 |
| Reference:
|
[F-G-N 91] R.W. Freund, G.H. Golub, N.M. Nachtigal: Iterative solution of linear systems.Acta Numerica (1991), 57–100. MR 1165723 |
| Reference:
|
[H-Y] L.A. Hageman, D.M. Young: Applied Iterative Method.New York, Academic Press, 1981. MR 0630192 |
| Reference:
|
[Ho] A.S. Householder: The Theory of Matrices in Numerical Analysis.Blaisdell Publishing Company, 1964. Zbl 0161.12101, MR 0175290 |
| Reference:
|
[J-Y] K.C. Jea, D.M. Young: Generalized conjugate gradient acceleration of nonsymmetrizable iterative methods.Linear Algebra Appl. 34 (1980), 159–194. MR 0591431, 10.1016/0024-3795(80)90165-2 |
| Reference:
|
[K-H] : Iterative Methods for Large Linear Systems.Papers from a conference held Oct. 19–21, 1988 at the Center for Numerical Analysis of the University of Texas at Austin, Edited by D.R. Kincaid, L.J. Hayes (eds.), Academic Press, 1989. Zbl 0703.68010, MR 1038083 |
| Reference:
|
[L 52] C. Lanczos: Solution of systems of linear equations by minimized iterations.J. Res. Nat. Bur. Stand. 49 (1952), 33–53. MR 0051583, 10.6028/jres.049.006 |
| Reference:
|
[O-R] J. M. Ortega, W. C. Rheinboldt: Iterative Solution of Nonlinear Equations in Several Variables.Academic Press, 1970. MR 0273810 |
| Reference:
|
[Sa 81] Y. Saad: Krylov subspace methods for solving large unsymmetric linear systems.Math Comput. 37 (1981), 105–126. Zbl 0474.65019, MR 0616364, 10.1090/S0025-5718-1981-0616364-6 |
| Reference:
|
[Sa 84] Y. Saad: Practical use of some Krylov subspace methods for solving indefinite and nonsymmetric linear systems.SIAM J. Sci. Stat. Comput. 5 (1984), 203–227. Zbl 0539.65012, MR 0731892, 10.1137/0905015 |
| Reference:
|
[S-S 86] Y. Saad, M.H. Schultz: GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems.SIAM J. Sci. Stat. Comput. 7 (1986), 856–869. MR 0848568, 10.1137/0907058 |
| Reference:
|
[Si-F-Sm] A. Sidi, W.F. Ford, D.A. Smith: Acceleration of convergence of vector sequences.SIAM J. Numer. Anal. 23 (1986), 178–196. MR 0821914, 10.1137/0723013 |
| Reference:
|
[Si 86] A. Sidi: Convergence and stability properties of minimal polynomial and reduced rank extrapolation algorithms.SIAM J. Numer. Anal. 23 (1986), 197–209. Zbl 0612.65001, MR 0821915, 10.1137/0723014 |
| Reference:
|
[Si 88] A. Sidi: Extrapolation vs. projection methods for linear systems of equations.J. Comput. Appl. Math. 22 (1988), 71–88. Zbl 0646.65031, MR 0948887, 10.1016/0377-0427(88)90289-0 |
| Reference:
|
[St 83] J. Stoer: Solution of large linear systems of equations by conjugate gradient type methods., Mathematical Programming—The State of the Art, A. Bachem, M. Grötschel and B. Korte (eds.), Springer (Berlin), 1983, pp. 540–565. Zbl 0553.65022, MR 0717414 |
| Reference:
|
[V] R.L. Varga: Matrix Iterative Analysis.Prentice-Hall Englewood Clifs, New Jersey, 1962. MR 0158502 |
| Reference:
|
[V-V 93] H.A. Van der Vorst, C. Vuik: The superlinear convergence behaviour of GMRES.J. Comput. Appl. Math. 48 (1993), 327–341. MR 1252545, 10.1016/0377-0427(93)90028-A |
| Reference:
|
[Y] D.M. Young: Iterative Solution of Large Linear Systems.Academic Press, New York-London, 1971. Zbl 0231.65034, MR 0305568 |
| Reference:
|
[W 81] J. Wimp: Sequence Transformations and their Aapplications.Academic Press, 1981. MR 0615250 |
| Reference:
|
[Zi 83] J. Zítko: Improving the convergence of iterative methods.Apl. Mat. 28 (1983), 215–229. MR 0701740 |
| Reference:
|
[Zi 84] J. Zítko: Convergence of extrapolation coefficients.Apl. Mat. 29 (1984), 114–133. MR 0738497 |
| Reference:
|
[Zi 94] J. Zítko: The behaviour of the error vector using the GMRES method.Technical report No 4/94, Prague, 1994, pp. 1–27. |
| Reference:
|
[Zi 96] J. Zítko: Combining the preconditioned conjugate gradient method and a matrix iterative method.Appl. Math. 41 (1996), 19–39. MR 1365137 |
| Reference:
|
[Zi1 96] J. Zítko: Combining the GMRES and a matrix iterative method.ZAMM (Proceedings of ICIAM/GAMM 95) Vol. 76, 1996, pp. 595–596. |
| Reference:
|
[Zi2 96] J. Zítko: Improving the convergence of GMRES using preconditioning and pre-iterations.Proceedings of the conference “Prague Mathematical Conference 1996”, 1996, pp. 377–382. |
| Reference:
|
[Zi 97] J. Zítko: Behaviour of GMRES iterations using preconditioning and pre-iterations.ZAMM (Proceedings of GAMM 96) Vol. 77, 1997, pp. 693–694. |
| . |
