×

Numerical accuracy of a certain class of iterative methods for solving linear system. (English) Zbl 1093.65035

Summary: One of the most important problems for solving the linear system \(Ax = b\), by using iterative methods, is to use a good stopping criterion and to determine the common significant digits between each corresponding components of computed solution and exact solution. In this paper, for a certain class of iterative methods, we propose a way to determine the number of common significant digits of \(x_{m}\) and \(x\), where \(x_{m}\) and \(x\) are the computed solution at iteration \(m\) and exact solution, respectively. By using the CADNA library which allows us to estimate the round-off error effect on any computed result, we also propose a good stopping criterion which is able to stop the process as soon as a satisfactory informatical solution is obtained. Numerical examples are used to show the good numerical properties.

MSC:

65F10 Iterative numerical methods for linear systems
65G50 Roundoff error

Software:

CADNA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chen, Tony F.; Vassilevski, Panayot S., A framework for block ILU fuctorizations using block-size reduction, Math. Comput., 64, 209, 129-156 (1995) · Zbl 0819.65018
[2] Chesneaux, J. M., Modélisation et conditions de validité de la méthode CESTAC, C.R. Acad. Sci., Paris, sér., 1, 307, 417-422 (1988) · Zbl 0661.65045
[3] J.M. Chesneaux, Etude théorique et implémentation en ADA de la méthode CESTAC, Thesis, Université P. et M. Curie, Paris, 1988.; J.M. Chesneaux, Etude théorique et implémentation en ADA de la méthode CESTAC, Thesis, Université P. et M. Curie, Paris, 1988.
[4] Chesneaux, J. M., Study of the computing accuracy by using probabilistic approach, (Ulrich, C., Contribution to Computer Arithmetic and Self Validating Numerical Methods (1990), IMACS: IMACS New Brunswick, NJ), 19-30 · Zbl 0784.65037
[5] J.M. Chesneaux, CADNA, An ADA tool for round-off error analysis and for numerical debugging, in: Proceeding Congress on ADA in Aerospace, Barcelona, 1990.; J.M. Chesneaux, CADNA, An ADA tool for round-off error analysis and for numerical debugging, in: Proceeding Congress on ADA in Aerospace, Barcelona, 1990.
[6] J.M. Chesneaux, Descriptif d’utilisation du logiciel CADNA-F, MASI Report No. 92.32, 1992.; J.M. Chesneaux, Descriptif d’utilisation du logiciel CADNA-F, MASI Report No. 92.32, 1992.
[7] Chesneaux, J. M.; Jezequel, F., Dynamical Control of Computations Using the Trapezodial and Simpson’s rules, J.U.C.S., 4, 2-10 (1998) · Zbl 0967.68175
[8] Chesneaux, J. M.; Vignes, J., Sur la robustesse de la méthode CESTAC, C.R. Acad. Sci. Paris, Sér. I, Math., 307, 855-860 (1988) · Zbl 0657.65061
[9] Chesneaux, J. M.; Vignes, J., Les fondements de l’arithmt´ique stochastique, C.R. Acad. Sci. Paris Sér. I Math., 315, 1435-1440 (1992) · Zbl 0778.65035
[10] Feldstein, A.; Goodman, R., Convergence estimates for distribution of trailing digits, J. ACM, 23, 287-297 (1976) · Zbl 0324.65019
[11] Hamming, R. W., On the distribution of numbers, Bell Syst. Tech. J., 9, 1609-1625 (1970) · Zbl 0211.46701
[12] Hull, T. E.; Swenson, J. R., Test of probabilistic models for propagation of round-off errors, Commun. ACM, 9 (1966) · Zbl 0158.15302
[13] Knuth, D. E., The Art of Computer Programming, vol. 2 (1969), Addison-Wesley: Addison-Wesley Reading · Zbl 0191.17903
[14] Kuczyński, J.; Woźniakowski, H., Probabilistic bounds on the extremal eigenvalues and condition number by the Lanczos algorithm, SIAM J. Matrix Anal. Appl., 15, 672-691 (1994) · Zbl 0801.65034
[15] Meier, U.; Sameh, A., The behavior of conjugate gradiant algorithms on a multivector processor with a hierarchical memory, J. Comput. Appl. Math., 24, 13-32 (1988) · Zbl 0738.65027
[16] Saad, Y., Iterative Methods for Sparse Linear System (1996), PWS Publishing Company: PWS Publishing Company Boston
[17] Van Dorsselaer, Jos L. M.; Hochstenbach, Michiel E.; Van Der Vorst, Henk A., Computing probabilistic bounds for extreme eigenvalues of symmetric matrices with the lanczos method, SIAM J. Matrix Anal. Appl., 22, 3, 837-852 (2000) · Zbl 0981.65044
[18] Vignes, J.; La Porte, M., Algorithmes Numériques, Analyse et Mise en Oeuvre, vols. 1 and 2 (1980), Edition Technip: Edition Technip Paris
[19] Vignes, J.; La Porte, M., Error analysis in computing, (Information Processing, 74 (1974), North-Holand) · Zbl 0295.65035
[20] Vignes, J., New methods for evaluating the validity of the results of mathematical computation, Math. Comp. Simul., 20, 221-249 (1978) · Zbl 0437.65041
[21] La Vie des Sciences, 4, 1, 1-13 (1987) · Zbl 0631.65044
[22] Vignes, J., Estimation de la précison des résultats de logiciels numériques, La Vie des Sciences, Comptes Rendus, série générale, 7, 93-115 (1990) · Zbl 0705.65035
[23] Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Oxford University Press: Oxford University Press Oxford · Zbl 0258.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.