Numerical solution of eigenvalue problems for Hamiltonian systems

This paper discusses the numerical solution of eigenvalue problems for Hamiltonian systems of ordinary differential equations. Two new codes are presented which incorporate the algorithms described here; to the best of the author’s knowledge, these are the first codes capable of solving numerically such general eigenvalue problems. One of these implements a new new method of solving a differential equation whose solution is a unitary matrix. Both codes are fully documented and are written inPfort-verifiedFortran 77, and will be available in netlib/aicm/sl11f and netlib/aicm/sl12f.     

Steady-state and Hopf bifurcations in the Langford ODE and PDE systems

This paper is concerned with the Langford ODE and PDE systems. For the Langford ODE system, the existence of steady-state solutions is firstly obtained by Lyapunov–Schmidt method, and the stability and bifurcation direction of periodic solutions are established. Then for the Langford PDE system, the steady-state bifurcations from simple and double eigenvalues are intensively studied. The techniques of space decomposition and implicit function theorem are adopted to deal with the case of double eigenvalue. Finally, by the center manifold theory and the normal form method, the direction of Hopf bifurcation and the stability of spatially homogeneous and inhomogeneous periodic solutions for the PDE system are investigated.     

Method of solving the generalized problem on eigenvalues of multidimensional circuits, I

This work is devoted to the development of a new method for solving the complete generalized problem of large-scale electrical circuit eigenvalues. We prove that the determinant of the conductance node matrix of an arbitrary k-loop LC-circuit is the Weinstein function for the loop impendance matrix of this circuit, and vice versa. A recurrent method of imposing constraints on the basic problem was defined, which permitted us to separate roots of characteristic polynomials in the recurrent process. Also a condition for conservativity of multiple eigenvalues was defined. A solution algorithm for the problem of defining a full range of eigenvalues of an oscillatory system with a finite number of degrees of freedom was suggested.     

Integrable discrete hungry systems and their related matrix eigenvalues

Recently, some of the authors designed an algorithm, named the dhLV algorithm, for computing complex eigenvalues of a certain class of band matrix. The recursion formula of the dhLV algorithm is based on the discrete hungry Lotka–Volterra (dhLV) system, which is an integrable system. One of the authors has proposed an algorithm, named the multiple dqd algorithm, for computing eigenvalues of a totally nonnegative (TN) band matrix. In this paper, by introducing a theorem on matrix eigenvalues, we first show that the eigenvalues of a TN matrix are also computable by the dhLV algorithm. We next clarify the asymptotic behavior of the discrete hungry Toda (dhToda) equation, which is also an integrable system, and show that a similarity transformation for a TN matrix is given through the dhToda equation. Then, by combining these properties of the dhToda equation, we design a new algorithm, named the dhToda algorithm, for computing eigenvalues of a TN matrix. We also describe the close relationship among the above three algorithms and give numerical examples.     

Extracting partial canonical structure for large scale eigenvalue problems

We present methods for computing a nearby partial Jordan-Schur form of a given matrix and a nearby partial Weierstrass-Schur form of a matrix pencil. The focus is on the use and the interplay of the algorithmic building blocks – the implicitly restarted Arnoldi method with prescribed restarts for computing an invariant subspace associated with the dominant eigenvalue, the clustering method for grouping computed eigenvalues into numerically multiple eigenvalues and the staircase algorithm for computing the structure revealing form of the projected problem. For matrix pencils, we present generalizations of these methods. We introduce a new and more accurate clustering heuristic for both matrices and matrix pencils. Particular emphasis is placed on reliability of the partial Jordan-Schur and Weierstrass-Schur methods with respect to the choice of deflation parameters connecting the steps of the algorithm such that the errors are controlled. Finally, successful results from computational experiments conducted on problems with known canonical structure and varying ill-conditioning are presented. This revised version was published online in June 2006 with corrections to the Cover Date.     

Approximate inverse preconditioner by computing approximate solution of Sylvester equation

This paper presents a new method for obtaining a matrix M which is an approximate inverse preconditioner for a given matrix A, where the eigenvalues of A all either have negative real parts or all have positive real parts. This method is based on the approximate solution of the special Sylvester equation AX + XA = 2I. We use a Krylov subspace method for obtaining an approximate solution of this Sylvester matrix equation which is based on the Arnoldi algorithm and on an integral formula. The computation of the preconditioner can be carried out in parallel and its implementation requires only the solution of very simple and small Sylvester equations. The sparsity of the preconditioner is preserved by using a proper dropping strategy. Some numerical experiments on test matrices from Harwell–Boing collection for comparing the numerical performance of the new method with an available well-known algorithm are presented.     

AN IMPROVEMENT ON THE QL ALGORITHM FOR SYMMETRIC TRIDIAGONAL MATRICES*

This paper establishes an improvement on the QL algorithm for a symmetric tridiagonal matrix T so that we can work out the eigenvalues of T faster. Meanwhile, the new algorithm don't worsen the stability and precision of the former algorithm.     

Continuous methods for extreme and interior eigenvalue problems

In this paper, continuous methods are introduced to compute both the extreme and interior eigenvalues and their corresponding eigenvectors for real symmetric matrices. The main idea is to convert the extreme and interior eigenvalue problems into some optimization problems. Then a continuous method which includes both a merit function and an ordinary differential equation (ODE) is introduced for each resulting optimization problem. The convergence of each ODE solution is proved for any starting point. The limit of each ODE solution for any starting point is fully studied. Both the extreme and the interior eigenvalues and their corresponding eigenvectors can be easily obtained under a very mild condition. Promising numerical results are also presented.     

On computation of real eigenvalues of matrices via the Adomian decomposition

The problem of matrix eigenvalues is encountered in various fields of engineering endeavor. In this paper, a new approach based on the Adomian decomposition method and the Faddeev-Leverrier’s algorithm is presented for finding real eigenvalues of any desired real matrices. The method features accuracy and simplicity. In contrast to many previous techniques which merely afford one specific eigenvalue of a matrix, the method has the potential to provide all real eigenvalues. Also, the method does not require any initial guesses in its starting point unlike most of iterative techniques. For the sake of illustration, several numerical examples are included.     

求解矩阵方程AXB+CXD=F参数迭代法的最优参数分析

本文针对求矩阵方程AXB+CXD=F唯一解的参数迭代法，分析当矩阵A，B，C，D均是Hermite正（负）定矩阵时，迭代矩阵的特征值表达式，给出了最优参数的确定方法，并提出了相应的加速算法.     

矩阵特征值的一类新的包含域

用盖尔圆盘定理来估计矩阵的特征值是一个经典的方法,这种方法仅利用矩阵的元素来确定特征值的分布区域.本文利用相似矩阵有相同的特征值这一理论,得到了矩阵特征值的一类新的包含域,它们与盖尔圆盘等方法结合起来能提高估计的精确度.     

A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity

A restarted Arnoldi algorithm is given that computes eigenvalues and eigenvectors. It is related to implicitly restarted Arnoldi, but has a simpler restarting approach. Harmonic and regular Rayleigh-Ritz versions are possible.For multiple eigenvalues, an approach is proposed that first computes eigenvalues with the new harmonic restarted Arnoldi algorithm, then uses random restarts to determine multiplicity. This avoids the need for a block method or for relying on roundoff error to produce the multiple copies.     

A new approach for calculating the real stability radius

We present a new fast algorithm to compute the real stability radius with respect to the open left half plane which is an important problem in many engineering applications. The method is based on a well-known formula for the real stability radius and the correspondence of singular values of a transfer function to pure imaginary eigenvalues of a three-parameter Hamiltonian matrix eigenvalue problem. We then apply the implicit determinant method, used previously by the authors to compute the complex stability radius, to find the critical point corresponding to the desired singular value. This corresponds to a two-dimensional Jordan block for a pure imaginary eigenvalue in the parameter dependent Hamiltonian matrix. Numerical results showing quadratic convergence of the algorithm are given.     

Construction of Real Band Anti-Symmetric Matrices from Spectral Data

In this paper,we describe how to construct a real anti-symmetric(2p-1)-band matrix with prescribed eigenvalues in its ρ leading principal submatrices.This is done in two steps.First,an anti-symmetric matrix B is constructed with the specified spectral data but not necessary a band matrix.Then B is transformed by Householder transformations to a (2ρ-1)-band matrix with the prescribed eigenvalues.An algorithm is presented.Numerical results are presented to demonstrate that the proposed method is effective.     

Résolution de problèmes hyperélastiques de recalage d'imagesResolution of some hyperelastic image-matching problems

We focus on some image-matching problems that are based on hyperelastic strain energies. We design an algorithm that solves numerically the Euler–Lagrange equations associated to the problem. This algorithm is formulated in terms of an ODE (Ordinary Differential Equation). We give a theorem which states that the ODE has a unique solution and converges to a solution of the Euler–Lagrange equations. To cite this article: F.J.P. Richard, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 295–299.     

A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems

The global Arnoldi method can be used to compute exterior eigenpairs of a large non-Hermitian matrix A, but it does not work well for interior eigenvalue problems. Based on the global Arnoldi process that generates an F-orthonormal basis of a matrix Krylov subspace, we propose a global harmonic Arnoldi method for computing certain harmonic F-Ritz pairs that are used to approximate some interior eigenpairs. We propose computing the F-Rayleigh quotients of the large non-Hermitian matrix with respect to harmonic F-Ritz vectors and taking them as new approximate eigenvalues. They are better and more reliable than the harmonic F-Ritz values. The global harmonic Arnoldi method inherits convergence properties of the harmonic Arnoldi method applied to a larger matrix whose distinct eigenvalues are the same as those of the original given matrix. Some properties of the harmonic F-Ritz vectors are presented. As an application, assuming that A is diagonalizable, we show that the global harmonic Arnoldi method is able to solve multiple eigenvalue problems both in theory and in practice. To be practical, we develop an implicitly restarted global harmonic Arnoldi algorithm with certain harmonic F-shifts suggested. In particular, this algorithm can be adaptively used to solve multiple eigenvalue problems. Numerical experiments show that the algorithm is efficient for the eigenproblem and is reliable for quite ill-conditioned multiple eigenproblems.     

求解Hamilton矩阵特征值问题的一种新方法

Hamilton矩阵的特征值问题常出现在控制理论的范畴中.在最优控制系统的设计中,若状态方程为     

Solving ODEs arising from non‐selfadjoint Hamiltonian eigenproblems

We consider three numerical methods – one based on power series, one on the Magnus series and matrix exponentials, and one a library initial value code – for solving a linear system arising in non‐selfadjoint ODE eigenproblems. We show that in general, none of these methods has a cost or an accuracy which is uniform in the eigenparameter, but that for certain special types of problem, the Magnus method does yield eigenparameter‐uniform accuracy. This property of the Magnus method is explained by a trajectory‐shadowing result which, unfortunately, does not generalize to higher order Magnus type methods such as those in [11,12]. This revised version was published online in June 2006 with corrections to the Cover Date.     

A Dai-Liao conjugate gradient algorithm with clustering of eigenvalues

A new value for the parameter in Dai and Liao conjugate gradient algorithm is presented. This is based on the clustering of eigenvalues of the matrix which determine the search direction of this algorithm. This value of the parameter lead us to a variant of the Dai and Liao algorithm which is more efficient and more robust than the variants of the same algorithm based on minimizing the condition number of the matrix associated to the search direction. Global convergence of this variant of the algorithm is briefly discussed.