Structured Error Analysis For Two Classes Of Structured Problems

In the past 50 or 60 years,a hot topic in the field of numerical algebra,matrix perturbation analysis,is to study the effect of small perturbation in matrix elements on the solution of matrix-related problems.As the main research content of matrix perturbation analysis,error analysis can be divided into forward error analysis and backward error analysis,which provides important theoretical basis for the research and improvement of numerical algorithms.However,many practical problems are often transformed into structured problems in numerical algebra through numerical discretization.Therefore,it is more practical to consider the influence of the structure-preserving error on the solution of structured problems.This thesis focuses on the structured error analysis for two types of structured problems.The main work includes the following two parts.In the first part,we discuss the structured backward error analysis of the approximate solution for the generalized saddle point systems.Firstly,the explicit and computable expressions of the normwise structured backward error for five kinds of 2 × 2 block generalized saddle point systems are presented.The derived results make up for the impractical or incorrect defects of some existing ones,and can be seen as the generalizations of the existing ones for standard saddle point problems,including some KKT systems.Our analysis can be viewed as a unified or general treatment for the structured backward errors for all kinds of 2 × 2 block saddle point problems.Secondly,we study the structured backward error analysis for the computed solutions of two special kinds of 3 × 3 block generalized saddle point systems.As far as we know,the commonly used stopping criterion for the generalized saddle point problems iterative solvers:the ratio of the residual to the right-side term is developed based on the normwise unstructured backward error analysis.However,our numerical examples show that the structured backward error can be much larger than the unstructured backward error of the computed solution for the generalized saddle point system in the worse case.Hence,this classic stopping criterion can not guarantee that the final iterative solution is the structure-preserving solution.Finally,we use the structured backward error of the generalized saddle point problems to design new stopping criteria for the corresponding iterative algorithms.Some numerical experiments are performed to illustrate that compare with the classic stopping criterion,the new stopping criterion is more robust and reliable.In the second part,we present the forward error analysis for the structure-preserving QR factorization(QX factorization)of the centrosymmetric matrix.To our knowdedge,no authors have discussed this problem so far.First of all,the uniqueness condition of the QX decomposition for the centrosymmetric matrices is given.Then,by using the modified matrix equation method,the modified matrix-vector equation method and the modified matrix-equation method,we obtain the normwise first-order perturbation bounds and normwise condition numbers for the two factors of the QX factorization.Finally,using the modified matrix method and the modified matrix-vector equation method based on the Brouwer fixed point theorem,the rigorous perturbation bounds of two different forms for the two factors of the QX factorization for centrosymmetric matrices are also obtained.