On componentwise condition numbers for eigenvalue problems with structured matrices

We give explicit expressions for the componentwise condition number for eigenvalue problems with structured matrices. We will consider only linear structures and show a general result from which expressions for the condition numbers follow. We obtain explicit expressions for the following structures: Toeplitz and Hankel. Details for other linear structures should follow in a straightforward manner from our general result. Copyright © 2008 John Wiley & Sons, Ltd.     

Effective condition numbers and small sample statistical condition estimation for the generalized Sylvester equation

In this paper,we investigate the effective condition numbers for the generalized Sylvester equation(AX-YB,DX-YE)=(C,F),where A,D∈R m×m,B,E∈R n×n and C,F ∈ R m×n.We apply the small sample statistical method for the fast condition estimation of the generalized Sylvester equation,which requires O(m2n+mn2) flops,comparing with O(m3+n3) flops for the generalized Schur and generalized HessenbergSchur methods for solving the generalized Sylvester equation.Numerical examples illustrate the sharpness of our perturbation bounds.     

Condition numbers and backward perturbation bound for linear matrix equations

This paper deals with the normwise perturbation theory for linear (Hermitian) matrix equations. The definition of condition number for the linear (Hermitian) matrix equations is presented. The lower and upper bounds for the condition number are derived. The estimation for the optimal backward perturbation bound for the Hermitian matrix equations is obtained. Copyright © 2010 John Wiley & Sons, Ltd.     

A combination of Sylvester block sum and block matrix Kronecker map for explicit solutions of Sylvester system of matrix equations

In this paper, we consider an explicit solution of system of Sylvester matrix equations of the form A₁V₁ ? E₁V₁F₁ = B₁W₁ and A₂V₂ ? E₂V₂F₂ = B₂W₂ with F₁ and F₂ being arbitrary matrices, where V₁,W₁,V₂ and W₂ are the matrices to be determined. First, the definitions, of the matrix polynomial of block matrix, Sylvester sum, and Kronecker product of block matrices are defined. Some definitions, lemmas, and theorems that are needed to propose our method are stated and proved. Numerical test problems are solved to illustrate the suggested technique.     

Perturbation analysis and condition numbers of scaled total least squares problems

The standard approaches to solving an overdetermined linear system Ax ≈ b find minimal corrections to the vector b and/or the matrix A such that the corrected system is consistent, such as the least squares (LS), the data least squares (DLS) and the total least squares (TLS). The scaled total least squares (STLS) method unifies the LS, DLS and TLS methods. The classical normwise condition numbers for the LS problem have been widely studied. However, there are no such similar results for the TLS and the STLS problems. In this paper, we first present a perturbation analysis of the STLS problem, which is a generalization of the TLS problem, and give a normwise condition number for the STLS problem. Different from normwise condition numbers, which measure the sizes of both input perturbations and output errors using some norms, componentwise condition numbers take into account the relation of each data component, and possible data sparsity. Then in this paper we give explicit expressions for the estimates of the mixed and componentwise condition numbers for the STLS problem. Since the TLS problem is a special case of the STLS problem, the condition numbers for the TLS problem follow immediately from our STLS results. All the discussions in this paper are under the Golub-Van Loan condition for the existence and uniqueness of the STLS solution. Yimin Wei is supported by the National Natural Science Foundation of China under grant 10871051, Shanghai Science & Technology Committee under grant 08DZ2271900 and Shanghai Education Committee under grant 08SG01. Sanzheng Qiao is partially supported by Shanghai Key Laboratory of Contemporary Applied Mathematics of Fudan University during his visiting.     

Normwise, mixed and componentwise condition numbers of nonsymmetric algebraic Riccati equations

This paper is devoted to the perturbation analysis for nonsymmetric algebraic Riccati equations. The upper bounds for the normwise, mixed and componentwise condition numbers are presented. The results are illustrated by numerical examples.     

A condition analysis of the weighted linear least squares problem using dual norms

In this paper, based on the theory of adjoint operators and dual norms, we define condition numbers for a linear solution function of the weighted linear least squares problem. The explicit expressions of the normwise and componentwise condition numbers derived in this paper can be computed at low cost when the dimension of the linear function is low due to dual operator theory. Moreover, we use the augmented system to perform a componentwise perturbation analysis of the solution and residual of the weighted linear least squares problems. We also propose two efficient condition number estimators. Our numerical experiments demonstrate that our condition numbers give accurate perturbation bounds and can reveal the conditioning of individual components of the solution. Our condition number estimators are accurate as well as efficient.     

On condition numbers for Moore–Penrose inverse and linear least squares problem involving Kronecker products

In this paper, we investigate the normwise, mixed, and componentwise condition numbers and their upper bounds for the Moore–Penrose inverse of the Kronecker product and more general matrix function compositions involving Kronecker products. We also present the condition numbers and their upper bounds for the associated Kronecker product linear least squares solution with full column rank. In practice, the derived upper bounds for the mixed and componentwise condition numbers for Kronecker product linear least squares solution can be efficiently estimated using the Hager–Higham Algorithm. Copyright © 2012 John Wiley & Sons, Ltd.     

On the explicit solutions of forms of the Sylvester and the Yakubovich matrix equations

In this paper, we consider the explicit solutions of two matrix equations, namely, the Yakubovich matrix equation V−AVF=BW and Sylvester matrix equations AV−EVF=BW,AV+BW=EVF and AV−VF=BW. For this purpose, we make use of Kronecker map and Sylvester sum as well as the concept of coefficients of characteristic polynomial of the matrix A. Some lemmas and theorems are stated and proved where explicit and parametric solutions are obtained. The proposed methods are illustrated by numerical examples. The results obtained show that the methods are very neat and efficient.     

Applications of statistical condition estimation to the solution of linear systems

This paper discusses some applications of statistical condition estimation (SCE) to the problem of solving linear systems. Specifically, triangular and bidiagonal matrices are studied in some detail as typical of structured matrices. Such a structure, when properly respected, leads to condition estimates that are much less conservative compared with traditional non‐statistical methods of condition estimation. Some examples of linear systems and Sylvester equations are presented. Vandermonde and Cauchy matrices are also studied as representative of linear systems with large condition numbers that can nonetheless be solved accurately. SCE reflects this. Moreover, SCE when applied to solving very large linear systems by iterative solvers, including conjugate gradient and multigrid methods, performs equally well and various examples are given to illustrate the performance. SCE for solving large linear systems with direct methods, such as methods for semi‐separable structures, are also investigated. In all cases, the advantages of using SCE are manifold: ease of use, efficiency, and reliability. Copyright © 2008 John Wiley & Sons, Ltd.     

New perturbation bounds and condition numbers for the hyperbolic QR factorization

Using the modified matrix-vector equation approach, the technique of Lyapunov majorant function and the Banach fixed point theorem, we obtain some new rigorous perturbation bounds for R factor of the hyperbolic QR factorization under normwise perturbation. These bounds are always tighter than the one given in the literature. Moreover, the optimal first-order perturbation bounds and the normwise condition numbers for the hyperbolic QR factorization are also presented.     

On Frobenius normwise condition numbers for Moore–Penrose inverse and linear least‐squares problems

Condition numbers play an important role in numerical analysis. Classical condition numbers are normwise: they measure the size of both input perturbations and output errors using norms. In this paper, we give explicit, computable expressions depending on the data, for the normwise condition numbers for the computation of the Moore–Penrose inverse as well as for the solutions of linear least‐squares problems with full‐column rank. Copyright © 2007 John Wiley & Sons, Ltd.     

Discretization of the Navier‐Stokes equations with slip boundary condition

We propose and analyze a two‐level method of discretizing the nonlinear Navier‐Stokes equations with slip boundary condition. The slip boundary condition is appropriate for problems that involve free boundaries, flows past chemically reacting walls, and other examples where the usual no‐slip condition u = 0 is not valid. The two‐level algorithm consists of solving a small nonlinear system of equations on the coarse mesh and then using that solution to solve a larger linear system on the fine mesh. The two‐level method exploits the quadratic nonlinearity in the Navier‐Stokes equations. Our error estimates show that it has optimal order accuracy, provided that the best approximation to the true solution in the velocity and pressure spaces is bounded above by the data. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17: 26–42, 2001     

Rank partitions and covering numbers under small perturbations of an element

We investigate how the rank partitions and the covering number of the elements can change with arbitrarily small perturbations of a fixed element.     

Condition numbers and perturbation analysis for the Tikhonov regularization of discrete ill‐posed problems

One of the most successful methods for solving the least‐squares problem min_x∥Ax?b∥₂ with a highly ill‐conditioned or rank deficient coefficient matrix A is the method of Tikhonov regularization. In this paper, we derive the normwise, mixed and componentwise condition numbers and componentwise perturbation bounds for the Tikhonov regularization. Our results are sharper than the known results. Some numerical examples are given to illustrate our results. Copyright © 2010 John Wiley & Sons, Ltd.     

Bounds for eigenvalues and condition numbers in the -version of the finite element method

In this paper, we present a theory for bounding the minimum eigenvalues, maximum eigenvalues, and condition numbers of stiffness matrices arising from the -version of finite element analysis. Bounds are derived for the eigenvalues and the condition numbers, which are valid for stiffness matrices based on a set of general basis functions that can be used in the -version. For a set of hierarchical basis functions satisfying the usual local support condition that has been popularly used in the -version, explicit bounds are derived for the minimum eigenvalues, maximum eigenvalues, and condition numbers of stiffness matrices. We prove that the condition numbers of the stiffness matrices grow like , where is the number of dimensions. Our results disprove a conjecture of Olsen and Douglas in which the authors assert that ``regardless of the choice of basis, the condition numbers grow like or faster". Numerical results are also presented which verify that our theoretical bounds are correct.