New schemes with fractal error compensation for PDE eigenvalue computations

With an error compensation term in the fractal Rayleigh quotient of PDE eigen-problems,we propose a new scheme by perturbing the mass matrix Mhto Mh=Mh+Ch2mKh,where Khis the corresponding stif matrix of a 2m 1 degree conforming finite element with mesh size h for a 2m-order self-adjoint PDE,and the constant C exists in the priority error estimationλh jλj~Ch2mλ2j.In particular,for Laplace eigenproblems over regular domains in uniform mesh,e.g.,cube,equilateral triangle and regular hexagon,etc.,we find the constant C=I h 1Mh2 hKh and show that in this case the computation accuracy can raise two orders,i.e.,fromλh jλj=O(h2)to O(h4).Some numerical tests in 2-D and 3-D are given to verify the above arguments.     

Asymptotic Convergence of Conjugate Gradient Methods for the Partial Symmetric Eigenproblem

Recently an efficient method (DACG) for the partial solution of the symmetric generalized eigenproblem A x = δB x has been developed, based on the conjugate gradient (CG) minimization of the Rayleigh quotient over successive deflated subspaces of decreasing size. The present paper provides a numerical analysis of the asymptotic convergence rate ρ_j of DACG in the calculation of the eigenpair λ_j, u _j, when the scheme is preconditioned with A⁻¹. It is shown that, when the search direction are A-conjugate, ρ_j is well approximated by 4/ξ_j, where ξ_j is the Hessian condition number of a Rayleigh quotient defined in appropriate oblique complements of the space spanned by the leftmost eigenvectors u ₁, u ₂,…, u _j−1 already calculated. It is also shown that 1/ξ_j is equal to the relative separation between the eigenvalue λ_j currently sought and the next higher one λ_j+1 and the next higher one λ_{j + 1}. A modification of DACG (MDACG) is studied, which involves a new set of CG search directions which are made M-conjugate, with M-conjugate, with M-conjugate, with M a matrix approximating the Hessian. By distinction, MDACG has an asymptotic rate of convergence which appears to be inversely proportional to the square root of ξ_j, in complete agreement with the theoretical results known for the CG solution to linear systems. © 1997 by John Wiley & Sons, Ltd.     

Convergence of algorithms for finding eigenvectors

1. IntroductionMethods for finding eigenvectors and eigenvalues of a matrix have importallt applications in colltrol theory, pattern recognition, signal processing and many other fields. Withthese applications the computational methods themselves have been developing rapidly. See[1--4] for some developments.For a square matriX of order n, when n is sufficiently large, it is very difficult to findits eigenvalues directly and one usually uses methods of iteration. Esseniiajly, we can evensac th…     

On a special basis of approximate eigenvectors with local supports for an isolated narrow cluster of eigenvalues of a symmetric tridiagonal matrix

Let $ \tilde \lambda Let be an approximate eigenvalue of multiplicity m _c = n − r of an n × n real symmetric tridiagonal matrix T having nonzero off-diagonal entries. A fast algorithm is proposed (and numerically tested) for deleting m _c rows of T− I so that the condition number of the r × n matrix B formed of the remaining r rows is as small as possible. A special basis of m _c vectors with local supports is constructed for the subspace kerB. These vectors are approximate eigenvectors of T corresponding to . Another method for deleting m _c rows of T− I is also proposed. This method uses a rank-revealing QR decomposition; however, it requires a considerably larger number of arithmetic operations. For the latter algorithm, the condition number of B is estimated, and orthogonality estimates for vectors of the special basis of kerB are derived. Original Russian Text ? S.K. Godunov, A.N. Malyshev, 2008, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2008, Vol. 48, No. 7, pp. 1156–1166.     

An initial-value method for the determinantal equations of vibrations and flutter

In many investigations in mechanics, we must solve the equation detB()=0, where the elements of the matrixB are general functions of . A method of solution is proposed, and results of numerical experiments are given.     

Some Convergence Properties of Descent Methods

In this paper, we discuss the convergence properties of a class of descent algorithms for minimizing a continuously differentiable function f on R ⁿ without assuming that the sequence { x _k } of iterates is bounded. Under mild conditions, we prove that the limit infimum of is zero and that false convergence does not occur when f is convex. Furthermore, we discuss the convergence rate of { } and { f(x _k )} when { x _k } is unbounded and { f(x _k )} is bounded.     

On the Randomized Error of Polynomial Methods for Eigenvector and Eigenvalue Estimates

In this paper we consider the problem of estimating the largest eigenvalue and the corresponding eigenvector of a symmetric matrix. In particular, we consider iterative methods, such as the power method and the Lanczos method. These methods need a starting vector which is usually chosen randomly. We analyze the behavior of these methods when the initial vector is chosen with uniform distribution over the unitn-dimensional sphere. We extend and generalize the results reported earlier. In particular, we give upper and lower bounds on the _pnorm of the randomized error, and we improve previously known bounds with a detailed analysis of the role of the multiplicity of the largest eigenvalue.     

Spectral pollution and second-order relative spectra for self-adjoint operators

We consider the phenomenon of spectral pollution arising incalculation of spectra of self-adjoint operators by projectionmethods. We suggest a strategy of dealing with spectral pollutionby using the so-called second-order relative spectra. The effectivenessof the method is illustrated by a detailed analysis of two modelexamples.     

A convergence theory of multilevel additive Schwarz methods on unstructured meshes

We develop a convergence theory for two level and multilevel additive Schwarz domain decomposition methods for elliptic and parabolic problems on general unstructured meshes in two and three dimensions. The coarse and fine grids are assumed only to be shape regular, and the domains formed by the coarse and fine grids need not be identical. In this general setting, our convergence theory leads to completely local bounds for the condition numbers of two level additive Schwarz methods, which imply that these condition numbers are optimal, or independent of fine and coarse mesh sizes and subdomain sizes if the overlap amount of a subdomain with its neighbors varies proportionally to the subdomain size. In particular, we will show that additive Schwarz algorithms are still very efficient for nonselfadjoint parabolic problems with only symmetric, positive definite solvers both for local subproblems and for the global coarse problem. These conclusions for elliptic and parabolic problems improve our earlier results in [12, 15, 16]. Finally, the convergence theory is applied to multilevel additive Schwarz algorithms. Under some very weak assumptions on the fine mesh and coarser meshes, e.g., no requirements on the relation between neighboring coarse level meshes, we are able to derive a condition number bound of the orderO(² L ²), where = max₁lL(h _l +_l– 1)/ _l,h _l is the element size of thelth level mesh, _l the overlap of subdomains on thelth level mesh, andL the number of mesh levels.The work was partially supported by the NSF under contract ASC 92-01266, and ONR under contract ONR-N00014-92-J-1890. The second author was also partially supported by HKRGC grants no. CUHK 316/94E and the Direct Grant of CUHK.     

CONVERGENCE RATE OF VECTOR SUBDIVISION SCHEME

In this paper,some characterizations on the convergence rate of both the homoge- neous and nonhomogeneous subdivision schemes in Sobolev space are studied and given.     

Quadratic Convergence of a Long-Step Interior-Point Method for Nonlinear Monotone Variational Inequality Problems

This paper offers an analysis on a standard long-step primal-dual interior-point method for nonlinear monotone variational inequality problems. The method has polynomial-time complexity and its q-order of convergence is two. The results are proved under mild assumptions. In particular, new conditions on the invariance of the rank and range space of certain matrices are employed, rather than restrictive assumptions like nondegeneracy.     

Convergence theory for the exact interpolation scheme with approximation vector as the first column of the prolongator and Rayleigh quotient iteration nonlinear smoother

We extend the analysis of the recently proposed nonlinear EIS scheme applied to the partial eigenvalue problem. We address the case where the Rayleigh quotient iteration is used as the smoother on the fine-level. Unlike in our previous theoretical results, where the smoother given by the linear inverse power method is assumed, we prove nonlinear speed-up when the approximation becomes close to the exact solution. The speed-up is cubic. Unlike existent convergence estimates for the Rayleigh quotient iteration, our estimates take advantage of the powerful effect of the coarse-space.     

Homotopy method for the numerical solution of the eigenvalue problem of self-adjoint partial differential operators

GivenA ₁, the discrete approximation of a linear self-adjoint partial differential operator, the smallest few eigenvalues and eigenvectors ofA ₁ are computed by the homotopy (continuation) method. The idea of the method is very simple. From some initial operatorA ₀ with known eigenvalues and eigenvectors, define the homotopyH(t)=(1–t)A ₀+tA₁, 0t1. If the eigenvectors ofH(t ₀) are known, then they are used to determine the eigenpairs ofH(t ₀+dt) via the Rayleigh quotient iteration, for some value ofdt. This is repeated untilt becomes 1, when the solution to the original problem is found. A fundamental problem is the selection of the step sizedt. A simple criterion to selectdt is given. It is shown that the iterative solver used to find the eigenvector at each step can be stabilized by applying a low-rank perturbation to the relevant matrix. By carrying out a small part of the calculation in higher precision, it is demonstrated that eigenvectors corresponding to clustered eigenvalues can be computed to high accuracy. Some numerical results for the Schrödinger eigenvalue problem are given. This algorithm will also be used to compute the bifurcation point of a parametrized partial differential equation.Dedicated to Herbert Bishop Keller on the occasion of his 70th birthdayThe work of this author was in part supported by RGC Grant DAG93/94.SC30.The work of this author was in part supported by NSF Grant DMS-9403899.     

Rates of Convergence for Bivariate Extremes

Under a second order regular variation condition, rates of convergence of the distribution of bivariate extreme order statistics to its limit distribution are given both in the total variation metric and in the uniform metric.     

Some limit theorems on the eigenvectors of large dimensional sample covariance matrices

Let {v_ij} i,j = 1, 2,…, be i.i.d. standardized random variables. For each n, let V_n = (v_ij) i = 1, 2,…, n; j = 1, 2,…, s = s(n), where $\text{(}\text{n}\text{s}\text{) → y > 0}$ as n → ∞, and let $\text{M}{}_{\mathrm{n}}\text{= (}\text{1}\text{s}\text{)V}{}_{\mathrm{n}}\text{V}{}_{\mathrm{n}}{}^{\mathrm{T}}$. Previous results [7, 8] have shown the eigenvectors of M_n to display behavior, for n large, similar to those of the corresponding Wishart matrix. A certain stochastic process X_n on [0, 1], constructed from the eigenvectors of M_n, is known to converge weakly, as n → ∞, on D[0, 1] to Brownian bridge when v₁₁ is N(0, 1), but it is not known whether this property holds for any other distribution. The present paper provides evidence that this property may hold in the non-Wishart case in the form of limit theorems on the convergence in distribution of random variables constructed from integrating analytic function w.r.t. X_n(F_n(x)), where F_n is the empirical distribution function of the eigenvalues of M_n. The theorems assume certain conditions on the moments of v₁₁ including E(v₁₁⁴) = 3, the latter being necessary for the theorems to hold.     

Local Convergence of an Inexact-Restoration Method and Numerical Experiments

Local convergence of an inexact-restoration method for nonlinear programming is proved. Numerical experiments are performed with the objective of evaluating the behavior of the purely local method against a globally convergent nonlinear programming algorithm. This work was supported by PRONEX-CNPq/FAPERJ Grant E-26/171.164/2003-APQ1, FAPESP Grants 03/09169-6 and 01/04597-4, and CNPq. The authors are indebted to Juliano B. Francisco and Yalcin Kaya for their careful reading of the first draft of this paper.     

Convergence Rate of the Augmented Lagrangian SQP Method

In this paper, the augmented Lagrangian SQP method is considered for the numerical solution of optimization problems with equality constraints. The problem is formulated in a Hilbert space setting. Since the augmented Lagrangian SQP method is a type of Newton method for the nonlinear system of necessary optimality conditions, it is conceivable that q-quadratic convergence can be shown to hold locally in the pair (x, ). Our interest lies in the convergence of the variable x alone. We improve convergence estimates for the Newton multiplier update which does not satisfy the same convergence properties in x as for example the least-square multiplier update. We discuss these updates in the context of parameter identification problems. Furthermore, we extend the convergence results to inexact augmented Lagrangian methods. Numerical results for a control problem are also presented.     

Convergence rate of a proximal multiplier algorithm for separable convex minimization

In this paper, we analyse the convergence rate of the proximal algorithm proposed by us in the article [A proximal multiplier method for separable convex minimization. Optimization. 2016; 65:501–537], which has been proposed to solve a separable convex minimization problem. We prove that, under mild assumptions, the primal-dual sequences of the algorithm converge linearly to the optimal solution for a class of proximal distances.     

Convergence analysis of finite volume scheme for nonlinear aggregation population balance equation

In this work, we introduce the convergence analysis of the recently developed finite volume scheme to solve a pure aggregation population balance equation that is of substantial interest in many areas such as chemical engineering, aerosol physics, astrophysics, polymer science, pharmaceutical sciences, and mathematical biology. The notion of the finite volume scheme is to conserve total mass of the particles in the system by introducing weight in the formulation. The consistency of the finite volume scheme is also analyzed thoroughly as it is an influential factor. The convergence study of the numerical scheme shows second order convergence on uniform, nonuniform smooth (geometric) as well as on locally uniform meshes independent of the aggregation kernel. Moreover, the first‐order convergence is shown when the finite volume scheme is implemented on oscillatory and random meshes. In order to check the accuracy, the numerical experimental order of convergence is also computed for the physically relevant as well as analytically tractable kernels and validated against its analytical results.