Numerical stability of the Richardson second order method

• Autorzy: Smoktunowicz A. , Wróbel I.
• Języki publikacji: EN

Abstrakty

EN

In this paper we study numerical properties of the Richardson second order method (RS) for solving a linear system Ax = b, where A € Rnxn is infinitysymmetric and positive definite. We consider the standard model of floating point arithmetic (cf. [6], [7], [11]). We prove that the RS-algorithm is numerically stable. This means that the algorithm computes approximations xk to the exact solution x* = A-1b such that the error limfk||xk - x*ll2 ls of order eMcond(A), where eM is the machine precision and cond(A) = ||A || 2 ||A-1|| denotes the condition number of the matrix A.

Słowa kluczowe

EN

floating point arithmetic; round-off error analysis; condition number; Chebyshev polynomials; iterative methods

PL

arytmetyka zmiennopozycyjna; analiza błędów; metoda iteracyjna; wielomiany Chebyseva

• Wydawca: De Gruyter
• Czasopismo: Demonstratio Mathematica
• Rocznik: 2005
• Tom: Vol. 38, nr 1
• Strony: 255--263
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Smoktunowicz A.

• Faculty of Mathematics and Information Science, Warsaw University of Technology, Pl. Politechnki 1, 00-661 Warsaw, Poland

autor

Wróbel I.

• Faculty of Mathematics and Information Science, Warsaw University of Technology, Pl. Politechnki 1, 00-661 Warsaw, Poland

Bibliografia

• [1] D. K Faddeev and V. N. Faddeeva, Computational Methods in Linear Algebra, Freeman, San Francisco, 1963.
• [2] G. H. Golub and Ch. F. Van Loan, Matrix Computations, Third Edition, The Johns Hopkins University Press, Baltimore and London, 1996.
• [3] G. H. Golub and R. S. Varga, Chebyshev semiiterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods, Numer. Math. 3 (1961), 147-168.
• [4] G. H. Golub, Bounds for the round-off errors in the Richardson second-order method, BIT 2 (1962), 212-223.
• [5] G. H. Golub and M. L. Overton, The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems, Numer. Math. 53 (1988), 571-591.
• [6] M. L. Overton, Numerical computing with IEEE floating arithmetic, SIAM, Philadelphia, 2001.
• [7] D. Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys 23 (1) (1991), 5-48.
• [8] M. H. Gutknecht, The Chebyshev iteration revisited, Parallel Comput. 28 (2002), 263-283.
• [9] A. Smoktunowicz, Backward stability of Clenshaw's algorithm, BIT vol. 42, no. 3 (2002), 600-610.
• [10] G. Szegö, Orthogonal Polynomials, rev. ed. New York, 1959.
• [11] J. H. Wilkinson, Rounding errors in algebraic processes. Notes on Applied Science No. 32, Her Majesty's Stationary Office, London, 1963.