QR algorithm with two-sided Rayleigh quotient shifts

We introduce the two-sided Rayleigh quotient shift to the QR algorithm for non-Hermitian matrices to achieve a cubic local convergence rate. For the singly shifted case, the two-sided Rayleigh quotient iteration is incorporated into the QR iteration. A modified version of the method and its truncated version are developed to improve the efficiency. Based on the observation that the Francis double-shift QR iteration is related to a 2D Grassmann–Rayleigh quotient iteration, A doubly shifted QR algorithm with the two-sided 2D Grassmann–Rayleigh quotient double-shift is proposed. A modified version of the method and its truncated version are also developed. Numerical examples are presented to show the convergence behavior of the proposed algorithms. Numerical examples also show that the truncated versions of the modified methods outperform their counterparts including the standard Rayleigh quotient single-shift and the Francis double-shift.     

A Wilkinson-like multishift QR algorithm for symmetric eigenvalue problems and its global convergence

In 1989, Bai and Demmel proposed the multishift QR algorithm for eigenvalue problems. Although the global convergence property of the algorithm (i.e., the convergence from any initial matrix) still remains an open question for general nonsymmetric matrices, in 1992 Jiang focused on symmetric tridiagonal case and gave a global convergence proof for the generalized Rayleigh quotient shifts. In this paper, we propose Wilkinson-like shifts, which reduce to the standard Wilkinson shift in the single shift case, and show a global convergence theorem.     

A Rayleigh quotient minimization algorithm based on algebraic multigrid

This paper presents a new algebraic extension of the Rayleigh quotient multigrid (RQMG) minimization algorithm to compute the smallest eigenpairs of a symmetric positive definite pencil ( A , M ). Earlier versions of RQMG minimize the Rayleigh quotient over a hierarchy of geometric grids. We replace the geometric mesh information with the algebraic information defined by an algebraic multigrid preconditioner. At each level, we minimize the Rayleigh quotient with a block preconditioned algorithm. Numerical experiments illustrate the efficiency of this new algorithm to compute several eigenpairs. Copyright © 2007 John Wiley & Sons, Ltd.     

计算张量特征对的瑞利商迭代法

In this paper,we propose a Rayleigh quotient iteration method (RQI)to calculate the Z-eigenpairs of the symmetric tensor,which can be viewed as a generalization of shifted symmetric higher-order power method (SS-HOPM).The convergence analysis and the fixed-point analysis of this algorithm are given.Nu-merical examples show that RQI needs fewer iterations than SS-HOPM while keep the amount of computation per iteration.     

A derivative-free three-term projection algorithm involving spectral quotient for solving nonlinear monotone equations

ABSTRACT

In this paper, we develop a three-term conjugate gradient method involving spectral quotient, which always satisfies the famous Dai-Liao conjugacy condition and quasi-Newton secant equation, independently of any line search. This new three-term conjugate gradient method can be regarded as a variant of the memoryless Broyden-Fletcher-Goldfarb-Shanno quasi-Newton method with regard to spectral quotient. By combining this method with the projection technique proposed by Solodov and Svaiter in 1998, we establish a derivative-free three-term projection algorithm for dealing with large-scale nonlinear monotone system of equations. We prove the global convergence of the algorithm and obtain the R-linear convergence rate under some mild conditions. Numerical results show that our projection algorithm is effective and robust, and is more competitive with the TTDFP algorithm proposed Liu and Li [A three-term derivative-free projection method for nonlinear monotone system of equations. Calcolo. 2016;53:427–450].     

Convergence and Stability of the Truncated Euler-Maruyama Method for Stochastic Differential Equations with Piecewise Continuous Arguments

In this paper, we develop the truncated Euler-Maruyama (EM) method for stochastic differential equations with piecewise continuous arguments (SDEPCAs), and consider the strong convergence theory under the local Lipschitz condition plus the Khasminskii-type condition. The order of convergence is obtained. Moreover, we show that the truncated EM method can preserve the exponential mean square stability of SDEPCAs. Numerical examples are provided to support our conclusions.     

Two-sided Grassmann–Rayleigh quotient iteration

The two-sided Rayleigh quotient iteration proposed by Ostrowski computes a pair of corresponding left–right eigenvectors of a matrix C. We propose a Grassmannian version of this iteration, i.e., its iterates are pairs of p-dimensional subspaces instead of one-dimensional subspaces in the classical case. The new iteration generically converges locally cubically to the pairs of left–right p-dimensional invariant subspaces of C. Moreover, Grassmannian versions of the Rayleigh quotient iteration are given for the generalized Hermitian eigenproblem, the Hamiltonian eigenproblem and the skew-Hamiltonian eigenproblem.     

Projected quasi-Newton algorithm with trust region for constrained optimization

In Ref. 1, Nocedal and Overton proposed a two-sided projected Hessian updating technique for equality constrained optimization problems. Although local two-step Q-superlinear rate was proved, its global convergence is not assured. In this paper, we suggest a trust-region-type, two-sided, projected quasi-Newton method, which preserves the local two-step superlinear convergence of the original algorithm and also ensures global convergence. The subproblem that we propose is as simple as the one often used when solving unconstrained optimization problems by trust-region strategies and therefore is easy to implement.This research was supported in part by the National Natural Science Foundation of China.     

Rayleigh quotient algorithms for nonsymmetric matrix pencils

A classical Rayleigh-quotient iterative algorithm (known as “broken iteration”) for finding eigenvalues and eigenvectors is applied to semisimple regular matrix pencils A − λB. It is proved that cubic convergence is attained for eigenvalues and superlinear convergence of order three for eigenvectors. Also, each eigenvalue has a local basin of attraction. A closely related Newton algorithm is examined. Numerical examples are included. Dedicated to the memory of Gene H. Golub.     

Generalized Rayleigh quotient and finite element two-grid discretization schemes

This study discusses generalized Rayleigh quotient and high efficiency finite element discretization schemes. Some results are as follows: 1) Rayleigh quotient accelerate technique is extended to nonselfadjoint problems. Generalized Rayleigh quotients of operator form and weak form are defined and the basic relationship between approximate eigenfunction and its generalized Rayleigh quotient is established. 2) New error estimates are obtained by replacing the ascent of exact eigenvalue with the ascent of fin...     

计算对称带状矩阵广义特征值问题的并行分治多分法

1 引 言 本文研究了广义特征值问题 Ax=λBx (1)的并行计算。其中,A,B均为半带宽为r的n阶实对称带状矩阵且其中之一是正定的.本文总假设B是正定的.     

On the Convergence of Diagonal Elements and Asymptotic Convergence Rates for the Shifted Tridiagonal QL Algorithm

The convergence of diagonal elements of an irreducible symmetric triadiagonal matrix under QL algorithm with some kinds of shift is discussed. It is proved that if $\alpha_1-\sigma$→0 and $\beta_j$→0, j=1,2,...,m, then $\alpha_j$→$λ_j$ where $λ_j$ are m eigenvalues of the matrix, and $\sigma$ is the origin shift. The asymptotic convergence rates of three kinds of shift, Rayleigh quotient shift, Wilkinson's shift and RW shift, are analysed.     

求解半光滑方程组的近似Newton法

本文提出了求解半光滑方程组的近似Newton法，并证明了该算法的局部超线性收敛性。数值结果表明 该算法是有效的。     

Subspace correction multi‐level methods for elliptic eigenvalue problems

In this work, we apply the ideas of domain decomposition and multi‐grid methods to PDE‐based eigenvalue problems represented in two equivalent variational formulations. To find the lowest eigenpair, we use a “subspace correction” framework for deriving the multiplicative algorithm for minimizing the Rayleigh quotient of the current iteration. By considering an equivalent minimization formulation proposed by Mathew and Reddy, we can use the theory of multiplicative Schwarz algorithms for non‐linear optimization developed by Tai and Espedal to analyse the convergence properties of the proposed algorithm. We discuss the application of the multiplicative algorithm to the problem of simultaneous computation of several eigenfunctions also formulated in a variational form. Numerical results are presented. Copyright © 2001 John Wiley & Sons, Ltd.     

A new adaptive mixed finite element method based on residual type a posterior error estimates for the Stokes eigenvalue problem

In this article, we combine mixed finite element method, multiscale discretization, and Rayleigh quotient iteration to propose a new adaptive algorithm based on residual type a posterior error estimates for the Stokes eigenvalue problem. Both reliability and efficiency of the error indicator are proved. The efficiency of the algorithm is also investigated using Chen's Innovation Finite Element Method (iFEM) package. Numerical results are satisfying.© 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 31–53, 2015     

A Dual Algorithm for Minimizing a Quadratic Function with Two Quadratic Constraints

In this paper, we present a dual algorithm for minimizing a convex quadratic function with two quadratic constraints. Such a minimization problem is a subproblem that appears in some trust region algorithms for general nonlinear programming. Some theoretical properties of the dual problem are given. Global convergence of the algorithm is proved and a local superlinear convergence result is presented. Numerical examples are also provided.     

可靠度的双侧M-Bayes可信限

对二项分布的可靠度,提出了一种新的参数估计方法—双侧M-Bayes可信限法.在无失效数据情形,给出了可靠度的双侧M-Bayes可信的定义、双侧M-Bayes可信的估计,关于双侧M-Bayes可信限的性质提出了一个猜想—可靠度的双侧M-Bayes可信限与双侧经典置信限的关系.最后,给出了一个例子,通过这个例子可以看出双侧M-Bayes可信限优于双侧经典置信限.     

Modifications to the Garside, Jarratt & Mack Method for Solving Ill-conditioned Polynomial Equations

Several major modifications have been made to a method proposedby Garside, Jarratt & Mack for finding roots of polynomialequations. The modifications have reduced the number of iterationsand provided a set of starting values for the iterative procedureby implementing modified versions of Lehmer's method that assureconvergence. The modifications were successful and a generalpurpose root finding algorithm that is at the present stateof the art for solving ill-conditioned polynomial equationshas been produced. Numerical examples and comparisons are presentedto substantiate the modified method's effectiveness.     

On a Global Optimization Algorithm for Bivariate Smooth Functions

The problem of approximating the global minimum of a function of two variables is considered. A method is proposed rooted in the statistical approach to global optimization. The proposed algorithm partitions the feasible region using a Delaunay triangulation. Only the objective function values are required by the optimization algorithm. The asymptotic convergence rate is analyzed for a class of smooth functions. Numerical examples are provided.     

COMPUTE A CELIS-DENNIS-TAPIA STEP

In this paper,we present an algorithm for the CDT subproblem.This problem stemsfrom computing a trust region step of an algorithm,which was first proposed by Celis,Dennis and Tapia for equality constrained optimization.Our algorithm considers generalcase of the CDT subproblem,convergence of the algorithm is proved.Numerical examplesare also provided.