Total Least Squares And KKT System

This thesis consists of two parts. First, TLS problem is studied. Golub and Van Loan first put forward TLS problem in 1980 and gave a numerical value stable algorithm firstly. Van Huffel and Vandewalle wrote a book which summarized almost all important theory results and numerical methods up to 1991. A basic viewpoint is noticed: where uses LS, there may use TLS. In some applications, it improves 10-15Golub and Van Loan gave a sufficient condition of solvability on Frobenius norm in 1980 when they put forward the problem of TLS, in which they did not consider the solvability condition of sufficient-necessary and the other norms resulted in bondage in investigation of the numerical value algorithm and theory analysis. Later researches are always based on this sufficient condition. Liu and Huang have to pointted out when solvability is considered. The former solved the solvability on Frobenius norm completely which the latter and Yan solved the solvability on 2-norm. This thesis give the sufficient and necessary condition on general unitarily invariant norms, which is need to realize the character of general unitarily invariant norms sufficiently. A classification can be given for all unitarily invariant norms which makes it more clear on dealing with the problem about unitarily invariant norms. The process and the result can improve the essential realization on TLS problem, so the corresponding algorithm and theory can get help from this. The second part of this thesis is KKT system. Such systems arise in several applications including mixed and hybrid finite element methods for Stokes and Maxwell equations and methods for quadratic programming. The corresponding results have wide application in physics ocean as the Stokes equation is a basic equation in hydromechanics. The backward errors and condition number are the two basic concepts on numerical algebra. The former depicts the stable of algorithm, and the latter reflects the sensitivity of data. The following equation is cited by Higham Errors of computer solution (less than equal to approximately) condition number backwards errors. For structured problem, extending structure-preserving-algorithm is used in the following aspects: first, the mathematic structure always reflect the need of physics, second, it makes the efficiency of algorithm be higher. There is structured sensitivity analysis corresponding to the structure-preserving-algorithm. The corre- sponding formula is Errors of computer solution (less than equal to approximately) structured condition number structured backward errors. This article researches the structured condition number on KKT system, for a special KKT system, the structured sensitivity is also considered. This thesis studies the condition number of linear systems, the condition number of matrix inversion, all problems with respect to normwise structured perturbations. It shows that for a given linear structured matrix the worst case structured condition number of matrix inversion is equal to the worst case distance to the structured nearest singular matrix. It extends some results of condition number of KKT structured, makes improvement technique of Rump. Especially it uses single parameter unfolded method and partial condition number to deal with the structured condition number and gives the ratio of the condition number with respect to structured and unstructured perturbations. From aspect of hydrodynamics, the top right corner of KKT matrix M is often semi-positive, sometimes, the factor F is given directly. This article deals with the sensitivity analysis for this subclass of KKT systems. Optimal backward perturbation analysis is investigated. The partial condition numbers are defined and explicit formulae are derived. Finally, some new perturbation bounds are proved.