Algorithms for the computation of functionals defined on the solution of a discrete ill-posed problem (Q915372)

Let x denote a solution to the problem \(\| Ax-b\|_ 2\leq \epsilon\). Then confidence intervals for this solution can be computed by minimizing certain linear functionals \(w^ Tx\) defined on the solution x. Although the problem of computing the functional \(w^ Tx\) may be better conditioned than that of computing x itself, it is in many cases not well-conditioned enough to give the answer to the required accuracy. In such cases one can supply extra information as a quadratic constraint \(\| x-d\|_ 2\leq \delta\). Thus, one is lead to minimizing a linear functional subject to two quadratic constraints. The author proves that this problem is essentially equivalent to a least squares problem with a linear and a quadratic constraint, which is easier to handle computationally. He also presents efficient algorithms for the latter problem. One is based on bidiagonalization of the coefficient matrix A; the other is based on bidiagonalization of the matrix \(AV_ 1\), where the columns of \(V_ 1\) span the null-space of w. A numerical example, which concludes the paper, clearly illustrates the numerical treatment of this problem.