×

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

Software:

LINPACK
Full Text: DOI

References:

[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.