Component-wise perturbation analysis and error bounds for linear least squares solutions

Perturbation bounds for the linear least squares problem min _x Ax –b₂ corresponding tocomponent-wise perturbations in the data are derived. These bounds can be computed using a method of Hager and are often much better than the bounds derived from the standard perturbation analysis. In particular this is true for problems where the rows ofA are of widely different magnitudes. Generalizing a result by Oettli and Prager, we can use the bounds to compute a posteriori error bounds for computed least squares solutions.     

On mixed and componentwise condition numbers for Moore-Penrose inverse and linear least squares problems

Classical condition numbers are normwise: they measure the size of both input perturbations and output errors using some norms. To take into account the relative of each data component, and, in particular, a possible data sparseness, componentwise condition numbers have been increasingly considered. These are mostly of two kinds: mixed and componentwise. In this paper, we give explicit expressions, computable from the data, for the mixed and componentwise condition numbers for the computation of the Moore-Penrose inverse as well as for the computation of solutions and residues of linear least squares problems. In both cases the data matrices have full column (row) rank.

     

Round off error analysis for Gram-Schmidt method and solution of linear least squares problems

Round off error analysis for the classical Gram-Schmidt orthogonalization method with re-orthogonalization is presented. The effect of the round-off error on the orthogonality of the derived vectors and also on the solution of the linear least squares problems when solved by the Gram-Schmidt algorithm are given. Numerical results compared favorably with the results of other methods. The classical case when no re-orthogonalization takes place is also discussed.     

Numerical methods for solving linear least squares problems

A common problem in a Computer Laboratory is that of finding linear least squares solutions. These problems arise in a variety of areas and in a variety of contexts. Linear least squares problems are particularly difficult to solve because they frequently involve large quantities of data, and they are ill-conditioned by their very nature. In this paper, we shall consider stable numerical methods for handling these problems. Our basic tool is a matrix decomposition based on orthogonal Householder transformations.Reproduction in Whole or in Part is permitted for any Purpose of the United States government. This report was supported in part by Office of Naval Research Contract Nonr-225(37) (NR 044-11) at Stanford University.     

On optimal backward perturbation bounds for the linear least squares problem

Consider the linear least squares problem min _x ‖b?Ax‖₂ whereA is anm×n (m<n) matrix, andb is anm-dimensional vector. Lety be ann-dimensional vector, and let ηls(y) be the optimal backward perturbation bound defined by $$\eta _{LS} (y) = \inf \{ ||F||_F :y is a solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} .$$ . An explicit expression of ηls(y) (y≠0) has been given in [8]. However, if we define the optimal backward perturbation bounds ηmls(y) by $$\eta _{MLS} (y) = \inf \{ ||F||_F :y is the minimum 2 - norm solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} ,$$ , it may well be asked: How to derive an explicit expression of ηmls(y)? This note gives an answer. The main result is: Ifb≠0 andy≠0, then ηmls(y)=ηls (y).     

Perturbation bounds for the linear least squares problem subject to linear inequality constraints

We study the effect on the solution to a linear least squares problem with linear inequality and equality constraints when the data defining the problem are perturbed. The existence and uniqueness of a solution are investigated. If the matrices involved have full rank, then a detailed bound is obtained by the duality theory for quadratic programming. Sufficient conditions are derived for an estimate of the perturbation in the solution to hold in terms of the largest perturbation in the data.     

Semidiscrete least squares methods for linear hyperbolic systems

Some approximate methods for solving linear hyperbolic systems are presented and analyzed. The methods consist of discretizing with respect to time and solving the resulting hyperbolic system for fixed time by least squares finite element methods. An analysis of least squares approximations is given, including optimal order estimates for piecewise polynomial approximation spaces. Numerical results for the inviscid Burgers' equation are also presented. © 1992 John Wiley & Sons, Inc.     

B-Nekrasov matrices and error bounds for linear complementarity problems

The class of B-Nekrasov matrices is a subclass of P-matrices that contains Nekrasov Z-matrices with positive diagonal entries as well as B-matrices. Error bounds for the linear complementarity problem when the involved matrix is a B-Nekrasov matrix are presented. Numerical examples show the sharpness and applicability of the bounds.     

Estimation of optimal backward perturbation bounds for the linear least squares problem

In this paper a method of estimating the optimal backward perturbation bound for the linear least squares problem is presented. In contrast with the optimal bound, which requires a singular value decomposition, this method is better suited for practical use on large problems since it requiresO(mn) operations. The method presented involves the computation of a strict lower bound for the spectral norm and a strict upper bound for the Frobenius norm which gives a gap in which the optimal bounds for the spectral and the Frobenius norm must be. Numerical tests are performed showing that this method produces an efficient estimate of the optimal backward perturbation bound.     

Constrained least squares methods for linear timevarying DAE systems

Summary This paper presents a family of methods for accurate solution of higher index linear variable DAE systems, . These methods use the DAE system and some of its first derivatives as constraints to a least squares problem that corresponds to a Taylor series ofy, or an approximative equality derived from a Pade' approximation of the exponential function. Accuracy results for systems transformable to standard canonical form are given. Advantages, disadvantages, stability properties and implementation of these methods are discussed and two numerical examples are given, where we compare our results with results from more traditional methods.     

Solving linear least squares problems by Gram-Schmidt orthogonalization

A general analysis of the condition of the linear least squares problem is given. The influence of rounding errors is studied in detail for a modified version of the Gram-Schmidt orthogonalization to obtain a factorizationA=QR of a givenm×n matrixA, whereR is upper triangular andQ ^T Q=I. Letx be the vector which minimizes ‖b?Ax‖₂ andr=b?Ax. It is shown that if inner-products are accumulated in double precision then the errors in the computedx andr are less than the errors resulting from some simultaneous initial perturbation δA, δb such that

$$\parallel \delta A\parallel _E /\parallel A\parallel _E \approx \parallel \delta b\parallel _2 /\parallel b\parallel _2 \approx 2 \cdot n^{3/2} machine units.$$     

Sparse linear problems of the least squares method

One gives a survey of the direct method of solving large sparse diverse overdetermined linear systems of full column rank in the least squares sense. The survey covers practically all investigations on this topic, published in the seventies and in the beginning of the eighties.Translated from Itogi Nauki i Tekhniki, Seriya Matematicheskii Analiz, Vol. 23, pp. 219–285, 1985.     

Solving interval linear least squares problems by PPS-methods

Numerical Algorithms - In our work, we consider the linear least squares problem for m × n-systems of linear equations Ax = b, m ≥ n, such that the matrix A and right-hand side vector b...     

Preconditioned GAOR methods for solving weighted linear least squares problems

In this paper, we present the preconditioned generalized accelerated overrelaxation (GAOR) method for solving linear systems based on a class of weighted linear least square problems. Two kinds of preconditioning are proposed, and each one contains three preconditioners. We compare the spectral radii of the iteration matrices of the preconditioned and the original methods. The comparison results show that the convergence rate of the preconditioned GAOR methods is indeed better than the rate of the original method, whenever the original method is convergent. Finally, a numerical example is presented in order to confirm these theoretical results.     

Stability of the solutions of linear least squares problems

Numerische Mathematik - In 1966 Golub and Wilkinson gave upper bounds for the errors of least squares solutions based on orthogonal transformations, in which the square of the condition number of...     

An algorithm for linear least squares problems with equality and nonnegativity constraints

We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core problem arising in the solution of the general linearly constrained linear least squares problem. The reduction process of the general problem to the core problem can be done in many ways. We discuss three such techniques.The method employed for solving the core problem is based on combining the equality constraints with differentially weighted least squares equations to form an augmented least squares system. This weighted least squares system, which is equivalent to a penalty function method, is solved with nonnegativity constraints on selected variables.Three types of examples are presented that illustrate applications of the algorithm. The first is rank deficient, constrained least squares curve fitting. The second is concerned with solving linear systems of algebraic equations with Hilbert matrices and bounds on the variables. The third illustrates a constrained curve fitting problem with inconsistent inequality constraints.     

Some new error bounds for linear complementarity problems of H-matrices

Some new error bounds for linear complementarity problems of H-matrices are presented based on the preconditioned technique. Numerical examples show that these bounds are better than some existing ones.     

Error bounds for least squares approximation by polynomials

Let f ε Cⁿ⁺¹[−1, 1] and let H[f](x) be the nth degree weighted least squares polynomial approximation to f with respect to the orthonormal polynomials q_k associated with a distribution dα on [−1, 1]. It is shown that if q_n+1/q_n max(q_n+1(1)/q_n(1), −q_n+1(−1)/q_n(−1)), then f − H[f] f^{n + 1} · q_n+1/q_{n + 1}^{(n + 1)}, where · denotes the supremum norm. Furthermore, it is shown that in the case of Jacobi polynomials with distribution (1 − t)^α (1 + t)^β dt, α, β > −1, the condition on q_n+1/q_n is satisfied when either max(α,β) −1/2 or −1 < α = β < −1/2.     

A posteriors error bounds for inhomogeneous linear dirichlet and neumann problems

Second-order inhomogeneous linear Dirichlet and Neumann problems in divergent form on a simply-connected to-dimensional domain with Lipschitz-continious boundary of finite length are considered. Conjugate problems, that is, a pair of one Dirichlet and one Neumann problem the minima of energies of which add to a known constant, are introduced. From the conceppt of conjugate problems, two-sided bounds for the energy of the exact solution of any given Dirichlet or Neumann problem are constructed. These two-sided bounds for the energy at the exact solution are in turn used to obtain easily calculable a posteriori error bounds for the norm of the difference of the approximate and exact solutions of the given problem