×

Forward error analysis of Gaussian elimination. I: Error and residual estimates. (English) Zbl 0554.65032

Part I of this work deals with the forward error analysis of Gaussian elimination for general linear algebraic systems. The error analysis is based on a linearization method which determines first order approximations of the absolute errors exactly. Superposition and cancellation of error effects, structure and sparsity of the coefficient matrices are completely taken into account by this method. The most important results of the paper are new condition numbers and associated optimal component-wise error and residual estimates for the solutions of linear algebraic systems under data perturbations and perturbations by rounding errors in the arithmetic floating-point operations. The estimate do not use vector or matrix norms. The relative data and rounding condition numbers as well as the associated backward and residual stability constants are scaling-invariant. The condition numbers can be computed approximately from the input data, the intermediate results, and the solution of the linear system. Numerical examples show that by these means realistic bounds of the errors and the residuals of approximate solutions can be obtained. Using the forward error analysis, also typical results of backward error analysis are deduced. Stability theorems and a priori error estimates for special classes of linear systems are proved in Part II of this work (reviewed below).

MSC:

65G50 Roundoff error
65F05 Direct numerical methods for linear systems and matrix inversion
65F35 Numerical computation of matrix norms, conditioning, scaling
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Forsythe, G.E., Moler, C.B.: Computer solution of linear algebraic systems. Englewood Cliffs: Prentice Hall 1967 · Zbl 0154.40401
[2] Sautter, W.: Fehleranalyse f?r die Gau?-Elimination zur Berechnung der L?sung minimaler L?nge. Numer. Math.30, 165-184 (1978) · Zbl 0425.65024 · doi:10.1007/BF02042943
[3] Stummel, F.: Rounding error analysis of elementary numerical algorithms. Fundamentals of numerical computation (Proc. Conf., Berlin, 1979). Computing (Suppl.)2, 169-195 (1980) · Zbl 0432.65023
[4] Stummel, F.: Perturbation theory for evaluation algorithms of arithmetic expressions. Math. Comput.37, 435-473 (1981) · Zbl 0515.65039 · doi:10.1090/S0025-5718-1981-0628707-8
[5] Stummel, F.: Rounding errors in numerical solutions of two linear equations in two unknowns. Math. Methods Appl. Sci.4, 549-571 (1982) · Zbl 0505.65011 · doi:10.1002/mma.1670040135
[6] Stummel, F.: Rounding error in Gaussian elimination of tridiagonal linear systems. Survey of results. Interval Mathematics 1980 (Proc. Int. Symp., Freiburg, 1980), pp. 223-245. New York: Academic Press 1980 · Zbl 0543.65011
[7] Stummel, F.: Rounding error in Gaussian elimination of tridiagonal linear systems. Part I, II. Preprint. U Frankfurt, 1980 · Zbl 0543.65011
[8] Stummel, F.: Optimal error estimates for Gaussian elimination in floating-point arithmetic. Z. Angew. Math. Mech.62, T355-T357 (1982) · Zbl 0496.65009
[9] Stummel, F.: Forward error analysis of the solutions of triangular linear systems and linear recurrences. Preprint. U Frankfurt, 1981 · Zbl 0515.65039
[10] Stummel, F.: Forward error analysis of Gaussian elimination. Part II: Stability theorems. Numer. Math.46, 397-415 (1985) · Zbl 0554.65033 · doi:10.1007/BF01389493
[11] Stummel, F., Hainer, K.: Praktische Mathematik, 2. erw. Auflage. Stuttgart: Teubner 1982
[12] Wilkinson, J.H.: Error analysis of direct methods of matrix inversion. J. ACM8, 281-330 (1961) · Zbl 0109.09005 · doi:10.1145/321075.321076
[13] Wilkinson, J.H.: Rounding erros in algebraic processes. Englewood Cliffs: Prentice Hall 1963 · Zbl 1041.65502
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.