Structure Of Linear Equations Iterative Methods And Perturbation Analysis

We discuss the iterative methods and perturbation analysis of structured linear systems in this thesis.Chapter 1 and Chapter 2 mainly concern about the iterative solution methods. In Chapter 1, we discuss the preconditioning technique. According to the special structure of the coefficient matrix arising from the SUPG discretization of convection-diffusion problem, or the MAC discretization of the Oseen problem, we use Kronecker product approximation to design the preconditioner. So we can change the spectral properties of the coefficient matrix, and improve the convergence. We focus on the inexact Krylov method in Chapter 2. When we use Krylov subspace methods as the outer iteration, we can apply relaxation strategy to inner iteration and use inexact matrix-vector product. We analyze the inexact BiCGStab and provide its corresponding relaxation strategy. We then apply the inexact Krylov subspace method to the Schur complement equation and the related equation. We also propose a new idea of combining relaxation strategy with Monte Carlo method.We turn to perturbation analysis from Chapter 3 to Chapter 5. In Chapter 3, we discuss the structured backward error and condition numbers of saddle point problem. The explicit general expression of structured backward error is obtained, and the structured condition number is applied to analyze the sensitivity of the solution. In Chapter 4, we use matrix derivative to deduce the mixed and componentwise condition numbers of structured matrix, such as Cauchy matrix, Vandermonde matrix, etc. In Chapter 5, we investigate the linear systems involving Kronecker product. We analyze its condition numbers and the level-2 condition numbers.In Chapter 6, we give a note on the minimax representation for the subspace distance and singular values.