Solving the linear least squares problem with very high relative accuracy (Q756369)

An algorithm is proposed for solving a linear least squares problem, when the matrix A is of full column rank, to a prescribed accuracy \(\epsilon >0\). This is achieved by means of programmed multi-precision arithmetics. It is assumed that all elements of A and b are exactly representable in a floating point arithmetic with \(t_ 0\) digit mantissa, \(f\ell (t_ 0)\). The idea is to decompose (in \(f\ell (t_ 0))\) the matrix A to factors of simple structure (e.g., triangular, orthogonal) and then use classical iterative refinements with increasing mantissa length to set the solution vector within the prescribed accuracy. The paper deals first with the error of a single stage of the algorithm and then gives estimates for its total error and time cost. If \(\epsilon\) is very small relative to \(t_ 0\), then the total cost of the algorithm equals evaluating a few residual vectors in \(f\ell ([\log_ 21/\epsilon])\).