Extra-Precise Iterative Refinement for Overdetermined Least Squares Problems
Extra-Precise Iterative Refinement for Overdetermined Least Squares Problems
复制标题
DOI：
10.1145/1462173.1462177
复制
发表时间：
2009-02
期刊：
影响因子：
--
通讯作者：
J. Demmel;Yozo Hida;E. J. Riedy;X. Li
中科院分区：
文献类型：
--
作者：
J. Demmel;Yozo Hida;E. J. Riedy;X. Li
我们介绍了应用于过度确定的线性最小二乘（LLS）问题的算法，误差界和数值结果。向前的和componentwise的错误（ϵW），其中ϵW是工作精度，除非系统与线性系统相反，否则我们提供了两个。解决方案X和残差r的单独误差边界仅需要有限的使用精度，并且仅在QR分解的O（MN2）成本中增加了o（mn）的作用。额外的精度计算由新的扩展推出BLAS标准以便携式方式支持，并且改进算法将包含在Lapack的将来版本中，并且可以扩展到最小二乘问题的其他类型。
We present the algorithm, error bounds, and numerical results for extra-precise iterative refinement applied to overdetermined linear least squares (LLS) problems. We apply our linear system refinement algorithm to Björck’s augmented linear system formulation of an LLS problem. Our algorithm reduces the forward normwise and componentwise errors to O(ϵw), where ϵw is the working precision, unless the system is too ill conditioned. In contrast to linear systems, we provide two separate error bounds for the solution x and the residual r. The refinement algorithm requires only limited use of extra precision and adds only O(mn) work to the O(mn2) cost of QR factorization for problems of size m-by-n. The extra precision calculation is facilitated by the new extended-precision BLAS standard in a portable way, and the refinement algorithm will be included in a future release of LAPACK and can be extended to the other types of least squares problems.