Reorthogonalization and stable algorithms for updating the Gram-Schmidt 𝑄𝑅 factorization 论文

摘要

Numerically stable algorithms are given for updating the Gram-Schmidt QR factorization of an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m times n"> <mml:semantics> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo> × </mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">m \times n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> matrix <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis m greater-than-or-slanted-equals n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>A</mml:mi> <mml:mspace width="thickmathspace"/> <mml:mo stretchy="false">(</mml:mo> <mml:mi>m</mml:mi> <mml:mo> ⩾ </mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">A\;(m \geqslant n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> when <italic>A</italic> is modified by a matrix of rank one, or when a row or column is inserted or deleted. The algorithms require <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis m n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>m</mml:mi> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(mn)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> operations per update, and are based on the use of elementary two-by-two reflection matrices and the Gram-Schmidt process with reorthogonalization. An error analysis of the reorthogonalization process provides rigorous justification for the corresponding ALGOL procedures.