On Sharp Quadratic Convergence Bounds for the Serial Jacobi Methods

Vjeran Hari^{∗} Department of Mathematics, University of Zagreb, P.O.Box 187, Yu-41000 Zagreb, Yugoslavia

Abstract

Using a new technique we derive sharp quadratic convergence bounds for the serial symmetric and SVD Jacobi methods. For the symmetric Jacobi method we consider the cases of well and poorely separated eigenvalues. Our result implies the result proposed, but not correctly proved, by Van Kempen. It also extends the well-known result of Wilkinson to the case of multiple eigenvalues.

∗This work was supported in part by the U.S. Army. Contract DAAL03-89-C-0038

Introduction

The aims of this paper are the following. First to introduce a more powerful technique for proving the asymptotic convergence estimates of Jacobi processes. Second, to give a sound proof of the sharp quadratic convergence result for the serial symmetric Jacobi methods, the result which is even better than the one proposed (but not correctly proved) by Van Kempen [12]. Our result directly generalizes the result which Wilkinson [23] proved for the case of distinct eigenvalues. Third , to include into consideration both, the case of well separated eigenvalues and the case of eigenvalues forming clusters. Finally, to apply the new technique to the serial Kogbetliantz methods for triangular matrices and to obtain a much better quadratic convergence result than those in [3] and [10].

We note that sharp quadratic convergence estimates of serial proceses recently found nice applications in proving cubic convergence of some quasi-cyclic Jacobi methods [20]. The technique described here recently found application in proving sharp quadratic convergence bounds of the J-symmetric Jacobi method (see [4, 22]).

We believe that this paper ends the quadratic convergence estimates for the serial symmetric and SVD Jacobi methods. For that reason we have tried to obtain the best possible bounds even at the expense of using some uncommon mathematical tricks.

The author is indebted to N. Rhee, Z. Drmač and to the anonymous referees of this journal for helpful comments.

1 Equivalent Orderings

Let us consider a Jacobi-type process of the general form

A^{(k+1)} = U_{k}^{∗}A^{(k)}V_{k}, k ≥ 1,  (1.1)

where A^{(1)} = A is the initial matrix of order n and U_{k} = (u_{ij}^{(k)}), V_{k} = (v_{ij}^{(k)}) are elementary plane matrices of the same order. For each k, U_{k} and V_{k} are defined by a pair of indices (l, m) = (l(k), m(k)) called pivot pair and by 2 × 2 matrices

Û_{k} = [ \begin{matrix}u_{ll}^{(k)} & u_{lm}^{(k)} \\ u_{ml}^{(k)} & u_{mm}^{(k)} \end{matrix} ] , V̂_{k} = [ \begin{matrix}v_{ll}^{(k)} & v_{lm}^{(k)} \\ v_{ml}^{(k)} & v_{mm}^{(k)} \end{matrix} ] ,

called pivot submatrices of U_{k}, V_{k}, respectively. Except for the elements at positions (l, l), (l, m), (m, l) and (m, m), U_{k} and V_{k} are equal to the identity matrix I_{n}. The process (1.1) is defined by a rule (algorithm) for computing Û_{k}, V̂_{k} and by a way of selecting pivot pairs (pivot strategy). The algorithm uniquely defines Û_{k} and V̂_{k} for given Â^{(k)}— the pivot submatrix of A^{(k)}. As in [7] and [6] we denote by T_{lm}(A^{(k)}) the transformation U_{k}^{∗}A^{(k)}V_{k}, so that (1.1) takes form A^{(k+1)} = T_{lm}(A^{(k)}), k ≥ 1. Here U_{k}^{∗} denotes the complex transpose of U_{k}.

We consider only the cyclic (pivot) strategies. They can be defined by the orderings of the set P_{n} = {(i, j) : 1 ≤ i < j ≤ n} (cf. [7]). If

O = (i_{1}, j_{1}), (i_{2}, j_{2}), … (i_{N}, j_{N}),  (1.2)

where N = n(n − 1)/2, is an ordering of P_{n}, then the appropriate cyclic strategy is defined by the index functions l(k), m(k) as follows: (l(k), m(k)) = (i_{r}, j_{r}) provided that k − 1 ≡ r − 1 (mod N), 1 ≤ r ≤ N. The most common cyclic strategies are the row- and the column- cyclic ones (also called serial strategies), defined by the orderings O_{R} = (1, 2), (1, 3), …, (1, n), (2, 3), …, (n − 1, n) and O_{C} = (1, 2), (1, 3), (2, 3), … (1, n), (2, n), …, (n − 1, n), respectively. The first N iterations make the first cycle or sweep of the process (1.1). If only one cycle is considered, we shall sometimes write U_{lm}, V_{lm}, Â_{lm} … instead of U^{(k)}, V^{(k)}, Â^{(k)} …, respectively. Assuming the ordering (1.2), after the first cycle we have

A^{(N+1)} = T_{i_{N} j_{N}} ⋯ T_{i_{1}j_{1}}(A) = U^{∗}AV

where

U = U_{i_{1}j_{1}} ⋯ U_{i_{N} j_{N}} , V = V_{i_{1}j_{1}} ⋯ V_{i_{N} j_{N}} .

Note that T_{i_{r}j_{r}} (U_{i_{r}j_{r}} , V_{i_{r}j_{r}}) commutes with T_{i_{r+1}j_{r+1}} (U_{i_{r+1}j_{r+1}} , V_{i_{r+1}j_{r+1}} resp.) provided the sets {i_{r}, j_{r}} and {i_{r+1}, j_{r+1}} are disjoint. In such a case we shall also call the pairs (i_{r}, j_{r}) and (i_{r+1}, j_{r+1}) disjoint. This fact has been widely used in defining special orderings that make Jacobi methods amenable for parallel processing, and also for proving the global convergence of such processes (see [17] ,[16] etc.). Here we shall use similar ideas for proving sharp quadratic convergence bounds of the serial processes.

Let T be any subset of P_{n} containing t, 1 ≤ t ≤ N elements. Let O(T) be the set (family) of all orderings of T, and let O ∈ O(T), O = (i_{1}, j_{1}), (i_{2}, j_{2}) … (i_{t}, j_{t}). An admissible transposition on O is any transposition of the adjacent terms, (i_{r}, j_{r}), (i_{r+1}, j_{r+1}) ⟼ (i_{r+1}, j_{r+1}), (i_{r}, j_{r}), 1 ≤ r ≤ t − 1, provided that (i_{r}, j_{r}) and (i_{r+1}, j_{r+1}) are disjoint. Two orderings O, Õ ∈ O(T) are equivalent if one can be obtained from the other by a sequence of admissable transpositions (cf. [7]). In this case we write O ∼ Õ. A simple inspection shows that ∼ is an equivalence relation on O(T).

Lemma 1.1 Let O = (i_{1}, j_{1}), …, (i_{t}, j_{t}) and Õ = (ĩ_{1}, j̃_{1}), …, (ĩ_{t}, j̃_{t}) be two orderings of T ⊆ P_{n}. Let U_{i_{r}j_{r}} , V_{i_{r}j_{r}} and Ũ_{ĩ_{r}j̃_{r}} , Ṽ_{ĩ_{r}j̃_{r}}, r = 1 …, t be genarated by the process (1.1) following the orderings O and Õ, respectively, so that

A^{(r+1)} = (U_{i_{1}j_{1}} ⋯ U_{i_{r}j_{r}})^{∗}A(V_{i_{1}j_{1}} ⋯ V_{i_{r}j_{r}}),
Ã^{(r+1)} = (Ũ_{ĩ_{1}j̃_{1}} ⋯ Ũ_{ĩ_{r}j̃_{r}})^{∗}A(Ṽ_{ĩ_{1}j̃_{1}} ⋯ Ṽ_{ĩ_{r}j̃_{r}})

holds for r = 1, …, t. If O ∼ Õ then

U_{ij} = Ũ_{ij}, V_{ij} = Ṽ_{ij} for all (i, j) ∈ T

and

A^{(t+1)} = Ã^{(t+1)}.

Proof: It suffices to proof Lemma 1.1 under assumption that Õ results from O by applying only one admissable transformation. However, the proof for this special case is identical to the proof of Theorem 1 from [7].

Lemma 1.1 is a slight modification of the notable result of Hansen [7] on the equivalence of O_{R} and O_{C}.

To provide usable equivalent orderings we introduce the following notation (cf. [25, page 20])

\begin{matrix}[i, j_{1} : j_{2}] \\ [i_{1} : i_{2}, j] \end{matrix} \begin{matrix}≡ \\ ≡ \end{matrix} \begin{matrix}(i, j_{1}), & (i, j_{1} + 1), & …, & (i, j_{2}) , & 1 ≤ i < j_{1} ≤ j_{2} ≤ n, \\ (i_{1}, j), & (i_{1} + 1, j), & …, & (i_{2}, j) , & 1 ≤ i_{1} ≤ i_{2} < j ≤ n. \end{matrix}

If the subset T ⊆ P_{n} is not explicitly specified, we shall rather use the term sequence than ordering (of T). For i < j we define sequences

\begin{matrix}O_{R,i,j} \\ O_{C,i,j} \end{matrix}  \begin{matrix}≡ \\ ≡ \end{matrix} \begin{matrix}[i, i + 1 : j] , & [i + 1, i + 2 : j] , & …, & [j − 1, j : j], \\ [i : i, i + 1], & [i : i + 1, i + 2], & …, & [i : j − 1, j], \end{matrix}

Õ_{R,i,j} ; Õ_{C,i,j}  \begin{matrix}≡ \\ ≡ \end{matrix} \begin{matrix}[i, j + 1 : n] , & [i + 1, j + 1 : n] , & …, & [j, j + 1 : n], \\ [i : j , j + 1], & [i : j , j + 2], & …, & [i : j , n], \end{matrix} \} j < n
\begin{matrix}O_{R,i} \\ O_{C,i} \end{matrix}  \begin{matrix}≡ \\ ≡ \end{matrix} \begin{matrix}O_{R,1,i} , & Õ_{R,1,i}, \\ O_{C,1,i} , & Õ_{C,1,i}, \end{matrix}

where generally, […], […] (O_{...} , Õ_{...}) denotes the sequence obtained by concatinating the sequences […] and […] (O_{...} and Õ_{...}). Note that O_{R,1,n} = O_{R,n} = O_{R} and O_{C,1,n} = O_{C,n} = O_{C}. In Figure 1 we have denoted by T_{ij} , T̃_{ij} and T_{i} the matrix blocks associated with the sequences O_{R,i,j}/O_{C,i,j} , Õ_{R,i,j}/Õ_{C,i,j} and O_{R,i}/O_{C,i}, respectively.

[figure: T_{ij}; T̃_{ij}; i; j; i; j; T_{i}; i]
Figure 1: The blocks T_{ij} , T̃_{ij} and T_{i}

Lemma 1.2 Let i < j. Then

(i) O_{R,i,j} ∼ O_{C,i,j}

(ii) Õ_{R,i,j} ∼ Õ_{C,i,j}

(iii) O_{R,i} ∼ O_{R,1,i} , Õ_{R,1,i}

(iv) O_{R,i} ∼ O_{C,i}

Proof: (i) In [6] and [7], Hansen has prooved that O_{R} ∼ O_{C}. This result implies (i). (ii) The proof is quite similar to that of (i). The gist lies in the fact that for i + 1 ≤ p ≤ j, j + 1 ≤ q < n, (p, q) is disjoint with all the pairs (r, s) satisfying r < p < q < s. So, the sequence Õ_{R,i,j} can be transformed into Õ_{C,i,j} by a finite set of admissable transformations . (iii) The proof uses the same argument as that in (ii). Here i + 1 ≤ p < q < j.

(iv) Using (i) and (ii) we obtain O_{C,i} = O_{C,1,i} , Õ_{C,1,i} ∼ O_{R,1,i} , Õ_{R,1,i}. Now the assertion (iii) implies (iv).

Later we shall use Lemma 1.1 together with the assertions (iii) and (iv) of Lemma 1.2.

2 Bounds for the Symmetric Jacobi Method

Here we derive sharp quadratic convergence estimates for the case of serial symmetric Jacobi methods. The bounds hold also for the case of complex (hermitian) serial methods but for the reason of keeping the explanation simpler we consider only the real case. First we present some basic results on symmetric Jacobi methods. Next we derive sharp angle estimates in the case of well and poorly separated multiple eigenvalues. Finally, we derive the appropriate quadratic convergence bounds.

Symmetric Jacobi method defines a process of the form (1.1) with U_{k} = V_{k} = R_{k}, R_{k} = R_{lm}(φ_{k}) being the Jacobi rotation with angle φ_{k}, i.e.

tan 2φ_{k} = \frac{±2 a_{lm}^{(k)}}{a_{mm}^{(k)} − a_{ll}^{(k)}} , −\frac{π}{4} ≤ φ_{k} ≤ \frac{π}{4} , k ≥ 1 ,  (2.1)

holds, where + or − sign is used according to whether R_{k} rotates in the negative or positive direction, respectively. Here A^{(k)} = (a_{ij}^{(k)}). The angle choice implies

∥A^{(k+1)}∥_{off}^{2} = ∥A^{(k)}∥_{off}^{2} − 2 | a_{lm}^{(k)} |^{2} , k ≥ 1 ,  (2.2)

where, generaly

∥A∥_{off} = \sqrt{∑_{i≠j^{i,j=1}}^{n} | a_{ij} |^{2}} , A = (a_{ij}).

The method is (globally) convergent provided that (for each initial symmetric matrix A) ∥A^{(k)}∥_{off} → 0 as k → ∞. The convergence is quadratic provided that ultimatelly ∥A^{(k)}∥_{off} reduces quadratically per cycle, that is to say, if

∥A^{(N+1)}∥_{off} ≤ c ∥A∥_{off}^{2} , c > 0,

holds whenever ∥A∥_{off} is sufficiently small. Here c is the constant (bound) we are to determine in this paper.

2.1 Asymptotic Assumptions

Here we derive angle estimates in the cases of well and poorely separated eigenvalues. In the case of well separated eigenvalues we make the following asymptotic assumptions:

A1 A is a symmetric matrix of order n satisfying

∥A∥_{off} ≤ δ ,  (2.3)

where 3δ is the minimal distance between two distinct eigenvalues of A.

A2 The diagonal elements of A affiliated with the same multiple eigenvalue occupy successive positions on the diagonal.

Let the assumptions A1 and A2 hold. Then A can be partitioned as follows

A = (A_{ij}) = [ \begin{matrix}A_{11} & ⋯ & A_{1p} \\ ⋮ & ... & ⋮ \\ A_{p1} & ⋯ & A_{pp} \end{matrix} ] .  (2.4)

For each i = 1, …, p, the block A_{ii} has order n_{i}, where n_{i} is the algebraic multiplicty of λ_{s_{i}}, and λ_{s_{i}} is the i’th multiple eigenvalue in an appropriate ordering of the eigenvalues of A:

λ_{1} = ⋯ = λ_{s_{1}} , λ_{s_{1}+1} = ⋯ = λ_{s_{2}} , …, λ_{s_{p−1}+1} = ⋯ = λ_{s_{p}}.

The perturbation theorem (see [25] or [19] for the eigenvalues of symmetric matrices ensures that all diagonal elements from the block A_{ii} lie in the circle of radius δ around λ_{s_{i}}. The next lemma will even refine this claim. Note that

n_{i} = s_{i} − s_{i−1} , 1 ≤ i ≤ p , s_{0} = o , s_{p} = n.

We assume that p > 1, since otherwise A = λ_{1}I_{n}. If we set

3 δ_{i} = min_{j≠i^{1≤j≤p}} | λ_{s_{j}} − λ_{s_{i}} | , 1 ≤ i ≤ p,

then

δ = min_{1≤i≤p} δ_{i}.

By ∥ · ∥ we denote the Euclidean (Schur, Frobenius) matrix norm and by ∥ · ∥_{2} the spectral (operator,2-) norm.

Lemma 2.1 If the assumptions A1 and A2 hold, then

∥A_{ii}∥_{off} ≤ ∥A_{ii} − λ_{s_{i}}I_{n_{i}}∥ ≤ 0.44\frac{1}{δ_{i}} ∑_{j≠i^{j=1}}^{p} ∥A_{ij}∥^{2}

≤ 0.22\frac{∥A∥_{off}^{2}}{δ_{i}} , 1 ≤ i ≤ p.  (2.5)

Proof: The proof partly relies on the estimates obtained in [11]. Let P_{i} be the permutation matrix satisfying

A_{i} = P_{i}^{T} AP_{i} − λ_{s_{i}}I_{n} = [ \begin{matrix}A_{ii} − λ_{s_{i}}I_{n_{i}} & G_{i} \\ G_{i}^{T} & K_{i} \end{matrix} ] , 1 ≤ i ≤ p ,

where P_{i}^{T} is the transpose of P_{i}, and

G_{i} = [A_{i1}, …, A_{i,i−1} , A_{i,i+1} , …, A_{ip}] , 1 ≤ i ≤ p.

In [11] it has been shown that the eigenvalues of K_{i} are larger than δ_{i} in modulus. Hence, A_{ii} − λ_{s_{i}}I_{n_{i}} is associated with the zero eigenvalue and the rank argument implies

A_{ii} − λ_{s_{i}}I_{n_{i}} = G_{i}K_{i}^{−1}G_{i}^{T} , 1 ≤ i ≤ p.  (2.6)

Applying the perturbation theorem for the eigenvalues of symmetric matrices to A_{i} and (A_{ii} − λ_{s_{i}}I_{n_{i}}) ⨁ K_{i} , where ⨁ denotes the orthogonal sum, we obtain for i = 1, …, p

| κ_{j}^{(i)} − (λ_{j} − λ_{s_{i}}) | ≤ ∥[ \begin{matrix}O & G_{i} \\ G_{i}^{T} & O \end{matrix} ]∥_{2} = ∥G_{i}∥_{2} ≤ ∥G_{i}∥
≤ \frac{\sqrt{2}}{2}∥A∥_{off} < \frac{\sqrt{2}}{2}δ , j ∈ S_{i}.

Here S_{i} = {1, …, n} \ {s_{i−1} + 1, …, s_{i}} and κ_{j}^{(i)} , j ∈ S_{i} are the eigenvalues of K_{i}. Thus

| κ_{j}^{(i)} |> 3δ_{i} − \frac{\sqrt{2}}{2}δ ≥ \frac{6 − \sqrt{2}}{2}δ_{i} , j ∈ S_{i} ,

implying

∥K_{i}^{−1}∥_{2} ≤ \frac{6 + \sqrt{2}}{17} \frac{1}{δ_{i}} ≤ 0.44\frac{1}{δ_{i}} , 1 ≤ i ≤ p ,

and proving the second inequality in the relation (2.5). The last inequality follows from the symmetry of A.

Lemma 2.1 is a slight improvement of the Wilkinson’s result from [24] (cf. [11],[12]). Note that Jacobi method cannot change affiliation of the diagonal elements. Namely, the diagonal elements a_{ll}^{(k)} and a_{mm}^{(k)} are updated by adding a_{lm}^{(k)} tan φ_{k}, a quantity smaller than (\sqrt{2}/2)δ in modulus. So a_{ll}^{(k)} and a_{mm}^{(k)} cannot move into another circles of radius δ (or 0.22δ if we use Lemma 2.1) around the eigenvalues. Let A^{(k)} = (A_{ij}^{(k)}) denote the partition (2.4) of A^{(k)}, k ≥ 1. Lemma 2.1 and the triangle inequality imply that for each k ≥ 1 (regardless of the pivot strategy) we have either

| a_{ll}^{(k)} − a_{mm}^{(k)} | ≤ 2 · 0.22\frac{∥A^{(k)}∥_{off}^{2}}{δ} < 0.44 δ

or

| a_{ll}^{(k)} − a_{mm}^{(k)} | > 3δ − 2 · 0.22δ = 2.56 δ.

Let

M = {k ≥ 1 :| a_{ll}^{(k)} − a_{mm}^{(k)} |> 2.56 δ}.

Then the relation (2.1) implies

| sin φ_{k} | ≤ | tan φ_{k} | ≤ \frac{1}{2} | tan 2ϕ_{k} | ≤ \frac{1}{2} · \frac{2 | a_{lm}^{(k)} |}{2.56δ} ≤ \frac{2}{5} \frac{| a_{lm}^{(k)} |}{δ}, k ∈ M.

Using this inequality together with the relation (2.2) we obtain

∑_{k∈M} sin^{2} φ_{k} ≤ \frac{4}{25} \frac{1}{δ^{2}} ∑_{k∈M}(a_{lm}^{(k)})^{2} ≤ \frac{2}{25} \frac{∥A∥_{off}^{2}}{δ^{2}}  (2.7)

In fact throughout this paper we shall consider only the first cycle of the row-cyclic method. This means that we shall use (2.7) with

M_{1} = {k ∈ M : 1 ≤ k ≤ N}.  (2.8)

instead of M. Since the affiliation is preserved the set M_{1} includes those and only those k’s for which the pivot element a_{lm}^{(k)} lies off the diagonal blocks A_{ii}^{(k)}, 1 ≤ i ≤ p. We can summarize the above considerations with Lemma 2.2 Let the assumptions A1 and A2 hold. Then the relations

∥A_{ii}^{(k)}∥_{off} ≤ ∥A_{ii}^{(k)} − λ_{s_{i}}I_{n_{i}}∥ ≤ 0.44\frac{1}{δ_{i}} ∑_{j≠i^{j=1}}^{p} ∥A_{ij}^{(k)}∥^{2}

≤ 0.22\frac{∥A^{(k)}∥_{off}^{2}}{δ_{i}} ≤ 0.22\frac{∥A∥_{off}^{2}}{δ_{i}} , 1 ≤ i ≤ p

and

∑_{k∈M_{1}} sin^{2} φ_{k} ≤ 0.08\frac{∥A∥_{off}^{2}}{δ^{2}}

hold with any pivot strategy.

Proof: The first assertion follows from Lemma 2.1 and the inequality (2.2). The second one is implied by the relations (2.7) and (2.8).

Later we shall also make use of the set M_{0} ⊂ M_{1} defined by

M_{0} = {k ∈ M_{1} : l(k) < m(k) − 1}.

Asymptotic Assumptions in the Case of Clusters

If the eigenvalues of A form one or more clusters the quantity δ becomes very small. Hence the results of lemmas 2.2 and 2.1 are getting useless in praxis since ∥A∥_{off} is supposed to be even smaller than δ. In such cases we shall use a different measure δ_{c} which can be significantly larger than δ.

Let us group the eigenvalues of A into sets of very close eigenvalues (clusters):

Cl_{i} = { λ_{s_{i−1}+1}, …, λ_{s_{i}} } , 1 ≤ i ≤ p.

We assume as above s_{0} = 0, s_{p} = n. Note that n_{i} = s_{i} − s_{i−1} ≥ 1 is the number of eigenvalues within the i’th cluster Cl_{i}. If n_{i} = 1 or λ_{s_{i}} is the only multiple eigenvalue within Cl_{i} then its width is zero. Here our basic assumption is that F (z) = F (z_{1}, …, z_{p}) = ∑_{i=1}^{p} ∑_{j=1}^{n_{i}} | λ_{s_{i−1}+j} − z_{i} |^{2} is pretty small at minimum. Obviously, F is minimum at z = c where c_{i} = (∑_{j=1}^{n_{i}} λ_{s_{i−1}+j})/n_{i}, 1 ≤ i ≤ p.

Now let A = UΛU^{T} be the spectral decomposition of A. If we write

Λ = Λ_{c} + Λ_{E}, where Λ_{c} = diag(\underbrace{c_{1}, …, c_{1}}_{n_{1}}, …, \underbrace{c_{p}, …, c_{p}}_{n_{p}}),

then

A = A_{c} + E, A_{c} = UΛ_{c}U^{T} .

Note that A_{c} has multiple eigenvalues while ∥E∥ is tiny. In particular ∥E∥ = \sqrt{F (c)} and ∥E∥_{2} is the width of the largest cluster.

For k ≥ 1 we define A_{c}^{(k)} = (a_{c,rt}^{(k)}) and E^{(k)} = (e_{rt}^{(k)}) by

A_{c}^{(k+1)} = R_{k}^{T} A_{c}^{(k)}R_{k} and E^{(k+1)} = R_{k}^{T} E^{(k)}R_{k},

where A_{c}^{(1)} = A_{c}, E^{(1)} = E. Thus A^{(k)} = A_{c}^{(k)} + E^{(k)} and A_{c}^{(k)} (E^{(k)}) is similar to A_{c} (E) for each k. We also have ∥E^{(k)}∥_{off} ≤ ∥E^{(k)}∥ = ∥E∥, k ≥ 1.

Let

3δ_{c,i} = min_{j≠i^{j}} | c_{i} − c_{j} |, 1 ≤ i ≤ p,
δ_{c} = min_{1≤i≤p} δ_{c,i}.  (2.9)

Now we formulate asymptotic assumptions in the case of clusters:

C1 A is a symmetric matrix of order n satisfying

∥A∥_{off} ≤ \frac{1}{2} δ_{c} and ∥E∥ ≤ \frac{∥A∥_{off}^{2}}{δ_{c}} .  (2.10)

C2 The diagonal elements of A affiliated with the same cluster occupy successive positions on the diagonal.

Since C1 implies

∥A_{c}^{(k)}∥_{off} ≤ ∥A^{(k)} − E^{(k)}∥_{off} ≤ ∥A^{(k)}∥_{off} + ∥E^{(k)}∥ ≤ ∥A∥_{off} + ∥E∥
≤ ∥A∥_{off} (1 + \frac{∥A∥_{off}}{δ_{c}} ) ≤ \frac{3}{2} ∥A∥_{off} < \frac{3}{4}δ_{c}, k ≥ 1,  (2.11)

we can apply Lemma 2.1 to A_{c}^{(k)} for every k. Since the diagonal elements a_{c,ll}^{(k)} and a_{c,mm}^{(k)} can change only by the amount which is smaller than | a_{lm}^{(k)} tan φ_{k} | +∥E∥ ≤ \frac{\sqrt{2}}{2}∥A^{(k)}∥_{off} + \frac{∥A∥_{off}^{2}}{δ_{c}} < \frac{1+2\sqrt{2}}{4} δ_{c} < 0.96 δ_{c} their affiliation remains invariant as k varies. By (A_{c,ij}^{(k)}) we denote the partition (2.4) of A_{c}^{(k)}. Lemma 2.3 Let the assumptions C1 and C2 hold. Then the relations

∥A_{c,ii}^{(k)}∥_{off} ≤ ∥A_{c,ii}^{(k)} − c_{i}I_{n_{i}}∥ ≤ 0.405\frac{1}{δ_{c,i}} ∑_{j≠i^{j=1}}^{p} ∥A_{c,ij}^{(k)}∥^{2}
≤ 0.2025\frac{∥A_{c}^{(k)}∥_{off}^{2}}{δ_{c,i}} ≤ 0.456\frac{∥A∥_{off}^{2}}{δ_{c,i}}
< 0.114δ_{c} , 1 ≤ i ≤ p,  (2.12)

and

∑_{k∈M_{1}} sin^{2} φ_{k} ≤ [\frac{1}{3.42} \frac{∥A∥_{off}}{δ_{c}} ]^{2}  (2.13)

hold with any pivot strategy. Proof: The proof follows the lines of proof of Lemma 2.1. In particular, for the eigenvalues κ_{c,j}^{(k)} of K_{c,i}^{(k)} (the submatrix of A_{c}^{(k)}) we have

| κ_{c,j}^{(k)} | ≥ 3δ_{c,i} − \frac{\sqrt{2}}{2}∥A_{c}^{(k)}∥_{off} > 3(1 − \frac{\sqrt{2}}{8})δ_{c,i} , j ∈ S_{i}, 1 ≤ i ≤ p.

Here we have used the relation (2.11). We see that

∥K_{c,i}^{(k)−1}∥_{2} ≤ 8/[3(8 − \sqrt{2})δ_{c,i}] < 0.405/δ_{c,i} , 1 ≤ i ≤ p,

which proves the second and automatically the third inequality in (2.12). The last two inequalities are implied by the relations (2.11) and (2.10).

To prove the second assertion, we use the relations ( 2.12) and (2.10). For k ∈ M_{1}, l(k) ∈ {s_{i−1} + 1, …, s_{i}} and m(k) ∈ {s_{j−1} + 1, …, s_{j}} we have

| a_{ll}^{(k)} − a_{mm}^{(k)} | ≥ | c_{i} − c_{j} | −(| a_{c,ll}^{(k)} − c_{i} | + | a_{c,mm}^{(k)} − c_{j} | +
| a_{ll}^{(k)} − a_{c,ll}^{(k)} | + | a_{mm}^{(k)} − a_{c,mm}^{(k)} |)
≥ 3 min\{δ_{c,i} , δ_{c,j}\} − 0.114δ_{c,i} − 0.114δ_{c,j} − \sqrt{2}∥E^{(k)}∥
> 3δ_{c} − 0.228δ_{c} − \frac{\sqrt{2}}{4}δ_{c} > 2.4184 δ_{c}.

This implies

∑_{k∈M} sin^{2} φ_{k} ≤ [\frac{1}{2.4184\sqrt{2}} \frac{∥A∥_{off}}{δ_{c}} ]^{2} ≤ [\frac{1}{3.42} \frac{∥A∥_{off}}{δ_{c}} ]^{2} ,

and completes the proof of Lemma 2.3.

Remark 2.4 Instead of using (2.9), δ_{c,i} and δ_{c} could have been defined using the metric distance between two sets on the real line R. In particular we would have

d(Cl_{i}, Cl_{j}) = min_{λ∈Cl_{i}} min_{λ̃∈Cl_{j}} | λ − λ̃ |

and

3δ_{c,i} = min_{j≠i^{j}} d(Cl_{i}, Cl_{j}), 1 ≤ i ≤ p,
δ_{c} = min_{1≤i≤p} δ_{c,i}.

In that case the assumption C1 would be a little more stringent, hence Lemma 2.3 and all later results would hold through.

2.2 Auxiliary Lemmas

Here we prove several auxiliary results dealing with bounds for the matrix elements after the completion of the first cycle. From this subsection on we assume that A^{(1)} = A, A^{(2)}, … is the sequence generated by the row-cyclic Jacobi method.

First we introduce notation. Let

q_{0} = 1,
q_{t} = q_{t−1} + (n − t), 1 ≤ t ≤ n,
q_{i}′ = q_{s_{i−1}}, 1 ≤ i ≤ p,

and

q̃_{0} = 1,
q̃_{t} = q̃_{t−1} + (n_{1} − t), 1 ≤ t ≤ n_{1}.

Note that the number q_{t} (q_{i}′) is associated with the stage of the process just after (before) rotating the elements of the t’th row (i’th block-row). The sequence q̃_{t} can be interpreted in the similar way as q_{t} but within the block A_{11}. We shall use the partition (2.4) of A^{(k)} in the form

A^{(k)} = [ \begin{matrix}A_{11}^{(k)} & G_{1}^{(k)} \\ G_{1}^{(k)}^{T} & K_{1}^{(k)} \end{matrix} ] , k ≥ 1.

With the blocks G_{1}^{(k)}, k ≥ 1 we associate the set G_{1} ⊂ P_{n} defined by

G_{1} = {(t, r) : 1 ≤ t ≤ n_{1}, n_{1} + 1 ≤ r ≤ n} \ {(n_{1}, n_{1} + 1)}.

and the following row-vectors:

g_{t}^{(k)}, 1 ≤ t ≤ n_{1}: the rows of G_{1}^{(k)},

a_{t}^{(k)}, 1 ≤ t ≤ n_{1} − 1: a_{t}^{(k)} = [a_{t,t+1}^{(k)}, …, a_{t,n_{1}}^{(k)}],

y_{tr}^{(k)}, 1 ≤ t ≤ n_{1} − 1, n_{1} + 1 ≤ r ≤ n: y_{tr}^{(k)} = [a_{t+1,r}^{(k)}, a_{t+2,r}^{(k)}, …, a_{n_{1},r}^{(k)}].

In Figure 2 we have displayed the first block-row of A^{(1)} = A, together with the vectors a_{t}, g_{t} and several vectors y_{tr}, in the case n = 14, n_{1} = 6.

a_{11}  a_{1} a_{22}  a_{2} a_{33}  a_{3} a_{44}  a_{4} a_{55} a_{5} a_{66} y_{1,7}^{T} y_{2,8}^{T} y_{3,9}^{T} y_{4,10}^{T}y_{5,11}^{T} g_{1} g_{2} g_{2} g_{3} g_{4} g_{5} g_{6}  123456 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Figure 2: n = 14, n^{1} = 6

For vectors x = (x_{t}) and y = (y_{t}) notation | x |≤ | y | means | x_{t} |≤ | y_{t} | for every t. Later on we shall often use the inequalitiy

(α + β)^{2} ≤ (1 + γ)α^{2} + (1 + \frac{1}{γ})β^{2}, γ > 0.  (2.14)

Here the equality is attained for γ = \frac{α}{β} i.e.

min_{γ>0} \{(1 + γ)α^{2} + (1 + \frac{1}{γ})β^{2}\} = (α + β)^{2}.  (2.15)

Lemma 2.5 Let Γ_{1}^{(k)} = ∥A_{11}^{(k)}∥_{off}^{2} + 2 ∑_{j=2}^{p} ∥A_{1j}^{(k)}∥^{2}, k ≥ 1.

(i) If n_{1} ≤ 2, then Γ_{1}^{(N+1)} ≤ ∥A∥_{off}^{2} ∑_{(t,r)∈G_{1}} sin^{2} φ_{tr}

(ii) If n_{1} > 2, then for every γ > 0 holds

Γ_{1}^{(N+1)} ≤ (1 + γ)∥A_{11}∥_{off}^{2} + (1 + \frac{1}{γ})∥A∥_{off}^{2} ∑_{(t,r)∈G_{1}} sin^{2} φ_{tr}.

Proof: (i) If n_{1} = 1, then by the analysis which has been used by Van Kempen [12] we obtain

Γ_{1}^{(n)} = 2∥g_{1}^{(n)}∥^{2} ≤ 2 [\frac{1}{2} ∥K_{1}∥_{off}^{2} + ∥g_{1}∥^{2}] ∑_{r=3}^{n} sin^{2} φ_{1r}
≤ ∥A∥_{off}^{2} ∑_{(t,r)∈G_{1}} sin^{2} φ_{tr}

where K_{1} is obtained from A by removing its first block-row and block-column. Later transformations will not change Γ_{1}^{(n)}, hence (i) follows.

If n_{1} = 2, then 2∥[a_{1}^{(n)}, g_{1}^{(n)}]∥^{2} is estimated in a similar way as 2∥g_{1}^{(n)}]∥^{2} above. In particular, we have

2∥a_{1}^{(n)}∥^{2} + 2∥g_{1}^{(n)}∥^{2} ≤ ∥A∥_{off}^{2} ∑_{r=2}^{n} sin^{2} φ_{1r}
2∥g_{2}^{(2n−2)}∥^{2} ≤ ∥A∥_{off}^{2} ∑_{r=4}^{n} sin^{2} φ_{2r}.

Using again the invariance of the Euclidean norm under orthogonal transformations we easily obtain (i).

(ii) In this case we shall replace the row-cyclic ordering O_{R} with the ordering Õ_{R} ≡ O_{R,1,n_{1}}, Õ_{R,1,n_{1}}, O_{R,n_{1}+1,n}. By Lemma 1.2 (iii) we have O_{R,n_{1}} ∼ O_{R,1,n_{1}}, Õ_{R,1,n_{1}}, hence O_{R} ∼ Õ_{R}. Let Ã^{(k)} = (Ã_{ij}^{(k)}) = (ã_{tr}^{(k)}), G̃_{1}^{(k)}, K̃_{1}^{(k)},ã_{t}^{(k)},g̃_{t}^{(k)}, ỹ_{tr}^{(k)},… be defined by the Jacobi method which uses pivot strategy following Õ_{R}. By Lemma 1.1 we know that φ_{tr} = φ̃_{tr}, (t, r) ∈ P_{n} and Ã^{(k)} = A^{(k)} for q_{n_{1}} + 1 ≤ k ≤ N + 1. Note that in the assertion (ii) only matrices A, A^{(N+1)} and angles φ_{tr} are used. After completing one sweep on the block A_{11} we have

∥Ã_{11}^{(q̃_{n_{1}})}∥_{off} ≤ ∥A∥_{off}, ∥G̃_{1}^{(q̃_{n_{1}})}∥ = ∥G_{1}∥, K̃_{1}^{(q̃_{n_{1}})} = K_{1}.  (2.16)

In order to simplify notation, till the end of this proof we shall denote Ã^{(q̃_{n_{1}}+k)} by Ã^{(k)} for 0 ≤ k ≤ N + 1 − q̃_{n_{1}}, and Ã^{(0)} (superscript shifted) by Ã. The same index shift is applied to G̃_{1}^{(·)}, ã_{t}^{(·)}, . . .. We also set m = n − n_{1}.

Using the analysis of Van Kempen [12] we obtain

∥g̃_{t}^{(t m)}∥^{2} ≤ [\frac{1}{2}∥K̃_{1}^{((t−1)m)}∥_{off}^{2} + ∥g̃_{t}^{((t−1)m)}∥^{2}] ∑_{r>t+1^{r=n_{1}+1}}^{n} sin^{2} φ_{tr}, 1 ≤ t ≤ n_{1}.  (2.17)

By an analysis similar to the one used by Wilkinson [23] we obtain

| ã_{t}^{(t m)} | ≤ | ã_{t}^{((t−1)m)} | + ∑_{r=n_{1}+1}^{n} | ỹ_{tr}^{((t−1)m)} | | sin φ_{tr} |,
= | ã_{t} | + ∑_{r=n_{1}+1}^{n} | ỹ_{tr}^{((t−1)m)} || sin φ_{tr} |, 1 ≤ t ≤ n_{1} − 1.  (2.18)

The last equality holds since ã_{t} is not affected by the transformations which rotate the elements in the rows g̃_{1}, …, g̃_{t−1}. Using the inequalities (2.18) and (2.14), and afterwards the inequality of Cauchy and Schwarz we obtain

∥ã_{t}^{(t m)}∥^{2} ≤ (1 + γ)∥ã_{t}∥^{2} + (1 + \frac{1}{γ}) ∑_{u=t+1}^{n_{1}} ∥g̃_{u}^{((t−1)m)}∥^{2} ∑_{r=n_{1}+1}^{n} sin^{2} φ_{tr}, 1 ≤ t ≤ n_{1} − 1. (2.19)

The invariance property of the Euclidean norm implies

∥a_{t}^{(N+1)}∥^{2} + ∥g_{t}^{(N+1)}∥^{2} = ∥ã_{t}^{(t m)}∥^{2} + |g̃_{t}^{(t m)}∥^{2} 1 ≤ t ≤ n_{1} − 1,
∥g_{n_{1}}^{(N+1)}∥^{2} = ∥g̃_{n_{1}}^{(t m)}∥^{2}

Now, combining the last equalities with the relations (2.19), (2.17) and (2.16) we obtain

Γ_{1}^{(N+1)} = 2 ∑_{t=1}^{n_{1}−1} ∥a_{t}^{(N+1)}∥^{2} + 2 ∑_{t=1}^{n_{1}} ∥g_{t}^{(N+1)}∥^{2} ≤ 2(1 + γ) ∑_{t=1}^{n_{1}−1} ∥ã_{t}∥^{2}
+ 2(1 + \frac{1}{γ}) ∑_{t=1}^{n_{1}} [\frac{1}{2}∥K̃_{1}^{((t−1)m)}∥_{off}^{2} + ∥G̃_{1}^{((t−1)m)}∥^{2}] ∑_{r>t+1^{r=n_{1}+1}}^{n} sin^{2} φ_{tr}

≤ (1 + γ)∥Ã_{11}∥_{off}^{2} + (1 + \frac{1}{γ})∥Ã∥_{off}^{2} ∑_{(t,r)∈G_{1}} sin^{2} φ_{tr}
≤ (1 + γ)∥A_{11}∥_{off}^{2} + (1 + \frac{1}{γ})∥A∥_{off}^{2} ∑_{(t,r)∈G_{1}} sin^{2} φ_{tr}.

Next we generalize Lemma 2.5 to hold for every i. For i = 1, …, p, we define

G_{i} = {(t, r) : s_{i−1} + 1 ≤ t ≤ s_{i}, s_{i} + 1 ≤ r ≤ n} \ {(s_{i}, s_{i} + 1)},
Γ_{i}^{(k)} = ∥A_{ii}^{(k)}∥_{off}^{2} + 2 ∑_{j=i+1}^{p} ∥A_{ij}^{(k)}∥^{2}, k ≥ 1.

Here the empty sum is considered zero.

Lemma 2.6 Let i ∈ {1, …, p}.

(i) If n_{i} ≤ 2, then Γ_{i}^{(N+1)} ≤ ∥A^{(q_{i}′)}∥_{off}^{2} ∑_{(t,r)∈G_{i}} sin^{2} φ_{tr}

(ii) If n_{i} > 2, then for every γ > 0 holds

Γ_{i}^{(N+1)} ≤ (1 + γ)∥A_{ii}^{(q_{i}′)}∥_{off}^{2} + (1 + \frac{1}{γ})∥A^{(q_{i}′)}∥_{off}^{2} ∑_{(t,r)∈G_{i}} sin^{2} φ_{tr}.

Proof: Note that A^{(q_{i}′)} is the matrix obtained by the row-cyclic method just before rotating the elements of the i’th block-row. We can consider the matrix B^{[i]} obtained by removing the first i − 1 block-rows and block-columns of A^{(q_{i}′)}. If we apply Lemma 2.5 to B^{[i]} and take into account that B_{11}^{[i]} = A_{ii}^{(q_{i}′)} and ∥B^{[i]}∥_{off} ≤ ∥A^{(q_{i}′)}∥_{off}, then the assertions of Lemma 2.6 follow for 1 ≤ i ≤ p − 1. For i = p we have Γ_{p}^{(N+1)} ≤ ∥A_{pp}^{(q_{p}′)}∥_{off}^{2}, hence the lemma follows.

As we see ∑_{i} Γ_{i}^{(N+1)} depends on ∑_{i} ∥A_{ii}^{(q_{i}′)}∥_{off}^{2}. The next lemma bounds the last expression.

Lemma 2.7 (i) If the assumptions A1 and A2 hold, then

∑_{i=1}^{p} ∥A_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ 0.08 \frac{∥A∥_{off}^{4}}{δ^{2}} .

(ii) If the assumptions C1 and C2 hold, then

∑_{i=1}^{p} ∥A_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ 3.6 \frac{∥A∥_{off}^{4}}{δ^{2}} .

Proof: (i) In the proof we shall use the row-vectors

x_{t}^{(k)} = [a_{t1}^{(k)}, …, a_{t,t−1}^{(k)}, 0 , a_{t,t+1}^{(k)}, …, a_{tn}^{(k)}] , 1 ≤ t ≤ n, k ≥ 1.

Let i ∈ {1, …, p}. By Lemma 2.1 we have

∥A_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ 0.22 \frac{∥A^{(q_{i}′)}∥_{off}^{2}}{δ_{i}} 0.44\frac{1}{δ_{i}} ∑_{j≠i^{j=1}}^{p} ∥A_{ij}^{(q_{i}′)}∥^{2}

≤ 2 (0.22)^{2} \frac{∥A∥_{off}^{2}}{δ_{i}^{2}} [ ∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q_{i}′)}∥^{2} − ∥A_{ii}^{(q_{i}′)}∥_{off}^{2} ] .

So we have

∥A_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ \frac{2 (0.22\frac{∥A∥_{off}}{δ_{i}} )^{2}}{1 + 2 (0.22\frac{∥A∥_{off}}{δ_{i}} )^{2}} ∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q_{i}′)}∥^{2}.  (2.20)

We shall bound ∥x_{t}^{(q_{i}′)}∥^{2}, s_{i−1} + 1 ≤ t ≤ s_{i}, 2 ≤ i ≤ p in terms of the initial data. For k = 1, …, q_{i}′, ∥x_{t}^{(k)}∥^{2} changes only when the elements of column t are rotated (see Figure 3 below). To get better estimates for ∥x_{t}^{(k)}∥^{2} it would be convenient to have at disposal the column-cyclic strategy. Hence, we shall use the equivalence of the orderings O_{R,s_{i−1}} and O_{C,s_{i−1}} established in Lemma 1.2 (iv). Let Ā^{(1)} = A, Ā^{(2)}, …, Ā^{(q_{i}′)} be obtained by q_{i}′ Jacobi steps following the ordering O_{C,s_{i−1}}. Let the vectors x̄_{t}^{(k)} be defined in the same way as x_{t}^{(k)}, only, using the elements from Ā^{(k)} instead of A^{(k)}. By Lemma 1.2 (iv) and Lemma 1.1 we can conclude that Ā^{(q_{i}′)} = A^{(q_{i}′)} and φ̄_{tr} = φ_{tr} for all (t, r) from O_{C,s_{i−1}} /O_{R,s_{i−1}}. In the following we use the ordering O_{C,s_{i−1}}. Let

w_{t} = [1 + 2 + ⋯ + (s_{i−1} − 1) + (t − s_{i−1} − 1) s_{i−1} ] + 1, s_{i−1} + 1 ≤ t ≤ s_{i}.

[figure] [figure] [figure] [figure]

s_{i−1} + 1

x̄_{s_{i−1}+1}

t

r

x̄_{t}

x̄_{r}

s_{i}

x̄_{s_{i}}
[figure] [figure]

pivot ; position ; in Ā^{(w_{t+1})}

pivot ; position ; in Ā^{(w_{t})}

Figure 3: n = 42, n_{i} = 10, i ∈ {2, …, p − 1}.

Then the pivot elements of Ā^{(w_{t})} and Ā^{(w_{t+1})} are ā_{1t}^{(w_{t})} and ā_{1,t+1}^{(w_{t+1})}, respectively. In Figure 3 are displayed these two pivot positions and the row-vectors x̄_{t}. By the invariance of the Euclidean norm under orthogonal transformations we have for s_{i−1} + 1 ≤ t ≤ s_{i}

∥x̄_{t}^{(w_{t+1})}∥ = ∥x̄_{t}^{(w_{t+1}+1)}∥ = ∥x̄_{t}^{(w_{t+1}+2)}∥ = ⋯ = ∥x_{t}^{(q_{i}′)}∥  (2.21)

and

∥x_{t}^{(1)}∥ = ∥x̄_{t}^{(1)}∥ = ∥x̄_{t}^{(2)}∥ = ⋯ = ∥x̄_{t}^{(w_{t})}∥.  (2.22)

Since the pivot elements are being annihilated we have (x̄_{t}^{(w_{t}+r)})_{r} = 0, 1 ≤ r ≤ s_{i−1}. To make use of it we devide each x̄_{t}^{( )} into three row-components. In particular we have for s_{i−1} + 1 ≤ t ≤ s_{i}

∥x̄_{t}^{(q_{i}′)}∥^{2} = ∥x̄_{t}^{(w_{t+1})}∥^{2} = ∥x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ O_{n−s_{i−1}})∥^{2}+
+ ∥x̄_{t}^{(w_{t+1})}(O_{s_{i−1}} ⊕ I_{n_{i}} ⊕ O_{n−s_{i}})∥^{2} + ∥x̄_{t}^{(w_{t+1})}(O_{s_{i}} ⊕ I_{n−s_{i}})∥^{2}.  (2.23)

Here O_{r} denotes the null matrix of order r and ⊕ stands for the orthogonal sum. For the first and the third row-component we have

| x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ O_{n−s_{i−1}}) |≤ ∑_{r=1}^{s_{i−1}} | x̄_{r}^{(w_{t}+r−1)}(I_{r} ⊕ O_{n−r}) || sin φ_{rt} |

and

| x̄_{t}^{(w_{t+1})}(O_{s_{i}} ⊕ I_{n−s_{i}}) | ≤ | x̄_{t}^{(w_{t})}(O_{s_{i}} ⊕ I_{n−s_{i}}) | +

+ ∑_{r=1}^{s_{i−1}} | x̄_{r}^{(w_{t}+r−1)}(O_{s_{i}} ⊕ I_{n−s_{i}}) || sin φ_{rt} |,

respectively. Using the Cauchy-Schwarz inequality and the inequality (2.14) we obtain for s_{i−1} + 1 ≤ t ≤ s_{i}

∥x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ O_{n_{i}} ⊕ I_{n−s_{i}})∥^{2} = ∥x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ O_{n−s_{i−1}})∥^{2}+

+ ∥x̄_{t}^{(w_{t+1})}(O_{s_{i}} ⊕ I_{n−s_{i}})∥^{2} ≤ (1 + β)∥x̄_{t}^{(w_{t})}(O_{s_{i}} ⊕ I_{n−s_{i}})∥^{2} +

+ (1 + \frac{1}{β}) ∑_{r=1}^{s_{i−1}} ∥x̄_{r}^{(w_{t}+r−1)}(I_{r} ⊕ O_{s_{i}−r} ⊕ I_{n−s_{i}})∥^{2} ∑_{r=1}^{s_{i−1}} sin^{2} φ_{rt} ≤

≤ (1 + β)∥x_{t}^{(1)}(O_{s_{i}} ⊕ I_{n−s_{i}})∥^{2} + (1 + \frac{1}{β}) \frac{1}{2} ∥A^{(1)}∥_{off}^{2} ∑_{r=1}^{s_{i−1}} sin^{2} φ_{rt}.  (2.24)

Here β > 0 is arbitrary, but the same for all t. In (2.24) we have used the following obvious relations

x_{t}^{(1)}(O_{s_{i}} ⊕ I_{n−s_{i}}) = x̄_{t}^{(k)}(O_{s_{i}} ⊕ I_{n−s_{i}}), 1 ≤ k ≤ w_{s_{i}},
∥x̄_{r}^{(w_{t}+k)}(I_{r} ⊕ O_{s_{i}−r} ⊕ I_{n−s_{i}})∥^{2} ≤ ∥x̄_{r}^{(w_{t}+k)}(I_{r} ⊕ O_{s_{i−1}−r} ⊕ I_{n−s_{i−1}})∥^{2} =
= ∥x̄_{r}^{(w_{t})}(I_{r} ⊕ O_{s_{i−1}−r} ⊕ I_{n−s_{i−1}})∥^{2}, 0 ≤ k ≤ r − 1, 1 ≤ r ≤ s_{i−1}

and

∑_{r=1}^{s_{i−1}} ∥x̄_{r}^{(w_{t})}(I_{r} ⊕ O_{s_{i−1}−r} ⊕ I_{n−s_{i−1}})∥^{2} ≤ \frac{1}{2} ∥Ā^{(w_{t})}∥_{off}^{2} ≤ \frac{1}{2} ∥A∥_{off}^{2}.

To find a bound for the norm of the middle row-component we make use of the inequality (2.6) in connection with the matrix Ā^{(w_{t+1})}. We have

Ā_{ii}^{(w_{t+1})} − λ_{s_{i}}I_{n_{i}} = Ḡ_{i}^{(w_{t+1})} \binom{}{K̄_{i}^{(w_{t+1})}}^{−1} Ḡ_{i}^{(w_{t+1}) T} ,

and choosing an appropriate row (the one with the subscript t − s_{i−1}) of the left- and right-hand side, we obtain

∥x̄_{t}^{(w_{t+1})}(O_{s_{i−1}} ⊕ I_{n_{i}} ⊕ O_{n−s_{i}})∥ ≤ ∥e_{t−s_{i−1}}^{T} (Ā_{ii}^{(w_{t+1})} − λ_{s_{i}}I_{n_{i}}) ∥
≤ 0.44\frac{∥Ḡ_{i}^{(w_{t+1})}∥}{δ_{i}} ∥x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ O_{n_{i}} ⊕ I_{n−s_{i}})∥.

Here e_{r}^{T} , 1 ≤ r ≤ n_{i} are the columns of I_{n_{i}}. Since ∥Ḡ_{i}^{(w_{t+1})}∥^{2} ≤ ∥Ā^{(w_{t+1})}∥_{off}^{2}/2 ≤ ∥A∥_{off}^{2}/2 < δ^{2}/2 the last relation together with the relations (2.23) and (2.24) implies

∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q_{i}′)}∥^{2} = ∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(w_{t+1})}∥^{2}

≤ (1 + 2 · 0.22^{2}) ∑_{t=s_{i−1}+1}^{s_{i}} ∥x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ O_{n_{i}} ⊕ I_{n−s_{i}})∥^{2}

≤ 1.0968 [(1 + β)\frac{1}{2} ∑_{t=s_{i−1}+1}^{s_{i}} 2∥x_{t}^{(1)} (O_{s_{i}} ⊕ I_{n−s_{i}})∥^{2}

+ (1 + \frac{1}{β}) \frac{1}{2} ∥A∥_{off}^{2} ∑_{s_{i−1}+1≤t≤s_{i}^{1≤r≤s_{i−1}}} sin^{2} φ_{rt}]

≤ 0.5484[(1 + β)Γ_{i} + (1 + \frac{1}{β}) ∥A∥_{off}^{2} ∑_{s_{i−1}+1≤t≤s_{i}^{1≤r≤s_{i−1}}} sin^{2} φ_{rt}].  (2.25)

This inequality holds for i = 2, …, p. It also holds for i = 1 since

∑_{t=s_{0}+1}^{s_{1}} ∥x_{t}^{(q_{1}′)}∥^{2} = ∑_{t=1}^{s_{1}} ∥x_{t}^{(1)}∥^{2} = \frac{1}{2}Γ_{1} + \frac{1}{2}∥A_{11}∥_{off}^{2}

≤ \frac{1}{2} (Γ_{1} + 2(0.22)^{2} \frac{∥A∥_{off}^{2}}{δ_{1}^{2}} ∥G_{1}∥^{2})
≤ \frac{1}{2} (Γ_{1} + 0.0968 · \frac{1}{2}Γ_{1}) ≤ 0.5242Γ_{1}.

Here we have used Lemma 2.1 and the assumption A1. Combining the relations (2.20), (2.25) and Lemma 2.2 we obtain

∑_{i=1}^{p} ∥A_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ \frac{2 (0.22\frac{∥A∥_{off}}{δ})^{2}}{1 + 2 (0.22\frac{∥A∥_{off}}{δ})^{2}} 0.5484[(1 + β) ∑_{i=1}^{p} Γ_{i} +

+ (1 + \frac{1}{β}) ∥A∥_{off}^{2} ∑_{i=2}^{p} ∑_{s_{i−1}+1≤t≤s_{i}^{1≤r≤s_{i−1}}} sin^{2} φ_{rt}]

≤ \frac{0.0531\frac{∥A∥_{off}^{4}}{δ^{2}}}{1 + 2 (0.22\frac{∥A∥_{off}}{δ})^{2}} [(1 + β) + (1 + \frac{1}{β}) \frac{2}{25} \frac{∥A∥_{off}^{2}}{δ^{2}} ].

Using an optimal β (see the relation (2.15) ) implies

∑_{i=1}^{p} ∥A_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ 0.0531\frac{∥A∥_{off}^{4}}{δ^{2}} \frac{(1 + \frac{\sqrt{2}}{5} \frac{∥A∥_{off}}{δ} )^{2}}{1 + 2 (0.22\frac{∥A∥_{off}}{δ})^{2}}
≤ 0.0531\frac{∥A∥_{off}^{4}}{δ^{2}} sup_{0≤x<1} \frac{(1 + \frac{\sqrt{2}}{5}x)^{2}}{1 + 2 (0.22x)^{2}}
≤ 0.0531\frac{(1 + \frac{\sqrt{2}}{5})^{2}}{1 + 2 (0.22)^{2}} \frac{∥A∥_{off}^{4}}{δ^{2}} ≤ 0.0797\frac{∥A∥_{off}^{4}}{δ^{2}} ,

which proves (i).

(ii) In this case we have for any γ > 0

∑_{i=1}^{p} ∥A_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ (1 + γ) ∑_{i=1}^{p} ∥A_{c,ii}^{(q_{i}′)}∥_{off}^{2} + (1 + \frac{1}{γ}) ∑_{i=1}^{p} ∥E_{ii}^{(q_{i}′)}∥^{2}.  (2.26)

We shall first estimate the second term on the right-hand side of the inequality (2.26). Let e_{t}^{(k)} denotes the t’th row of E^{(k)}. Then we have

∥E_{ii}^{(q_{i}′)}∥^{2} ≤ ∑_{j=1}^{p} ∥E_{ij}^{(q_{i}′)}∥^{2} = ∑_{t=s_{i−1}+1}^{s_{i}} ∥e_{t}^{(q_{i}′)}∥^{2}, s_{i−1} + 1 ≤ t ≤ s_{i}.  (2.27)

By an analysis similar to the one above we have for s_{i−1} + 1 ≤ t ≤ s_{i}

∥e_{t}^{(q_{i}′)}∥^{2} ≤ (1 + β)∥e_{t}^{(1)}∥^{2} + (1 + \frac{1}{β})∥E^{(1)}∥^{2} ∑_{r=1}^{s_{i−1}} sin^{2} φ_{rt}, β > 0.  (2.28)

The relations (2.27), (2.28) and (2.13) yield

∑_{i=1}^{p} ∥E_{ii}^{(q_{i}′)}∥^{2} ≤ ∑_{i=1}^{p} ∑_{t=s_{i−1}+1}^{s_{i}} ∥e_{t}^{(q_{i}′)}∥^{2} ≤  (2.29)

≤ (1 + β) ∑_{i=1}^{p} ∑_{t=s_{i−1}+1}^{s_{i}} ∥e_{t}^{(1)}∥^{2} + (1 + \frac{1}{β})∥E∥^{2} ∑_{k∈M_{1}} sin^{2} φ_{k} ≤

≤ ∥E∥^{2} [(1 + β) + (1 + \frac{1}{β} ) (\frac{1}{3.42} \frac{∥A∥_{off}}{δ_{c}} )^{2}] , β > 0.

Using the relations (2.15) and (2.10) we obtain

∑_{i=1}^{p} ∥E_{ii}^{(q_{i}′)}∥^{2} ≤ ∥E∥^{2} (1 + \frac{1}{3.42} \frac{1}{2})^{2} < 1.314\frac{∥A∥_{off}^{4}}{δ_{c}^{2}} .  (2.30)

Next we consider the first term on the right-hand side of (2.26). By the assertion (2.12) of Lemma 2.3 and by the relation (2.11) we obtain for each 1 ≤ i ≤ p

∥A_{c,ii}^{(q_{i}′)}∥_{off}^{2} ≤ 2 (0.2025)^{2} \frac{∥A_{c}^{(q_{i}′)}∥^{2}}{δ_{c,i}^{2}} ∑_{j≠i^{j=1}}^{p} ∥A_{c,ij}^{(q_{i}′)}∥^{2}

≤ (\sqrt{2} · 0.2025 · \frac{3}{2} \frac{∥A∥}{δ_{c,i}})^{2} ∑_{j≠i^{j=1}}^{p} (∥A_{ij}^{(q_{i}′)}∥ + ∥E_{ij}^{(q_{i}′)}∥)^{2}

≤ (0.43 \frac{∥A∥}{δ_{c,i}})^{2} [(1 + α) ∑_{t=s_{i−1}+1}^{s_{i−1}} ∥x_{t}^{(q_{i}′)}∥^{2} +

+ (1 + \frac{1}{α}) ∑_{t=s_{i−1}+1}^{s_{i−1}} ∥e_{t}^{(q_{i}′)}∥^{2}] , α > 0.  (2.31)

Assuming the same α for all i and using (2.31), (2.29) and (2.30) we obtain

∑_{i=1}^{p} ∥A_{c,ii}^{(q_{i}′)}∥_{off}^{2} ≤ (0.43 \frac{∥A∥}{δ_{c,i}})^{2} [(1 + α) ∑_{i=1}^{p} ∑_{t=s_{i−1}+1}^{s_{i−1}} ∥x_{t}^{(q_{i}′)}∥^{2} +

+ (1 + \frac{1}{α})1.314 · \frac{∥A∥_{off}^{4}}{δ_{c}^{2}} ] , α > 0.  (2.32)

To estimate the first term on the right-hand side we use the relations (2.21), (2.22) and an analysis similar to that in the proof of (i), but much simpler. We obtain for each 1 ≤ i ≤ p

∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q_{i}′)}∥^{2} ≤ (1 + β) ∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(1)}∥^{2} +

+ (1 + \frac{1}{β}) ∥A∥_{off}^{2} ∑_{s_{i−1}+1≤t≤s_{i}^{1≤r≤s_{i−1}}} sin^{2} φ_{rt}, β > 0.

Here the empty sum is considered zero. Assuming the same β for each i and using (2.13) we obtain

∑_{i=1}^{p} ∑_{t=s_{i−1}+1}^{s_{i−1}} ∥x_{t}^{(q_{i}′)}∥^{2} ≤ (1 + β) ∑_{i=1}^{p} ∑_{t=s_{i−1}+1}^{s_{i−1}} ∥x_{t}^{(1)}∥^{2} +

+ (1 + \frac{1}{β}) ∥A∥_{off}^{2} ∑_{k∈M_{1}} sin^{2} φ_{k}

≤ ∥A∥_{off}^{2} [(1 + β) + (1 + \frac{1}{β}) (\frac{1}{3.42} \frac{∥A∥_{off}}{δ_{c}} )^{2}] .

Choosing an optimal β and using the assumption C1 we obtain

∑_{i=1}^{p} ∑_{t=s_{i−1}+1}^{s_{i−1}} ∥x_{t}^{(q_{i}′)}∥^{2} ≤ ∥A∥_{off}^{2} (1 + \frac{1}{3.42} \frac{∥A∥_{off}}{δ_{c}} )^{2} ≤ (1 + \frac{1}{3.42} \frac{1}{2})^{2} ∥A∥_{off}^{2}
≤ 1.314 ∥A∥_{off}^{2}.

Inserting the obtained bound 1.314 ∥A∥_{off}^{2} into (2.32) and choosing an optimal α we have

∑_{i=1}^{p} ∥A_{c,ii}^{(q_{i}′)}∥_{off}^{2} ≤ (0.43 \frac{∥A∥^{2}}{δ_{c,i}} )^{2} (\sqrt{1.314} + \sqrt{1.314}\frac{∥A∥}{δ_{c}})^{2}

≤ [0.43 \sqrt{1.314}(1 + \frac{1}{2})\frac{∥A∥_{off}^{2}}{δ_{c,i}} ]^{2} ≤ (0.74 \frac{∥A∥_{off}^{2}}{δ_{c,i}} )^{2} .

Using this inequality together with the inequalities (2.26) and (2.30) we obtain

∑_{i=1}^{p} ∥A_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ [(1 + γ) (0.74)^{2} + (1 + \frac{1}{γ}) 1.314] \frac{∥A∥_{off}^{4}}{δ_{c}^{2}} .

Choosing an optimal γ yields

∑_{i=1}^{p} ∥A_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ (0.74 + \sqrt{1.314})^{2} \frac{∥A∥_{off}^{4}}{δ_{c}^{2}} ≤ 3.6\frac{∥A∥_{off}^{4}}{δ_{c}^{2}} .

This proves (ii) and completes the proof of Lemma 2.7.

2.3 Principal Results

Here we prove the central theorem concerning the quadratic convergence of symmetric serial Jacobi methods.

Theorem 2.8 Let the sequence A^{(1)} = A, A^{(2)}, … be generated by a cyclic strategy which is equivalent to the row-cyclic one.

(i) If A satisfies the assumptions A1 and A2, then

∥A^{(N+1)}∥_{off} ≤ \frac{3}{5} \frac{∥A∥_{off}^{2}}{δ} .

(ii) If A satisfies the assumptions C1 and C2, then

∥A^{(N+1)}∥_{off} ≤ \frac{11}{5} \frac{∥A∥_{off}^{2}}{δ_{c}} .

Proof: By Lemma 1.1 it suffices to prove Theorem 2.8 for the row-cyclic strategy.

(i) By Lemma 2.6 we have

∥A^{(N+1)}∥_{off}^{2} = ∥A_{pp}^{(N+1)}∥_{off}^{2} + ∑_{i=1}^{p−1} [∥A_{ii}^{(N+1)}∥_{off}^{2} + 2 ∑_{j=i+1}^{p} ∥A_{ij}^{(N+1)}∥^{2}]

≤ ∥A_{pp}^{(N+1)}∥_{off}^{2} + ∑_{i=1}^{p−1} Γ_{i}^{(N+1)}

≤ ∥A_{pp}^{(N+1)}∥_{off}^{2} + ∑_{i=1}^{p−1} [(1 + γ)∥A_{ii}^{(q_{i}′)}∥_{off}^{2} +

(1 + \frac{1}{γ})∥A_{ii}^{(q_{i}′)}∥_{off}^{2} ∑_{(t,r)∈G_{i}} sin^{2} φ_{tr}] , γ > 0.

Here we have assumed the same γ for all i. Since the pivot strategy is row-cyclic we have

∥A_{pp}^{(N+1)}∥_{off} ≤ ∥A_{pp}^{(q_{p}′)}∥_{off}.

Hence

∥A^{(N+1)}∥_{off}^{2} ≤ (1 + γ) ∑_{i=1}^{p} ∥A_{ii}^{(q_{i}′)}∥_{off}^{2} + (1 + \frac{1}{γ})∥A∥_{off}^{2} ∑_{i=1}^{p} ∑_{(t,r)∈G_{i}} sin^{2} φ_{tr}

≤ (1 + γ) ∑_{i=1}^{p} ∥A_{ii}^{(q_{i}′)}∥_{off}^{2} + (1 + \frac{1}{γ})∥A∥_{off}^{2} ∑_{k∈M_{0}} sin^{2} φ_{k}.  (2.33)

Using Lemma 2.7 (i) and the relations (2.7) and(2.15) we obtain

∥A^{(N+1)}∥_{off}^{2} ≤ (1 + γ) 0.08\frac{∥A∥_{off}^{4}}{δ^{2}} + (1 + \frac{1}{γ})∥A∥_{off}^{2} ∑_{k∈M_{0}} sin^{2} φ_{k}

≤ [(1 + γ) 0.08 + (1 + \frac{1}{γ}) 0.08] \frac{∥A∥_{off}^{4}}{δ^{2}} .

An optimal choice for γ implies

∥A^{(N+1)}∥_{off}^{2} ≤ [(\sqrt{0.08} + \sqrt{0.08}) \frac{∥A∥_{off}^{2}}{δ} ]^{2}

≤ [0.566 \frac{∥A∥_{off}^{2}}{δ} ]^{2} .

This proves (i).

(ii) In this case we use the relation (2.33), Lemma 2.7(ii) and the second assertion of Lemma 2.3. We obtain

∥A^{(N+1)}∥_{off}^{2} ≤ [(1 + γ) 3.6 + (1 + \frac{1}{γ}) (\frac{1}{3.42})^{2}] \frac{∥A∥_{off}^{4}}{δ_{c}^{2}} , γ > 0.

An optimal choice for γ implies

∥A^{(N+1)}∥_{off}^{2} ≤ [(\sqrt{3.6} + \frac{1}{3.42}) \frac{∥A∥_{off}^{2}}{δ_{c}} ]^{2} ≤ [2.19\frac{∥A∥_{off}^{2}}{δ_{c}} ]^{2} .

Since 2.19 < 11/5 the proof of the theorem is completed.

From Theorem 2.7 we see that the quadratic reduction of ∥A∥_{off} will occur whenever the eigenvalues of A are well saparated or grouped in clusters of sufficiently small widths. In the second case however a slowdown in the off-norm reduction can happen. Namely, as ∥A∥_{off} is getting smaller quadratically , the second condition in the assumption C2 can fail to hold (i.e. ∥E∥ fails to be quadratically small with respect to ∥A∥_{off}). If the condition (2.3) of the assumption A1 is still not satisfied we are likely to have a slowdown in the off-norm reduction. However, ultimately ∥A∥_{off} will satisfy the assumptions A1 and A2 and the quadratic convergence will prevail. The following example shows this well known phenomenon (cf. Example 3 in [3])

Example 2.9 The matrix A of order n = 8 has been generated by the formula

A = U diag(−1, 1, 2 − 2 · 10^{−7}, 2 − 10^{−7}, 2, 2 + 10^{−7}, 2 + 2 · 10^{−7}, 3) U^{T} ,

using a floating point arithmetic with 18 significant digits. Here U is generated as a product of 2 n^{2} rotatations (4 cycles) whose angles were randomly chosen within the interval (−π/4, π/4).

Matrix A

row 1: 1.71022782641771121 -0.47771747374416791 0.12744824734141938 -0.17899217108154641 -0.43447403622519996 -0.03064941404704253 -0.01145976759339185 0.42753295526447045 row: 2 0.63024177107252076 0.89087913932698411 -0.64518496685786945 -1.15091017499640396 0.31781197164474316 -0.13981696911039142 0.29343973265467501 row: 3 2.01436559851330745 0.19008549610018806 0.08400885457771696 0.24842938585684695 0.05487417066485427 0.05573591909887845 row: 4 1.78140861828352346 -0.31810576653283833 -0.02638383594855642 -0.04830231245471433 0.09830845160106086 row: 5 1.46104813723145849 -0.24368404145080640 -0.04243404133308754 0.50240108142934927 row: 6 2.27510952876663488 0.00494899257815551 0.12321381805390081 row: 7 1.98410671442090193 -0.04346538912080283 row: 8 1.14349180529394182

Here each line starts with the diagonal element. We have applied on A the row-cyclic method with reordering of the diagonal elements in the nonincreasing sequence after each cycle (so that the assumptions C2 and later A2 hold through). The following off-norm reduction of A has been obtained

\begin{matrix}cycle & ∥A∥_{off} \\ 0 & 2.80923346694E + 0000 \\ 1 & 4.73526910592E − 0001 \\ 2 & 6.85142143831E − 0003 \\ 3 & 6.34117549405E − 0008 \\ 4 & 4.82953155214E − 0009 \\ 5 & 5.19685212420E − 0013 \\ 6 & 1.67767882511E − 0021 \\ 7 & 3.00773510031E − 0051 \end{matrix}

Here cycle = 0 corresponds to the starting matrix. Note that in this example δ_{c} = 1, δ = 10^{−7} and ∥E∥ = \sqrt{10} 10^{−7} up to the arithmetic accuracy. During the second and the third cycle we have quadratic off-norm reduction, then during the next two cycles a slowdown and after that again the quadratic reduction. Note that Theorem 2.8 well estimates the off-norm reduction in this example.

Let us make several remarks. First, the constants 0.566 and 2.19 can be further reduced when A has only simple and double eigenvalues. To get appropriate bounds simply use assertion (i) of Lemma 2.6. In the case of clusters the smaller bounds could be obtained by using a more stringent assumption than C1.

The question arises whether some off-diagonal elements or the whole blocks can tend to zero faster than the others. An indication for the answer lies in the following corollary.

Corollary 2.10 Let the assumptions A1 and A2 hold. Then

Γ_{i}^{(N+1)} ≤ (0.58\frac{∥A∥_{off}^{2}}{δ_{i}} )^{2} , 1 ≤ i ≤ p.

Proof: Using Lemma 2.6, the relations (2.15), (2.20), the relation (2.25) with an optimal β, the assumption A1, and the fact that | sin φ_{lm} |≤ 2 | a_{lm}^{(k)} | /(5δ_{i}) for (l, m) ∈ G_{i} we obtain for 1 ≤ i ≤ p − 1

Γ_{i}^{(N+1)} ≤ [∥A_{ii}^{(q_{i}′)}∥_{off} + ∥A^{(q_{i}′)}∥_{off} ( ∑_{(t,r)∈G_{i}} sin^{2} φ_{tr})^{\frac{1}{2}} ]^{2}

≤ [0.22\sqrt{2}\frac{∥A∥_{off}}{δ_{i}} \sqrt{0.5484} (\sqrt{Γ_{i}} + ∥A∥_{off} \sqrt{0.08}\frac{∥A∥_{off}}{δ_{i}} )

+\sqrt{0.08}\frac{∥A∥_{off}^{2}}{δ_{i}} ]^{2}
≤ [0.22\sqrt{1.0968} (1 + \sqrt{0.08}) + \sqrt{0.08}]^{2} \frac{∥A∥_{off}^{4}}{δ_{i}^{2}}
≤ [0.58 \frac{∥A∥_{off}^{2}}{δ_{i}} ]^{2} .

For i = p we have Γ_{p}^{(N+1)} ≤ ∥A_{pp}^{(q_{p}′)}∥_{off}^{2}, hence Corollary 2.10 follows by Lemma 2.2.

Thus, if some eigenvalue λ_{s_{i}} is well separated from the other eigenvalues (δ_{i} is relatively large) the reduction of Γ_{i} is likely to be better than the reduction of other Γ_{j}, j ≠ i.

Let us now show that our result implies the estimate proposed by Van Kempen [12]. In [12] (see also [23]) Van Kempen has used instead of A1 the assumption

S(A) < \frac{δ̃}{4}  (2.34)

where S(A) = ∥A∥_{off}/\sqrt{2}, and 2δ̃ = 3δ. He has proposed the estimate

S(A^{(N+1)}) ≤ \sqrt{\frac{17}{9}} \frac{S^{2}(A)}{δ̃},  (2.35)

but his proof is not correct since the contributions to the row-vectors a_{t}^{(k)} have not been taken into account. Also, the bound for ∑_{i=1}^{p} ∥A^{(q_{i}′)}∥_{off} is missing. This incorrectness has been noticed by Ruhe [21] and Charlier and Van Dooren [3]. Translated in our notation his assumption (2.34) reads

∥A∥_{off} < \frac{3\sqrt{2}}{8}δ.

Thus (2.34) is more stringent than A1. Hence Theorem 2.8(i) can be applied. We obtain

S(A^{(N+1)}) = \frac{\sqrt{2}}{2}∥A^{(N+1)}∥_{off} ≤ \frac{\sqrt{2}}{2} \frac{3}{5} \frac{∥A∥_{off}^{2}}{δ}
= \frac{3 \sqrt{2}}{10} \frac{2 S^{2}(A)}{\frac{2}{3} δ̃} = \frac{9\sqrt{2}}{10} \frac{S^{2}(A)}{δ̃}.

Since \frac{9\sqrt{2}}{10} < \sqrt{\frac{17}{9}} Van Kempen’s inequality (2.35) holds. Using the above technique together

with the Van Kempen’s assumption (2.34) the bound \sqrt{17/9} can be further decreased to 1 thus showing that the well-known Wilkinson’s result for serial symmetric Jacobi methods holds in the general case.

Corollary 2.11 If A satisfies the inequality (2.34) and the assumption A2 then

S(A^{(N+1)}) ≤ \frac{S^{2}(A)}{δ̃}.

Proof: Since the condition (2.34) implies (2.3) all the relations in the proof of Lemma 2.1 hold. The appropriate inequalities are given below. For 1 ≤ i ≤ p, we have

∥G_{i}∥ ≤ S(A) < \frac{1}{4}δ̃,
| κ_{j}^{(i)} | > 2 δ̃ − \frac{1}{4}δ̃ = \frac{7}{4}δ̃, j ∈ S_{i},
∥K_{i}^{−1}∥_{2} ≤ \frac{4}{7} \frac{1}{δ̃}.

Since the sequence S^{2}(A^{(k)}), k ≥ 1 is nonincreasing, we have for all 1 ≤ i ≤ p and k ≥ 1

S(A_{ii}^{(k)}) ≤ \frac{\sqrt{2}}{2}∥A_{ii}^{(k)} − λ_{s_{i}}I_{n_{i}}∥ ≤ \frac{2\sqrt{2}}{7} \frac{1}{δ̃} ∑_{j≠i^{j=1}}^{p} ∥A_{ij}^{(k)}∥^{2}

≤ \frac{2\sqrt{2}}{7} \frac{S^{2}(A^{(k)})}{δ̃} ≤ \frac{2\sqrt{2}}{7} \frac{S^{2}(A)}{δ̃} < \frac{\sqrt{2}}{56}δ̃.  (2.36)

If k ∈ M_{1} then | a_{mm}^{(k)} − a_{ll}^{(k)} |> 2δ̃ − 2 · (1/28)δ̃ = (27/14)δ̃. Hence

| sin φ_{k} |≤ (14/27) | a_{lm}^{(k)} | /δ̃

and we have

∑_{k∈M1} sin^{2} φ_{k} ≤ (\frac{14}{27})^{2} ∑_{k∈M1} \frac{(a_{lm}^{(k)})^{2}}{δ̃^{2}} ≤ (\frac{14}{27} \frac{S(A)}{δ̃})^{2} .  (2.37)

Next we follow the lines of the proof of Lemma 2.7(i). Replacing ∥ · ∥_{off} with \sqrt{2}S(·) and using (2.34), (2.25) and (2.36) we obtain

∑_{i=1}^{p} S^{2}(A_{ii}^{(q_{i}′)}) ≤ \frac{\frac{8}{49} \frac{S^{2}(A)}{δ̃^{2}}}{1 + 2\frac{8}{49} \frac{S^{2}(A)}{δ̃^{2}}} ∑_{i=1}^{p} ∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q_{i}′)}∥^{2} ≤

\frac{\frac{8}{49} \frac{S^{2}(A)}{δ̃^{2}}}{1 + 2\frac{8}{49} \frac{S^{2}(A)}{δ̃^{2}}} 0.5484 [(1 + β)2S^{2}(A) + (1 + \frac{1}{β})2S^{2}(A) ∑_{k∈M1} sin^{2} φ_{k}] .

Choosing an optimal β and using (2.37) we obtain

∑_{i=1}^{p} S^{2}(A_{ii}^{(q_{i}′)}) ≤ \frac{8}{49}1.0968\frac{S^{4}(A)}{δ̃^{2}} \frac{(1 + \frac{14}{27} \frac{S(A)}{δ̃})^{2}}{1 + (\frac{4}{7} \frac{S(A)}{δ̃})^{2}}

≤ \frac{8.7744}{49} sup_{0≤x< \frac{1}{4}} \frac{(1 + \frac{14}{27} x)^{2}}{1 + (\frac{4}{7} x)^{2}} \frac{S^{4}(A)}{δ̃^{2}}

≤ \frac{8.7744}{49} \frac{(1 + \frac{14}{27} · \frac{1}{4})^{2}}{1 + (\frac{4}{7} · \frac{1}{4})^{2}} \frac{S^{4}(A)}{δ̃^{2}}

≤ 0.224\frac{S^{4}(A)}{δ̃^{2}}.  (2.38)

Finally, using Lemma 2.6(ii) and the relations (2.37) and (2.38) we obtain

S^{2}(A^{(N+1)}) = S^{2}(A_{pp}^{(N+1)}) + \frac{1}{2} ∑_{i=1}^{p−1} Γ_{i}^{(N+1)}

≤ S^{2}(A_{pp}^{(q_{p}′)}) + (1 + γ) ∑_{i=1}^{p−1} S^{2}(A_{ii}^{(q_{i}′)}) +

(1 + \frac{1}{γ}) ∑_{i=1}^{p−1} S^{2}(A^{(q_{i}′)}) ∑_{(t,r)∈G_{i}} sin^{2} φ_{tr}

≤ (1 + γ) ∑_{i=1}^{p} S^{2}(A_{ii}^{(q_{i}′)}) + (1 + \frac{1}{γ})S^{2}(A) ∑_{k∈M_{0}} sin^{2} φ_{k}

≤ [(1 + γ)0.224 + (1 + \frac{1}{γ})(\frac{14}{27})^{2}] \frac{S^{4}(A)}{δ̃^{2}}.

An optimal γ yields

S(A^{(N+1)}) ≤ (\sqrt{0.224} + \frac{14}{27}) \frac{S^{2}(A)}{δ̃} ≤ 0.992\frac{S^{2}(A)}{δ̃},

which proves the corollary.

3 SVD Jacobi Methods

Jacobi methods for computing the singular value decomposition (SVD) of a square matrix A are proceses of the form (1.1) with unitary plane matrices U_{k} and V_{k}, k ≥ 1. They are also called Kogbetliantz methods (see [3],[2], etc.) for his first contributions [13] and [14]. Recent research on these methods is mostly connected with parallel processing [1], [2],[15], etc. On standard computers these methods are not very efficient if applied to full matrices (cf. [18],[8]). However, if A is triangular and the pivot strategy is row- or column-cyclic, then the SVD Jacobi methods are as efficient as the corresponding symmetric Jacobi methods (see [9],[3],[10]). Namely, if A is triangular, then each A^{(k)} is block-triangular whose diagonal blocks are again block-triangular with triangular diagonal blocks. Such matrices are permutationally similar to triangular matrices (PST) and the whole process can be operated on the upper-/lower-triangle of the current matrix. Let T^{(k)} be the upper-triangular matrices satisfying

T^{(k)} + T^{(k)}^{T} = A^{(k)} + A^{(k)}^{T} , k ≥ 1.  (3.1)

Considering (for simplicity) only the case of real matrices we can assume

Û_{k} = [ \begin{matrix}cos φ_{k} & sin φ_{k} \\ − sin φ_{k} & cos φ_{k} \end{matrix} ] , V̂_{k} = [ \begin{matrix}cos ψ_{k} & sin ψ_{k} \\ − sin ψ_{k} & cos ψ_{k} \end{matrix} ] .

The transformation formulae for T^{(k)} = (t_{ij}^{(k)}) take the following form

t_{lm}^{(k+1)} = 0
\begin{matrix}t_{il}^{(k+1)} & = & t_{il}^{(k)} cos φ_{k} − t_{im}^{(k)} sin φ_{k} \\ t_{im}^{(k+1)} & = & t_{il}^{(k)} sin φ_{k} + t_{im}^{(k)} cos φ_{k} \end{matrix} \} 1 ≤ i ≤ l − 1,
\begin{matrix}t_{li}^{(k+1)} & = & t_{li}^{(k)} cos ψ_{k} − t_{im}^{(k)} sin ψ_{k} \\ t_{im}^{(k+1)} & = & t_{li}^{(k)} sin ψ_{k} + t_{im}^{(k)} cos ψ_{k} \end{matrix} \} l + 1 ≤ i ≤ m − 1,
\begin{matrix}t_{li}^{(k+1)} & = & t_{li}^{(k)} cos φ_{k} − t_{mi}^{(k)} sin φ_{k} \\ t_{mi}^{(k+1)} & = & t_{li}^{(k)} sin φ_{k} + t_{mi}^{(k)} cos φ_{k} \end{matrix} \} m + 1 ≤ i ≤ n.

(3.2)

The formulae (3.2) hold for an odd/even cycle of the upper-/lower-triangular matrix A, provided that the pivot strategy is row-or column-cyclic. For even/odd cycles the roles of φ_{k} and ψ_{k} in the relation (3.2) are interchanged. The angles φ_{k} and ψ_{k} are determined from the requirement a_{lm}^{(k+1)} = a_{ml}^{(k+1)} = 0 i.e. from t_{lm}^{(k+1)} = 0. This requirement implies

∥T^{(k+1)}∥_{off}^{2} = ∥T^{(k)}∥_{off}^{2}− | t_{lm}^{(k)} |^{2}, k ≥ 1.  (3.3)

The explicit formulae for φ_{k} and ψ_{k} can be found in [9], [2], [10], [1] etc. Here we assume the formulae from [10] so that we can use the results obtained there. For simplicity we call the serial SVD Jacobi methods for triangular matrices SVDT methods (cf. [10]). Their global convergence has been proved in [9] and [5] whereas their quadratic convergence has been proved in [3] and [10]. Here we use the technique from Section 2 to derive sharper quadratic convergence bounds. Our analysis shall be briefly presented since major part of the work has already been done in [10] and in Section 2 of this paper.

Almost Diagonal PST Matrices

We shall use the following asymptotic assumptions

S1 A is a triangular matrix satisfying

∥A∥_{off} < ν,
where 3ν = min_{σ_{i}≠σ_{j}} | σ_{i} − σ_{j} |, and σ_{1}, …, σ_{n} are the singular values of A.

S2 The diagonal elements of A affiliated with the same multiple singular value occupy successive positions on the diagonal.

S3 If the following two conditions:

1. The multiplicity of the minimal singular value σ_{min} is larger than two,

2.

0 < 2σ_{min} < 3ν ,

simultaneously hold, then the diagonal elements affiliated with σ_{min} take the first/last positions on the diagonal.

Note that the assumptions S1 and S2 quite correspond to the assumptions A1 and A2 from Section 2. The third assumption S3 is somewhat redundant, but it ensures the validity of the estimates in the next lemma. Note that S3 is not very restrictive since in practical procedures the assumption S2 is usually achieved by ordering | a_{ll}^{(k+1)} | and | a_{mm}^{(k+1)} | in a prescribed monotonic order. Because of the assumptions S1 and S2, A can be partitioned according to the multiplicities n_{1}, n_{2}, …, n_{p} of the singular values. The appropriate ordering of the singular values of A is given by

σ_{1} = ⋯ = σ_{s_{1}}, σ_{s_{1}+1} = ⋯ = σ_{s_{2}}, …, σ_{s_{p−1}+1} = ⋯ = σ_{s_{p}},

where s_{p} = n and n_{i} = s_{i} − s_{i−1} (s_{0} = 0) is the multiplicity of σ_{s_{i}}, 1 ≤ i ≤ p. Note that p = 1 would imply that A is a multiple of a unitary matrix. Since A is a PST matrix it would imply that A is diagonal. So p > 1 is a natural hypothesis.

In a similar way as above we can define

3ν_{i} = min_{j≠i^{1≤j≤p}} | σ_{s_{i}} − σ_{s_{j}} |, 1 ≤ i ≤ p

and

ν = min_{1≤i≤p} ν_{i}.

Lemma 3.1 If the assumptions S1, S2 and S3 hold, then

∥A_{ii}∥_{off} ≤ \sqrt{2}∥(| A_{ii} | + | A_{ii}^{T} |) − σ_{s_{i}}I_{n_{i}}∥
≤ \frac{\sqrt{2}}{4} \frac{1}{ν_{i}} [∥A_{ii}∥_{off}^{2} + ∑_{j≠i^{j=1}}^{p}(∥A_{ij}∥^{2} + ∥A_{ji}∥^{2}]

≤ \frac{\sqrt{2}}{4} \frac{∥A∥_{off}^{2}}{ν_{i}} , 1 ≤ i ≤ p.

Proof: See Lemma 2.1, Lemma 2.2 and Lemma 2.3 from [10].

Let the sequence A^{(1)} = A, A^{(2)}, … be generated by applying a SVDT method to the triangular matrix A satisfying the assumptions S1, S2 and S3. From the relations (3.3) and (3.1) we see that the assumption S1 holds for each A^{(k)}, k ≥ 1. Since the affiliation cannot be changed (see Lemma 3.2 from [10]), we conclude that also each A^{(k)} satisfies the assumptions S2 and S3. Consequently Lemma 3.1 holds for all A^{(k)}, k ≥ 1. Therefore | | a_{jj}^{(k)} | −σ_{j} |< \frac{ν}{4}, 1 ≤ j ≤ n, k ≥ 1. This implies | a_{mm}^{(k)} − a_{ll}^{(k)} |≥|| a_{mm}^{(k)} | − | a_{ll}^{(k)} ||> 3ν − 2(ν/4) whenever a_{ll}^{(k)} and a_{mm}^{(k)} are not affiliated with the same singular value. Since p > 1, the set of positive integers

MS = \{k ≥ 1 : | a_{mm}^{(k)} − a_{mm}^{(k)} | > \frac{5}{2}ν\}

is well defined. In fact we shall only use the set MS_{1} = { k ∈ MS : 1 ≤ k ≤ N}.

Lemma 3.2 If the assumptions S1, S2 and S3 hold, then

∑_{k∈MS_{1}} max\{sin^{2} φ_{k} , sin^{2} ψ_{k}\} ≤ [\frac{4}{7} \frac{∥T ∥_{off}}{ν} ]^{2} .

Proof: See Theorem 4.1 in [10].

We shall consider only the first cycle of the process. Hence, the angles φ_{k}, ψ_{k} shall be also denoted by φ_{lm}, ψ_{lm}, respectively. In order to simplify notation we shall use the quantity η_{lm} = ψ_{lm} (φ_{lm}) provided that A is upper- (lower- ) triangular. We presume that q_{t}, 1 ≤ t ≤ n and q′_{i}, 1 ≤ i ≤ p are defined as in Section 2.2. By (T_{ij}^{(k)}) we denote the partition (2.4) of T^{(k)}. For i = 1, …, p we define (cf. G_{i} and Γ_{i}^{(k)} from Section 2.2)

G_{i} = {(t, r) : s_{i−1} + 1 ≤ t ≤ s_{i}, s_{i} + 1 ≤ r ≤ n} \ {(s_{i}, s_{i} + 1)},
⊤_{i}^{(k)} = ∥T_{ii}^{(k)}∥_{off}^{2} + ∑_{j=i+1}^{p} ∥T_{ij}^{(k)}∥^{2}, k ≥ 1.

Lemma 3.3 Let i ∈ {1, …, p}.

(i) If n_{i} ≤ 2, then ⊤_{i}^{(N+1)} ≤ ∥T^{(q_{i}′)}∥_{off}^{2} ∑_{(t,r)∈G_{i}} sin^{2} η_{tr}

(ii) If n_{i} > 2, then for every γ > 0 holds

⊤_{i}^{(N+1)} ≤ (1 + γ)∥T_{ii}^{(q_{i}′)}∥_{off}^{2} + (1 + \frac{1}{γ})∥T^{(q_{i}′)}∥_{off}^{2} ∑_{(t,r)∈G_{i}} sin^{2} η_{tr}.

Proof: The proof follows easily by modifying the proof of Lemma 2.5 and Lemma 2.6. A similar, but less accurate result is also proved in [10] as part of the proof of Theorem 4.3.

Lemma 3.4 If the assumptions S1, S2 and S3 hold, then

∑_{i=1}^{p} ∥T_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ 0.493 \frac{∥T ∥_{off}^{4}}{ν^{2}} .

Proof: The proof quite corresponds to the proof of Lemma 2.7(i). In particular we use the row-vectors (see Figure 4)

x_{τ}^{(k)} = [t_{1τ}^{(k)}, t_{2τ}^{(k)}, …, t_{τ,τ−1}^{(k)}, 0 , t_{τ,τ+1}^{(k)}, …, t_{τn}^{(k)}] , 1 ≤ τ ≤ n, k ≥ 1

to obtain

∥T_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ \frac{1}{8} \frac{∥T^{(q_{i}′)}∥_{off}^{2}}{ν_{i}^{2}} [∥T_{ii}^{(q_{i}′)}∥_{off}^{2} + ∑_{j=1}^{i−1} ∥T_{ji}^{(q_{i}′)}∥^{2} + ∑_{j=i+1}^{p} ∥T_{ij}^{(q_{i}′)}∥^{2}] ,

≤ \frac{1}{8} \frac{∥T ∥_{off}^{2}}{ν_{i}^{2}} ∑_{τ=s_{i−1}+1}^{s_{i}} ∥x_{τ}^{(q_{i}′)}∥^{2}, 1 ≤ i ≤ p.

Here we have used Lemma 3.1 with A^{(q_{i}′)}. For k = 1, …, q_{i}′, ∥x_{τ}^{(k)}∥^{2} changes only when the elements of column τ are rotated. Replacing the row-cyclic sequence O_{R,s_{i−1}} by the columncyclic one O_{C,s_{i−1}} and denoting by Ā^{(k)}, T̄^{(k)}, x̄_{τ}^{(k)}, … the appropriate matrices and vectors, we obtain (see Figure 4)

| x̄_{τ}^{(w_{τ+1})} |≤| x̄_{τ}^{(w_{τ})} | + ∑_{r=1}^{s_{i−1}} | x̄_{r}^{(w_{τ} +r−1)} Z_{r,i} | | sin ξ_{rτ} |, s_{i−1} + 1 ≤ τ ≤ s_{i}.

where for s_{i−1} + 1 ≤ τ ≤ s_{i},

Z_{r,i} = I_{r−1} ⊕ O_{s_{i−1}−r+1} ⊕ I_{n−s_{i−1}}, 1 ≤ r ≤ s_{i−1},
w_{τ} = (s_{i−1} − 1)s_{i−1}/2 + (τ − s_{i−1} − 1)s_{i−1} + 1,

and

| ξ_{rτ} |= max{| φ_{rτ} |, | ψ_{rτ} |}, r < τ.

Here we have used the fact that pivot elements are being annihilated and that the transformation formulae for the SVDT processes under the orderings O_{R,s_{i−1}} and O_{C,s_{i−1}} are both given by the

[figure] [figure] [figure] [figure]

s_{i−1} + 1 x̄_{s_{i−1}+1}

t

r

x̄_{t} x̄_{r}

s_{i}

x̄_{s_{i}}

[figure] [figure]

pivot ; position ; in T̄^{(w_{t+1})} pivot ; position ; in T̄^{(w_{t})}

Figure 4: n = 42, n_{i} = 10, i ∈ {2, …, p − 1}.

relation (3.2). Also, by Lemma 1.2(iv) and Lemma 1.1 we know that φ̄_{lm} = φ_{lm} and ψ̄_{lm} = ψ_{lm} for all l < m.

Using the invariance properties of ∥x̄_{τ}^{(k)}∥ and the equalities

∥x̄_{r}^{(w_{τ} +r−1)} Z_{r,i}∥ = ∥x̄_{r}^{(w_{τ})} Z_{r,i}∥, 1 ≤ r ≤ s_{i−1}

we obtain

∑_{τ=s_{i−1}+1}^{s_{i}} ∥x_{τ}^{(q_{i}′)}∥^{2} ≤

≤ (1 + β) ∑_{τ=s_{i−1}+1}^{s_{i}} ∥x̄_{τ}^{(w_{τ})}∥^{2} + (1 + \frac{1}{β}) ∑_{r=1}^{s_{i−1}} ∥x̄_{r}^{(w_{τ} +r−1)} Z_{r,i}∥ ∑_{s_{i−1}+1≤τ≤s_{i}^{1≤r≤s_{i−1}}} sin^{2} ξ_{rτ} ≤

≤ (1 + β) ∑_{τ=s_{i−1}+1}^{s_{i}} ∥x_{τ}^{(1)}∥^{2} + (1 + \frac{1}{β}) ∥T̄^{(w_{t})}∥_{off}^{2} ∑_{s_{i−1}+1≤τ≤s_{i}^{1≤r≤s_{i−1}}} sin^{2} ξ_{rτ}.

Since ∥T̄^{(w_{τ})}∥_{off} ≤ ∥T ∥_{off} we have

∑_{i=1}^{p} ∥T_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ \frac{1}{8} \frac{∥T ∥_{off}^{2}}{ν^{2}} [(1 + β) ∑_{i=1}^{p} ∑_{τ=s_{i−1}+1}^{s_{i}} ∥x_{τ}^{(1)}∥^{2} +

(1 + \frac{1}{β}) ∥T ∥_{off}^{2} ∑_{i=2}^{p} ∑_{s_{i−1}+1≤τ≤s_{i}^{1≤r≤s_{i−1}}} sin^{2} ξ_{rτ} ] , β > 0.

Using the relation (2.15), Lemma 3.2 and the assumption S1 we obtain

∑_{i=1}^{p} ∥T_{ii}^{(q_{i}′)}∥_{off}^{2} ≤ \frac{1}{8} \frac{∥T ∥_{off}^{4}}{ν^{2}} (\sqrt{2} + \frac{4}{7} \frac{∥T ∥_{off}}{ν} )^{2}
≤ \frac{1}{8} (\sqrt{2} + \frac{4}{7})^{2} \frac{∥T ∥_{off}^{4}}{ν^{2}} ≤ 0.493 \frac{∥T ∥_{off}^{4}}{ν^{2}} ,

which proves Lemma 3.4.

Theorem 3.5 Let A be a triangular matrix of order n, and let the sequence A^{(1)} = A, A^{(2)}, … be generated by a SVDT method. If A satisfies the assumptions S1, S2 and S3, then

∥A^{(N+1)}∥_{off} ≤ \frac{4}{3} \frac{∥A∥_{off}^{2}}{ν} .

Proof: The proof follows the lines of the proof of Theorem 2.8. By Lemma 3.3, Lemma 3.4 and Lemma 3.2 we obtain

∥A^{(N+1)}∥_{off}^{2} = ∥T^{(N+1)}∥_{off}^{2} = ∥T_{pp}^{(N+1)}∥_{off}^{2} + ∑_{i=1}^{p−1} ⊤_{i}^{(N+1)}
≤ (1 + γ) ∑_{i=1}^{p} ∥T_{ii}^{(q_{i}′)}∥_{off}^{2} + (1 + \frac{1}{γ})∥T ∥_{off}^{2} ∑_{(τ,r)∈G_{i}} sin^{2} η_{τr}

≤ (1 + γ) 0.493 \frac{∥T ∥_{off}^{4}}{ν^{2}} + (1 + \frac{1}{γ})\frac{16}{49} \frac{∥T ∥_{off}^{4}}{ν^{2}} , γ > 0.

Using the relation (2.15) we obtain

∥A^{(N+1)}∥_{off} ≤ (\sqrt{0.493} + \frac{4}{7}) \frac{∥T ∥_{off}^{2}}{ν} ≤ 1.274 \frac{∥T ∥_{off}^{2}}{ν} ,

which proves the theorem.

This result quite corresponds to the one stated by Theorem 2.8. At this place we could add comments and remarks similar to those after Theorem 2.8.

For SVDT methods we have not considered the case of pathologically close singular values. The way how to handle that case is similar to the one for the symmetric case. We note that another approach to that case ( which is simpler but yields somewhat weaker results) is presented in [3].

References

[1] R. P. Brent and F. T. Luk: The Solution of Singular-value and Symmetric Eigenvalue Problems on Multiprocessor Arrays. SIAM Journal of Scientific and Statistical Computing 6 (1985) 69-84.

[2] J. P. Charlier and M. Vanbegin and P. Van Dooren: On Efficient Implementations of Kogbetliantz’s Algorithm for Computing the Singular Value Decomposition. Numerische Mathematik 52 (1988) 279-300.

[3] Charlier, J.-P. and Van Dooren, P.: On Kogbetliantz’s SVD Algorithm in the Presence of Clusters. Linear Algebra and Its Applications 95 (1987) 135–160.

[4] Z. Drmač, V. Hari and K. Veselić: On the Quadratic Convergence Bounds for the Serial J-symmetric Jacobi Method. Technical Report. University of Zagreb, 1991.

[5] K.Vince Fernando: Linear Convergence of the Row Cyclic Jacobi and Kogbetliantz Methods. Numer. Math. 56 (1989) 71-91

[6] E. R. Hansen: On Jacobi Methods and Block Jacobi Methods for Computing Matrix Eigenvalues. Stanford University 1960.

[7] E. R. Hansen: On Cyclic Jacobi Methods. SIAM J. Appl. Math. 11 (1963) 449–459.

[8] V. Hari: On the Quadratic Convergence of Jacobi Algorithms. Radovi Mathematički 2 (1986) 127–146.

[9] V. Hari and K. Veselić: On Jacobi Methods for Singular Value Decompositions. SIAM Journal on Scientific and Statistical Computing, Vol. 8, No. 5 (1987) 741–754.

[10] V. Hari: On the Quadratic Convergence of the Serial SVD Jacobi Methods for Triangular Matrices. SIAM Journal of Scientific and Statistical Computing, Vol. 10, No. 6 (1989) 1076– 1096.

[11] V. Hari: On Pairs of Almost Diagonal Matrices. To appear in Linear Algebra and Its Applications.

[12] H. P. M. Van Kempen: On the Quadratic Convergence of the Special Cyclic Jacobi Method. Numerische Mathematik 9 (1966) 19–22.

[13] E. Kogbetliantz: Diagonalization of General Complex Matrices as a New Method for Solution of Linear Equations. Proc.Imtern. Congr. Math. Amsterdam 2 (1954) 356–357.

[14] E. Kogbetliantz: Solutions of Linear Equations by Diagonalization of Coeficient Matrices. Quart. Appl. Math. 13 (1955) 123–132.

[15] F. T. Luk: A Triangular Processor Array for Computing Singular Values. Linear Algebra and Its Applications 77 (1986) 259–273.

[16] F.T.Luk and H.Park: On Parallel Jacobi Orderings. SIAM J. Sci.Statist.Comput. 10 (1989) 18–26.

[17] F.T.Luk and H.Park: A Proof of Convergence for Two Parallel Jacobi SVD Algorithms. IEEE Trans. Comput. 38 (1989) 806–811.

[18] C. C. Paige and Van Dooren, P.: On the Quadratic Convergence of Kogbetliantz’s Algorithm for Computing the Singular Value Decomposition. Linear Algebra and Its Applications 77 (1986) 301–313.

[19] B. N. Parlett: The Symmetric Eigenvalue Problem. Prentice-Hall. Englewood Cliffs. N. J. 1980.

[20] N. Rhee and V. Hari: On the Global and Cubic Convergence of a Quasi-cyclic Jacobi Method. Technical Report, University of Missouri in Kansas City 90-1, 1990.

[21] A. Ruhe: On the Quadratic Convergence of the Jacobi Method for Normal Matrices. BIT 7 (1967) 305–313.

[22] K.Veselić: An Eigenreduction Algorithm for Definite Matrix Pairs and its Applications to Overdamped Linear Systems. Technical Report. University of Hagen, 1990.

[23] J. H. Wilkinson: Note on the Quadratic Convergence of the Cyclic Jacobi Process. Numerische Mathematik 4 (1962) 296–300.

[24] J. H. Wilkinson: Almost Diagonal Matrices with Multiple or Close Eigenvalues. Linear Algebra and Its Applications 1 (1968) 1–12.

[25] G. H. Golub and C. F. Van Loan: Matrix Computations. The Johns Hopkins University Press, 2nd edition, 704 West 40th Street, Baltimore, Maryland 21211, 1989.