Solution of augmented linear systems using orthogonal factorizations
type: Item
instance of: scholarly article
title: Solution of augmented linear systems using orthogonal factorizations
zbMATH Open document ID: 0822.65021
DOI: 10.1007/BF01935013
author: Christopher C. Paige
author: Åke Björck
published in: BIT
publication date: 1995-10-15T00:00:00Z
review text: The paper deals with solving \(x+ Ay= b\) and \(A^ T x= c\) for given vectors \(b\), \(c\) and an \(m\times n\) matrix \(A\) of rank \(n\). This system is called the augmented system formulation since it represents the necessary and sufficient conditions for the solution of the following two optimization problems: \(\min_ x\| b- x\|_ 2\) subject to \(A^ T x= c\) and \(\min_ y \{\| b- Ay\|^ 2_ 2+ 2c^ T y\}\). It is shown that the augmented system formulation can be effectively handled by various \(QR\)-factorizations of \(A\), where \(Q\) is orthogonal and \(R\) upper triangular. It is further shown that there exist backward stable algorithms where the \(QR\)-factorization is based on Householder transformations, rotations, or the modified Gram-Schmidt algorithm. When no part of \(Q\) is available, it is shown that the standard methods are not stable for the general augmented system formulation problem. Some iterative refinements are proposed to improve this.
Mathematics Subject Classification ID: 65F20
Mathematics Subject Classification ID: 65F25
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65G50
zbMATH DE Number: 716123
zbMATH Keywords: least squares
zbMATH Keywords: seminormal equations
zbMATH Keywords: numerical stability
zbMATH Keywords: augmented system
zbMATH Keywords: \(QR\)-factorizations
zbMATH Keywords: Householder transformations
zbMATH Keywords: Gram-Schmidt algorithm
zbMATH Keywords: iterative refinements
Wikidata QID: Q114233891
reviewed by: Florica Luban
MaRDI profile type: Publication
cites work: On the augmented system approach to sparse least-squares problems
cites work: Error analysis of algorithms for computing the projection of a point onto a linear manifold
cites work: Solving linear least squares problems by Gram-Schmidt orthogonalization
cites work: Iterative refinement of linear least squares solutions I
cites work: Stability analysis of the method of seminormal equations for linear least squares problems
cites work: Loss and Recapture of Orthogonality in the Modified Gram–Schmidt Algorithm
cites work: The weak and strong stability of algorithms in numerical linear algebra
cites work: The Strong Stability of Algorithms for Solving Symmetric Linear Systems
cites work: Q4739659
cites work: Q3359644
cites work: Note on the iterative refinement of least squares solution
cites work: The Accuracy of Solutions to Triangular Systems
cites work: An Error Analysis of a Method for Solving Matrix Equations
cites work: Q4057472
cites work: Q3754586
cites work: Q5674306
description: scientific article; zbMATH DE number 716123