Round-off Error Analysis Of Some Least Squares Problems

Least squares (LS) problems are one of the most important and widely used tools in many fields, such as economics, statistics, optimizations, engineering, automation,etc, which have attracted many numerical algebra analysts to attach deep importance to the numerical stabilities of least squares problems.In this dissertation, we mainly study numerical properties/algorithms and roundoff error estimates related to least squares problems, as mentioned in the following sections:1. Forward roundoff error estimates of LU and Cholesky factorizationsLU factorization(Gaussian elimination) is a fundamental tool for solving invert-ible linear system. In fact, the LU of a rectangular matrix also plays an important role in solving the equality constrained least squares problem, and rank revealing LU (RRLU) factorization, etc. Backward roundoff error estimates of LU factorization are widely studied in literature. However, forward roundoff error estimates of LU expressed in literature are not concise enough. We will study forward roundoff errors of LU and Cholesky factorizations, and concisely express the forward roundoff errors, which are only related to the submatrices of original matrix and the model of roundoff error accumulation. Furthermore, we also give roundoff estimates for LU factor and the solution of an invertible system.2. Roundoff error estimates of the modified Gram-Schmidt(MGS) algorithm for solving standard LS problemThe Householder QR, Givens QR and modified Gram-Schmidt algorithm are frequently used methods for solving standard least squares problem(LS): min ||Ax— b||2. MGS has its particular numerical properties. Backward roundoff error estimates of MGS have studied in literature, but most of the estimates are norm-wise. We derive the component-wise backward error estimates of the MGS with column pivoting (PMGS). We also firstly study forward roundoff error estimates of MGS, and reveal that if coefficient matrix is well conditioned, then with properly chosen tolerance η, the PMGS can also correctly determine the numerical rank of the coefficient matrix.Roundoff error estimates of PMGS for solving the standard LS problem are also discussed.3. Roundoff error estimates of the MGS-like algorithm for solving the equality constrained least squares problemThe equality constrained least squares (LSE) problemis equivalent to the weighted least squares problem(WLS) : when t→∞ , i.e., lim x_wls(t) = x_LSE We derive the MGS-like method for LSEproblem by taking limits in the MGS of (?) , and express the LSE solution of minimum norm explicitly. We also derive backward roundoff error estimates of the MGS-like algorithm. Furthermore, based on the error estimates of LU and MGS algorithm, we present forward roundoff error estimates of MGS-like algorithm for solving the LSE problem.4. The numerical stable algorithm and roundoff error estimates for the stiff weighted least squares problemThe stiff weighted least squares problems(SWLS): min ||W^1/2 (Ax-b)||2, arises in several application areas including linear programming, electrical power networks, elliptic boundary value problems and structural analysis[58], in which the entries of in which W = diag(w₁₁,…,w_mm) > 0 vary widely. A number of numerical tests showed that standard PMGS algorithm is numerical unstable for solving SWLS, and the more stiff of W, the worse of the numerical stability. Based on the sufficient and necessary conditions deduced by M. Wei for solving SWLS[72], we present numerical stable algorithm for solving the stiff weighted least squares problem and evaluate the forward and backward roundoff error estimates of the algorithm.5. On upper bounds of the growth factors for LU, Cholesky, MGS algorithmsRoundoff error estimates of LU , MGS and MGS-like algorithms showed that the upper bounds of the growth factors for matrix factorizations play an important role in numerical stability of matrix factorizations. We therefore study the upper bounds of the growth factors for LU, Cholesky and MGS, MGS-like algorithms.The upper bounds of the growt...