# The Rate of Convergence of the SOR Method in the Positive Semidefinite Case

Authors: Achiya Dax
Journal: Computational and Mathematical Methods
 (2022)

---

## Abstract

In this paper, we derive upper bounds that characterize the rate of convergence of the SOR method for solving a linear system of the formGx=b, where G is a real symmetric positive semidefinite n×n matrix. The bounds are given in terms of the condition number of G, which is the ratio κ=α/β, where α is the largest eigenvalue of G and β is the smallest nonzero eigenvalue of G. Let H denote the related iteration matrix. Then, since G has a zero eigenvalue, the spectral radius of H equals 1, and the rate of convergence is determined by the size of η, the largest eigenvalue of H whose modulus differs from 1. The bound has the form η2≤1−1/κc, where c=2+log2n. The main consequence from this bound is that small condition number forces fast convergence while large condition number allows slow convergence.


---

## Body

## 1. Introduction

The SOR method is one of the basic iterative algorithms for solving a large sparse linear system of the form(1)Gx=b,where G∈ℝn×n,b∈ℝn, and x∈ℝn denotes the vector of unknowns. That is, we need to solve a system of n linear equations with n unknowns. The abbreviation SOR stands for “successive overrelaxation.” For a detailed description and discussion of this method, see [1–41]. In this paper, we investigate the SOR rate of convergence in the special case when G is a real symmetric positive semidefinite matrix. This means that G has at least one zero eigenvalue and that the system (1) can be inconsistent. It is also assumed that all the diagonal entries of G are positive. This has two justifications. First, it is not possible to apply the SOR iteration without this assumption. Second, since G is positive semidefinite, a zero diagonal entry implies that the corresponding row and column are null and can be deleted. The last assumption enables us to express G in the form
(2)G=D−L−LT,where L is a strictly lower triangular matrix and D is a positive definite diagonal matrix. The kth SOR iteration, k=1,2,⋯, starts xk−1∈ℝn and computes xk by the rule
(3)xk=Hwxk−1+dw.The matrix(4)Hw=I−wD−wL−1G,is called the SOR iteration matrix,
(5)dw=wD−wL−1b,and w is a relaxation parameter that satisfies
(6)0<w<2.Remark 1.
In this paper, we study the asymptotic rate of convergence of the SOR iteration (3). Thus, when using simpler terms like “fast rate of convergence” or “fast convergence,” we always refer to asymptotic behavior.The role ofHw is seen from the following known observation. Assume for a moment that the linear system (1) has a solution x^∈ℝn. Then, the iteration (3) satisfies
(7)xk−x^=Hwkx0−x^,where x0 denotes the starting point. The last equality reveals the importance of ρHw, the spectral radius of Hw. If ρHw<1, then the sequence xk converges toward x^, and the rate of convergence depends on the size of ρHw. The smaller ρHw is, the faster is the convergence. Otherwise, when ρHw>1, the SOR iteration diverges. Yet, when G has a zero eigenvalue, then ρHw=1 and the situation depends on the consistency of (1). If the SOR iteration attempts to solve an inconsistent system, it diverges. Otherwise, when the system to solve is consistent, it converges. The question discussed in this paper is how the spectral properties of G affect the rate of convergence in this case.The treatment of the positive semidefinite case becomes easier by noting the relation with Kaczmarz’s method. For a detailed description and discussion of Kaczmarz’s method, see [4–6, 8, 10, 11, 13, 15, 20, 21, 31, 33, 34, 36] and the references therein. Let r denote the rank of G. Then, 0<r<n and G has t=n−r zero eigenvalues. Moreover, using the spectral decomposition, it is possible to express G in the form
(8)G=AAT,where A∈ℝn×r has r orthogonal columns. Let the sequence yk, k=0,1,2,⋯, be generated by Kaczmarz’s method for solving the linear system
(9)Ay=b,where y∈ℝr denotes the vector of unknowns. Then, the following observation is well known, e.g., [4, 8]. If the starting points satisfy
(10)y0=ATx0,then the equalities
(11)yk=ATxk,hold for all k. This relation implies that Kaczmarz’s method obeys the rule
(12)yk=Fwyk−1+ATdw,where
(13)Fw=I−wATD−wL−1A,is the corresponding iteration matrix. The role of Fw will be clarified in the coming discussions.The literature on the SOR method is huge and includes various types of convergence results. However, many of the early results are derived under certain assumptions onG, such as being an “M-matrix” or “consistently ordered,” e.g., [1, 17–19, 35, 37, 41]. One of the first results without such assumptions is Ostrowski’s theorem [29, 37], which ensures that ρHw<1 whenever G is positive definite. Yet, it took about forty years until Oswald [30] lowered the bound on ρHw. See also Axelsson [1] (pp. 241-242) for a similar bound. The current paper extends Oswald’s bound to the positive semidefinite case. The difficulty here is that ρHw=1. So we need to see what dominates the rate of convergence in this case.The interest in the semidefinite case was initiated in the work of Keller [22]. Then, the surprising behavior of the SOR method when solving inconsistent linear systems was studied in a small number of papers, e.g., [2, 7, 8, 28]. It is shown there that if the linear system (1) is inconsistent then although the SOR sequence xk diverges it obeys the rule
(14)xk=x^k+kv,k=1,2,⋯,where x^k is a converging sequence and v is a fixed vector that belongs to NullG=NullAT. Otherwise, when the linear system is consistent, v=0 and xk=x^k. This explains why the related Kaczmarz sequence (11) always converges.The convergence properties of iterative methods for solving consistent positive semidefinite linear systems have attracted the attention of several authors. See, for example, [2, 3, 7, 8, 14, 22–26, 40], and the references therein. In particular, if G is positive semidefinite as above then the SOR iteration matrix, Hw, is known to be “semiconvergent”. Let λj,j=1,⋯,n, denote the eigenvalues of Hw and assume that they are sorted to satisfy
(15)λ1≥λ2≥⋯≥λn,which implies that ρHw=λ1. Then “semiconvergent” means that λ1=1, and that any eigenvalue of Hw that satisfies λj=1 must equal 1 and has a 1×1 Jordan block. Furthermore, since G has t zero eigenvalues, the eigenvalues of Hw satisfy
(16)λj=1forj=1,⋯,t,1>λt+1≥⋯≥λn.Consequently, the Jordan canonical form ofHw shows that the rate of convergence is determined by the size of λt+1, which is sometimes called the “convergence factor,” e.g., [26]. This situation means that we need an upper bound on λt+1.The bound is gained in two stages. First, we show that(17)λt+1=ρFw.Then, we establish the inequality(18)ρFw2≤ρFwTFw,and derive a bound on ρFwTFw.The plan of the paper is as follows. We start by exploring the relations between the eigenvalues ofHw and Fw, showing that the two matrices share all the eigenvalues that differ from 1, which proves (17). Then, we study the relations between the iteration matrices of the symmetric SOR (SSOR) method and the symmetric Kaczmarz method and use these relations to simplify the expression for FwTFw. The bound on the spectral radius of this matrix is derived in the third section. The bound has the form
(19)ρFwTFw≤1−1κc,where κ denotes the condition number of G and
(20)c=2+log2n.The condition number is defined as the ratioκ=α/β, where α is the largest eigenvalue of G and β is the smallest nonzero eigenvalue of G. The bound shows that small condition number forces fast rate of convergence, while large condition number allows slow convergence. However, as this is an upper bound, a large condition number does not force slow convergence. Hence, it is worthwhile to have a close look at the reasons behind slow convergence. This issue is discussed in Section 4. It is shown there that small nonzero eigenvalues of G are likely to cause slow asymptotic rate of convergence. Finally, in the last section, we compare our approach with former attempts to derive such bounds.


## 2. Iteration Matrices and Their Eigenvalues

The assumption thatG has positive diagonal entries allows us to make the following simplification. Consider the SOR iteration for solving the normalized system G~x=b~, where G~=D−1/2GD−1/2 and b~=D−1/2b. Then, the related iteration matrix is similar to Hw. Thus, when studying the rate of convergence of the SOR method, it is possible to replace (1) with its normalized form. That is, there is no loss of generality in assuming that D=I. Hence, from now on, we assume that G has the form
(21)G=I−L−LT,where I denotes the identity matrix and L is a strictly lower triangular matrix. As before, r denotes the rank of G and r<n. Consequently, G can be factorized in the form
(22)G=AAT,where the matrix A∈ℝn×r has r orthogonal columns. Moreover, let aiT denote the ith row of A,i=1,⋯,n. Then, (21) implies
(23)aiTai=1fori=1,⋯,n.That is, the rows ofA have unit length. The SOR iteration splits G in the form
(24)G=Bw−Cw,where
(25)Bw=I−wLw,and
(26)Cw=1−wI+wLTw.Recall thatw is a given relaxation parameter that satisfies 0<w<2. The kth SOR iteration, k=1,2,⋯, starts with xk−1 and ends with xk, which is computed by solving the linear system
(27)Bwx=Cwxk−1+b.In other words,xk is obtained from xk−1 by the rule
(28)xk=Hwxk−1+dw,where
(29)Hw=Bw−1Cw,is the related iteration matrix, and
(30)dw=Bw−1b.Observe that (24) enables us to express Hw in the form
(31)Hw=I−Bw−1G=I−Bw−1AAT.Multiplying (28) by AT and using (11) gives
(32)yk=ATHwxk−1+ATdw,while substituting I−Bw−1AAT instead of Hw shows that
(33)yk=I−ATBw−1Ayk−1+ATdw.This means that the iteration matrix of Kaczmarz’s method has the form(34)Fw=I−ATBw−1A.Note thatHw is an n×n matrix while Fw is an r×r matrix. However, as the next theorem shows, these matrices share several eigenvalues.Theorem 2.
Letλ be a nonzero eigenvalue of the matrix Bw−1AAT; then, λ is also an eigenvalue of the matrix ATBw−1A. Conversely, let λ be a nonzero eigenvalue of ATBw−1A; then, λ is also an eigenvalue of Bw−1AAT.Proof.
Letu∈ℝn be a unit eigenvector of Bw−1AAT that corresponds to a nonzero eigenvalue λ. Then, the equality
(35)Bw−1AATu=λu,implies ATu≠0, and multiplying this equality by AT gives
(36)ATBw−1AATu=λATu,which means that λ is an eigenvalue of ATBw−1A.
The converse direction is proved in a similar way. Letv∈ℝr be a unit eigenvector of ATBw−1A that corresponds to a nonzero eigenvalue λ. Then, the equality
(37)ATBw−1Av=λv,implies Av≠0,
(38)AATBw−1Av=λAv,and
(39)Bw−1AATBw−1Av=λBw−1Av,which means that λ is an eigenvalue of Bw−1AAT.☐We have seen that the eigenvalues ofHw satisfy (16). The next theorem shows that λt+1 equals the spectral radius of Fw.Theorem 3.
The eigenvalues ofHw satisfy (16) and (17) with t=n−r.Proof.
Recall thatHw=I−Bw−1G and Fw=I−ATBw−1A, where the matrix ATBw−1A is nonsingular. Now the last theorem implies that the largest eigenvalue of Fw equals the largest eigenvalue of Hw whose modulus differs from 1.☐The bounds which are derived in the next section are using the close relations between the Kaczmarz-SOR method and its symmetric version. The symmetric iteration is combined of two parts. The first one is the usual (“forward”) iteration, while the second is a “backward” iteration in which the rows of the linear system are approached in the reverse order. See, for example, [1, 13, 14, 26, 33, 34, 37, 41]. The iteration matrix of the backward SOR method has the form
(40)H~w=I−Bw−TG,where Bw−T denotes the matrix Bw−1T=BwT−1. This implies that the iteration matrix of the backward Kaczmarz method is
(41)F~w=I−ATBw−TA=FwT.Consequently, the iteration matrix of the symmetric SOR method (SSOR in brief) has the form(42)H~wHw=I−Bw−TGI−Bw−1G,while that of the symmetric Kaczmarz method is
(43)FwTFw=I−ATBw−TAI−ATBw−1A.The next assertion expresses these matrices in a useful form.Theorem 4.
The iteration matrix of the SSOR method has the form(44)H~wHw=I−2w−1Bw−TBw−1G,while that of the symmetric Kaczmarz method is
(45)FwTFw=I−2w−1ATBw−TBw−1A.Proof.
The second equality is a direct consequence of the first one, which is derived from the following identities.(46)H~wHw=I−Bw−TGI−Bw−1G=I−Bw−1G−Bw−TG+Bw−TGBw−1G=I−Bw−1+Bw−T−Bw−TGBw−1G=I−Bw−TBwTBw−1+Bw−TBwBw−1−Bw−TGBw−1G=I−Bw−TBwT+Bw−GBw−1G=I−Bw−T2w−1IBw−1G=I−2w−1Bw−TBw−1G.☐The importance of the last theorem is that it gives a better insight into the eigenvalues of these matrices. In particular, by following the proof of Theorem2, we obtain the following conclusions.Theorem 5.
Letλ be a nonzero eigenvalue of the matrix Bw−TBw−1G; then, λ is also an eigenvalue of the matrix ATBw−TBw−1A and vice versa. Moreover, since the last matrix is symmetric and positive definite, both matrices share the same r positive eigenvalues. The other n−r eigenvalues of Bw−TBw−1G are zeros.Corollary 6.
Letθ denote the smallest eigenvalue of the matrix ATBw−TBw−1A. Then
(47)θ=minxTATBw−TBw−1Ax∣x∈ℝrand∥x∥2=1>0,(48)ρFwTFw=ρI−2w−1ATBw−TBw−1A=1−2w−1θ<1.The next section uses these results to derive upper bounds onρFw and ρFwTFw.


## 3. Upper Bounds on the Spectral Radius

LetT∈ℝn×n be an arbitrary square matrix, and let T2 denote the spectral norm of T. Then, it is well known that T2=σ1T where σ1T denotes the largest singular value of T. It is also well known that the spectral radius of T cannot exceed its spectral norm. That is, ρT≤T2 and
(49)ρT2≤T22=ρTTT.Combining these relations with Corollary6 yields the following useful observation.Theorem 7.
The Kaczmarz iteration matrix,Fw , and the symmetric Kaczmarz iteration matrix, FwTFw , satisfy the relations
(50)ρFw2≤ρFwTFw=1−2w−1θ.The rest of this section is aimed at deriving an “effective” upper bound on the right hand side of (50). In particular, we are looking for a bound that shows how the condition number of A affects the rate of convergence. The first step is to establish a lower bound on the value of θ.Letβ>0 denote the smallest nonzero eigenvalue of G. Then, β is also the smallest eigenvalue of the matrix ATA. Note that the smallest eigenvalue of the matrix Bw−TBw−1 is 1/Bw22. Now from (47), we see that
(51)θ≥β/Bw22≥β/I/w+L22,where the last inequality follows from the triangle inequality for the matrix Bw=I/w−L. Observe that ∥L∥2 is not expected to be much larger than ∥G∥2. Indeed, using induction on n, one can verify that
(52)L2≤12log22nG2.For a detailed proof of this assertion, see Oswald [30]. Let α=∥G∥2 denote the largest eigenvalue of G. Then, (52) can be rewritten as
(53)L2≤γα,where
(54)γ=12log22n.Combining (51) with (53) gives
(55)θ≥β1/w+γα2,and from (50), we obtain that
(56)ρFw2≤ρFwTFw≤1−2/w−1β1/w+γα2,for any w from the interval 0,2. A further improvement is gained by noting that the bound function
(57)φw=1−2/w−1β1/w+γα2,has a unique minimizer in this interval. Computing the derivative of φw and eliminating w′ from the equality φ′w′=0 shows that the minimizer lies at the point
(58)w′=11+γα.It is also easy to verify that(59)φw′=1−1/α/β1/α+2γ,while the assumption that A has unit rows implies α≥1 and
(60)φw′≤1−1/α/β1+2γ.In other words, the spectral radii ofFw′ and Fw′TFw′ satisfy the inequalities
(61)ρFw′2≤ρFw′TFw′≤1−1/κc,where
(62)c=1+2γ=2+log2n,and κ=α/β denotes the condition number of G. The bound on ρFw′ can be simplified by using the inequality
(63)1−1κc≤1−1/2κc2,which shows that
(64)ρFw′≤1−1/2κc.Letw″∈0,2 be a value of w for which ρFwTFw attains its smallest value. That is, w″ is an optimal relaxation parameter for the symmetric Kaczmarz method. Then, clearly,
(65)ρFw″TFw″≤ρFw′TFw′,and the inequalities (61) and (64) remain valid when w″ replaces w′. Similarly, let wopt denote the optimal relaxation parameter for Kaczmarz’s method. Then, the inequality
(66)ρFwopt≤ρFw′,implies
(67)ρFwopt2≤1−1kc,and
(68)ρFwopt≤1−12kc.Sinceα is often considerably larger than 1, the point w′=1/1+γα is often much smaller than 1. On the other hand, in many cases, wopt is larger than 1, and the function ψw=ρFw is decreasing in the interval w′,wopt, which implies that the bound
(69)ρFw≤1−12kc,is likely to hold for all w∈w′,wopt, including w=1.The main consequence from these bounds is that small condition number forces fast rate of convergence, while large condition number allows slow convergence. Yet the bounds are not tight in the sense that the actual rate of convergence is often considerably faster than the implied rate. This behavior is due to a number of reasons. First, in many symmetric positive semidefinite matrices, the ratio∥L∥2/∥G∥2 is considerably smaller than γ. Second, as noted above, w′ is expected to be considerably smaller than 1, so the rate of convergence for wopt (or w=1) is expected to be much faster. Third, let P∈ℝn×n be an arbitrary permutation matrix and consider the SOR method for solving the linear system
(70)PGPTz=Pb.Then, since the iteration matrix ofPGPT is not necessarily similar to that of G, we might get a different rate of convergence, e.g., [27, 32, 37]. On the other hand, since PGPT has the same eigenvalues as G, both matrices share the same upper bound. This shows that the bound holds for the worst possible ordering.Finally, we note that the above treatment of the positive semidefinite case is easily adapted to the positive definite case. In the latter case,A is an n×n invertible matrix, and Fw is similar to Hw, so the bounds on ρFw apply to ρHw.


## 4. Slow Rate of Convergence

The bounds derived in the former section indicate that slow rate of convergence is possible only whenG has a large condition number. On the other hand, the assumption that G has unit diagonal implies that the largest eigenvalue of G satisfies 1≤α≤n. Consequently, a large condition number occurs whenever G has small positive eigenvalues. These observations raise the question of whether small positive eigenvalues are the reason behind slow convergence. Indeed, as explained below, a small positive eigenvalue may cause slow rate of convergence. The first two lemmas provide the tools for proving this claim.Lemma 8.
Defineτ=2−w/w. Then, G satisfies the equality
(71)G=HwTGHw+τBw−1GTBw−1G.Proof.
The definition ofBw implies that Bw=1/wI−L and
(72)BwT+Bw−G=τI.
Now the equalityHw=I−Bw−1G shows that
(73)G−HwTGHw=Bw−1GTG+GBw−1G−Bw−1GTGBw−1G=Bw−1GTBwBw−1G+Bw−1GTBwTBw−1G−Bw−1GTGBw−1G=Bw−1GTBw+BwT−GBw−1G=τBw−1GTBw−1G.☐Lemma 9.
Letβ denote a nonzero eigenvalue of G and let v denote the corresponding unit eigenvector. That is, Gv=βv,vTv=1, and β>0. Then
(74)Bw−1v2≤1/βτ1/2.Proof.
Using (71) and the fact that the matrix HwTGHw is positive semidefinite, we obtain the inequalities
(75)β=vTGv≥τvTGBw−TBw−1Gv=τβ2∥Bw−1v∥22,and
(76)∥Bw−1v∥22≤1τβ.☐Theorem 10.
Letv be an eigenvector of G as above, and let u and η be defined by the equalities
(77)u=Bw−1v∥Bw−1v∥2,η=β∥Bw−1v∥2.
Then(78)Hwv=v−ηu,where η satisfies
(79)η≤βτ1/2,and
(80)Hwv2≥1−η.Proof.
A further use of the equalityHw=I−Bw−1G gives
(81)Hwv=v−Bw−1Gv=v−βBw−1v=v−ηu,while from (74) we see that
(82)η=βBw−1v≤β/βτ1/2=β/τ1/2.
Finally, the inequality(83)v−ηu2≥v2−ηu2=1−η,proves (80).☐One consequence of (79) is that small β implies small η, while (80) shows that for small η the error component in the direction of v decays slowly. That is, small β leads to slow error decay. Another consequence is that small τ (which means w close to 2) may compensate the slowing effect of small β.


## 5. Concluding Remarks

The SOR method and Kaczmarz’s method have been intensively studied for many years. Thus, naturally, some of the mentioned results can be found elsewhere in different forms. In particular, the Kaczmarz iteration matrix (34) and the symmetric Kaczmarz iteration matrix (45) both easily come out as special cases of a more general iteration, see [13] (prop. 4 and 10). Also, the relation between the spectral radius of Kaczmarz and symmetric Kaczmarz (first part of Theorem 7) is already observed in [13] (§4).Estimates of the rate of convergence in the semidefinite case are derived in a series of papers by Lee et al. [23, 24, 40]. However, these estimates have a different flavor, as they are not using the eigenvalues of G or its condition number.More recently Oswald and Zhou [31] have used the concept of stable Hilbert splittings to develop a unified approach for studying the convergence of multiplicative Schwartz methods. This approach was used in [31] to derive upper bounds on the rate of convergence of Kaczmarz’s method, and later in [32], it was modified to bound the SOR convergence in the semidefinite case.The current treatment of the semidefinite case is quite different. It is based on direct arguments from linear algebra, such as the Jordan canonical form ofHw and the relations between the eigenvalues of Hw and Fw. This simplifies the proof and adds important insight into the semidefinite case.The upper bounds on the convergence factor explain why small condition number ensures fast convergence. Another related question is whether and why large condition number leads to slow convergence. The analysis in Section4 provides a convincing explanation. Yet, as this is the first attempt to resolve this enigma, there may be further ways to answer this question.The relation between the condition number and the rate of convergence stands behind the “Kaczmarz anomaly” phenomenon [10, 11]. The Kaczmarz-SOR method is often considered as a prototype of more sophisticated methods from the families of Row-action methods [5, 6, 9], Projection methods [6, 33, 36], Column-action methods [8, 12, 38], and Coordinate-descent algorithms [39]. This suggests that other members of these families may share similar asymptotic behavior. Examples that illustrate this connection are described in [9].



---

*Source: 6143444-2022-03-02.xml*