Structured backward error for palindromic polynomial eigenvalue problems,II: Approximate eigentriplets

A detailed structured backward error analysis for four kinds of palindromic polynomial eigenvalue problems (PPEPs)P(\lambda )\equiv \left({\displaystyle \sum _{l=\mathrm{0}}^d{{\displaystyle A}}_l{\lambda }^l}\right)x=\mathrm{0},{{\displaystyle A}}_{d-l}=\epsilon {{\displaystyle A}}_l^{★},L=\mathrm{0},\mathrm{1},\dots ,\left[{\displaystyle \frac{d}{\mathrm{2}}}\right], for an approximate eigentriplet is performed, where ★ is one of the two actions: transpose and conjugate transpose, and \epsilon \in \{\pm \mathrm{1}\}. The analysis is concerned with estimating the smallest perturbation to P(\lambda); while preserving the respective palindromic structure, such that the given approximate eigentriplet is an exact eigentriplet of the perturbed PPEP. Previously, R. Li, W. Lin, and C. Wang [Numer. Math., 2010, 116(1): 95–122] had only considered the case of an approximate eigenpair for PPEP but commented that attempt for an approximate eigentriplet was unsuccessful. Indeed, the latter case is much more complicated. We provide computable upper bounds for the structured backward errors. Our main results in this paper are several informative and very sharp upper bounds that are capable of revealing distinctive features of PPEP from general polynomial eigenvalue problems (PEPs). In particular, they reveal the critical cases in which there is no structured backward perturbation such that the given approximate eigentriplet becomes an exact one of any perturbed PPEP, unless further additional conditions are imposed. These critical cases turn out to the same as those from the earlier studies on an approximate eigenpair.     

A structure-preserving doubling algorithm for quadratic eigenvalue problems arising from time-delay systems

We propose a structure-preserving doubling algorithm for a quadratic eigenvalue problem arising from the stability analysis of time-delay systems. We are particularly interested in the eigenvalues on the unit circle, which are difficult to estimate. The convergence and backward error of the algorithm are analyzed and three numerical examples are presented. Our experience shows that our algorithm is efficient in comparison to the few existing approaches for small to medium size problems.     

Numerical methods for palindromic eigenvalue problems: Computing the anti‐triangular Schur form

We present structure‐preserving numerical methods for the eigenvalue problem of complex palindromic pencils. Such problems arise in control theory, as well as from palindromic linearizations of higher degree palindromic matrix polynomials. A key ingredient of these methods is the development of an appropriate condensed form—the anti‐triangular Schur form. Ill‐conditioned problems with eigenvalues near the unit circle, in particular near ±1, are discussed. We show how a combination of unstructured methods followed by a structured refinement can be used to solve such problems accurately. Copyright © 2008 John Wiley & Sons, Ltd.     

Exponentially convergent parallel algorithm for nonlinear eigenvalue problems

A. V. Klimenko, V. L. Makarov ^{A new algorithm for nonlinear eigenvalue problems is proposed.The numerical technique is based on a perturbation of the coefficientsof differential equation combined with the Adomian decompositionmethod for the nonlinear part. The approach provides an exponentialconvergence rate with a base which is inversely proportionalto the index of the eigenvalue under consideration. The eigenpairscan be computed in parallel. Numerical examples are presentedto support the theory. They are in good agreement with the spectralasymptotics obtained by other authors.}     

A new look at the doubling algorithm for a structured palindromic quadratic eigenvalue problem

Recently, Guo and Lin [SIAM J. Matrix Anal. Appl., 31 (2010), 2784–2801] proposed an efficient numerical method to solve the palindromic quadratic eigenvalue problem (PQEP) (λ²A^T+λQ + A)z = 0 arising from the vibration analysis of high speed trains, where have special structures: both Q and A are, among others, m × m block matrices with each block being k × k (thus, n = mk), and moreover, Q is block tridiagonal, and A has only one nonzero block in the (1,m)th block position. The key intermediate step of the method is the computation of the so‐called stabilizing solution to the n × n nonlinear matrix equation X + A^TX⁻¹A = Q via the doubling algorithm. The aim of this article is to propose an improvement to this key step through solving a new nonlinear matrix equation having the same form but of only k × k in size. This new and much smaller matrix equation can also be solved by the doubling algorithm. For the same accuracy, it takes the same number of doubling iterations to solve both the larger and the new smaller matrix equations, but each doubling iterative step on the larger equation takes about 4.8 as many flops than the step on the smaller equation. Replacing Guo's and Lin's key intermediate step by our modified one leads to an alternative method for the PQEP. This alternative method is faster, but the improvement in speed is not as dramatic as just for solving the respective nonlinear matrix equations and levels off as m increases. Numerical examples are presented to show the effectiveness of the new method. Copyright © 2014 John Wiley & Sons, Ltd.     

On the need for special purpose algorithms for minimax eigenvalue problems

It has been recently reported that minimax eigenvalue problems can be formulated as nonlinear optimization problems involving smooth objective and constraint functions. This result seems very appealing since minimax eigenvalue problems are known to be typically nondifferentiable. In this paper, we show, however, that general purpose nonlinear optimization algorithms usually fail to find a solution to these smooth problems even in the simple case of minimization of the maximum eigenvalue of an affine family of symmetric matrices, a convex problem for which efficient algorithms are available.This work was supported in part by NSF Engineering Research Centers Program No. NSFD-CDR-88-03012 and NSF Grant DMC-84-20740. The author wishes to thank Drs. M. K. H. Fan and A. L. Tits for their many useful suggestions.     

Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations

In this paper we address the problem of efficiently computing all the eigenvalues of a large N×N Hermitian matrix modified by a possibly non Hermitian perturbation of low rank. Previously proposed fast adaptations of the QR algorithm are considerably simplified by performing a preliminary transformation of the matrix by similarity into an upper Hessenberg form. The transformed matrix can be specified by a small set of parameters which are easily updated during the QR process. The resulting structured QR iteration can be carried out in linear time using linear memory storage. Moreover, it is proved to be backward stable. Numerical experiments show that the novel algorithm outperforms available implementations of the Hessenberg QR algorithm already for small values of N.      

Arnoldi versus nonsymmetric Lanczos algorithms for solving matrix eigenvalue problems

We present theoretical and numerical comparisons between Arnoldi and nonsymmetric Lanczos procedures for computing eigenvalues of nonsymmetric matrices. In exact arithmetic we prove that any type of eigenvalue convergence behavior obtained using a nonsymmetric Lanczos procedure may also be obtained using an Arnoldi procedure but on a different matrix and with a different starting vector. In exact arithmetic we derive relationships between these types of procedures and normal matrices which suggest some interesting questions regarding the roles of nonnormality and of the choice of starting vectors in any characterizations of the convergence behavior of these procedures. Then, through a set of numerical experiments on a complex Arnoldi and on a complex nonsymmetric Lanczos procedure, we consider the more practical question of the behavior of these procedures when they are applied to the same matrices.This work was supported by NSF grant GER-9450081 while the author was visiting the University of Maryland.     

Nonlinear eigenvalue problems for quasilinear equations in unbounded domains

We prove the existence of a solution of the nonlinear equation in IR^N and in exterior domains, respectively. We concentrate to the case when p ≥ N and the nonlinearity f(x, · ) is “superlinear” and “subcritical”.     

Convergence of the Implicit Filtering Method for Constrained Optimization of Noisy Functions

In this paper, we develop convergence theory of the implicit filtering method for solving the box constrained optimization whose objective function includes a smooth term and a noisy term. It is shown that under certain assumption on the noisy function, the sequence of projected gradients on the smooth function produced by the method goes to zero. Moreover, it is shown that if the smooth function is convex and the noisy function decays near optimality, the whole sequence of iterates converges to a solution of the concerned problem and possesses the finite identification for the optimal active set under the nondegenerate assumption. Finally, preliminary numerical results are reported.     

Algorithms for hyperbolic quadratic eigenvalue problems

We consider the quadratic eigenvalue problem (or the QEP) , where and are Hermitian with positive definite. The QEP is called hyperbolic if 4(x^*Ax)(x^*Cx)$"> for all nonzero . We show that a relatively efficient test for hyperbolicity can be obtained by computing the eigenvalues of the QEP. A hyperbolic QEP is overdamped if is positive definite and is positive semidefinite. We show that a hyperbolic QEP (whose eigenvalues are necessarily real) is overdamped if and only if its largest eigenvalue is nonpositive. For overdamped QEPs, we show that all eigenpairs can be found efficiently by finding two solutions of the corresponding quadratic matrix equation using a method based on cyclic reduction. We also present a new measure for the degree of hyperbolicity of a hyperbolic QEP.

     

Local and parallel finite element algorithms for the Steklov eigenvalue problem

Based on the work of Xu and Zhou [Math Comput 69 (2000) 881–909], we propose and analyze in this article local and parallel finite element algorithms for the Steklov eigenvalue problem. We also prove a local error estimate which is suitable for the case that the locally refined region contains singular points lying on the boundary of domain, which is an improvement of the existing results. Numerical experiments are reported finally to validate our theoretical analysis. © 2015 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 399–417, 2016     

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.     

实对称带状矩阵逆特征值问题

研究了一类实对称带状矩阵逆特征值问题：给定三个互异实数λ,μ和v及三个非零实向量x,y和z,分别构造实对称五对角矩阵T和实对称九对角矩阵A,使其都具有特征对(λ,x),(μ,y)和(v,z)．给出了此类问题的两种提法,研究了问题的可解性以及存在惟一解的充分必要条件,最后给出了数值算法和数值例子．     

Multiple nontrivial solutions for nonlinear eigenvalue problems

In this paper we study a nonlinear eigenvalue problem driven by the -Laplacian. Assuming for the right-hand side nonlinearity only unilateral and sign conditions near zero, we prove the existence of three nontrivial solutions, two of which have constant sign (one is strictly positive and the other is strictly negative), while the third one belongs to the order interval formed by the two opposite constant sign solutions. The approach relies on a combination of variational and minimization methods coupled with the construction of upper-lower solutions. The framework of the paper incorporates problems with concave-convex nonlinearities.

     

An inexact inverse iteration for large sparse eigenvalue problems

In this paper, we propose an inverse inexact iteration method for the computation of the eigenvalue with the smallest modulus and its associated eigenvector for a large sparse matrix. The linear systems of the traditional inverse iteration are solved with accuracy that depends on the eigenvalue with the second smallest modulus and iteration numbers. We prove that this approach preserves the linear convergence of inverse iteration. We also propose two practical formulas for the accuracy bound which are used in actual implementation. © 1997 John Wiley & Sons, Ltd.     

Rellich type identities for eigenvalue problems and application to the Pompeiu problem

For classical Neumann eigenvalue, buckling eigenvalue and clamped plate eigenvalue, we give the corresponding Rellich type identities. As an application of these results, then, we obtain a new necessary and sufficient condition for a domain without the Pompeiu property.     

Adaptive finite element algorithms for eigenvalue problems based on local averaging type a posteriori error estimates

The local averaging technique has become a popular tool in adaptive finite element methods for solving partial differential boundary value problems since it provides efficient a posteriori error estimates by a simple postprocessing. In this paper, the technique is introduced to solve a class of symmetric eigenvalue problems. Its efficiency and reliability are proved by both the theory and numerical experiments structured meshes as well as irregular meshes. Dedicated to Charles A. Micchelli on his 60th birthday Mathematics subject classifications (2000) 65N15, 65N25, 65N30, 65N50. Subsidized by the Special Funds for Major State Basic Research Projects, and also supported in part by the Chinese National Natural Science Foundation and the Knowledge Innovation Program of the Chinese Academy of Sciences.