{'fraction_non_alphanumeric': 0.05085422321571132, 'fraction_numerical': 0.01656554366916813, 'mean_word_length': 3.9384979302188055, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Residual norms in the Rayleigh-Ritz and refined Projection methods

This paper derives bounds for the ratio of residual norms in the refined and Rayleigh- Ritz projection methods. To do this, it uses the Least squares and line search projection method proposed in [6]. The bound derived in this paper is less costly to compute. Further, it is practically useful to assess the superiority of the refined and the Rayleigh-Ritz projection methods one over the other.

1. Introduction. Projection methods are quite familiar to solve large sparse eigenvalue problems. These methods produce eigenpair approximations using either oblique or orthogonal projections onto a specifically chosen vector space. Depending on a chosen vector space these methods are classified as Krylov subspace methods and Jacobi-Davidson type methods. The Lanczos method for symmetric matrices and the Arnoldi method for non-symmetric matrices are well-known and come under the category of Krylov subspace methods. Similar to Lanczos and Arnoldi methods, Jacobi-Davidson method also starts with an arbitrarily chosen unit vector called the Initial Vector. Then at each iteration, it extends an existing vector space using the solution of a system of linear equations called the Correction Equation. The correction equation varies depending on the procedure chosen for extracting eigenpair approximations from a vector space.
The Rayleigh-Ritz projection is a well-known procedure for extracting eigenpair approximations and is inherent in these projection methods [7,9]. The Rayleigh-Ritz projection produces good approximations to the eigenvalues in the exterior of the spectrum. To better approximate interior eigenvalues, It requires the inverse of a given matrix which is computationally more costly. This problem resolved by using the Harmonic projection [3], but, as in the Rayleigh-Ritz projection, the eigenvector approximations produced by the Harmonic projection method also may not converge to an eigenvector, even though the corresponding eigenvalue approximations do converge [2,10]. This misconvergence problem is avoidable in the Refined projection method [4,1], and in the Least squares and Line search technique (LLS).
The refined projection method preserves an eigenvalue approximation that obtained using Rayleigh-Ritz projection. Then, it determines corresponding eigenvector approximation such that residual norm is minimum overall unit vectors in a vector space, from which an eigenvalue approximation sought. To find such an approximate eigenvector, it solves a singular value problem of smaller size. The LLS technique procures an approximate eigenpair from Rayleigh-Ritz projection. Then, it improves an eigenvector approximation in Rayleigh-Ritz projection by using least squares heuristics and line search technique [5,6].
It is a general belief that the residual norm in the refined projection method is too small compared to that in the Rayleigh-Ritz projection. However, it is still unknown how much smaller the former residual norm compared to the later. Although the answer for this will be quite useful to create robust and efficient eigensolvers, it is still unanswered as these two methods came from different perspectives, singular value problem, and eigenvalue problem respectively. This paper extinguishes this question by deriving bounds for the ratio of residual norms in Rayleigh-Ritz and refined projections.
The paper is organized as follows; Section 2 briefly discusses the Rayleigh-Ritz projection, Refined projection, and LLS methods. Then, Section 3 determines the upper and lower bounds for the concerned ratio of residual norms. Section 4 concludes the paper.
2. Rayleigh-Ritz, Refined Rayleigh-Ritz and LLS methods. Let A be a given matrix of order n and V is a k dimensional vector space. Suppose that column vectors of a matrix V = [v 1 v 2 · · · v k ] form an orthonormal basis of V. Then to produce an approximate eigenpairs of A, the Rayleigh-Ritz projection method solves an eigenvalue problem for the matrix H := V * AV of order k. In general, k is small and this eigenvalue problem can be solved using classical methods such as the QR algorithm.
As column vectors of V are orthonormal, V * V = I. Further, an eigenpair (θ i , y i ) of H satisfies the relation: V * (A − θ i I)V y i = 0. That means, approximations to eigenpairs of A produced by the Rayleigh-Ritz projection method satisfy the Galerkin condition: Equivalently, this can be written as follows: In general, the above equation is not a good indication on V y i being an eigenvector approximation. It shows that V y i is orthogonal to its corresponding residual vector AV y i −θ i V y i . It further shows that eigenvector approximations V y i may not converge to an eigenvector of A, even though corresponding eigenvalue approximations converge to an eigenvalue [2].
The Refined projection method is a remedy for the mis-convergence problem of eigenvector approximations in Rayleigh-Ritz projection. An eigenvector approximation u Ri in the Refined projection method satisfies the following: where θ i is an eigenvalue approximation that retained from the Rayleigh-Ritz projection. Thus, an eigenvector approximation u Ri has the least residual norm overall unit vectors in the vector space from which eigenvalue approximations sought. Hence, the refined projection method computes an eigenvector approximation u Ri by solving a singular value problem for (A − θ i I)V . It is a general belief that (A − θ i I)u Ri ≪ (A − θ i I)V y i . In this paper, we estimate (A − θ i I)u Ri / (A − θ i I)V y i by using a residual vector in the LLS method.
The LLS method preserves an eigenvalue approximation from the Rayleigh-Ritz projection. Then, it solves the following least squares problem to find a vector z i : Further the LLS method uses the line search technique and updates an eigenvector approximation V y i in Rayleigh-Ritz projection to V s i / V s i . Therefore, an eigenvector approximation V s i / V s i in the LLS method has the following optimal property: Note that eigenvector approximations in the LLS method are explicitly related to those in the Rayleigh-Ritz projection, unlike eigenvector approximations in the refined projection method. Further, The LLS method avoids the mis-convergence problem of eigenvector approximations in the Rayleigh-Ritz projection. The LLS method proved its better efficiency in the Jacobi-Davidson method compared to the Jacobi-Davidson method that inherently uses refined projection [6]. The following section will first establish a few relations between residual norms in the refined projection and the LLS method.
In what follows, the Ritz value fixed as θ and its corresponding eigenvector approximations as V y, V u R , V m V m and V s V s in the Rayleigh-Ritz, refined and the LLS methods respectively. Further, a subscript notation i in this section will be ignored.
3. Comparison of residual norms. The following theorem derives a relation between residual norms in the Rayleigh-Ritz and the least squares part of the LLS methods via using a matrix (A − θI)V.
Theorem 1. Let the minimization problem (2.2) have a non-zero solution vector (I − yy * )z. Then the following is true: Proof. From the equation (2.2) note that a vector (I − yy * )z minimizes the least squares functional (A − θI)V y + (A − θI)V (I − yy * )z 2 . Thus, it is a solution of the following normal equations: From the equation (2.2) note that V m = V y + V (I − yy * )z. Thus, Therefore, by using the equation (3.3), the above equation proves the equation (3.1).
The Theorem-1 shows that the least squares approach in the LLS method reduces residual norm to a better extent than the Rayleigh-Ritz method, provided (A − θI)V (I − yy * )z 2 is large. Next, the following lemma [6, Lemma-3] will be helpful in the Theorem-2 to see that the line search technique of the LLS method will bring a further reduction in the residual norms.
Lemma 1. Let u be a vector of unit norm and α be the Rayleigh quotient of u with respect to a Hermitian matrix B. Let s := u + τ (I − uu * )t, where τ = 0 is chosen so that the Rayleigh quotient ρ(s) of s is minimum over span{u, (I − uu * )t}. Write J u,s := (I − uu * )(B − ρ(s)I)(I − uu * ). Then the following relations hold: Theorem 2. Let V y be the Ritz vector corresponding to a Ritz value θ and the vector V (I − yy * )z be a solution of the minimization problem (2.2). Let τ be a scalar such that s := y + τ (I − yy * )z minimizes (A − θI)V s 2 s 2 over span{y, (I − yy * )z}. Write Then the following relations hold: Proof. Conveying the equation (3.4) in the Lemma-1 for the matrix B := V * (A − θI) * (A − θI)V and the vectors u := y, t := z gives the relation in the equation (3.9). Observe that in the Lemma-1, α = (A − θI)V y 2 for B := V * (A − θI) * (A − θI)V and u := y.
Next, to prove the equation (3.10), carry the equations 3.5, 3.6 and 3.7 in the Lemma-1 for the matrix B := V * (A − θI) * (A − θI)V and the vectors u := y, t := z. This gives the following equations respectively: Since y ⊥ (I − yy * )z, by using the equation (3.3), the equations (3.9) and (3.11) gives the following relations: Proof. As the vector (I − yy * )z is a solution of the minimization problem (2.2), it satisfies the equation (3.3). Now, on expanding the expression (A − θI)V s 2 by using s = y + τ (I − yy * )z, we have As s = y + τ (I − yy * )z and y = 1, we have s 2 = 1 + τ 2 (I − yy * )z 2 . This implies . Now, substitute the equations (3.10) and (3.17) in the above equation. On simplification, this gives the following relation: Recall from the equation (3.10) that the right-hand side of the above equation is equal . Thus, we have Therefore, we proved the equation (3.15). To prove the equation (3.16), observe the following from the equations (3.1), (3.10) and (3.17): Now, subtracting one of the above equation from the other gives the equation (3.16).
In the Theorems-2 and 3, we have seen that the relations between norms of residuals in the LLS method involve the scalar τ. The following theorem gives a lower bound for the scalar τ .
Theorem 4. Let τ be a scalar the same as that in the Theorem-2.

Comparison of line search least squares with refined projection.
In the previous section, we compared the residual norms in the Rayleigh-Ritz projection and Line search Least squares(LLS) methods. In this subsection, we establish a connection between the LLS and refined projection methods.
Recall that an approximate eigenvalue θ in the refined projection method is the same as that in the Rayleigh-Ritz projection, and u R := V z R is an eigenvector approximation, where z R is a right singular vector corresponding to the smallest non-zero singular value σ 2 of a matrix (A − θI)V. Hence, a vector z R satisfies the following relations: Using the normal equations (3.2) of a least squares problem (2.2), observe that a vector m = y + (I − yy * )z satisfies the following equation: Now, take an inner product on both sides with a vector z R and use the equation (3.20) to obtain the following: The above equation shows that the ratio of z * R y to z * R (I − yy * )z is real. In fact, the ratio is positive since The last inequality follows since the refined Ritz vector has smallest residual norm overall unit vectors in the vector space spanned by column vectors of V.
By using the equation (3.22) and s = y + τ (I − yy * )z, we have Since τ > 1 and K ≥ σ 2 , the ratio of z * R s to z * R y is positive. Now, we restate this discussion in the form of a lemma for the future use.
Lemma 2. Let s, (I − yy * )z be the same as that in the equation (2.3), and V z R be the refined Ritz vector corresponding to the Ritz value θ. Then, The above lemma inherently assumed that z * R y = 0, which means the Ritz and refined Ritz vectors are not orthogonal. In numerical experiments, this statement holds true, in general. In the next theorem, we will use the above lemma to derive a lower bound for K−σ 2 σ 2 . Theorem 5. Let τ and a vector (I − yy * )z be the same as that in the Theorem-2.

refined Ritz vector corresponding to the Ritz value θ, and m is a solution vector of a least squares problem (2.2). Then
Proof. Recall the equation (3.8) from the previous subsection: Note that s − y = τ (I − yy * )z. Then, by using the equations (3.3) and (3.20), we have By using the equations (3.1), (3.21), and (3.22), this gives Recall the following equation (3.13) from the previous subsection: Apply an inner product on both sides of the above equation with a vector z R . In the resulting equation substitute z * R J y,s (s − y) from the previous equation in the righthand side expression. Then use the equation (3.20) on the left-hand side expression of the same equation. It gives the following: Now, divide the both sides of the above equation with z * R y to obtain the following: (3.26) Recall from Lemma-2 that z * R s z * R y and z * R (I−yy * )z z * R y are positive, and from the Theorem-4 that τ ≥ 1. By using these, the following inequality relation follows from the equations (3.22) and (3.23).
is non-positive, by using the above inequation, the equation (3.26) gives Now, by rearranging the terms, the above inequation can be written as follows: . Since τ > 1, by using these two inequalities the above equation gives the following relation: Now, on substituting the equation (3.22) this inequality gives Further, by using the equation (3.16) the left-hand side expression in the above equation becomes equal to s 2 −1 τ . Thus, we have As s = y + τ (I − yy * )z and y = 1, we have s 2 = 1 + τ 2 (I − yy * )z 2 . Therefore, on substituting this in the above equation, we get the required inequality as in the equation (3.24). The above theorem gives a lower bound for K−σ 2 σ 2 . In order to derive an upper bound for K−σ 2 σ 2 , we define the following function of a variable α : Now, the following lemma describes the characteristics of the function f (α). Lemma 3. Let f (α) be a function of α defined as in the equation (3.27). Then the following are hold true: a) f (α) is a monotonic decreasing function of α. b) If f (α) ≤ 0 for any 0 ≤ α < τ then α satisfies the inequation: c) There exists a root between 0 and τ for the equation f (α) = 0.
Proof. a) For the given function f (α), we have To see f ′ (α) ≤ 0, ∀α, use the optimal property of residual norms in the refined projection method and observe σ 2 ≤ K. Therefore, f (α) is a monotonically decreasing function of α.
b) The substitution of the equation (3.16) in the equation (3.27) leads to is non-positive. Therefore, by using the equation (3.24), this gives the required inequality as 0 ≤ α < τ. c) We have By using s 2 = 1 + τ 2 (I − yy * )z 2 , the above equation can be written as As τ > 1, it is an easy to see that f (0) > 0 by using (3.24) and the above equation.
Similarly, consider As s 2 = 1 + τ 2 (I − yy * )z 2 > 1, we have f (τ ) < 0. Therefore, we have f (0) > 0 and f (τ ) < 0. Hence, there exists a root for the equation f (α) = 0 between 0 and τ. The Lemma-3 has shown that equation f (α) = 0 has a solution between 0 and τ. Let α 3 is such a root. Then, from the equation (3.28) we have Note that the above equation turns the problem of finding an upper bound for K−σ 2 σ 2 into deriving an upper bound for α 3 . To derive an upper bound for α 3 , which depends only on the scalar τ, we make use of the following function of α : Note that the function g(α) is obtained by multiplying the difference between both sides of the inequality in the Lemma-3(b) with (A−θI)V s 2 s 2 . In the following lemma, we characterize the function g(α) defined in the above equation and will establish its relation with the function f (α).
In what follows, with the help of the function g(α) we derive an upper bound for α 3 , a solution of the equation f (α) = 0. For this, the following theorem introduce α 6 , a root of the equation f (α) − τ α (I − yy * )z 2 (A−θI)V s 2 s 2 = 0 and determine a relation between α 6 and α 3 .
Recall that our aim is to determine an upper bound for α 3 in terms of τ. From the above theorem it is equivalent to identify an upper bound for α 6 . For this,the following section introduces another scalar, called α 7 and determine its location with respect to α 3 and α 6 on the real line.

Sectional Formulae.
In this section, we introduce a scalar α 7 < τ, a root of the equation f (α) − g(α) = 0. The following lemma determines a sufficient condition for α 6 to divide α 7 and α 3 externally on the real line.
The above lemma had given an upper bound for α 3 when α 6 externally divides α 7 and α 3 on the real line. In the following, we derive an upper bound for α 3 when α 6 lies in between α 7 and α 3 on the real line. Further, In what follows we use the notation for the convenience. Lemma 7. Let α 7 ≤ α 6 and the point C(α 6 , α 6 z) divides the points A(α 7 , g(α 7 )) and B(α 3 , 0) internally in the ratio m : n. Then, note that the following relations hold true: Proof. Note that A, B, and C are lies on the same straight line as f (α 3 ) = 0, α 6 z = f (α 6 ) and f (α 7 ) = g(α 7 ) from the Theorem-6 and the Lemma-5. Further, as C divides A and B internally in the ratio m : n, we have The above equation yields the following relations: The two relations in the above equation give: Hence the lemma proved. The Lemma-7 has found the ratio at which the point C divides A and B. By using this the next theorem finds a relation between α 6 , α 7 , and τ.
By using the above theorem the following lemma gives the values of α 6 and α 3 in terms of τ, when α 6 stays in between α 7 and α 3 as mentioned in the Lemma-7.
From the Lemmas-6 and 8 observe that the inequality α 3 ≤ τ − 1 14 holds true, irrespective of the position of α 6 with respect to the scalars α 3 and α 7 . We use this in the next section to find a bound for the ratio of residual norms in the refined and Rayleigh-Ritz projection methods. Here, we used the fact that s 2 = 1 + τ 2 (I − yy * )z 2 . Then using α 3 ≤ τ − 1/14 we have K σ 2 ≤ 14τ 2 (I − yy * )z 2 + 1.
This together with the Theorem-5 gives the result that we state in the form of a lemma here.
Lemma 9. Let τ and a vector (I − yy * )z be the same as in the Theorem-2. Also assume that V z R is a refined Ritz vector corresponding to the Ritz value θ. Then

and m is a solution vector of a least squares problem (2.2).
The Lemma-9 has established the relation between residual norms in LLS and refined projection methods. It has shown that the residual norms in both the methods converge to zero together. Now, recall from the equations (3.1) and (3.18) that By using this equation, the Lemma-9 gives the following main result which relates residual norms in Rayliegh-Ritz and refined projection methods. Theorem 8. Let θ be a Ritz value, and V y, V z R be the corresponding eigenvector approximations in the Rayleigh-Ritz and refined projection methods respectively. Then The above theorem relates residual norms in the Rayleigh-Ritz and refined projection methods. It helps us to predict the range of σ 2 , square of a residual norm in the refined projection method without computing a refined Ritz vector, a right singular vector of (A − θI)V. It just requires computing τ and (I − yy * )z. Note that (I − yy * )z is obtained by solving normal equations for the least squares problem in equation (2.2). τ, a solution of the problem considered in the equation (2.3) is obtained by solving an eigenvalue problem of the following matrix of order 2.
The above theorem may helps to create an efficient algorithm that use a combination of refined projection and Rayleigh-Ritz projection methods for solving sparse linear eigenvalue problems.
6. Numerical experiments. In this section, we demonstrate the theory developed so far. This section been divided into two subsections. The first part discusses a method to compute τ and (I − yy * )z . The second part reports numerical results.
6.1. Implementation details. In this section, we discuss how the LLS method obtains eigenvector approximations as the LLS method is the most recent one. The following theorem will be helpful to compute an eigenvector approximation in the Least squares and line search(LLS) method.
Theorem 9. Let (θ, V y) be a Ritz pair but not an exact eigenpair of A. Let the vector x satisfies equation is the corresponding eigenvector approximation in the least squares method, where For the proof of the theorem; See Theorem-4 in [5]. Using the above theorem the LLS method computes a vector (I−yy * )z (I−yy * )z without computing (I − yy * )z explicitly. The LLS technique further improves an eigenvector approximation in the Theorem-9 by using the Line-Search technique introduced in the Theorem-2. As mentioned in the previous section, LLS obtains it by solving the following eigenvalue problem of a matrix of order 2.
From the Lemma-9 note that τ and (I −yy * )z 2 are required to compare residual norms in the Rayleigh-Ritz projection, LLS, and refined projection methods. Observe So far, In this section we discussed how to compute τ and (I − yy * )z . In the following subsection, we report the numerical results. At each iteration of the Jacobi-Davidson method, we compute refined Ritz vector also and compare its residual norm with those in the Rayliegh-Ritz and LLS methods in accordance with the Lemma-9.
In this example we fixed the size of a search subspace in the Jacobi-Davidson method to 200. It is well known that τ = 1 in the first iteration as the search subspace contains only initial vector. The Figure-1 depicts the curves of (I − yy * )z 2 against the iteration number. It is clear from the figure that as the iteration number grows, (I − yy * )z 2 decreases. We found that from the 150 th iteration onwards its value is below O(10 −5 ). Thus, the Figure-1   The Figure-2 shows K/σ 2 and its bounds in the Lemma-9 against iteration number.
Recall that σ is residual norm in the refined projection method which is minimum over all unit vectors in the entire search subspace. From the figure it is easy to see that K/σ 2 lies in the interval (1, 1.2), that means σ 2 > (0.8)K. Here, K = (A − θI)V (y + (I − yy * )z 2 , a residual norm of non-normalized vector V y + V (I − yy * )z. Therefore, normalized residual norm of this vector will be much closer to residual norm in the refined projection.  Example 2. In this example the matrix is DW 2048 from the Matrix Market. We use the Arnoldi method with LLS to compute the eigenvalue with largest real part. The initial vector chosen as ones(2048, 1). Since search subspace updataion in the Arnoldi method doesn't require eigenvector approximation like the Jacobi-Davidson method, we tested our theoretical results with explicitly restarting Arnoldi method. In restarting Arnoldi method the size of a Krylov subspace is fixed to 10 for this example. However, the same scenario that we present here is observed with subspaces of larger size. At the end of each restart, an initial vector updated by an eigenvector approximation at hand obtained using the LLS method.
The Figures-4, 5, and 6 shows the curves for (I − yy * )z 2 , K/σ 2 , and τ against restart number respectively. Observe from the Figure-4 that norm of (I − yy * )z recedes near to zero as the restart number grows. Thus, by using the Lemma-9 note 7. Conclusions. In this paper, bounds for a ratio of residual norms in the refined and Rayleigh-Ritz projections have been derived. These bounds are in terms of (I − yy * )z 2 . andτ, a scalar in the line search and least sqaures method; See equation (2.3). Here, V y is an eigenvector approximation in the Rayleigh-Ritz projection method and z is a solution vector of a least squares problem in the equation (2.2).
Moreover, the bounds that are derived in this paper are different from the relationships between the above mentioned residuals which have already been studied by Z. Jia; see Section 4 in Z. Jia "Some theoretical comparisons of refined Ritz vectors and Ritz vectors", Science in China Ser. A Mathematics 2004 Vol.47 Supp. 222-233. In this reference, the relationships between the above-mentioned residuals are in terms of the angle between refined Ritz vector and Ritz vector and the second smallest singular value of a singular value problem in the refined method. Thus, computing those bounds practically requires the computation of a Ritz vector, refined Ritz vector, the angle between them and the second smallest singular value. It is very costly to compute all these quantities. Thus, these relations are useful only theoretically since once refined Ritz vector and Ritz vectors are computed, practically there is no requirement of computing the second smallest singular value to compare the residual norms in both the methods.
The bounds derived in this article for the ratio of residual norms in the Rayleigh-Ritz and the refined projection methods are practically useful. These bounds predicts how much smaller the residual norm in refined projection method compared to residual norm in the Rayleigh-Ritz method, without computing the refined Ritz vector.