# A Study on the Convergence Analysis of the Inexact Simplified Jacobi–Davidson Method

Authors: Jutao Zhao; Pengfei Guo
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The Jacobi–Davidson iteration method is very efficient in solving Hermitian eigenvalue problems. If the correction equation involved in the Jacobi–Davidson iteration is solved accurately, the simplified Jacobi–Davidson iteration is equivalent to the Rayleigh quotient iteration which achieves cubic convergence rate locally. When the involved linear system is solved by an iteration method, these two methods are also equivalent. In this paper, we present the convergence analysis of the simplified Jacobi–Davidson method and present the estimate of iteration numbers of the inner correction equation. Furthermore, based on the convergence factor, we can see how the accuracy of the inner iteration controls the outer iteration.


---

## Body

## 1. Introduction

LetA be a sparse and Hermitian matrix. Then, we are supposed to compute the smallest eigenvalue λ of A and the associated eigenvector x of λ with large, i.e.,(1)Ax=λx,withx=1.Here and in the following,⋅ indicates the induced Euclidean norm for either a vector or a matrix. In the literature, there have been many methods developed involving gradient-type methods and subspace methods. The Lanczos, Arnoldi, Davidson, and Jacobi–Davidson methods are classical and effective methods for solving eigenproblem (1), and there have been many convergence results developed for these methods. It should be mentioned that, for the Lanczos and Arnoldi methods, the involved projection subspace should be restricted to the Krylov subspace. For more details about these methods as well as their variants, refer to in [1–7].The main framework for the subspace methods is generating a sequence of enlarging subspacesVk, which contain more and more information for the desired eigenvalue or eigenvector of matrix A. The central problem for this method, which can be accomplished by the Rayleigh–Ritz procedure, is to extract the approximation to the desired eigenvalue or eigenvector from the projection subspace. For more details of the Rayleigh–Ritz procedure, refer to in [4].As we know, for Hermitian matrices, the exact Rayleigh quotient iteration (RQI) [4] converges cubically. However, an ill-conditioned linear system of equations should be solved exactly which is expensive in each step of the iteration as the approximation is close to the target eigenvalue. The idea replacing the exact solution by a cheaper approximate solution results in an inexact Rayleigh quotient iteration (IRQI) [8, 9]; however, this replacement may destroy the local convergence property of the RQI.The Jacobi–Davidson (JD) iteration method [6] proposed by Sleijpen and van der Vorst can overcome these difficulties. A so-called correction equation(2)I−uu∗A−θII−uu∗t=−r,where u is the current approximation to the desired eigenvector with norm unity, θ=u∗Au is the Rayleigh quotient, and r=Au−θu is the current residual, is solved to expand the projection subspace which contains more and more information of the desired eigenvector x theoretically. As we know, if (2) is solved exactly, the JD method converges as fast as the RQI method. However, what we are interested in is the iterative solver with an ideal preconditioner for it. Although the shifted matrix A−θI becomes ill-conditioned as the approximation θ is near to the desired eigenvalue, correction equation (2) remains well conditioned, thanks to the projection onto the orthogonal complement of u. As Notay in [10] pointed out, with proper implementations, the potential indefiniteness of the coefficient matrix in system (2) cannot spoil the method.At present, we have not seen the analysis of the connection between the solution of the correction equation and the convergence of the approximate vectoru towards the wanted eigenvector. In this paper, we study the convergence of the simplified JD iteration. Through the convergence factor, we try to analyze how the inner linear system controls the outer iteration. Moreover, we can also see that, under some assumptions, the JD method attains quadratic convergence rate locally. Then, we can gain higher convergence rate through increasing the accuracy precision of the inner linear system. In the last part of this paper, we give the convergence analysis in terms of the residual norms, from which we can see that these results are asymptotically identical to those derived in the former section; we also gave the analysis on the iteration number of the inner linear system.We should mention that some analyses for the JD method or, more generally, the Newton method have been established so far; see, e.g., [7, 11–13] and the references therein. In particular, Bai and Miao in [11] presented the convergence of the JD iteration method, and they proved that the JD iteration method attains quadratic convergence locally when the involved correction equation is solved by a Krylov subspace method and attains cubic convergence rate when the correction equation is solved to a prescribed precision proportional to the norm of the current residual vector. In this paper, we will use a completely different technique to demonstrate the convergence of the JD method from another point of view. In addition, we have further studied the connection between the iteration steps of the inner correction equation with the convergence of the outer iteration.This paper is organized as follows. In Section2, we give some preliminaries of the JD method. In Section 3, we give some known results and then built several new results concerning the convergence property of the simplified JD method whose involved correction equation is inexactly solved by Krylov solvers. In Section 4, we give the estimate on the iteration number of the inner linear system. Finally, we give some concluding remarks.


## 2. Preliminaries

Letxii=1n be the eigenvectors of the Hermitian matrix A associated with the eigenvalues λii=1n with the ascending order λ1<λ2≤…≤λn. In the following discussion, we want to compute the eigenvector x1 associated with the simple smallest eigenvalue λ1. Denote by ϕ the angle between the current approximation u and the wanted eigenvector x1.We first present the algorithmic description of the simplified JD method in Algorithm1.Algorithm 1: The simplified Jacobi-Davidson iteration.
Given a normalized vectoru arbitrary and a stopping factor εForm = 1, 2, …, do(1)
Computeθ=u∗Au(2)
Computer=Au−θu(3)
Test the convergence; ifr≤ε, stop(4)
Solve the correction equationI−uu∗A−θII−uu∗t=−r for t⊥u(5)
Letu:=u+t/u+tEnd forAs we know, if the correction equation in Algorithm1 is solved accurately, the simplified JD method is equivalent to the RQI method. In fact, according to (2), we have A−θIt−u∗A−θItu=−r or, equivalently, A−θIu+t=u∗A−θItu. We can see that the new approximation u˜=u+t/u+t is the Rayleigh quotient iteration vector. In fact, Theorem 4.2 in [14] tells us that the inexact simplified JD method and the IRQI method can also be equivalent if the inner linear system is solved by Krylov subspace methods. Here, the ‘inexact’ method means that the inner linear system is solved by an iteration method.Based on the property of the correction equation, the inner linear system in Algorithm1 is solved approximately by Krylov subspace methods, and we will use the obtained vector to update the current eigenvector approximation.Suppose that we have obtained an approximate eigenvectoru which is close to the wanted eigenvector x in Algorithm 1; we decompose it in the following way:(3)u=a1x1+a2x2+⋯+anxn=a1x1+1−a12∑j=2najxj1−a12=x1cosϕ+wsinϕ,where w⊥x1 with w=1 and ϕ is the angle between vectors u and x1. Also, in this paper, the approximate vector u is close to the wanted eigenvector x1 which means Osin2ϕ=λ1−θ≪λ2−θ.In the following, we give a lemma which reveals the relation between two Krylov subspaces.Lemma 2.1.
Letu be a normalized vector, θ=u∗Au, and r=Au−θu. Denote by Π=I−uu∗ and Aθ,u=ΠA−θIΠ. Then, for k≥2, the two Krylov subspaces Vk−1J and VkR have the following relation:(4)Vk−1J⊆VkR,where(5)Vk−1J=spanr,Aθ,ur,…,Aθ,uk−2r,and(6)VkR=spanu,A−θIu,…,A−θIk−1u.Proof.
We prove this lemma by induction overk. Obviously, for k=2, V1J=spanr⊆V2R=spanu,A−θIu. Assume that, for all i≤k−1, we have Vi−1J⊆ViR. Next, we will prove that this relation satisfies for i=k. Denote v=Aθ,uk−3r; based on the fact v⊥u and the induction hypothesis, we have v∈Vk−2J⊆Vk−1R. Then, we have Aθ,uk−2r=Aθ,uAθ,uk−3r=Aθ,uv=ΠA−θIv=A−θIv−u∗A−θIvu∈VkR. Thus, we have verified the relation Vk−1J⊆VkR.


## 3. Convergence Analysis of the JD Iteration

In the following discussion, we solve the correction equation approximately by Krylov subspace methods, such as CG or MINRES with the initial vector being zero, to obtain an approximate solutiont to update the new eigenvector approximation u. That is to say, solution t satisfies the following equation:(7)I−uu∗A−θII−uu∗t=−r+ηm,where ηm is the residual at step m.In order to analyze conveniently, (7) can also be represented by other equivalent forms such as (30).As we know, the JD method is one of the “inner-outer” type iterations. In the method of this type, it is essential to know how the inner iteration controls the outer iteration. In other words, we want to know how accuracy or how many steps should be solved for the inner iteration equation to ensure the convergence of the outer iteration. As Sleijpen and van der Vorst pointed out in [6], we cannot answer the question at present. All these problems may be based on the convergence analysis of the algorithm. In the following, we first give some convergence results.Lemma 3.1.
(see [7]). If Algorithm 1 is applied to seek the smallest simple eigenvalue of the Hermitian matrix A and we assume that the approximate solution t satisfies the relation in (30), then for u˜=u+t/u+t, we asymptotically have(8)tanϕ˜≤ξλn−λλ2−λsinϕ+Osin2ϕ.Lemma 3.2.
(see [13]). If Algorithm 1 is applied to seek the smallest simple eigenvalue of the Hermitian matrix A and we assume that the approximate solution t satisfies the relation in (30), then for u˜=u+t/u+t, we asymptotically have(9)tanϕ˜≤ξA−θIeA−θI−1fcosϕsinψsinϕ+Osin2ϕ.The two convergence results above are analysed based on the angle between vectorsu and x1. Proposition 1 in [15] gives us another result for the convergence analysis based on the metric of u−x1. However, all these results cannot answer the question asked above, and we could not answer how the convergence order varies as the inner correction equation is being solved.Theorem 3.1.
Letλ1,x1 be a simple eigenpair of the Hermitian matrix A in Algorithm 1, λi−θ,xi be the eigenpair of the shifted matrix A−θI with the ascending order λ1−θ<λ2−θ≤…≤λn−θ, tm be the approximate solution obtained by using the unpreconditioned Krylov subspace method with zero starting vector, and ηm=I−uu∗A−θII−uu∗tm+r=qm+1A−θIu be the associated residual. Then, the following estimate holds:(10)tanϕ˜≤ηm2−qm+1λ1−θcosϕ21/2+τsinϕqm+1λ1−θ+τλ1−w∗Awλ2−θcosϕsin2ϕ,where ϕ˜ is the angle between the new approximation u˜ and x1 and τ=u∗A−θItm.Proof.
Suppose thatu is the current approximation to the wanted eigenvector x1, and we decompose it in the way of (3). If we solve the correction equation I−uu∗A−θII−uu∗t=−r inexactly with zero starting vector by the unpreconditioned Krylov subspace method, then the approximate solution tm of the linear system in step m is in the Krylov subspace VmJ=spanr,Aθ,ur,Aθ,u2r,…,Aθ,um−1r, where Aθ,u and VmJ are defined as Lemma 2.1. Based on Lemma 2.1, we have tm∈VmJ⊆Vm+1R for tm⊥u. Then, the solution tm=q^mA−θIu, and we get the new approximation(11)u˜=u+tm=u+q^mA−θIu=qmA−θIu,where qmλ=q^mλ+1.
The residual of the correction equation at stepm is(12)ηm=I−uu∗A−θII−uu∗tm+r=I−uu∗A−θItm+r=A−θItm−τu+r=A−θIu+tm−τu=A−θIqmA−θIu−τu=qm+1A−θIu,with τ=u∗A−θItm and qm+1λ=λqmλ−τ.
According to the decomposition in (3), we have(13)u˜=qmA−θIu=qmA−θIx1cosϕ+wsinϕ=qmλ1−θx1cosϕ+qmA−θIwsinϕ.
Thus, we obtain(14)tanϕ˜=qmA−θIwqmλ1−θtanϕ.
Note thatqm+1λ=λqmλ−τ; that is, qmλ=qm+1λ+τ/λ; then,(15)tanϕ˜=A−θI−1qm+1A−θI+τIwqm+1λ1−θ+τλ1−θtanϕ.
Based on (3) and (12), we get(16)ηm2=qm+1λ1−θcosϕ2+qm+1A−θIw2sin2ϕ.
Thus, we have(17)qm+1A−θIw=ηm2−qm+1λ1−θcosϕ21/2sinϕ.
In addition, it obviously holds that(18)A−θI−1qm+1A−θI+τIw≤qm+1A−θIw+τλ2−θ,(19)λ1−θ=λ1−u∗Au=λ1−x1cosϕ+wsinϕ∗Ax1cosϕ+wsinϕ=λ1−λ1cos2ϕ+w∗Awsin2ϕ=λ1−w∗Awsin2ϕ.
Thereby, based on (15), (17), (18), and (19), we have the estimate(20)tanϕ˜≤ηm2−qm+1λ1−θcosϕ21/2+τsinϕqm+1λ1−θ+τλ1−w∗Awλ2−θcosϕsin2ϕ.Theorem3.1 gives us a preliminary convergence analysis of the simplified JD method. Since the simplified JD method is a JD method without subspace acceleration, the convergence factor of the former is an upper bound of the latter. That is to say, in order to gain the convergence property of the JD method, we can analyze its simplified form.Next, we analyze the convergence factor of Theorem3.1. The current approximation u is very near to the wanted vector x1; that is to say, cosϕ≥δ with δ being a constant smaller than one. Combining with the fact λ1−w∗Aw≤λn−λ1, it is clear that the second term of the convergence factor can be bounded; then, it is the first term which plays a vital role on the analysis of the convergence.For the purpose of analysis, we present the following lemma.Lemma 3.3.
Letxii=1n be the orthonormal eigenvectors of Hermitian matrix A. Assume that u is a normalized vector which is near to x1 such that the corresponding Rayleigh quotient θ=u∗Au satisfies(21)λ1−θ<λ2−θ≤…≤λn−θandtanϕ≤122.Then, the following estimate holds:(22)σmin⊥A−θI≥λ2−λ122,where ϕ is the angle between vectors u and x1 and σmin⊥A represents the smallest singular value of A restricted to the subspace span u⊥.Proof.
∀x∈spanu⊥ with x=1, we decompose u and x as u=∑i=1nαixi and x=∑i=1nβixi, where ∑i=1nαi2=∑i=1nβi2=1. Then, we have(23)x∗A−θI2x=∑i=1nβixi∗A−θI2∑i=1nβixi=∑i=1nβixi∗∑i=1nβiλi−θ2xi=∑i=1nβi2λi−θ2≥λ2−θ2∑i=2nβi2+β12λ1−θ2=λ2−θ21−β12+β12λ1−θ2=λ2−θ2−β12λ2+λ1−2θλ2−λ1.
It follows fromx∗u=0 that ∑i=1nαiβ¯i=0; equivalently, we have α1β1¯=−∑i=2nαiβi¯. Moreover, we have(24)β12=∑i=2nαiβi¯2α12≤∑i=2nαi2∑i=2n|βi¯|2α1|2≤1−α12α12.
The first assumption in (21) indicates that λ2+λ1−2θ<λ2−λ1 and λ2−θ>λ2−λ1/2 hold; then, we have the estimate(25)x∗A−θI2x≥λ2−λ122−tanϕ2λ2−λ12.
Here, we use the factα1=cosϕ. Combining the above estimate with the second assumption in (21), we frequently obtain the estimate in (22).In the following, we give an estimate ofτ with τ=u∗A−θItm.(26)I−uu∗A−θII−uu∗tmtm≥minvI−uu∗A−θII−uu∗vv=σmin⊥A−θI.Thus, combining (26) and the correct equation in (7), we have(27)−r+ηmtm≥σmin⊥A−θI.It further indicates that(28)tm≤−r+ηmσmin⊥A−θI≤r+ηmσmin⊥A−θI,and, at last, we obtain(29)τ=u∗A−θItm≤rtm≤r+ηmσmin⊥A−θIr.To see the behavior of the convergence for the JD method clearly, the stopping criterion we adopt is that the norm of the current residual is reduced by a factorξ from that of the initial residual. That is, t satisfies the following equation:(30)I−uu∗A−θII−uu∗t=−r+ξrd,where d is the residual direction and ξ is the stopping factor.Theorem 3.2.
Givenξ1, ξ2<1, if ηm≤ξ1r, then the JD method converges linearly as follows:(31)tanϕ˜≤ξ1α+|τ|C1λ1−w∗Awλ2−θcosϕsinϕ,under the assumption(32)min2≤j≤nλj−θqm+1λj−θ>λ1−θλn+λ2−2λ1λn−λ11+ξ1σmin⊥.Ifηm≤ξ2r2, then the JD method converges quadratically as follows:(33)tanϕ˜≤α2ξ2+1+αξ2sinϕ/σmin⊥sinϕC2λ1−w∗Awλ2−θcosϕsin2ϕunder the assumption(34)min2≤j≤nλj−θqm+1λj−θ>λ1−θλn+λ2−2λ1λn−λ11+ξ2λn−λ1sinϕσmin⊥,where σmin⊥=σmin⊥A−θI, α=λ1−w∗Aw2sin2ϕ+A−θIw21/2,(35)C1=λn−λ1λ2−λ1+2θ−λ121+ξ1σmin⊥,and(36)C2=λn−λ1λ2−λ1+2θ−λ121+ξ2λn−λ1sinϕσmin⊥.Proof.
According to the properties of the Krylov subspace method, e.g., the conjugate gradient method, we have(37)ηm⊥VmJ=spanr,Aθ,ur,…,Aθ,um−1r.
Specially, we haveηm⊥r; combining with the factorization in (3), we have(38)r∗ηm=u∗A−θIqm+1A−θIu=x1cosϕ+wsinϕ∗A−θIqm+1A−θIx1cosϕ+wsinϕ=λ1−θqm+1λ1−θcos2ϕ+w∗A−θIqm+1A−θIwsin2ϕ=0.
Then, we further have(39)|qm+1λ1−θ|=w∗A−θIqm+1A−θIwλ1−θcos2ϕsin2ϕ≥min2≤j≤nλj−θqm+1λj−θλ1−θcos2ϕsin2ϕ.
By straightforward computations, we have(40)r2=λ1−w∗Aw2sin4ϕcos2ϕ+A−θIw2sin2ϕ,which implies that(41)r≤αsinϕ.
Ifηm≤ξ1r, according to the estimate of τ, we get(42)τ≤1+ξ1σmin⊥r2≤α21+ξ1σmin⊥sin2ϕ.
Thereby, we obtain(43)qm+1λ1−θ−τ≥min2≤j≤nλj−θqm+1λj−θλ1−θcos2ϕsin2ϕ−α21+ξ1σmin⊥sin2ϕ=min2≤j≤nλj−θqm+1λj−θλ1−θcos2ϕ−α21+ξ1σmin⊥sin2ϕ.
On the contrary, under the assumption in (3), we have(44)min2≤j≤nλj−θqm+1λj−θλ1−θcos2ϕ−α21+ξ1σmin⊥≥λn+λ2−2λ1λn−λ1cos2ϕ1+ξ1σmin⊥−α21+ξ1σmin⊥≥λn+λ2−2λ1λn−λ11+ξ1σmin⊥−α21+ξ1σmin⊥=λn+λ2−2λ1λn−λ1−α21+ξ1σmin⊥=λn+λ2−2λ1λn−λ1−λ1−θλ1−w∗Aw−A−θIw21+ξ1σmin⊥≥λn+λ2−2λ1λn−λ1−λ2−λ12λn−λ1−λn−θ21+ξ1σmin⊥=2λn+λ2−3λ12λn−λ1−λn−θ21+ξ1σmin⊥≥2λn+λ2−3λ12λn−λ1−λn−θλn−λ11+ξ1σmin⊥=λn−λ1λ2−λ1+2θ−λ121+ξ1σmin⊥.
Thus, combining with the estimate in (10), we have the following estimate:(45)tanϕ˜≤ξ1r+|τ|sinϕC1sin2ϕλ1−w∗Awλ2−θcosϕsin2ϕ≤ξ1α+|τ|C1λ1−w∗Awλ2−θcosϕsinϕ.
Similar to the above proof, ifηm≤ξ2r2, according to the estimate of τ, we get(46)τ≤1+ξ2rσmin⊥r2≤α21+αξ2sinϕσmin⊥sin2ϕ.
Note that(47)1+αξ2sinϕ=1+ξ2λ1−θλ1−w∗Aw|+A−θIw212sinϕ≤1+ξ2θ−λ1λn−λ1+λn−θ212sinϕ≤1+ξ2θ−λ1λn−λ1+λn−θλn−λ112sinϕ=1+ξ2λn−λ1sinϕ,and combining with the assumption in (33), we obtain(48)qm+1λ1−θ−τ≥min2≤j≤n|λj−θqm+1λj−θλ1−θcos2ϕsin2ϕ−α21+αξ2sinϕσmin⊥sin2ϕ=min2≤j≤nλj−θqm+1λj−θλ1−θcos2ϕ−α21+αξ2sinϕσmin⊥sin2ϕ≥1+ξ2λn−λ1sinϕσmin⊥λn+λ2−2λ1λn−λ1−α2sin2ϕ≥λn−λ1λ2−λ1+2θ−λ121+ξ2λn−λ1sinϕσmin⊥sin2ϕ.
Utilizing the estimate in (10) again, we have the following estimate:(49)tanϕ˜≤ξ2r2+τsinϕC2sin2ϕλ1−w∗Awλ2−θcosϕsin2ϕ≤α2ξ2+1+αξ2sinϕ/σmin⊥sinϕC2λ1−w∗Awλ2−θcosϕsin2ϕ.Note that the assumptions in (32) and (34) will easily be satisfied if min2≤j≤nλj−θqm+1λj−θ is not very small because the right terms of the two assumptions have the factor λ1−θ=Osin2ϕ, which would be small if the current approximate eigenvector is near to the desired one.From Theorem3.1, we cannot fully understand the convergence of the JD method because it just gives us a preliminary convergence analysis and includes some unknown factors to be explored. Thus, we further explored these unknown factors in Theorem 3.2 and established the convergence of the JD method, from which we can see clearly how the inner correction equation controls the convergence of the outer iteration.In addition, from Theorem3.2, we can see that the JD method converges linearly if the accuracy of the correction equation is roughly Or and converges quadratically with the accuracy of the correction equation being Or2. Moreover, observing the convergence factor, we can see that the method can gain cubic convergence rate ideally.


## 4. Estimate for the Iteration Number

In this section, we first give the bounds of the residual norms of the JD iteration method. Through this bound, we may analyze the relation between the outer iteration and the inner iteration; more clearly speaking, we can see how the inner iteration controls the convergence property of the outer iteration.Theorem 4.1.
Letθ,u be the approximate eigenpair obtained by Algorithm (1) with u=1, θ=u∗Au, and the residual r=Au−θu. If we solve the JD correction equation by the Krylov subspace method with the zero initial vector, then we get the following estimate:(50)r˜≤1u˜1+ξmrσmin⊥+ξmr,where σmin⊥=σmin⊥A−θI and u˜=qmA−θIu is the new approximation defined as (11).Proof.
Using the minimal residual property of Ritz values (Fact 1.9 in [4]), we have(51)r˜=Au˜u˜−θ˜u˜u˜≤1u˜A−θIu˜.
Based on the relation in (12) of the residual equation, we have(52)A−θIqmA−θIu=τu+ηmwithτ=u∗A−θItm.
By making use of the estimate ofτ, we get(53)r˜≤1u˜τu+ηm≤1u˜τ+ηm≤1u˜r+ηmσmin⊥r+ηm=1u˜1+ξmrσmin⊥+ξmr.From the above theorem, we can choose a considerate stopping factorξ to obtain a higher convergence rate as follows.Corollary 4.1.
Under the assumption of Theorem 4.1, if the stopping factorξ¯ satisfies ξ≤cr (equivalent to ηm≤cr2) with c≤1, then the following relation holds:(54)r˜≤1u˜1+crσmin⊥+cr2.Next, we give a rough estimate foru˜; based on u˜=qmA−θIu and qm+1λ=λqmλ−τ, we have(55)u˜A−θI−1qm+1A−θI+τu=λ1−θ−1qm+1λ1−θ+τx1cosϕ+A−θI−1qm+1A−θI+τwsinϕ,which further indicates that(56)u˜≥qm+1λ1−θ+τλ1−θcosϕ.We can see that, under some assumptions, e.g.,qm+1λ1−θ+τ≥Osin2ϕ and λ1−θ≤Osin2ϕ, the asymptotical convergence properties of Theorem 4.1 and Corollary 4.1 are identical to those of Theorem 3.2.Theorem4.1 provides us with an asymptotical description of the convergence property from the point of view of the residual norm. We can see that, at the starting iterate, i.e., r is not very small relative to the stopping precision, the stopping factor ξ need not be very small; we can obtain a fast convergence rate; that is to say, it only needs a few iterate numbers for the inner iteration. As the approximate eigenvector u is near to the desired eigenvector x1, we need a relative high accuracy for the inner iteration to gain an ideal convergence rate.In theory, we can give an estimate whether the JD method converges or not through the factorq=1/u˜1+ξmr/σmin⊥+ξm. From the above factor, we can see that it is u˜ and the inner residual factor ξm which determine whether the outer residual norm decreases or not. So, we can use q<1 as the inner iteration stopping criterion. Perhaps, we can also estimate the convergence property through judging the norm of the new approximation u˜.In the following discussion, let us give an estimate on the iteration number roughly by using the conjugate gradient method to solve the JD correction equation.First, we illustrate that it is reasonable to solve the correction equation by using the conjugate gradient method as the approximationu is close to the desired vector x1.Lemma 4.1.
For anyv∈spanu⊥, the following inequality satisfies(57)Jμ,uv,v≥λ1+λ2−μ−λuv2,where Jμ,u=I−uu∗A−μII−uu∗.From the above lemma, we can see that ifθ<λ1+λ2/2, which is satisfied under the assumption λ1−θ<λ2−θ, Jθ,u is positive definite in the subspace span u⊥.Next, we give a simple convergence property of the conjugate gradient method for the linear equationAx=b with A being positive definite.Lemma 4.2.
Solving the symmetric positive definite linear system of equationsAx=b by applying the conjugate gradient algorithm, the following estimate holds for the residual norm:(58)ηm≤2k32k−1k+1mη0,where xm is the approximate solution obtained at the mth step of the conjugate gradient algorithm, ηm=Axm−b is the corresponding residual, and k=AA−1 is the condition number of A.Proof.
According to Theorem 6.6 in [5], we have(59)xm−x∗A≤2k−1k+1mx0−x∗A,where x∗ is the exact solution and xA is the A-norm defined as xA=x∗Ax.
Based on the minimax theorem, we know that(60)λminAx2≤xA2=x∗Ax≤λmaxAx2,and by straightforward computations, we frequently obtain(61)xm−x∗≤2kk−1k+1mx0−x∗.
Thus, the residual norm has the following estimate:(62)ηm=Axm−b≤Axm−x∗≤2Akk−1k+1mx0−x∗≤2AA−1kk−1k+1mη0=2k32k−1k+1mη0,which completed the proof of this theorem.Next, we will combine Theorem4.1 with Lemma 4.2 to give an estimate on the iteration number of the correction equation roughly.In fact, the coefficient operatorI−uu∗A−θII−uu∗ of the correction equation can be seen as the operator A−θI restricted to the subspace spanu⊥, which is denoted by A−θI⊥.Assume that, at the current outer iterate, all approximationsui˜ obtained by the conjugate gradient method satisfy μ1≤‖ui˜‖≤μ2 for i=1,2,…,m, where m is the maximum iteration number of the correction equation.Theorem 4.2.
In the JD method, solving the correction equation by applying the conjugate gradient method with the zero initial vector, the iteration numberm of the correction equation should satisfy(63)m≥ln2k⊥3/2+lnr+σmin⊥/μ1σmin⊥−rlnk⊥+1/k⊥−1,where k⊥ is the condition number of the matrix A−θI⊥ to ensure the convergence of the algorithm.Proof.
By assumption, the convergence factorq in Theorem 4.1 satisfies(64)q=1u˜1+ξmrσmin⊥+ξm≤1μ11+ξmrσmin⊥+ξm.
Thus, if1/μ11+ξmr/σmin⊥+ξm<1, that is,(65)ξm≤μ1σmin⊥−rr+σmin⊥,the JD method converges. It indicates that the residual norm of the correction equation resm satisfies(66)resm≤μ1σmin⊥−rr+σmin⊥r.
Based on Lemma4.2, we know that if 2k⊥3/2k⊥−1/k⊥+1mr≤μ1σmin⊥−r/r+σmin⊥r, the JD method converges. By straightforward computations, we frequently get(67)m≥ln2k⊥3/2+lnr+σmin⊥/μ1σmin⊥−rlnk⊥+1/k⊥−1.We remark that the convergence theories in Theorem4.1 and Corollary 4.1 are identical to those of Theorem 3.2 to interpret the convergence of the JD method from the point of view of the residual norm. It indicates that, at the start of the iteration process, the inner correction equation only needs to be solved with a small number of iterations; however, once we obtain a good approximate eigenvector, the inner correction equation is recommended to be solved with a high accuracy.From Theorem4.2, we can see that the iteration number of the correction equation solved by the CG method, which ensures the decrease of the outer iteration, depends on r. If r does not shake vigorously, the inner iteration number will be roughly a constant as the outer iteration proceeds.


## 5. Concluding Remarks

We have proved that the inexact simplified Jacobi–Davidson iteration method for Hermitian eigenvalue problems can attain cubic convergence rate locally, and it is asymptotically convergent as fast as the Rayleigh quotient iteration. Thus, both exact and inexact simplified Jacobi–Davidson methods are competitive with the exact and inexact Rayleigh quotient iterations. Moreover, we give an estimate of iteration numbers of the inner correction equation. Based on these theoretical results, we can see clearly how the accuracy of the inner correction equation controls the outer iteration.



---

*Source: 2123897-2021-12-07.xml*