ISSN:
1572-9125
Schlagwort(e):
65F25
;
65G05
;
65F05
;
65F20
;
augmented systems
;
QR factorization
;
least squares
;
minimum norm solution
;
seminormal equations
;
numerical stability
;
Gram-Schmidt
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
Notizen:
Abstract We consider solvingx+Ay=b andA T x=c for givenb, c andm ×n A of rankn. This is called the augmented system formulation (ASF) of two standard optimization problems, which include as special cases the minimum 2-norm of a linear underdetermined system (b=0) and the linear least squares problem (c=0), as well as more general problems. We examine the numerical stability of methods (for the ASF) based on the QR factorization ofA, whether by Householder transformations, Givens rotations, or the modified Gram-Schmidt (MGS) algorithm, and consider methods which useQ andR, or onlyR. We discuss the meaning of stability of algorithms for the ASF in terms of stability of algorithms for the underlying optimization problems. We prove the backward stability of several methods for the ASF which useQ andR, inclusing a new one based on MGS, and also show under what circumstances they may be regarded as strongly stable. We show why previous methods usingQ from MGS were not backward stable, but illustrate that some of these methods may be “acceptable-error stable”. We point out that the numerical accuracy of methods that do not useQ does not depend to any significant extent on which of of the above three QR factorizations is used. We then show that the standard methods which do not useQ are not backward stable or even acceptable-error stable for the general ASF problem, and discuss how iterative refinement can be used to counteract these deficiencies.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01935013
Permalink
