Error analysis of algorithms for computing the projection of a point onto a linear manifold. (English) Zbl 0629.65042
Given an \(n\times m\) matrix A and vectors \(b\in {\mathbb{R}}^ m\), \(p\in {\mathbb{R}}^ n\), the vector x with minimal distance to p is to be computed on the linear manifold \(\{A^ Tx=b\}\). The accumulation of rounding errors is studied for a modified Gram-Schmidt process, Householder, and Givens orthogonal factorization. If \(n\gg m\), then there is no substantial difference between Gram-Schmidt and the Householder method. On the other hand the Householder method is favorable if \(m\approx n\).
Reviewer: D.Braess
MSC:
65F20 | Numerical solutions to overdetermined systems, pseudoinverses |
Keywords:
projection of a point onto a linear manifold; least distance problem; projection; Householder factorization; accumulation of rounding errors; Gram-Schmidt process; Givens orthogonal factorizationSoftware:
LINPACKReferences:
[1] | Huang, H. Y., A direct method for the general solution of a system of linear equations, J. Optim. Theory Appl., 16, 429-445 (1975) · Zbl 0291.90038 |
[2] | Arioli, M.; Laratta, A., Metodi diretti per la risoluzione di sistemi lineari, Calcolo, XXI, 229-252 (1984) · Zbl 0574.65032 |
[3] | Arioli, M.; Laratta, A., Error analysis of an algorithm for solving an underdetermined linear system, Numer. Math., 46, 255-268 (1985) · Zbl 0543.65012 |
[4] | Arioli, M.; Laratta, A.; Menchi, O., Numerical computation of the projection of a point onto a polyhedron, J. Optim. Theory Appl., 43, 495-525 (1984) · Zbl 0518.65044 |
[5] | Bjorck, A., Solving linear least squares problems by Gram-Schmidt orthogonalization, BIT, 7, 1-21 (1967) · Zbl 0183.17802 |
[6] | Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Clarendon: Clarendon Oxford · Zbl 0258.65037 |
[7] | Lawson, C. L.; Hanson, R. J., Solving Least Squares Problems (1974), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0185.40701 |
[8] | Gentleman, W. M., Error analysis of QR decompositions by Givens transformations, Linear Algebra Appl., 10, 189-197 (1975) · Zbl 0308.65022 |
[9] | Dongarra, J. J.; Brunch, J. R.; Moler, G. B.; Stewart, G. W., LINPACK User’s Guide (1979), SIAM: SIAM Philadelphia |
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.