Improved Gram–Schmidt Type Downdating Methods |
| |
Authors: | Jesse L Barlow Alicja Smoktunowicz and Hasan Erbay |
| |
Institution: | (1) Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA 16802–6822, USA;(2) Faculty of Mathematics and Information Science, Warsaw University of Technology, Pl. Politechniki 1, Warsaw, 00-661, Poland;(3) Department of Mathematics, Kırıkkale University, Yahşihan, Kırıkkale, 71100, Turkey |
| |
Abstract: | The problem of deleting a row from a Q–R factorization (called downdating) using Gram–Schmidt orthogonalization is intimately
connected to using classical iterative methods to solve a least squares problem with the orthogonal factor as the coefficient
matrix. Past approaches to downdating have focused upon accurate computation of the residual of that least squares problem,
then finding a unit vector in the direction of the residual that becomes a new column for the orthogonal factor. It is also
important to compute the solution vector of the related least squares problem accurately, as that vector must be used in the
downdating process to maintain good backward error in the new factorization. Using this observation, new algorithms are proposed.
One of the new algorithms proposed is a modification of one due to Yoo and Park BIT, 36:161–181, 1996]. That algorithm is
shown to be a Gram–Schmidt procedure.
Also presented are new results that bound the loss of orthogonality after downdating. An error analysis shows that the proposed
algorithms’ behavior in floating point arithmetic is close to their behavior in exact arithmetic. Experiments show that the
changes proposed in this paper can have a dramatic impact upon the accuracy of the downdated Q–R decomposition.
AMS subject classification (2000) 65F20, 65F25 |
| |
Keywords: | orthogonalization Q– R factorization matrix splittings residual |
本文献已被 SpringerLink 等数据库收录! |
|