Accuracy And Stability Of Several Kinds Of Numerical Algorithms

Accuracy and stability of numerical algorithms are important and fundamental branches of study in numerical algebra. With the progress of science and the develop-ment of computer technology, the size of practical considerations in numerical calculation is increasing and the generated matrices become larger and larger, then solving linear sys-tems gets more difficult, thus some feasible algorithms need be presented to settle these questions. After the scheme presented, a general question appears, whether the scheme is feasible or whether the problem that there exists more different between the numerical solution and the exact solution appears when the slight perturbation is caused. Therefore, it is quite necessary to investigate accuracy and stability of algorithms. In this disserta-tion a research on stability and accuracy of interrelated algorithms of block tridiagonal matrices, general nonsingular matrices and unsymmetrical strictly t-diagonally dominant matrices is presented; several kinds of growth factors are discussed; the accuracy of the updating and rank-r updating of the polar decomposition is analyzed; the accuracy and stability of saddle-point problems and weighted linear least-squares problems are consid-ered, respectively.The accuracy and stability of interrelated algorithms of block tridiagonal matrices are investigated. First of all, by divide-and-conquer and URV factorization, inverses of tridiagonal matrices and rounding errors incurred at the process of inverses are pre-sented. Both the computing complexity and the error of the algorithm are sharper than those of Block Gaussian-Jordan Elimination. Secondly, assume that the original block tridiagonal matrix is I-block diagonally dominant (â…¡-block diagonally dominant), then the reduced matrices preserver the same property. Some properties on several kinds of comparison matrices are given and backward error of BLU factorization for tridiagonal matrices is presented. Thirdly, applying a block representation of LU factorization pre-sented by Amodio and Mazzia, we give a block representation of BLU factorization for block tridiagonal matrices, block tridiagonal block H-matrices and complex symmetric block tridiagonal matrices, and the accuracy and backward errors which embody whose superiority are considered. Finally, to avoid the case that the factors are not triangular, partitioned LU factorization for block tridiagonal matrices is presented and the accuracy and stability are analyzed.Based on the first-order terms in the Taylor series and matrix-vector equation, per-turbation theory for the LU and QR factors are touched. For the LU factorization for the general nonsingular matrices, the question presented by Chang and Paige is considered and the interrelated question of the LU factorization with complete pivoting is investi-gated. In addition, diagonal ill-conditioning may be characterized by strict t-diagonal dominance, thus the backward error of the LU and QR factorizations for a nonsymmetric strictly t-diagonally dominant system is analyzed.By the definition of the growth factor presented by Amodio and Mazzia, the growth factors in BLU factorization for block tridiagonal block H-matrices and complex sym-metric block tridiagonal matrices are referred to. Moreover, the definition of a generalized Buckley matrix is presented, based on the growth factor given by Wilkinson, the growth factors in Gaussian elimination for this class and its related class of matrices are discussed. In addition, the updating and downdating of algorithms are involved in a number of areas. Perturbation analyses of the updating and rank-r updating of the polar decomposition are presented.Perturbation theory for saddle-point problem is researched. Firstly, perturbation the-ory is considered when the perturbed system is still the saddle-point system. Since the accuracy of the solution to the system depend on the submatrices of the saddle-point ma-trix, some schemes are presented to avoid their influence. In order to improve the accuracy of the solution, a scaling is given. Secondly, when the original matrix is a saddle-point matrix and the perturbed matrix is a generalized saddle-point matrix, the sensitivity of block LDLT factorization is considered and perturbation theory in this case is discussed. Thirdly, since saddle-point problems have tied up with least-squares problems, a provably backward stable algorithm for the solution of weighted linear least-squares problems with indefinite diagonal weighted matrices is presented. However, since a similar algorithm is not necessarily backward stable when the weighted matrices are generalized saddle-point matrices, finally, conditions are derived under which the algorithm is provably backward stable.