【作者】 王学锋；

【导师】 刘新国；

【作者基本信息】 中国海洋大学 ， 物理海洋学， 2007， 博士

【摘要】 这篇学位论文有两部分内容。首先,我们介绍第一个工作,TLS问题可解性研究。1980年Golub和Van Loan提出TLS问题,并且给出了了求解TLS问题的第一个数值稳定的算法。Van Huffel和Vandewalle的著作总结了直到1991年取得的重要理论结果和数值方法。书中有个基本观点特别提及:那里用LS,那里就用TLS;在一些典型应用中,用TLS比用LS可以使参数估计精度平均提高10-15在1980年,Golub和Van Loan提出TLS问题时,他们同时也给出了在Frobenius范数下可解性的一个充分条件,但是没有讨论充分必要条件以及其它范数的情形,这导致了一定的局限性,为研究数值算法和其他形式的TLS问题带来了一定的束缚。后继的相关的TLS问题的研究往往均以此作为基础来进行。在可解性方面的工作,需要提到的是刘新国和黄开斌的工作,前者给出了在Frobenius范数下TLS问题可解的充分必要条件;而后者与颜世健给出了在谱范数下可解的充分必要条件。本论文的第一个工作是在充分了解一般酉不变范数的性质的前提下给出了了TLS问题在一般的酉不变范数下可解的充分必要条件,从而在更大范围中解决了可解性问题。在文中,对于一般酉不变范数,我们给出了它的一种分类方法,从而能够更加充分地认识一般地酉不变范数。顺便的,我们还讨论了LS和TLS的相关地几何问题。解决的过程和充分必要条件的结论能够提高我们对TLS问题本质的认识,从而为算法的改进和其它相关的TLS问题的研究提供理论上的帮助。下面我们介绍第二部分的工作,即KKT系统的研究。Stokes问题的混合有限元方法离散导出了KKT系统,由于Stokes方程是流体力学的基本方程,因而其研究成果在物理海洋科学中有广泛的应用背景。在数值代数中,向后误差和条件数是两个基本概念。前者刻画了算法的稳定性,后者则反映解关于数据扰动的敏感性。二者相结合,按照Higham的观点,在一阶近似下,有计算解的误差(近似小于等于)条件数向后误差。对于结构问题,发展保结构算法有两方面的考虑。其一,数学结构一般是物理机制的反映,数学上保结构等同于遵从物理要求;其二,充分地利用结构有可能使求解效率更高。对应于保结构算法,相应地有结构敏度分析。即,对于保结构算法的计算结果分析,相应的有计算解的误差(近似小于等于)结构条件数结构向后误差。本文主要研究了KKT系统的结构条件数,而且对于一类特殊的KKT系统,研究了它的结构敏度方面的问题。Higham和Higham 1992年定义了结构条件数和结构向后误差,并对一些重要的线性结构研究了结构向后误差。Rump于2004年对一些重要而常见的结构系统比较了条件数与结构条件数。然而,Higham和Rump没有讨论KKT系统,他们讨论的主要是单结构系统。我们对KKT系统的条件数与结构条件数做了定量和定性两方面的比较,我们对Rump的研究结构条件数的几乎所有工具都应用在KKT系统上,比较了它们的优点和不足,得不到满意的结论。我们采取的主要研究思路是引入子条件数,建立Byers型不等式,改进Rump的技术,写出KKT矩阵的逆矩阵形式,然后进行比较。首先利用单参数展开方法建立了Byers型不等式,然后讨论结构条件数与条件数的定性比较。结果表明,在极端情形,条件数与结构条件数之比可以任意大。对于一般的线性结构,我们还给出了求逆结构条件数和到结构不可逆阵的距离之间的关系。从计算流体力学角度看,KKT系统中右上角矩阵M一般是半正定的,有时直接给出的是它的因子F,所以我们研究F。对于这一类的KKT系统,定义了偏条件数,给出了最优向后误差的分析,相应的结构条件数和一些扰动界。更多还原

【Abstract】 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.更多还原