Research On Condition Numbers For The Least Squares And Total Least Squares Problems

It is well-known that both the least square(LS) and total least squares(TLS) are two important methods in scientific computation. Condition number measures the worst-case sensitivity of the solution of a problem to small perturbations in the data. Research on condition number is an important topic issue of matrix perturbation analysis and numerical analysis. Considerable work have been made over the past decades on LS and TLS problems.In this thesis, we continue to study the condition numbers for the LS and TLS problems. The main work of this thesis contains the following five parts:In the first part, we study the conditioning theory of the Tikhonov regularization solution. We first present the relative normwise, mixed and componentwise condition numbers for the Tikhonov regularization solution when the coefficient matrix, regularization matrix and right-hand side vector are all perturbed, which generalized the results obtained in [Chu et al., Numer. Linear Algebra Appl. 2011, 18(1): 87-103]. Then we study the structured condition numbers for the Tikhonov regularization solution when the coefficient matrix A has linear structure.In the second part, we consider the condition numbers of the LS problem with multiple right-hand sides. The normwise, mixed and componentwise condition numbers for the least squares problem with multiple right-hand sides are presented when the coefficient matrix has full column rank or is rank deficient, respectively. The results extend the earlier condition numbers for the least squares problem with single right-hand side.In the third part, we study the condition numbers of the TLS problem with single right-hand side. We first present the closed formulas and upper bounds for the mixed and componentwise condition numbers of the TLS problem with single right-hand side. Then the closed formulas for structured condition numbers of the TLS problems with linear structures such as lower triangular, Toeplitz and Hankel structures and non-linear structures with Vandermonde and Cauchy structures are also provided. Numerical examples illustrate that the structured condition numbers can be much even substantially smaller than the unstructured ones.In the fourth part, we focus on the condition numbers of a linear function of the truncated TLS(T-TLS) solution. We present the closed formulas and upper bounds for the normwise, mixed and componentwise condition numbers of a linear function of the T-TLS solution, i.e. LTxk, where xkis the truncated total least squares solution with truncation level k. The results generalize or improve those in the literature. We also give two statistical estimates of the absolute normwise condition number of LTxk. Numerical examples demonstrate that our upper bounds of the condition numbers and the statistical estimates are often good estimates of their corresponding exact values.In the fifth part, we consider the condition numbers of the TLS problem with multiple right-hand sides. As far as we know, there is no literature to discuss this issue. When the TLS problem with multiple right-hand sides has a unique solution, we first present closed formulas and upper bounds for the normwise, mixed and componentwise condition numbers of it. These results generalize the ones in the literature on condition numbers of the TLS problems with a single right-hand side. An efficient power method for computing the absolute normwise condition number is also described. We further study the normwise,mixed and componentwise condition numbers of the minimum Frobenius norm solution of the TLS problem with multiple right-hand sides when it has infinite number of solutions and their upper bound estimates are given. Numerical examples demonstrate that these upper bounds are sharp.