A Riemannian inexact Newton‐CG method for stochastic inverse singular value problems

In this article, we consider the stochastic inverse singular value problem (ISVP) of constructing a stochastic matrix from the prescribed realizable singular values. We propose a Riemannian inexact Newton‐CG method with various choices of forcing terms for solving the stochastic ISVP. We show the proposed method converges linearly or superlinearly for different forcing terms under some assumptions. We also extend the proposed method to the case of prescribed entries. Finally, we report some numerical results to demonstrate the effectiveness of the proposed method. MOS SUBJECT CLASSIFICATION 65F18; 65F15; 15A18; 65K05; 90C26; 90C48     

An inverse eigenvalue method for frequency isolation in spring–mass systems

The action of external vibrating forces on mechanical structures can cause severe damages when resonance occurs. The removal of natural frequencies of the structure from resonance bands is therefore of great importance. This problem is called frequency isolation problem and is the subject of this paper. A new inverse eigenvalue method is proposed and applied to spring–mass systems, which have generated much interest in the literature as prototypes of vibrating structures. The novelty of the method lies in using the zeros of the frequency response function at the last mass as control variables in an optimization problem to minimize the impact of redesign. Numerically accurate algorithms for computing the sensitivity with respect to the control variables are presented, which form the basis of an efficient multidimensional search strategy to solve the frequency isolation problem. Copyright © 2001 by John Wiley & Sons, Ltd.     

Homogenization of eigenvalue problem for Laplace–Beltrami operator on Riemannian manifold with complicated ‘bubble‐like’ microstructure

We study the asymptotic behavior of the eigenvalues and the eigenfunctions of the Laplace–Beltrami operator on a Riemannian manifold M^ε depending on a small parameter ε>0 and whose structure becomes complicated as ε→0. Under a few assumptions on scales of M^ε we obtain the homogenized eigenvalue problem. In addition we study the behavior of the heat equation on M^ε and investigate the large time behavior of the homogenized equation. Copyright © 2009 John Wiley & Sons, Ltd.     

A new,globally convergent Riemannian conjugate gradient method

This article deals with the conjugate gradient method on a Riemannian manifold with interest in global convergence analysis. The existing conjugate gradient algorithms on a manifold endowed with a vector transport need the assumption that the vector transport does not increase the norm of tangent vectors, in order to confirm that generated sequences have a global convergence property. In this article, the notion of a scaled vector transport is introduced to improve the algorithm so that the generated sequences may have a global convergence property under a relaxed assumption. In the proposed algorithm, the transported vector is rescaled in case its norm has increased during the transport. The global convergence is theoretically proved and numerically observed with examples. In fact, numerical experiments show that there exist minimization problems for which the existing algorithm generates divergent sequences, but the proposed algorithm generates convergent sequences.     

A Ulm-like method for inverse eigenvalue problems

We propose a Ulm-like method for solving inverse eigenvalue problems, which avoids solving approximate Jacobian equations comparing with other known methods. A convergence analysis of this method is provided and the R-quadratic convergence property is proved under the assumption of the distinction of given eigenvalues. Numerical experiments as well as the comparison with the inexact Newton-like method are given in the last section.     

A stability analysis of the jacobi matrix inverse eigenvalue problem

In this paper, we give a perturbation bound for the solution of the Jacobi matrix inverse eigenvalue problem.China State Major Key Project for Basic Researches.     

Determination of space‐dependent coefficients from temperature measurements using the conjugate gradient method

In this article, we consider coefficient identification problems in heat transfer concerned with the determination of the space‐dependent perfusion coefficient and/or thermal conductivity from interior temperature measurements using the conjugate gradient method (CGM). We establish the direct, sensitivity and adjoint problems and the iterative CGM algorithm which has to be stopped according to the discrepancy principle in order to reconstruct a stable solution for the inverse problem. The Sobolev gradient concept is introduced in the CGM iterative algorithm in order to improve the reconstructions. The numerical results illustrated for both exact and noisy data, in one‐ and two‐dimensions for single or double coefficient identifications show that the CGM is an efficient and stable method of inversion.     

Combination of Jacobi–Davidson and conjugate gradients for the partial symmetric eigenproblem

To compute the smallest eigenvalues and associated eigenvectors of a real symmetric matrix, we consider the Jacobi–Davidson method with inner preconditioned conjugate gradient iterations for the arising linear systems. We show that the coefficient matrix of these systems is indeed positive definite with the smallest eigenvalue bounded away from zero. We also establish a relation between the residual norm reduction in these inner linear systems and the convergence of the outer process towards the desired eigenpair. From a theoretical point of view, this allows to prove the optimality of the method, in the sense that solving the eigenproblem implies only a moderate overhead compared with solving a linear system. From a practical point of view, this allows to set up a stopping strategy for the inner iterations that minimizes this overhead by exiting precisely at the moment where further progress would be useless with respect to the convergence of the outer process. These results are numerically illustrated on some model example. Direct comparison with some other eigensolvers is also provided. Copyright © 2001 John Wiley & Sons, Ltd.     

The conjugate gradient method for computing all the extremal stationary probability vectors of a stochastic matrix

Summary The conjugate gradient method is developed for computing stationary probability vectors of a large sparse stochastic matrixP, which often arises in the analysis of queueing system. When unit vectors are chosen as the initial vectors, the iterative method generates all the extremal probability vectors of the convex set formed by all the stationary probability vectors ofP, which are expressed in terms of the Moore-Penrose inverse of the matrix (P−I). A numerical method is given also for classifying the states of the Markov chain defined byP. One particular advantage of this method is to handle a very large scale problem without resorting to any special form ofP. The Institute of Statistical Mathematics     

Two‐step Newton‐type methods for solving inverse eigenvalue problems

In this paper, we apply the two‐step Newton method to solve inverse eigenvalue problems, including exact Newton, Newton‐like, and inexact Newton‐like versions. Our results show that both two‐step Newton and two‐step Newton‐like methods converge cubically, and the two‐step inexact Newton‐like method is super quadratically convergent. Numerical implementations demonstrate the effectiveness of new algorithms.     

Preconditioned conjugate gradient method for generalized least squares problems

A variant of the preconditioned conjugate gradient method to solve generalized least squares problems is presented. If the problem is min (Ax − b)^TW⁻¹(Ax − b) with A ∈ R^m×n and W ∈ R^m×m symmetric and positive definite, the method needs only a preconditioner A₁ ∈ R^n×n, but not the inverse of matrix W or of any of its submatrices. Freund's comparison result for regular least squares problems is extended to generalized least squares problems. An error bound is also given.     

A Jacobi–Davidson method for two‐real‐parameter nonlinear eigenvalue problems arising from delay‐differential equations

The critical delays of a delay‐differential equation can be computed by solving a nonlinear two‐parameter eigenvalue problem. The solution of this two‐parameter problem can be translated to solving a quadratic eigenvalue problem of squared dimension. We present a structure preserving QR‐type method for solving such quadratic eigenvalue problem that only computes real‐valued critical delays; that is, complex critical delays, which have no physical meaning, are discarded. For large‐scale problems, we propose new correction equations for a Newton‐type or Jacobi–Davidson style method, which also forces real‐valued critical delays. We present three different equations: one real‐valued equation using a direct linear system solver, one complex valued equation using a direct linear system solver, and one Jacobi–Davidson style correction equation that is suitable for an iterative linear system solver. We show numerical examples for large‐scale problems arising from PDEs. Copyright © 2012 John Wiley & Sons, Ltd.     

一种求解非线性无约束优化问题的充分下降的共轭梯度法

共轭梯度法是一类具有广泛应用的求解大规模无约束优化问题的方法. 提出了一种新的非线性共轭梯度(CG)法,理论分析显示新算法在多种线搜索条件下具有充分下降性. 进一步证明了新CG算法的全局收敛性定理. 最后,进行了大量数值实验,其结果表明与传统的几类CG方法相比,新算法具有更为高效的计算性能.     

Jacobi–Davidson methods for cubic eigenvalue problems

Several Jacobi–Davidson type methods are proposed for computing interior eigenpairs of large‐scale cubic eigenvalue problems. To successively compute the eigenpairs, a novel explicit non‐equivalence deflation method with low‐rank updates is developed and analysed. Various techniques such as locking, search direction transformation, restarting, and preconditioning are incorporated into the methods to improve stability and efficiency. A semiconductor quantum dot model is given as an example to illustrate the cubic nature of the eigenvalue system resulting from the finite difference approximation. Numerical results of this model are given to demonstrate the convergence and effectiveness of the methods. Comparison results are also provided to indicate advantages and disadvantages among the various methods. Copyright © 2004 John Wiley & Sons, Ltd.     

A note on the efficiency of the conjugate gradient method for a class of time‐dependent problems

We discuss the efficiency of the conjugate gradient (CG) method for solving a sequence of linear systems; Auⁿ⁺¹ = uⁿ, where A is assumed to be sparse, symmetric, and positive definite. We show that under certain conditions the Krylov subspace, which is generated when solving the first linear system Au¹ = u⁰, contains the solutions {uⁿ} for subsequent time steps. The solutions of these equations can therefore be computed by a straightforward projection of the right‐hand side onto the already computed Krylov subspace. Our theoretical considerations are illustrated by numerical experiments that compare this method with the order‐optimal scheme obtained by applying the multigrid method as a preconditioner for the CG‐method at each time step. Copyright © 2007 John Wiley & Sons, Ltd.     

On inverse eigenvalue problems for block Toeplitz matrices with Toeplitz blocks

We propose an algorithm for solving the inverse eigenvalue problem for real symmetric block Toeplitz matrices with symmetric Toeplitz blocks. It is based upon an algorithm which has been used before by others to solve the inverse eigenvalue problem for general real symmetric matrices and also for Toeplitz matrices. First we expose the structure of the eigenvectors of the so-called generalized centrosymmetric matrices. Then we explore the properties of the eigenvectors to derive an efficient algorithm that is able to deliver a matrix with the required structure and spectrum. We have implemented our ideas in a Matlab code. Numerical results produced with this code are included.     

A stochastic conjugate gradient method for the approximation of functions

A stochastic conjugate gradient method for the approximation of a function is proposed. The proposed method avoids computing and storing the covariance matrix in the normal equations for the least squares solution. In addition, the method performs the conjugate gradient steps by using an inner product that is based on stochastic sampling. Theoretical analysis shows that the method is convergent in probability. The method has applications in such fields as predistortion for the linearization of power amplifiers.     

A solution of the affine quadratic inverse eigenvalue problem

The quadratic inverse eigenvalue problem (QIEP) is to find the three matrices M,C, and K, given a set of numbers, closed under complex conjugations, such that these numbers become the eigenvalues of the quadratic pencil P(λ)=λ²M+λC+K. The affine inverse quadratic eigenvalue problem (AQIEP) is the QIEP with an additional constraint that the coefficient matrices belong to an affine family, that is, these matrices are linear combinations of substructured matrices. An affine family of matrices very often arise in vibration engineering modeling and analysis. Research on QIEP and AQIEP are still at developing stage. In this paper, we propose three methods and the associated mathematical theories for solving AQIEP: A Newton method, an alternating projections method, and a hybrid method combining the two. Validity of these methods are illustrated with results on numerical experiments on a spring-mass problem and comparisons are made with these three methods amongst themselves and with another Newton method developed by Elhay and Ram (2002) [12]. The results of our experiments show that the hybrid method takes much smaller number of iterations and converges faster than any of these methods.