Convergence of inexact inverse iteration with application to preconditioned iterative solves

In this paper we study inexact inverse iteration for solving the generalised eigenvalue problem A x=λM x. We show that inexact inverse iteration is a modified Newton method and hence obtain convergence rates for various versions of inexact inverse iteration for the calculation of an algebraically simple eigenvalue. In particular, if the inexact solves are carried out with a tolerance chosen proportional to the eigenvalue residual then quadratic convergence is achieved. We also show how modifying the right hand side in inverse iteration still provides a convergent method, but the rate of convergence will be quadratic only under certain conditions on the right hand side. We discuss the implications of this for the preconditioned iterative solution of the linear systems. Finally we introduce a new ILU preconditioner which is a simple modification to the usual preconditioner, but which has advantages both for the standard form of inverse iteration and for the version with a modified right hand side. Numerical examples are given to illustrate the theoretical results. AMS subject classification (2000)  65F15, 65F10     

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.     

Inexact inverse subspace iteration for generalized eigenvalue problems

n this paper, we present an inexact inverse subspace iteration method for computing a few eigenpairs of the generalized eigenvalue problem Ax=λBx. We first formulate a version of inexact inverse subspace iteration in which the approximation from one step is used as an initial approximation for the next step. We then analyze the convergence property, which relates the accuracy in the inner iteration to the convergence rate of the outer iteration. In particular, the linear convergence property of the inverse subspace iteration is preserved. Numerical examples are given to demonstrate the theoretical results.     

A geometric theory for preconditioned inverse iteration applied to a subspace

The aim of this paper is to provide a convergence analysis for a preconditioned subspace iteration, which is designated to determine a modest number of the smallest eigenvalues and its corresponding invariant subspace of eigenvectors of a large, symmetric positive definite matrix. The algorithm is built upon a subspace implementation of preconditioned inverse iteration, i.e., the well-known inverse iteration procedure, where the associated system of linear equations is solved approximately by using a preconditioner. This step is followed by a Rayleigh-Ritz projection so that preconditioned inverse iteration is always applied to the Ritz vectors of the actual subspace of approximate eigenvectors. The given theory provides sharp convergence estimates for the Ritz values and is mainly built on arguments exploiting the geometry underlying preconditioned inverse iteration.     

A geometric theory for preconditioned inverse iteration I: Extrema of the Rayleigh quotient

The discretization of eigenvalue problems for partial differential operators is a major source of matrix eigenvalue problems having very large dimensions, but only some of the smallest eigenvalues together with the eigenvectors are to be determined. Preconditioned inverse iteration (a “matrix-free” method) derives from the well-known inverse iteration procedure in such a way that the associated system of linear equations is solved approximately by using a (multigrid) preconditioner. A new convergence analysis for preconditioned inverse iteration is presented. The preconditioner is assumed to satisfy some bound for the spectral radius of the error propagation matrix resulting in a simple geometric setup. In this first part the case of poorest convergence depending on the choice of the preconditioner is analyzed. In the second part the dependence on all initial vectors having a fixed Rayleigh quotient is considered. The given theory provides sharp convergence estimates for the eigenvalue approximations showing that multigrid eigenvalue/vector computations can be done with comparable efficiency as known from multigrid methods for boundary value problems.     

A class of Uzawa-SOR methods for saddle point problems

In this paper, we consider a class of Uzawa-SOR methods for saddle point problems, and prove the convergence of the proposed methods. We solve a lower triangular system per iteration in the proposed methods, instead of solving a linear equation Az=b. Actually, the new methods can be considered as an inexact iteration method with the Uzawa as the outer iteration and the SOR as the inner iteration. Although the proposed methods cannot achieve the same convergence rate as the GSOR methods proposed by Bai et al. [Z.-Z. Bai, B.N. Parlett, Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math. 102 (2005) 1-38], but our proposed methods have less workloads per iteration step. Experimental results show that our proposed methods are feasible and effective.     

Cubically convergent methods for selecting the regularization parameters in linear inverse problems

We present three cubically convergent methods for choosing the regularization parameters in linear inverse problems. The detailed algorithms are given and the convergence rates are estimated. Our basic tools are Tikhonov regularization and Morozov's discrepancy principle. We prove that, in comparison with the standard Newton method, the computational costs for our cubically convergent methods are nearly the same, but the number of iteration steps is even less. Numerical experiments for an elliptic boundary value problem illustrate the efficiency of the proposed algorithms.     

AN ADAPTIVE INVERSE ITERATION FEM FOR THE INHOMOGENEOUS DIELECTRIC WAVEGUIDES

We introduce an adaptive finite element method for computing electromagnetic guided waves in a closed, inhomogeneous, pillared three-dimensional waveguide at a given frequency based on the inverse iteration method. The problem is formulated as a generalized eigenvalue problems. By modifying the exact inverse iteration algorithm for the eigenvalue problem, we design a new adaptive inverse iteration finite element algorithm. Adaptive finite element methods based on a posteriori error estimate are known to be successful in resolving singularities of eigenfunctions which deteriorate the finite element convergence. We construct a posteriori error estimator for the electromagnetic guided waves problem. Numerical results are reported to illustrate the quasi-optimal performance of our adaptive inverse iteration finite element method.     

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.     

Frozen Landweber Iteration for Nonlinear Ill-Posed Problems

In this paper we propose a modification of the Landweber iteration termed frozen Landweberiteration for nonlinear ill-posed problems.A convergence analysis for this iteration is presented.The numericalperformance of this frozen Landweber iteration for a nonlinear Hammerstein integral equation is compared withthat of the Landweber iteration.We obtain a shorter running time of the frozen Landweber iteration based onthe same convergence accuracy.     

Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming

We propose to compute the search direction at each interior-point iteration for a linear program via a reduced augmented system that typically has a much smaller dimension than the original augmented system. This reduced system is potentially less susceptible to the ill-conditioning effect of the elements in the (1,1) block of the augmented matrix. A preconditioner is then designed by approximating the block structure of the inverse of the transformed matrix to further improve the spectral properties of the transformed system. The resulting preconditioned system is likely to become better conditioned toward the end of the interior-point algorithm. Capitalizing on the special spectral properties of the transformed matrix, we further proposed a two-phase iterative algorithm that starts by solving the normal equations with PCG in each IPM iteration, and then switches to solve the preconditioned reduced augmented system with symmetric quasi-minimal residual (SQMR) method when it is advantageous to do so. The experimental results have demonstrated that our proposed method is competitive with direct methods in solving large-scale LP problems and a set of highly degenerate LP problems. Research supported in parts by NUS Research Grant R146-000-076-112 and SMA IUP Research Grant.     

Iterative Methods for a Linearly Perturbed Algebraic Matrix Riccati Equation Arising in Stochastic Control

We start with a discussion of coupled algebraic Riccati equations arising in the study of linear-quadratic optimal control problems for Markov jump linear systems. Under suitable assumptions, this system of equations has a unique positive semidefinite solution, which is the solution of practical interest. The coupled equations can be rewritten as a single linearly perturbed matrix Riccati equation with special structures. We study the linearly perturbed Riccati equation in a more general setting and obtain a class of iterative methods from different splittings of a positive operator involved in the Riccati equation. We prove some special properties of the sequences generated by these methods and determine and compare the convergence rates of these methods. Our results are then applied to the coupled Riccati equations of jump linear systems. We obtain linear convergence of the Lyapunov iteration and the modified Lyapunov iteration, and confirm that the modified Lyapunov iteration indeed has faster convergence than the original Lyapunov iteration.     

两步定常线性迭代法的收敛区域及最优参数选取

１．引言 给定一线性系统 Ａｘ＝ｂ,（１．１）其线性两步定常迭代方法可表示为 ｘｎ＋１＝ ｘｎ＋ αｒｎ＋ β（ｘｎ－ ｘｎ－１）,（１．２）其中 ｒｎ＝ｂ－Ａｘｎ（１．３）是剩余向量, ｘ０, ｘ１是任意的（ｃｆ．Ｙｏｕｎｇ［１,ｐ．４８７］）．本文我们将研究迭代式（１．２）的收敛条件及参数α,β如何选取问题．关于此问题已有一些结果,如［２－４］,本文将从方程根的角度讨论最一般的情况,即在复数域上来讨论此问题,同时作为其特例来讨论复 ＳＯＲ、 ＭＳＯＲ的收敛性． 下文中除了特别说明,Ａ是复矩阵,α,β是复…     

Accelerated PMHSS iteration methods for complex symmetric linear systems

In this paper, we introduce and analyze an accelerated preconditioning modification of the Hermitian and skew-Hermitian splitting (APMHSS) iteration method for solving a broad class of complex symmetric linear systems. This accelerated PMHSS algorithm involves two iteration parameters α,β and two preconditioned matrices whose special choices can recover the known PMHSS (preconditioned modification of the Hermitian and skew-Hermitian splitting) iteration method which includes the MHSS method, as well as yield new ones. The convergence theory of this class of APMHSS iteration methods is established under suitable conditions. Each iteration of this method requires the solution of two linear systems with real symmetric positive definite coefficient matrices. Theoretical analyses show that the upper bound σ₁(α,β) of the asymptotic convergence rate of the APMHSS method is smaller than that of the PMHSS iteration method. This implies that the APMHSS method may converge faster than the PMHSS method. Numerical experiments on a few model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of the new method.     

A combination model for image denoising

In this paper, we propose an efficient combination model of the second-order ROF model and a simple fourth-order partial differential equation (PDE) for image denoising. The split Bregman method is used to convert the nonlinear combination model into a linear system in the outer iteration, and an algebraic multigrid method is applied to solve the linear system in the inner iteration. Furthermore, Krylov subspace acceleration is adopted to improve convergence in the outer iteration. At the same time, we prove that the model is strictly convex and exists a unique global minimizer. We have also conducted a variety of numerical experiments to analyze the parameter selection criteria and discuss the performance of the fourth-order PDE in the combination model. The results show that our model can reduce blocky effects and our algorithm is efficient and robust to solve the proposed model.     

Local convergence analysis of several inexact Newton-type algorithms for general nonlinear eigenvalue problems

We study the local convergence of several inexact numerical algorithms closely related to Newton’s method for the solution of a simple eigenpair of the general nonlinear eigenvalue problem $T(\lambda )v=0$ . We investigate inverse iteration, Rayleigh quotient iteration, residual inverse iteration, and the single-vector Jacobi–Davidson method, analyzing the impact of the tolerances chosen for the approximate solution of the linear systems arising in these algorithms on the order of the local convergence rates. We show that the inexact algorithms can achieve the same order of convergence as the exact methods if appropriate sequences of tolerances are applied to the inner solves. We discuss the connections and emphasize the differences between the standard inexact Newton’s method and these inexact algorithms. When the local symmetry of $T(\lambda )$ is present, the use of a nonlinear Rayleigh functional is shown to be fundamental in achieving higher order of convergence rates. The convergence results are illustrated by numerical experiments.     

On preconditioned eigensolvers and Invert-Lanczos processes

This paper deals with the convergence analysis of various preconditioned iterations to compute the smallest eigenvalue of a discretized self-adjoint and elliptic partial differential operator. For these eigenproblems several preconditioned iterative solvers are known, but unfortunately, the convergence theory for some of these solvers is not very well understood.The aim is to show that preconditioned eigensolvers (like the preconditioned steepest descent iteration (PSD) and the locally optimal preconditioned conjugate gradient method (LOPCG)) can be interpreted as truncated approximate Krylov subspace iterations. In the limit of preconditioning with the exact inverse of the system matrix (such preconditioning can be approximated by multiple steps of a preconditioned linear solver) the iterations behave like Invert-Lanczos processes for which convergence estimates are derived.     

Asymptotic properties of a stochastic predator-prey model with Crowley-Martin functional response

A two-step iterative scheme based on the multiplicative splitting iteration is presented for PageRank computation. The new algorithm is applied to the linear system formulation of the problem. Our method is essentially a two-parameter iteration which can extend the possibility to optimize the iterative process. Theoretical analyses show that the iterative sequence produced by our method is convergent to the unique solution of the linear system, i.e., PageRank vector. An exact parameter region of convergence for the method is strictly proved. In each iteration, the proposed method requires solving two linear sub-systems with the splitting of the coefficient matrix of the problem. We consider using inner iterations to compute approximate solutions of these linear sub-systems. Numerical examples are presented to illustrate the efficiency of the new algorithm.     

A new algorithm for total variation based image denoising

We propose a new algorithm for the total variation based on image denoising problem. The split Bregman method is used to convert an unconstrained minimization denoising problem to a linear system in the outer iteration. An algebraic multi-grid method is applied to solve the linear system in the inner iteration. Furthermore, Krylov subspace acceleration is adopted to improve convergence in the outer iteration. Numerical experiments demonstrate that this algorithm is efficient even for images with large signal-to-noise ratio.     

一类特征值反问题(IEP)的基于矩阵方程的Ulm型算法

应用求解算子方程的Ulm方法构造了求解一类矩阵特征值反问题（IEP）的新算法.所给算法避免了文献[Aishima K.,A quadratically convergent algorithm based on matrix equations for inverse eigenvalue problems,Linear Algebra and its Applications,2018,542：310-33]中算法在每次迭代中要求解一个线性方程组的不足,证明了在给定谱数据互不相同的条件下所给算法具有根收敛意义下的二次收敛性.数值实验表明本文所给算法在矩阵阶数较大时计算效果优于上文所给算法.