×

zbMATH — the first resource for mathematics

On the augmented system approach to sparse least-squares problems. (English) Zbl 0678.65024
When the least-squares problem \(\| Ax-b\|_ 2\to \min !\) is to be solved, one may consider the augmented system \[ \left( \begin{matrix} I\\ A^ T\end{matrix} \begin{matrix} A\\ 0\end{matrix} \right)\left( \begin{matrix} r\\ x\end{matrix} \right)=\left( \begin{matrix} b\\ 0\end{matrix} \right) \] instead of the normal equations. In order to reduce the condition number of the augmented matrix, the identity matrix I may be replaced by \(\alpha\) I with \(\alpha\) being a suitable scaling factor. Iterative refinements and perturbation theoretic arguments are discussed in the framework of an error analysis. Ten tables with numerical results for several test matrices are given.
Reviewer: D.Braess

MSC:
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F35 Numerical computation of matrix norms, conditioning, scaling
PDF BibTeX Cite
Full Text: DOI EuDML
References:
[1] Arioli, M., Demmel, J.W., Duff, I.S.: Solving sparse linear systems with sparse backward error. Report CSS 214, CSS Division, Harwell Laboratory, England. SIAM J. Matrix Anal. Appl. 1988 (to appear) · Zbl 0684.65022
[2] Bartels, R.H., Golub, G.H., Saunders, M.A.: Numerical techniques in mathematical programming. In: Rosen, J.B., Mangasarian, O.L., Ritter, K. (eds.): Nonlinear programming, pp. 123-176. New York: Academic Press 1970 · Zbl 0228.90030
[3] Björck, Å.: Iterative refinement of linear least squares solutions. BIT7, 257-278 (1967) · Zbl 0159.20404
[4] Duff, I.S., Grimes, R.G., Lewis, J.G.: Sparse matrix test problems. Report CSS 191, CSS Division, Harwell Laboratory, England. ACM Trans. Math. Software 1987 (to appear) · Zbl 0667.65040
[5] Duff, I.S., Reid, J.K.: The multifrontal solution of indefinite sparse symmetric linear equations. ACM Trans. Math. Software9, 302-325 (1983) · Zbl 0515.65022
[6] Gay, D.M.: Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Newsletter 1985
[7] Golub, G.H., Van Loan, C.F.: Matrix computations. 1st Ed. North Oxford Academic, Oxford, and John Hopkins Press, Baltimore 1983 · Zbl 0559.65011
[8] Hachtel, G.D.: Extended applications of the sparse tableau approach?finite elements and least squares. In: Spillers, W.R. (ed.): Basic question of design theory. Amsterdam: North Holland 1974 · Zbl 0388.65011
[9] Hager, W.W.: Condition estimators. SIAM J. Sci. Stat. Comput.5, 311-316 (1984) · Zbl 0542.65023
[10] Higham, N.J.: A survey of condition number estimation for triangular matrices. SIAM Review29, 575-596 (1987) · Zbl 0635.65049
[11] Läuchli, P.: Jordan-Elimination und Ausgleichung nach kleinsten Quadraten. Numer. Math.3, 226-240 (1961) · Zbl 0117.10902
[12] Karmarkar, N.: A new polynomial time algorithm for linear programming. Combinatorica4, 373-395 (1984) · Zbl 0557.90065
[13] Oettli, W., Prager, W.: Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numer. Math.6, 405-409 (1964) · Zbl 0133.08603
[14] Skeel, R.D.: Scaling for numerical stability in Gaussian elimination. J. ACM26, 494-526 (1979) · Zbl 0435.65035
[15] Skeel, R.D.: Iterative refinement implies numerical stability for Gaussian elimination. Math. Comput.35, 817-832 (1980) · Zbl 0441.65027
[16] Van Loan, C.F.: On the method of weighting for equality-constrained least-squares problems. SIAM J. Numer. Anal.22, 851-864 (1985) · Zbl 0584.65015
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.