On linearizations of the quadratic two-parameter eigenvalue problem

We present several transformations that can be used to solve the quadratic two-parameter eigenvalue problem (QMEP), by formulating an associated linear multiparameter eigenvalue problem. Two of these transformations are generalizations of the well-known linearization of the quadratic eigenvalue problem and linearize the QMEP as a singular two-parameter eigenvalue problem. The third replaces all nonlinear terms by new variables and adds new equations for their relations. The QMEP is thus transformed into a nonsingular five-parameter eigenvalue problem. The advantage of these transformations is that they enable one to solve the QMEP using existing numerical methods for multiparameter eigenvalue problems. We also consider several special cases of the QMEP, where some matrix coefficients are zero     

The solution methods for the largest eigenvalue (singular value) of nonnegative tensors and convergence analysis

In this paper we study two solution methods for finding the largest eigenvalue (singular value) of general square (rectangular) nonnegative tensors. For a positive tensor, one can find the largest eigenvalue (singular value) based on the properties of the positive tensor and the power-type method. While for a general nonnegative tensor, we use a series of decreasing positive perturbations of the original tensor and repeatedly recall power-type method for finding the largest eigenvalue (singular value) of a positive tensor with an inexact strategy. We prove the convergence of the method for the general nonnegative tensor. Under a certain assumption, the computing complexity of the method is established. Motivated by the interior-point method for the convex optimization, we put forward a one-step inner iteration power-type method, whose convergence is also established under certain assumption. Additionally, by using embedding technique, we show the relationship between the singular values of the rectangular tensor and the eigenvalues of related square tensor, which suggests another way for finding the largest singular value of nonnegative rectangular tensor besides direct power-type method for this problem. Finally, numerical examples of our algorithms are reported, which demonstrate the convergence behaviors of our methods and show that the algorithms presented are promising.     

Trimmed linearizations for structured matrix polynomials

We discuss the eigenvalue problem for general and structured matrix polynomials which may be singular and may have eigenvalues at infinity. We derive condensed forms that allow (partial) deflation of the infinite eigenvalue and singular structure of the matrix polynomial. The remaining reduced order staircase form leads to new types of linearizations which determine the finite eigenvalues and corresponding eigenvectors. The new linearizations also simplify the construction of structure preserving linearizations.     

Krylov type subspace methods for matrix polynomials

We consider solving eigenvalue problems or model reduction problems for a quadratic matrix polynomial Iλ² − Aλ − B with large and sparse A and B. We propose new Arnoldi and Lanczos type processes which operate on the same space as A and B live and construct projections of A and B to produce a quadratic matrix polynomial with the coefficient matrices of much smaller size, which is used to approximate the original problem. We shall apply the new processes to solve eigenvalue problems and model reductions of a second order linear input-output system and discuss convergence properties. Our new processes are also extendable to cover a general matrix polynomial of any degree.     

A backward error for the inverse singular value problem

A backward error for inverse singular value problems with respect to an approximate solution is defined, and an explicit expression for the backward error is derived by extending the approach described in [J.G. Sun, Backward errors for the inverse eigenvalue problem, Numer. Math. 82 (1999) 339-349]. The expression may be useful for testing the stability of practical algorithms.     

The automatic solution of two-parameter Sturm-Liouville eigenvalue problems in ordinary differential equations

An algorithm is described for the numerical solution of quite general two-parameter eigenvalue problems, whether singular or not. The scheme is completely automatic. Even the usual requirement of an initial guess is not needed. The scheme is based on the solution of suitable initial-value problems or “shooting”.     

非线性特征值问题的二次近似方法

本文研究求解非线性特征值问题的数值方法.基于矩阵值函数的二次近似,将非线性特征值问题转化为二次特征值问题,提出了求解非线性特征值问题的逐次二次近似方法,分析了该方法的收敛性.结合求解二次特征值问题的Arnoldi方法和Jacobi-Davidson方法,给出求解非线性特征值问题的一些二次近似方法.数值结果表明本文所给算法是有效的.     

Existence of an extremal ground state energy of a nanostructured quantum dot

This paper is concerned with two rearrangement optimization problems. These problems are motivated by two eigenvalue problems which depend nonlinearly on the eigenvalues. We consider a rational and a quadratic eigenvalue problem with Dirichlet’s boundary condition and investigate two related optimization problems where the goal function is the corresponding first eigenvalue. The first eigenvalue in the rational eigenvalue problem represents the ground state energy of a nanostructured quantum dot. In both the problems, the admissible set is a rearrangement class of a given function.     

Solving inverse eigenvalue problems via Householder and rank-one matrices

A brief and practical algorithm is introduced to solve symmetric inverse eigenvalue problems, which we call HROU algorithm. The algorithm is based on Householder transformations and rank one updating. We give some basic properties and the computational amount and develop sensitivity analysis of HROU algorithm. Furthermore, we develop HROU algorithm into a multi-level and adaptive one, named MLAHROU, to solve symmetric nonnegative inverse eigenvalue problems. New sufficient conditions to ensure symmetric nonnegative matrices and symmetric M-matrices are given. Many numerical examples are given to verify our theory, compare with existing results and show the efficiency of our algorithms.     

On the numerical treatment of the eigenparameter dependent boundary conditions

In this paper, we consider the numerical treatment of singular eigenvalue problems supplied with eigenparameter dependent boundary conditions using spectral methods. On the one hand, such boundary conditions hinder the construction of test and trial space functions which could incorporate them and thus providing well-conditioned Galerkin discretization matrices. On the other hand, they can generate surprising behavior of the eigenvectors hardly detected by analytic methods. These singular problems are often indirectly approximated by regular ones. We argue that spectral collocation as well as tau method offer remedies for the first two issues and provide direct and efficient treatment to such problems. On a finite domain, we consider the so-called Petterson-König’s rod eigenvalue problem and on the half line, we take into account the Charney’s baroclinic stability problem and the Fourier eigenvalue problem. One boundary condition in these problems depends on the eigenparameter and additionally, this also could depend on some physical parameters. The Chebyshev collocation based on both, square and rectangular differentiation and a Chebyshev tau method are used to discretize the first problem. All these schemes cast the problems into singular algebraic generalized eigenvalue ones which are solved by the QZ and/or Arnoldi algorithms as well as by some target oriented Jacobi-Davidson methods. Thus, the spurious eigenvalues are completely eliminated. The accuracy of square Chebyshev collocation is roughly estimated and its order of approximation with respect to the eigenvalue of interest is determined. For the problems defined on the half line, we make use of the Laguerre-Gauss-Radau collocation. The method proved to be reliable, accurate, and stable with respect to the order of approximation and the scaling parameter.     

A Jacobi matrix inverse eigenvalue problem with mixed data

In this paper, the inverse eigenvalue problem of reconstructing a Jacobi matrix from part of its eigenvalues and its leading principal submatrix is considered. The necessary and sufficient conditions for the existence and uniqueness of the solution are derived. Furthermore, a numerical algorithm and some numerical examples are given.     

Solutions to an inverse monic quadratic eigenvalue problem

Given n+1 pairs of complex numbers and vectors (closed under complex conjugation), the inverse quadratic eigenvalue problem is to construct real symmetric or anti-symmetric matrix C and real symmetric matrix K of size n×n so that the quadratic pencil Q(λ)=λ²I_n+λC+K has the given n+1 pairs as eigenpairs. Necessary and sufficient conditions under which this quadratic inverse eigenvalue problem is solvable are obtained. Numerical algorithms for solving the problem are developed. Numerical examples illustrating these solutions are presented.     

Vector space of linearizations for the quadratic two-parameter matrix polynomial

Given a quadratic two-parameter matrix polynomial Q(λ,?μ), we develop a systematic approach to generating a vector space of linear two-parameter matrix polynomials. The purpose for constructing this vector space is that potential linearizations of Q(λ,?μ) lie in it. Then, we identify a set of linearizations and describe their constructions. Finally, we determine a class of linearizations for a quadratic two-parameter eigenvalue problem.     

A method based on Rayleigh quotient gradient flow for extreme and interior eigenvalue problems

Recently, a continuous method has been proposed by Golub and Liao as an alternative way to solve the minimum and interior eigenvalue problems. According to their numerical results, their method seems promising. This article is an extension along this line. In this article, firstly, we convert an eigenvalue problem to an equivalent constrained optimization problem. Secondly, using the Karush-Kuhn-Tucker conditions of this equivalent optimization problem, we obtain a variant of the Rayleigh quotient gradient flow, which is formulated by a system of differential-algebraic equations. Thirdly, based on the Rayleigh quotient gradient flow, we give a practical numerical method for the minimum and interior eigenvalue problems. Finally, we also give some numerical experiments of our method, the Golub and Liao method, and EIGS (a Matlab implementation for computing eigenvalues using restarted Arnoldi’s method) for some typical eigenvalue problems. Our numerical experiments indicate that our method seems promising for most test problems.     

Backward errors for eigenvalue and singular value decompositions

Summary. We present bounds on the backward errors for the symmetric eigenvalue decomposition and the singular value decomposition in the two-norm and in the Frobenius norm. Through different orthogonal decompositions of the computed eigenvectors we can define different symmetric backward errors for the eigenvalue decomposition. When the computed eigenvectors have a small residual and are close to orthonormal then all backward errors tend to be small. Consequently it does not matter how exactly a backward error is defined and how exactly residual and deviation from orthogonality are measured. Analogous results hold for the singular vectors. We indicate the effect of our error bounds on implementations for eigenvector and singular vector computation. In a more general context we prove that the distance of an appropriately scaled matrix to its orthogonal QR factor is not much larger than its distance to the closest orthogonal matrix. Received July 19, 1993     

Algorithmic copositivity detection by simplicial partition

We present new criteria for copositivity of a matrix, i.e., conditions which ensure that the quadratic form induced by the matrix is nonnegative over the nonnegative orthant. These criteria arise from the representation of the quadratic form in barycentric coordinates with respect to the standard simplex and simplicial partitions thereof. We show that, as the partition gets finer and finer, the conditions eventually capture all strictly copositive matrices. We propose an algorithmic implementation which considers several numerical aspects. As an application, we present results on the maximum clique problem. We also briefly discuss extensions of our approach to copositivity with respect to arbitrary polyhedral cones.     

Structured eigenvalue condition numbers and linearizations for matrix polynomials

This work is concerned with eigenvalue problems for structured matrix polynomials, including complex symmetric, Hermitian, even, odd, palindromic, and anti-palindromic matrix polynomials. Most numerical approaches to solving such eigenvalue problems proceed by linearizing the matrix polynomial into a matrix pencil of larger size. Recently, linearizations have been classified for which the pencil reflects the structure of the original polynomial. A question of practical importance is whether this process of linearization significantly increases the eigenvalue sensitivity with respect to structured perturbations. For all structures under consideration, we show that this cannot happen if the matrix polynomial is well scaled: there is always a structured linearization for which the structured eigenvalue condition number does not differ much. This implies, for example, that a structure-preserving algorithm applied to the linearization fully benefits from a potentially low structured eigenvalue condition number of the original matrix polynomial.     

A Newton iteration process for inverse eigenvalue problems

Summary We suppose an inverse eigenvalue problem which includes the classical additive and multiplicative inverse eigenvalue problems as special cases. For the numerical solution of this problem we propose a Newton iteration process and compare it with a known method. Finally we apply it to a numerical example.     

Discretization methods for the solution of semi-infinite programming problems

In the first part of this paper, we prove the convergence of a class of discretization methods for the solution of nonlinear semi-infinite programming problems, which includes known methods for linear problems as special cases. In the second part, we modify and study this type of algorithms for linear problems and suggest a specific method which requires the solution of a quadratic programming problem at each iteration. With this algorithm, satisfactory results can also be obtained for a number of singular problems. We demonstrate the performance of the algorithm by several numerical examples of multivariate Chebyshev approximation problems.     

求解右定两参数特征值问题的精化Jacobi-Davidson方法(英文)

在文献[1]中,作者M E Hochstenbach和B Plestenjak认为精化的方法不适合两参数特征值问题,原因是求解两参数特征值问题的精化方法存在着三个问题:即精化Ritz向量收敛性差,运算量大,不能计算多个特征值.本文指出,事实并非如此.针对右定两参数特征值问题,本文提出了一种有效的精化数值方法.并通过理论证明和数值实验说明了Ritz值的收敛性,以及精化Ritz向量具有比通常的Ritz向量更好的收敛性.