Scaled Iterates by Kogbetliantz Method

J. Matejaš^{∗}, V. Hari^{†}

Abstract

Scaled iterates associated with the serial Kogbetliantz method for computing the SVD of complex triangular matrices are considered. They are defined by B_{S}^{(k)} = |diag(B^{(k)})|^{− \frac{1}{2}} B^{(k)}|diag(B^{(k)})|^{− \frac{1}{2}} , where B^{(k)} are matrices generated by the method. Sharp estimates are derived for the Frobenius norm of the off-diagonal part of B_{S}^{(k)} in the case of simple singular values. This norm represents a good measure for advancing of the algorithm. The obtained estimates can be used in connection with the quadratic convergence of the algorithm.

Key words. Kogbetliantz method, scaled matrices, simple singular values.

AMS subject classification. 65F15, 65G05.

0 Introduction

Kogbetliantz method is a known two-sided SVD Jacobi method for square matrices. Since its discovery [16, 17] the method has been thoroughly studied, especially its global convergence [9], its quadratic convergence [23, 11, 3] and its implementation details [2, 18, 4]. Later, it was found out that the method becomes more simple and efficient if it is applied to triangular matrix under the row- or column-cyclic pivot strategy (see [14]). In that case the method exhibits behavior very similar to the known Jacobi method for symmetric/Hermitian matrices (see [14, 12, 8, 13]). The starting triangular matrix is obtained by applying once or twice (cf. [7]) the QR factorization.

∗Faculty of Economics, University of Zagreb, Kennedyjev trg 6, 10000 Zagreb, CROATIA

†Department of Mathematics, University of Zagreb, Bijenička 30, 10000 Zagreb, CROATIA

Although it has not yet been proven, numerical tests lead to presumption, that on triangular matrices obtained by the QR factorization with column pivoting, the serial Kogbetliantz method computes the singular values and vectors with high relative accuracy.

In the recent paper [22] (see also Theorem 1 here) it has been shown that one proper measure for the relative distance between diagonal elements and the corresponding singular values is the norm of the off-diagonal part (the so called off-norm) of the scaled matrix divided by the minimum relative gap in the set of singular values. Since this relative gap depends only on the initial matrix, one is forced to monitor the off-norms of the scaled iterates. Thus, a proper measure for advancing of the algorithm is the off-norm of the scaled iterates.

The same conclusion holds for the Hermitian Jacobi method when applied to positive definite matrices (see [6]). The same will hold (cf. [1, 15]) if the initial matrix is scaled diagonally dominant indefinite Hermitian matrix. In these cases however, sharp quadratic convergence bounds of scaled iterates have already been proved in [20] and [21]. These results have nice applications in conection with the stopping criterions of one- and two-sided Hermitian Jacobi methods.

In this paper we estimate the off-norms of scaled iterates for the complex Kogbetliantz method under the column-cyclic pivot startegy, in the case of simple singular values. Although elementary, some proofs presented here are pretty long and complex. The estimates presented are generalizations of those from [21]. As an application, we sketch how the new estimates can be used in the quadratic convergence proof of the serial Kogbetliantz method. We believe that another application lies in the accuracy consideration of the method.

In the same fashion, as the estimates from [15] have been used in [21], here the estimates from [22] are used. The role of the minimum absolute gap in the classical result [13], is replaced here by the minimum relative gap. Therefore, the obtained results are especially well suited for the case when singular values cluster around the origin.

Note that the proof of the quadratic convergence of scaled iterates by the Hermitian Jacobi method from [21], is much more complicated than the already complicated proof for the non-scaled iterates from [13]. A similar, although somewhat more complex situation is present here, so acquintance with the proofs from [21] could help in understanding the paper.

The paper is organized as follows. In Section 1 we present recent results on the structure of scaled diagonaly dominant triangular matrices based on the relative gaps in the set of singular values. In Section 2 we shortly describe the complex Kogbetliantz method. In Section 3 we prove some general estimates for scaled iterates. In Section 4 asymptotic estimates are proved. This means that the initial matrix is assumed to be sufficiently diagonally dominant in the scaled sense. As an application, in the last section we formulate asymptotic assumptions that are needed for the quadratic convergence of scaled iterates in the case of simple singular values. We also briefly sketch the quadratic convergence proof.

1 Notation and Auxiliaries

First we introduce notation. By C^{n×n} is denoted the set of complex matrices of order n. For every X ∈C^{n×n}, diag(X) = diag(x_{11}, …, x_{nn}) is the diagonal and

Ω(X) = X − diag(X)

is the off-diagonal part of X = (x_{ij}). The i’th row of Ω(X) is denoted by (cf. [15]), τ_{i}(X), i.e.

τ_{i}(X) = [x_{i1} … x_{i,i−1} x_{i,i+1} … x_{in}] .  (1.1)

If X has invertible diag(X), then

X_{S} = |diag(X)|^{−1/2} X |diag(X)|^{−1/2}  (1.2)

is regarded as scaled matrix^{1} X. Note that the scaled matrix X_{S} has diagonal elements of unit modulus.

If ||Ω(X_{S})|| ≤ α < 1, then X is α-scaled diagonally dominant (α-s.d.d.) matrix with respect to norm ||·|| (see [1]). By ||X||_{2} and ||X|| will be denoted the spectral and the Frobenius norm of X, respectively.

1We use only the symmetric scaling.

Let us introduce yet the relative gap function (see [15]) rg of two real arguments,

rg(a, b) = \{ \begin{matrix}\frac{|a − b|}{|a| + |b|}, & |a| + |b| > 0 \\ 0, & a = b = 0 \end{matrix} .  (1.3)

Let B ∈C^{n×n} has simple singular values

σ_{1} > σ_{2} > σ_{3} > … > σ_{n} .  (1.4)

Using the relations (1.3) and (1.4), we define the relative gaps in the set of singular values of B,

θ_{i} = min_{j≠i^{1≤j≤n}} rg(σ_{i}, σ_{j}), 1 ≤ i ≤ n,  (1.5)

and the minimum relative gap

θ = min_{1≤i≤n} θ_{i} .  (1.6)

Note that θ_{i} < 1 for all 1 ≤ i ≤ n.

The structure of an α-s.d.d. matrix is given in [22]. In this paper we consider only triangular and essentialy triangular α-s.d.d. matrices with simple singular values (see Section 2). For such matrices holds b_{ij} · b_{ji} = 0 and the result from [22, Corollary 6] takes the following form.

Theorem 1.1 Let B ∈C^{n×n} be essentialy triangular matrix with positive diagonal, satisfying

b_{11} > b_{22} > … > b_{nn}  (1.7)

and

||Ω(B_{S})||_{2} < \frac{θ}{3} ,  (1.8)

where B_{S} and θ are defined by the relations (1.2) and (1.6) respectively. If the singular values of B are simple, then

(i) |1 − \frac{σ_{i}}{b_{ii}} | ≤ \frac{2}{θ_{i}} [||τ_{i}(B_{S})||^{2} + ||τ_{i}(B_{S}^{∗})||^{2}] , 1 ≤ i ≤ n,
(ii) ∑_{i=1}^{n} |1 − \frac{σ_{i}}{b_{ii}} |^{2} ≤ \frac{8}{θ^{2}} ||Ω(B_{S})||^{4} ,

where τ_{i}(·) and θ_{i} are defined by the relation (1.1) and (1.5), respectively If diag(B) is not positive definite, every appearance of diagonals of B (in the assumption (1.7) and in the assertions (i) and (ii)) should be replaced by their modulii. Theorem 1.1 is used in the asymptotic estimates for scaled iterates by the Kogbetliantz method.

2 Kogbetliantz method

Here we give a short description of the Kogbetliantz method for computing the singular value decomposition of triangular matrices (SVDT). Let B = (b_{rt}) be a complex triangular matrix of order n with positive diagonal elements satisfying the assumption (1.7). Note that (1.7) naturally results after applying the QR factorization with column pivoting. Kogbetliantz method for complex triangular matrices has a nice property to maintain the reality (positivity) of the initially real (positive) diagonal elements. Since real, or even better, positive diagonal elements, make the algorithm simpler, we assume the initial matrix B has positive diagonals which satisfy (1.7).

Note also that for any square complex matrix the condition (1.7) can be achieved by considering the matrix P^{∗}Φ^{∗}BP, where Φ = diag(e^{ı arg(b_{11})}, … , e^{ı arg(b_{nn})}) and P is a suitably chosen permutation matrix. The matrices B and P^{∗}Φ^{∗}BP have the same singular values, while the singular vectors are simply related. If B is triangular matrix for which |b_{11}| > ⋯ > |b_{nn}| holds, then P = I_{n}.

Starting from a triangular matrix B, Kogbetliantz method generates a sequence of matrices B^{(k)} = (b_{lm}^{(k)}), k ≥ 0, by the rule

B^{(k+1)} = (U^{(k)})^{∗}B^{(k)}V^{(k)}, k ≥ 0 ; B^{(0)} = B ,  (2.1)

where U^{(k)} and V^{(k)}, k ≥ 0 are unitary plane matrices whose essential four elements are

(U^{(k)})_{ii} = (U^{(k)})_{jj} = cos φ^{(k)}
(U^{(k)})_{ij} = −\overline{(U^{(k)})_{ji}} = e^{ı ω_{k}} sin φ^{(k)}
(V^{(k)})_{ii} = (V^{(k)})_{jj} = cos ψ^{(k)}
(V^{(k)})_{ij} = −\overline{(V^{(k)})_{ji}} = e^{ı ϑ_{k}} sin ψ^{(k)}.

(2.2)

For the other elements, we have (U^{(k)})_{lm} = (V^{(k)})_{lm} = δ_{lm}, {l, m}∩{i, j} = ∅. Here, ı is the imaginary unit, \overline{z} is the complex conjugate z and δ_{lm} is the Kronecker’s delta. The 2 × 2 matrices

[ \begin{matrix}b_{ii}^{(k)} & b_{ij}^{(k)} \\ b_{ji}^{(k)} & b_{jj}^{(k)} \end{matrix} ] , [ \begin{matrix}(U^{(k)})_{ii} & (U^{(k)})_{ij} \\ (U^{(k)})_{ji} & (U^{(k)})_{jj} \end{matrix} ] , [ \begin{matrix}(V^{(k)})_{ii} & (V^{(k)})_{ij} \\ (V^{(k)})_{ji} & (V^{(k)})_{jj} \end{matrix} ] ,

are called pivot submatrices of B^{(k)}, U^{(k)}, V^{(k)}, respectively. The pair of indices (i, j) = (i(k), j(k)) is called pivot pair and b_{ij}^{(k)} is the pivot element. The relation (2.1) defines the k’th step or the k’th iteration of the method. In the sequel, i and j will be reserved for pivot indices.

For b_{ij}^{(k)} ≠ 0 the angles φ^{(k)}, ψ^{(k)}, ω_{k} and ϑ_{k} are determinated by the requirement

b_{ij}^{(k+1)} = b_{ji}^{(k+1)} = 0 ,  (2.3)

which ensures that

||Ω(B^{(k+1)})||^{2} = ||Ω(B^{(k)})||^{2} − |b_{ij}^{(k)}|^{2}, k ≥ 0 ,  (2.4)

holds. The relation (2.3) yields several sets of formulas for required angles, depending on whether U^{(k)} or V^{(k)} is calculated first (see [9, 25, 4, 12, 13]). Here we consider only the serial, that is, the column- and the row-cyclic pivot strategies. In the first case, the pivot pair runs through the sequence of pairs (1, 2), (1, 3), (2, 3), …, (1, n), …, (n − 1, n), in the cyclic way. In the second case the sequence is (1, 2), (1, 3), …, (1, n), (2, 3), …, (2, n), …, (n − 1, n). Serial Kogbetliantz methods do not essentially ruin the triangular form. If B is upper-triangular, then within an odd (even) cycle the nontrivial offdiagonal elements push downwards (upwards) so that after each odd (even) sweep the current matrix is lower- (upper-) triangular. Similar situation is when B is lower-triangular. Within every cycle each current matrix is permutationally similar to a matrix in triangular form (PST), hence it is essentialy triangular (see [14]). Therefore, the whole process can be performed on an upper-triangular array (see [12, 13]). At step k, we can associate the uppertriangular matrix G^{(k)} = (g_{lm}^{(k)}) with the content of that array. Then, we have

G^{(k)} + G^{(k)T} = B^{(k)} + B^{(k)T} , k ≥ 0 .  (2.5)

In the following we assume positive diagonal elements. We shall express the angle formulas in terms of the elements of G^{(k)}. If the right-hand transformation V^{(k)} is computed first, the relation (2.3) implies

e^{ı ϑ_{k}} tan 2ψ^{(k)} = \frac{2g_{ii}^{(k)}g_{ij}^{(k)}}{(g_{jj}^{(k)})^{2} − (g_{ii}^{(k)})^{2} + |g_{ij}^{(k)}|^{2}} ,

e^{ı ω_{k}} tan φ^{(k)} = e^{ıϑ_{k}} \frac{|g_{ij}^{(k)}| + g_{ii}^{(k)} tan ψ^{(k)}}{g_{jj}^{(k)}} = \frac{g_{jj}^{(k)}e^{ıϑ_{k}} tan ψ^{(k)}}{g_{ii}^{(k)} − |g_{ij}^{(k)}| tan ψ^{(k)}} . (2.6)

Hence, we obtain the following angle formulas (see [25, 12, 13]) for the first sweep:

\begin{matrix}e^{ı ϑ_{k}} & = & \frac{g_{ij}^{(k)}}{|g_{ij}^{(k)}|}, i.e. ϑ_{k} = arg(g_{ij}^{(k)}) \\ tan 2ψ^{(k)} & = & \frac{2g_{ii}^{(k)}|g_{ij}^{(k)}|}{(g_{jj}^{(k)})^{2}−(g_{ii}^{(k)})^{2}+|g_{ij}^{(k)}|^{2}} , ψ^{(k)} ∈ [−\frac{π}{4}, \frac{π}{4}] , \\ z_{k} & = & \frac{g_{ij}^{(k)}+g_{ii}^{(k)}e^{ıϑ_{k}} tan ψ^{(k)}}{g_{jj}^{(k)}} = e^{ıϑ_{k}} \frac{|g_{ij}^{(k)}|+g_{ii}^{(k)} tan ψ^{(k)}}{g_{jj}^{(k)}} \\ & = & \frac{g_{jj}^{(k)}e^{ıϑ_{k}} tan ψ^{(k)}}{g_{ii}^{(k)}−|g_{ij}^{(k)}| tan ψ^{(k)}} , \\ e^{ı ω_{k}} & = & \frac{z_{k}}{|z_{k}|}, i.e. ω_{k} = arg(z_{k}) , \\ tan φ^{(k)} & = & |z_{k}|, φ^{(k)} ∈ [0, \frac{π}{2}]. \end{matrix} \}  (2.7)

Using convenient notation: c_{φ}^{(k)} = cos φ^{(k)}, s_{φ}^{(k)} = sin φ^{(k)}, c_{ψ}^{(k)} = cos ψ^{(k)}, s_{ψ}^{(k)} = sin ψ^{(k)}, the transformation formulas for the elements of G^{(k)} become

\begin{matrix}g_{li}^{(k+1)} = c_{φ}^{(k)}g_{li}^{(k)} − e^{ı ω_{k}}s_{φ}^{(k)}g_{lj}^{(k)} \\ g_{lj}^{(k+1)} = e^{−ı ω_{k}}s_{φ}^{(k)}g_{li}^{(k)} + c_{φ}^{(k)}g_{lj}^{(k)} \end{matrix} \} 1 ≤ l ≤ i − 1 ; \begin{matrix}g_{il}^{(k+1)} = c_{ψ}^{(k)}g_{il}^{(k)} − e^{−ı ϑ_{k}}s_{ψ}^{(k)}g_{lj}^{(k)} \\ g_{lj}^{(k+1)} = e^{ı ϑ_{k}}s_{ψ}^{(k)}g_{il}^{(k)} + c_{ψ}^{(k)}g_{lj}^{(k)} \end{matrix} \} i + 1 ≤ l ≤ j − 1 ; \begin{matrix}g_{il}^{(k+1)} = c_{φ}^{(k)}g_{il}^{(k)} − e^{ı ω_{k}}s_{φ}^{(k)}g_{jl}^{(k)} \\ g_{jl}^{(k+1)} = e^{−ı ω_{k}}s_{φ}^{(k)}g_{il}^{(k)} + c_{φ}^{(k)}g_{jl}^{(k)} \end{matrix} \} j + 1 ≤ l ≤ n ; \begin{matrix}g_{ii}^{(k+1)} = \frac{c_{φ}^{(k)}}{c_{ψ}^{(k)}} g_{ii}^{(k)} = \frac{|s_{ψ}^{(k)}|}{s_{φ}^{(k)}}g_{jj}^{(k)} = \frac{c_{ψ}^{(k)}}{c_{φ}^{(k)}} g_{ii}^{(k)} − \frac{s_{ψ}^{(k)}}{c_{φ}^{(k)}} |g_{ij}^{(k)}| \\ g_{jj}^{(k+1)} = \frac{c_{ψ}^{(k)}}{c_{φ}^{(k)}} g_{jj}^{(k)} = \frac{s_{φ}^{(k)}}{|s_{ψ}^{(k)}|}g_{ii}^{(k)} = \frac{c_{φ}^{(k)}}{c_{ψ}^{(k)}} g_{jj}^{(k)} + sgn (s_{ψ}^{(k)})\frac{s_{φ}^{(k)}}{c_{ψ}^{(k)}} |g_{ij}^{(k)}| \\ g_{ij}^{(k+1)} = 0 \end{matrix}  (2.8)

The transformation G^{(k)} → G^{(k+1)}, defined by the relations (2.7) and (2.8) will be referred to as Kogbetliantz transformation or Kogbetliantz step on the associated matrix G^{(k)}, with pivot pair (i, j). Shorter, we call it associated Kogbetliantz transformation or step. The algorithm (or the whole process) on matrices G^{(k)} we call associated Kogbetliantz algorithm (process).

Starting with upper-triangular B, the relation (2.8) holds for odd cycles only. For even cycles φ^{(k)}, ω_{k} and ψ^{(k)}, ϑ_{k} interchange their places. We can consider a method in which U^{(k)} and V^{(k)} interchange their places in subsequent cycles and thus ensure that (2.8) holds for every cycle.^{2} But we need not be concerned aboat that. The obtained bounds will be symmetric in the arguments φ^{(k)} and ψ^{(k)}. For this reason we have even not considered the angle formulas when U^{(k)} is calculated first.

Let us now consider the scaled iterates of the matrices G^{(k)},

G_{S}^{(k)} = |diag(G^{(k)})|^{−1/2}G^{(k)}|diag(G^{(k)})|^{−1/2}, k ≥ 0.  (2.9)

The matrix G_{S}^{(k)} is associated with the content of the upper-triangular array when B_{S}^{(k)} is compactly stored in it. Next, we define

A^{(k)} = Ω(G_{S}^{(k)} + G_{S}^{(k)T}) = Ω(G_{S}^{(k)}) + Ω(G_{S}^{(k)})^{T} , k ≥ 0.  (2.10)

Note that A^{(k)} = (a_{lm}^{(k)}) is a symmetric matrix with zero diagonal, whose off-diagonal elements are given by

a_{lm}^{(k)} = a_{ml}^{(k)} = \frac{g_{lm}^{(k)}}{\sqrt{g_{ll}^{(k)}g_{mm}^{(k)}}} , l ≠ m, k ≥ 0.  (2.11)

Since each B_{S}^{(k)} is essentially triangular, the relations (2.5), (1.2), (2.9) and (2.10) imply

A^{(k)} = Ω(B_{S}^{(k)}) + Ω(B_{S}^{(k)})^{T} , k ≥ 0.

Hence

a_{lm}^{(k)} = \frac{b_{lm}^{(k)} + b_{ml}^{(k)}}{\sqrt{b_{ll}^{(k)}b_{mm}^{(k)}}} , l ≠ m, k ≥ 0.

2The interchanges reflect only on singular vector updates.

The Frobenius norm of Ω(G_{S}^{(k)}) shall be denoted by α_{k},

α_{k} = ||Ω(G_{S}^{(k)})|| = ||Ω(B_{S}^{(k)})|| = \frac{\sqrt{2}}{2}||A^{(k)}||, k ≥ 0.  (2.12)

This paper estimates the changes of α_{k} within one cycle. To this end, we can presume that k = 0. We shall consider both, the general estimates and the estimates that require small enough α_{0}.

3 General Estimates

Here, we prove estimates that do not require small α_{0}. From the relation (2.4), we conclude that

∥Ω(G^{(k+1)})∥^{2} = ∥Ω(G^{(k)})∥^{2} − |g_{ij}^{(k)}|^{2}, k ≥ 0 ,

holds. This property is not shared with the sequence ∥Ω(G_{S}^{(k)})∥^{2} because G_{S}^{(k)} → G_{S}^{(k+1)} is not an orthogonal transformation. Let us consider this transformation more carefully.

Lemma 3.1 Suppose the sequence G^{(k)} = (g_{lm}^{(k)}), k ≥ 0 is obtained by the associated Kogbetliantz process, and suppose that G^{(0)} has positive diagonal elements. For a fixed k, let us denote G = (g_{lm}) = G^{(k)} and G̃ = (g̃_{lm}) = G^{(k+1)}. Thus, G̃ = is obtained from G by a single Kogbetliantz transformation which annihilates the element g_{ij}. Let A = (a_{lm}) and Ã = (ã_{lm}) be defined by

A = Ω(G_{S}) + Ω(G_{S})^{T} , Ã = Ω(G̃_{S}) + Ω(G̃_{S})^{T} .

If |a_{ij}| < 1, then

|ã_{li}|^{2} + |ã_{lj}|^{2} ≤ \frac{1 + |a_{ij}|}{1 − |a_{ij}|}(|a_{li}|^{2} + |a_{lj}|^{2}), l ≠ i, j .

Proof. In the proof we omit the index k. Using the relation (2.8) we obtain for 1 ≤ l ≤ i − 1,

|g̃_{li}|^{2} = c_{φ}^{2}|g_{li}|^{2} + s_{φ}^{2}|g_{lj}|^{2} − 2s_{φ}c_{φ}ℜ(e^{ıω}\overline{g}_{li}g_{lj}),  (3.1)
|g̃_{lj}|^{2} = c_{φ}^{2}|g_{lj}|^{2} + s_{φ}^{2}|g_{li}|^{2} + 2s_{φ}c_{φ}ℜ(e^{ıω}\overline{g}_{li}g_{lj}).  (3.2)

Using now the relations (2.11), (3.1) and (3.2) we have

(|ã_{li}|^{2} + |ã_{lj}|^{2}) − (|a_{li}|^{2} + |a_{lj}|^{2})
= (\frac{|g̃_{li}|^{2}}{g̃_{ii}g_{ll}} + \frac{|g̃_{lj}|^{2}}{g̃_{jj}g_{ll}}) − (\frac{|g_{li}|^{2}}{g_{ii}g_{ll}} + \frac{|g_{lj}|^{2}}{g_{jj}g_{ll}})
= \frac{1}{g_{ll}} · (\frac{|g̃_{li}|^{2}}{g̃_{ii}} + \frac{|g̃_{lj}|^{2}}{g̃_{jj}} − \frac{|g_{li}|^{2}}{g_{ii}} − \frac{|g_{lj}|^{2}}{g_{jj}})
= \underbrace{(\frac{c_{φ}^{2}}{g̃_{ii}} + \frac{s_{φ}^{2}}{g̃_{jj}} − \frac{1}{g_{ii}})}_{ω_{iφ}} ·\frac{|g_{li}|^{2}}{g_{ll}} + \underbrace{(\frac{c_{φ}^{2}}{g̃_{jj}} + \frac{s_{φ}^{2}}{g̃_{ii}} − \frac{1}{g_{jj}})}_{ω_{jφ}} ·\frac{|g_{lj}|^{2}}{g_{ll}}  (3.3)

+ \underbrace{2s_{φ}c_{φ} · (\frac{1}{g̃_{jj}} − \frac{1}{g̃_{ii}})}_{ω_{φ}} ·\frac{ℜ(e^{ıω}\overline{g}_{li}g_{lj})}{g_{ll}} , 1 ≤ l ≤ i − 1 .

The relation (3.3) holds for i + 1 ≤ l ≤ j − 1 provided that c_{φ}, s_{φ}, g_{li} are replaced by c_{ψ}, s_{ψ}, g_{il} and for j +1 ≤ l ≤ n, provided that g_{li}, g_{lj} are replaced by g_{il}, g_{jl}. Our next task is to find sharp upper bounds for ω_{iφ}, ω_{jφ}, |ω_{φ}|, ω_{iψ}, ω_{jψ}, |ω_{ψ}|, where the last three terms are defined in the same way as the former ones with φ replaced by ψ. Although the desired estimates are obtained by using elementary calculus, the way is pretty complicated.

In order to simplify the notation, we set

a := |a_{ij}| = \frac{|g_{ij}|}{\sqrt{g_{ii}g_{jj}}} .  (3.4)

We start with some basic relations between ψ and φ that follow from (2.7).

tan φ ≥ 0, | tan ψ| ≤ 1,  (3.5)
sgn(tan ψ) = sgn(tan 2ψ) = sgn(g_{jj}^{2} − g_{ii}^{2} + |g_{ij}|^{2}).  (3.6)

According to the relation (3.6), we consider two cases: tan ψ < 0 and tan ψ ≥ 0. In the both cases g_{ij} ≠ 0 is presumed, since otherwise all angles are zero, the transformation skipped and the assertion of the lemma holds with equality. This means that to the rest of the proof, the both angles are nontrivial.

(a) tan ψ < 0. In this case we have g_{jj}^{2} + |g_{ij}|^{2} < g_{ii}^{2}, hence g_{jj} < g_{ii}. Using the relation (2.7), we obtain

tan φ < \frac{g_{jj}}{g_{ii}} | tan ψ|  (3.7)
< | tan ψ| ≤ 1 .  (3.8)

Since g_{jj} tan φ = | |g_{ij}| − g_{ii} | tan ψ| |, we have

| tan ψ| ≤ \frac{g_{jj}}{g_{ii}} tan φ + \frac{|g_{ij}|}{g_{ii}}  (3.9)
< tan φ + \frac{|g_{ij}|}{g_{ii}}  (3.10)
< tan φ + a .  (3.11)

(b) tan ψ > 0. In this case g_{jj}^{2} + |g_{ij}|^{2} > g_{ii}^{2}, and we consider two further cases

(b1) g_{ii} ≥ g_{jj}. Using the relation (2.7), we have

g_{jj} tan φ = |g_{ij}| + g_{ii}| tan ψ| ,

whence

| tan ψ| = tan ψ = \frac{g_{jj}}{g_{ii}} tan φ − \frac{|g_{ij}|}{g_{ii}}
< \frac{g_{jj}}{g_{ii}} tan φ  (3.12)
≤ tan φ .  (3.13)

Note that by assumption a < 1. Since by (3.5) |g_{ij}|| tan ψ| ≤ |g_{ij}| = a·\sqrt{g_{ii}g_{jj}} ≤ ag_{ii} < g_{ii} and |g_{ij}|/g_{ii} = a\sqrt{g_{jj}/g_{ii}} ≤ a, from the second formula for tan φ, we obtain

\frac{tan φ}{| tan ψ|} = \frac{tan φ}{tan ψ} ≤ \frac{g_{jj}}{g_{ii} − |g_{ij}| tan ψ} < \frac{g_{jj}}{g_{ii}} · \frac{1}{1 − \frac{|g_{ij}|}{g_{ii}}} ≤ \frac{1}{1 − \frac{|g_{ij}|}{g_{ii}}}  (3.14)

and

\frac{tan φ}{tan ψ} ≤ \frac{g_{jj}}{g_{ii}} · \frac{1}{1 − a}  (3.15)
≤ \frac{1}{1 − a} .  (3.16)

(b2) g_{jj} > g_{ii}. Since |g_{ij}|| tan ψ| ≤ \frac{g_{ii}|g_{ij}|^{2}}{g_{jj}^{2}−g_{ii}^{2}+|g_{ij}|^{2}} < g_{ii}, the second formula for tan φ in (2.7) implies

g_{ii} tan φ − |g_{ij}| tan φ| tan ψ| = g_{jj}| tan ψ| .

Hence

| tan ψ| = tan ψ = \frac{g_{ii}}{g_{jj}} tan φ − \frac{|g_{ij}|}{g_{jj}} tan φ tan ψ
< \frac{g_{ii}}{g_{jj}} tan φ  (3.17)
< tan φ .  (3.18)

In this case we obtain the following estimates for angle φ,

tan φ = \frac{1}{g_{jj}} (|g_{ij}| + g_{ii} tan ψ)
= a\sqrt{\frac{g_{ii}}{g_{jj}}} + \frac{g_{ii}}{g_{jj}} tan ψ
< a\sqrt{\frac{g_{ii}}{g_{jj}}} + tan ψ  (3.19)

and

tan φ < \sqrt{\frac{g_{ii}}{g_{jj}}} · (a + tan ψ)  (3.20)
< a + tan ψ .  (3.21)

Since g_{ii} tan φ = g_{jj} tan ψ + |g_{ij}| tan φ tan ψ, using (3.21) and (3.5), we also obtain

\frac{tan φ}{tan ψ} = \frac{g_{jj}}{g_{ii}} + \frac{|g_{ij}|}{g_{ii}} tan φ
= \frac{g_{jj}}{g_{ii}} (1 + \frac{|g_{ij}|}{g_{jj}} tan φ)
≤ \frac{g_{jj}}{g_{ii}} (1 + a tan φ)  (3.22)
< \frac{g_{jj}}{g_{ii}} (1 + a(tan ψ + a))
< \frac{g_{jj}}{g_{ii}} (1 + a(1 + a)) .  (3.23)

Now, we shall bound ω_{iφ}, …, |ω_{ψ}|. For each term we have to consider three cases: (a), (b1) and (b2). We shall need to transform each term to the appropriate form.

\underline{Bound for ω_{iφ}:} Using the relation (3.3) and (2.8), we obtain

ω_{iφ} = \frac{c_{φ}^{2}}{\frac{|s_{ψ}|}{s_{φ}}g_{jj}} + \frac{s_{φ}^{2}}{\frac{c_{ψ}}{c_{φ}} g_{jj}} − \frac{1}{g_{ii}}

= \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} (\frac{s_{φ}c_{φ}^{2}}{|s_{ψ}|} + \frac{s_{φ}^{2}c_{φ}}{c_{ψ}}) − 1]
= \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · \frac{s_{φ}c_{φ}}{|s_{ψ}|c_{ψ}} (c_{φ}c_{ψ} + s_{φ}|s_{ψ}|) − 1]

= \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · \frac{\frac{s_{φ}}{c_{φ}}}{\frac{|s_{ψ}|}{c_{ψ}}} · \frac{\frac{1}{c_{ψ}^{2}}}{\frac{1}{c_{φ}^{2}}} (c_{φ}c_{ψ} + s_{φ}|s_{ψ}|) − 1]

= \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · \frac{tan φ}{| tan ψ|} · \frac{1 + tan^{2} ψ}{1 + tan^{2} φ} cos(φ − |ψ|) − 1] . (3.24)

In the case (a), using the relation (3.11), we obtain

\frac{1 + tan^{2} ψ}{1 + tan^{2} φ} ≤ \frac{1 + (tan φ + a)^{2}}{1 + tan^{2} φ}
= 1 + a · \frac{2 tan φ + a}{1 + tan^{2} φ}
≤ 1 + a · (1 + a) .  (3.25)

Now the relations (3.24), (3.7) and (3.25) yield

ω_{iφ} ≤ \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · \frac{g_{jj}}{g_{ii}} · (1 + a(1 + a)) · 1 − 1]
= \frac{1}{g_{ii}} · a · (1 + a) < \frac{1}{g_{ii}} · \frac{a}{1 − a} .

In the case (b1), using the relations (3.24), (3.15) and (3.13), we obtain

ω_{iφ} ≤ \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · \frac{g_{jj}}{g_{ii}} · \frac{1}{1 − a} · 1 · 1 − 1]
≤ \frac{1}{g_{ii}} · \frac{a}{1 − a} .

In the case (b2), using the relations (3.24), (3.18) and (3.23), we obtain

ω_{iφ} ≤ \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · \frac{g_{jj}}{g_{ii}} · (1 + a(1 + a)) · 1 · 1 − 1]
≤ \frac{1}{g_{ii}} · a(1 + a) < \frac{1}{g_{ii}} · \frac{a}{1 − a} .

\underline{Bound for ω_{jφ}:} Using the relation (2.8) we obtain

ω_{jφ} = \frac{c_{φ}^{2}}{\frac{c_{ψ}}{c_{φ}} g_{jj}} + \frac{s_{φ}^{2}}{\frac{|s_{ψ}|}{s_{φ}}g_{jj}} − \frac{1}{g_{jj}}

= \frac{1}{g_{jj}} [\frac{c_{φ}^{3}}{c_{ψ}} + \frac{s_{φ}^{3}}{|s_{ψ}|} − 1]
= \frac{1}{g_{jj}} [\frac{c_{φ}}{c_{ψ}} · c_{φ}^{2} · (1 + \frac{s_{φ}^{2}}{c_{φ}^{2}} · \frac{\frac{s_{φ}}{c_{φ}}}{\frac{|s_{ψ}|}{c_{ψ}}}) − 1]

= \frac{1}{g_{jj}} [\sqrt{\frac{1 + tan^{2} ψ}{1 + tan^{2} φ}} · \frac{1}{1 + tan^{2} φ} · (1 + tan^{2} φ\frac{tan φ}{| tan ψ|}) − 1] .

In the case (a), from the relations (3.8) and (3.25) it follows that

ω_{jφ} ≤ \frac{1}{g_{jj}} [\sqrt{1 + a(1 + a)} · \frac{1}{1 + tan^{2} φ} · (1 + tan^{2} φ) − 1]
≤ \frac{1}{g_{jj}} [1 + a(1 + a) − 1] < \frac{1}{g_{jj}} · \frac{a}{1 − a} .

In the case (b1), from (3.12) and (3.16) we have

ω_{jφ} ≤ \frac{1}{g_{jj}} [1 · \frac{1}{1 + tan^{2} φ} · (1 + tan^{2} φ · \frac{1}{1 − a}) − 1]
= \frac{1}{g_{jj}} · \frac{tan^{2} φ}{1 + tan^{2} φ} · \frac{a}{1 − a} < \frac{1}{g_{jj}} · \frac{a}{1 − a} .

In the case (b2), from (3.18) we obtain

ω_{jφ} ≤ \frac{1}{g_{jj}} [1 · \frac{1}{1 + tan^{2} φ} · (1 + tan^{2} φ · \frac{tan φ}{tan ψ}) − 1]

= \frac{1}{g_{jj}} [\frac{1}{1 + tan^{2} φ} · (1 + tan^{2} φ − tan^{2} φ + tan^{2} φ · \frac{tan φ}{tan ψ}) − 1]
= \frac{1}{g_{jj}} [1 + (\frac{tan φ}{tan ψ} − 1) · \frac{tan^{2} φ}{1 + tan^{2} φ} − 1]
= \frac{1}{g_{jj}} (tan φ − tan ψ) · \frac{tan φ}{tan ψ} · \frac{tan φ}{1 + tan^{2} φ}

Now the relations (3.19), (3.22), (3.20) and (3.18) yield

ω_{jφ} ≤ \frac{1}{g_{jj}} · a · \sqrt{\frac{g_{ii}}{g_{jj}}} · \frac{g_{jj}}{g_{ii}} (1 + a tan φ) · \sqrt{\frac{g_{ii}}{g_{jj}}} · \frac{a + tan ψ}{1 + tan^{2} φ}
= \frac{1}{g_{jj}} · \frac{a(1 + a tan φ)(a + tan φ)}{1 + tan^{2} φ}
= \frac{1}{g_{jj}} · a · [a + (1 + a^{2})\frac{tan φ}{1 + tan^{2} φ}]
≤ \frac{1}{g_{jj}} · a · \frac{[a + (1 + a^{2}) · 1](1 − a)}{1 − a}
= \frac{1}{g_{jj}} · a · \frac{1 − a^{3}}{1 − a}
< \frac{1}{g_{jj}} · \frac{a}{1 − a} .

\underline{Bound for |ω_{φ}|:} Using the relation (2.8) we obtain

ω_{φ} = 2s_{φ}c_{φ}(\frac{c_{φ}}{c_{ψ}g_{jj}} − \frac{s_{φ}}{|s_{ψ}| g_{jj}})
= \frac{1}{g_{jj}} · 2s_{φ}c_{φ} · \frac{c_{φ}}{c_{ψ}} (1 − \frac{\frac{s_{φ}}{c_{φ}}}{\frac{|s_{ψ}|}{c_{ψ}}})

= \frac{1}{g_{jj}} · \frac{2 tan φ}{1 + tan^{2} φ} · \frac{cos φ}{cos ψ} · (1 − \frac{tan φ}{| tan ψ|}) .

In the case (a), using the relations (3.8) and (3.10) we have

|ω_{φ}| = \frac{1}{g_{jj}} · \frac{2}{1 + tan^{2} φ} · \frac{sin φ}{| sin ψ|} · (| tan ψ| − tan φ)
≤ \frac{1}{g_{jj}} · 2 · 1 · \frac{|g_{ij}|}{g_{ii}} = \frac{2}{g_{jj}} · a · \sqrt{\frac{g_{jj}}{g_{ii}}}

= \frac{1}{\sqrt{g_{ii}g_{jj}}} · 2a < \frac{1}{\sqrt{g_{ii}g_{jj}}} · \frac{2a}{1 − a} .

In the case (b1), the relations (3.12) and (3.14) yield

|ω_{φ}| < \frac{1}{g_{jj}} · 1 · 1 · (\frac{1}{1 − |g_{ij}|/g_{ii}} − 1)

= \frac{1}{g_{jj}} · \frac{|g_{ij}|/g_{ii}}{1 − |g_{ij}|/g_{ii}} = \frac{1}{g_{jj}} · \frac{a\sqrt{g_{jj}/g_{ii}}}{1 − a\sqrt{g_{jj}/g_{ii}}}

≤ \frac{1}{g_{jj}} · \frac{a\sqrt{g_{jj}/g_{ii}}}{1 − a} ≤ \frac{1}{\sqrt{g_{ii}g_{jj}}} · \frac{a}{1 − a} .

In the case (b2), using the relations (3.18), (3.22) and (3.19), we obtain

|ω_{φ}| = \frac{1}{g_{jj}} · \frac{2}{1 + tan^{2} φ} · \frac{cos φ}{cos ψ} · \frac{tan φ}{tan ψ}(tan φ − tan ψ)
≤ \frac{1}{g_{jj}} · \frac{2}{1 + tan^{2} φ} · 1 · \frac{g_{jj}}{g_{ii}} (1 + a tan φ) · a · \sqrt{\frac{g_{ii}}{g_{jj}}}
= \frac{1}{\sqrt{g_{ii}g_{jj}}} · 2a · (\frac{1}{1 + tan^{2} φ} + a · \frac{tan φ}{1 + tan^{2} φ})
≤ \frac{1}{\sqrt{g_{ii}g_{jj}}} · 2a · (1 + a)
< \frac{1}{\sqrt{g_{ii}g_{jj}}} · \frac{2a}{1 − a} .

\underline{Bound for ω_{iψ}:} Using the relation (2.8) we obtain

ω_{iψ} = \frac{c_{ψ}^{2}s_{φ}}{|s_{ψ}|g_{jj}} + \frac{s_{ψ}^{2}c_{φ}}{c_{ψ}g_{jj}} − \frac{1}{g_{ii}}
= \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} c_{φ}c_{ψ}(\frac{c_{ψ}s_{φ}}{|s_{ψ}|c_{φ}} + \frac{s_{ψ}^{2}}{c_{ψ}^{2}} ) − 1]
= \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} cos φ cos ψ · (\frac{tan φ}{| tan ψ|} + tan^{2} ψ) − 1] .

In the case (a), using the relations (3.8), (3.7) and (3.9) we have

ω_{iψ} < \frac{1}{g_{ii}} \{\frac{g_{ii}}{g_{jj}} cos^{2} φ · [\frac{g_{jj}}{g_{ii}} + (\frac{g_{jj}}{g_{ii}} tan φ + \frac{|g_{ij}|}{g_{ii}})^{2}] − 1\}

= \frac{1}{g_{ii}} \{\frac{g_{ii}}{g_{jj}} cos^{2} φ · \frac{g_{jj}}{g_{ii}} [1 + (\sqrt{\frac{g_{jj}}{g_{ii}}} tan φ + a)^{2}] − 1\}
< \frac{1}{g_{ii}} \{cos^{2} φ [1 + (tan φ + a)^{2}] − 1\}
= \frac{1}{g_{ii}} \{\frac{1 + (tan φ + a)^{2}}{1 + tan^{2} φ} − 1\}
= \frac{1}{g_{ii}} \{1 + a · \frac{2 tan φ + a}{1 + tan^{2} φ} − 1\}
< \frac{1}{g_{ii}} · a(1 + a) < \frac{1}{g_{ii}} · \frac{a}{1 − a} .

In the case (b1), the relations (3.13), (3.12) and (3.15) yield

ω_{iψ} = \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · (cos^{2} ψ \frac{sin φ}{sin ψ} + sin^{2} ψ \frac{cos φ}{cos ψ}) − 1]
< \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · (cos^{2} ψ \frac{sin φ}{sin ψ} + sin φ sin ψ · 1) − 1]
= \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · \frac{sin φ}{sin ψ} − 1]
= \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · \frac{tan φ}{tan ψ} · \frac{cos φ}{cos ψ} − 1]
≤ \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · \frac{g_{jj}}{g_{ii}} · \frac{1}{1 − a} · 1 − 1]
= \frac{1}{g_{ii}} · \frac{a}{1 − a} .

In the case (b2), similary as above, using the relations (3.18) and (3.23), we obtain

ω_{iψ} < \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · \frac{tan φ}{tan ψ} · \frac{cos φ}{cos ψ} − 1]
≤ \frac{1}{g_{ii}} [\frac{g_{ii}}{g_{jj}} · \frac{g_{jj}}{g_{ii}} · (1 + a(1 + a)) − 1]
= \frac{1}{g_{ii}} · a(1 + a) < \frac{1}{g_{ii}} · \frac{a}{1 − a} .

\underline{Bound for ω_{jψ}:} Using the relation (2.8) we obtain

ω_{jψ} = \frac{c_{ψ}^{2}}{\frac{c_{ψ}}{c_{φ}} g_{jj}} + \frac{s_{ψ}^{2}}{\frac{|s_{ψ}|}{s_{φ}}g_{jj}} − \frac{1}{g_{jj}}

= \frac{1}{g_{jj}} [cos φ cos ψ + sin φ| sin ψ| − 1] .

In the case (a), using the relations (3.8) and (3.11) we have

ω_{jψ} ≤ \frac{1}{g_{jj}} [cos^{2} φ + sin φ| sin ψ| − 1]
= \frac{1}{g_{jj}} sin φ(| sin ψ| − sin φ)
≤ \frac{1}{g_{jj}} · 1 · [\frac{| tan ψ|}{\sqrt{1 + tan^{2} ψ}} − \frac{tan φ}{\sqrt{1 + tan^{2} φ}}]

< \frac{1}{g_{jj}} · \frac{| tan ψ| − tan φ}{\sqrt{1 + tan^{2} φ}}

< \frac{1}{g_{jj}} [| tan ψ| − tan φ] < \frac{a}{g_{jj}} < \frac{1}{g_{jj}} · \frac{a}{1 − a} .

In the case (b1), in the same way as above, using the relations (3.12) and (3.16) we have

ω_{jψ} < \frac{1}{g_{jj}} [cos^{2} ψ + sin φ sin ψ − 1]
= \frac{sin ψ}{g_{jj}} [sin φ − sin ψ]
≤ \frac{1}{g_{jj}} [tan φ − tan ψ]
≤ \frac{1}{g_{jj}} tan ψ[\frac{1}{1 − a} − 1]
≤ \frac{1}{g_{jj}} [\frac{1}{1 − a} − 1] = \frac{1}{g_{jj}} · \frac{a}{1 − a} .

Similary, in the case (b2), using the relations (3.18) and (3.21), we have

ω_{jψ} ≤ \frac{1}{g_{jj}} [tan φ − tan ψ]

≤ \frac{1}{g_{jj}} · a < \frac{1}{g_{jj}} · \frac{a}{1 − a} .

\underline{Bound for |ω_{ψ}|:} Using the relation (2.8) we obtain

ω_{ψ} = 2s_{ψ}c_{ψ}(\frac{c_{φ}}{c_{ψ}g_{jj}} − \frac{s_{φ}}{|s_{ψ}|g_{jj}})
= \frac{2}{g_{jj}} cos φ cos ψ · (tan ψ − sgn s_{ψ} tan φ) .

In the case (a), using the relations (3.8) and (3.10) we have

|ω_{ψ}| = \frac{2}{g_{jj}} cos φ cos ψ · (| tan ψ| − | tan φ|)
< \frac{2}{g_{jj}} · 1 · 1 · \frac{|g_{ij}|}{g_{ii}} = \frac{2}{g_{jj}} · a · \sqrt{\frac{g_{jj}}{g_{ii}}}
= \frac{2a}{\sqrt{g_{ii}g_{jj}}} < \frac{1}{\sqrt{g_{ii}g_{jj}}} · \frac{2a}{1 − a} .

In the case (b1), using the relations (3.12) and (3.14) we have

|ω_{ψ}| = \frac{2}{g_{jj}} cos φ sin ψ · (\frac{tan φ}{tan ψ} − 1)
< \frac{2}{g_{jj}} cos φ sin φ · (\frac{1}{1 − |g_{ij}|/g_{ii}} − 1)

= \frac{sin 2φ}{g_{jj}} · \frac{|g_{ij}|/g_{ii}}{1 − |g_{ij}|/g_{ii}} = \frac{sin 2φ}{g_{jj}} · \frac{a\sqrt{g_{jj}/g_{ii}}}{1 − a\sqrt{g_{jj}/g_{ii}}}

≤ \frac{1}{\sqrt{g_{ii}g_{jj}}} · \frac{a}{1 − a} .

In the case (b2), using the relation (3.21), we have

|ω_{ψ}| = \frac{2}{g_{jj}} cos φ cos ψ · (tan φ − tan ψ)
< \frac{2}{\sqrt{g_{ii}g_{jj}}} · 1 · 1 · a < \frac{1}{\sqrt{g_{ii}g_{jj}}} · \frac{2a}{1 − a} .

Now, the obtained estimates yield

max\{ω_{iφ}, ω_{iψ}\} < \frac{1}{g_{ii}} · \frac{a}{1 − a} ,
max\{ω_{jφ}, ω_{jψ}\} < \frac{1}{g_{jj}} · \frac{a}{1 − a} ,  (3.26)
max\{|ω_{φ}|, |ω_{ψ}|\} < \frac{1}{\sqrt{g_{ii}g_{jj}}} · \frac{2a}{1 − a} .

The relation (3.3) together with (3.26) yields

(|ã_{li}|^{2} + |ã_{lj}|^{2}) − (|a_{li}|^{2} + |a_{lj}|^{2})
≤ \frac{a}{1 − a}|a_{li}|^{2} + \frac{a}{1 − a}|a_{lj}|^{2} + \frac{2a}{1 − a}|a_{li}a_{lj}|
= \frac{a}{1 − a}(|a_{li}| + |a_{lj}|)^{2}
≤ \frac{2a}{1 − a}(|a_{li}|^{2} + |a_{lj}|^{2}) , l ≠ i , j .

which imply the assertion of Lemma 3.1 and thus completes the proof.

Note that the relation (3.26) holds for even and odd odd cycles because the inequalities are symmetric in the arguments φ and ψ and therefore invariant to their interchange. The next lemma bounds the growth of the off-norm of scaled matrices after one step.

Lemma 3.2 Let G_{S} and G̃_{S} be as in Lemma 3.1. If ||Ω(G̃_{S})|| > ||Ω(G_{S})||, then

(i) ||Ω(G̃_{S})||^{2} − ||Ω(G_{S})||^{2} ≤ |a_{ij}| · \frac{2||Ω(G_{S})||^{2} − |a_{ij}|}{1 − |a_{ij}|},
(ii) |a_{ij}| ≤ 2||Ω(G_{S})||^{2} .

Proof. Since only the i’th and j’th row and column change, we can use Lemma 3.1 (see also the proof of [21, Lemma 2]) to obtain

||Ã||^{2} − ||A||^{2} = 2 ∑_{l≠i,j^{l=1}}^{n}[(|ã_{il}|^{2} + |ã_{jl}|^{2}) − (|a_{il}|^{2} + |a_{jl}|^{2})] − 2a_{ij}^{2}

≤ \frac{4|a_{ij}|}{1 − |a_{ij}|} ∑_{l≠i,j^{l=1}}^{n}(|a_{il}|^{2} + |a_{jl}|^{2}) − 2a_{ij}^{2}

≤ \frac{2|a_{ij}|}{1 − |a_{ij}|}(||A||^{2} − 2a_{ij}^{2}) − 2a_{ij}^{2}
= \frac{2|a_{ij}|}{1 − |a_{ij}|}(||A||^{2} − a_{ij}^{2} − |a_{ij}|)
≤ \frac{2|a_{ij}|}{1 − |a_{ij}|}(||A||^{2} − |a_{ij}|) ,

which implies the assertions (i) and (ii), because

||Ã||^{2} = 2||Ω(G̃_{S})||^{2}, ||A||^{2} = 2||Ω(G_{S})||^{2}.

We are now able to bound the growth of α_{k} during one cycle of the method.

4 Asymptotic Estimates

Here, we assume that B^{(0)} is α_{0}-scaled diagonally dominant, with α_{0} sufficiently small for obtaining usable estimates of α_{k} for all 1 ≤ k ≤ N.

Lemma 4.1 Let G^{(0)} = G, G^{(1)}, …, G^{(N)} be obtained by applying N Kogbetliantz steps to G and let α_{k}, 0 ≤ k ≤ N, be defined by the relation (2.12). If

α_{0} ≤ \frac{1}{10n}, n ≥ 3,  (4.1)

then

α_{k}^{2} ≤ c_{k}α_{0}^{2}, 0 ≤ k ≤ N,  (4.2)

where

c_{k} = (1 + \frac{0.011}{n^{2}})^{k} < 1.006, 0 ≤ k ≤ N .  (4.3)

Proof. The proof is analogous to the proof of [21, Lemma 3] with a suitable modification of constants.

First, we use (4.2) and the definition (4.3) of c_{k} to prove the inequality in (4.3), that is: c_{k} < 1.006 for all 1 ≤ k ≤ N.

Using the known inequality (1 + x)^{m} < 1/(1 − mx), which holds for all x, m > 0 such that xm < 1, we obtain

c_{k} < c_{N} = (1 + \frac{0.011}{n^{2}})^{N} ≤ \frac{1}{1 − \frac{0.011}{n^{2}} · \frac{n(n−1)}{2}}
< \frac{1}{1 − 0.0055} < 1.005531.  (4.4)

The inequality (4.2) is proved by induction with respect to k. For k = 0 the inequality holds trivially. Suppose that it holds for some 0 ≤ k < N. Then, usung the asymptotic assumption (4.1) and (4.4), we have

α_{k}^{2} ≤ c_{k}α_{0}^{2} ≤ \frac{1.005531}{100n^{2}} ≤ 0.01005531\frac{1}{n^{2}} < 0.001118.  (4.5)

It suffices to prove the induction step only for the case α_{k+1} > α_{k}. By lemma 3.2 (i) we have

α_{k+1}^{2} − α_{k}^{2} ≤ |a_{ij}^{(k)}| · \frac{2α_{k}^{2} − |a_{ij}^{(k)}|}{1 − |a_{ij}^{(k)}|}  (4.6)

The function f(a) = a\frac{2α_{k}^{2}−a}{1−a}, a ∈ [0, 2α_{k}^{2}] attains maximum at a_{∗} = \frac{2α_{k}^{2}}{1+\sqrt{1−2α_{k}^{2}}}

and f(a_{∗}) = \frac{4α_{k}^{4}}{(1+\sqrt{1−2α_{k}^{2}})^{2}} . From the relations (4.6) and (4.5), we have

α_{k+1}^{2} ≤ α_{k}^{2} + f(a_{∗}) < α_{k}^{2} (1 + \frac{4α_{k}^{2}}{(1 + \sqrt{1 − 2 · 0.001118})^{2}} ) .

Using the last relation, the induction hypothesis and the third inequality in (4.5), we obtain

α_{k+1}^{2} ≤ c_{k}α_{0}^{2}(1 + 1.00112 · \frac{0.01005531}{n^{2}}) ≤ c_{k+1}α_{0}^{2}

which completes the induction step and the proof of the lemma.

Let

N_{t} = 1 + 2 + … + (t − 1) = \frac{t(t − 1)}{2}, 2 ≤ t ≤ n .  (4.7)

The next lemma estimates the growth of the affected part of column t after N_{t−1} Kogbetliantz rotations. This result is closely related with the content of the next section.

Lemma 4.2 Let G^{(0)} = G, G^{(1)}, …, G^{(N)} be obtained by applying N Kogbetliantz steps to G under the column-cyclic strategy. Let

a_{t}^{(k)} = [a_{1t}^{(k)}, …, a_{t−1,t}^{(k)}]^{T} , 2 ≤ t ≤ n, 0 ≤ k ≤ N .

If

α_{0} ≤ \frac{1}{10n}

then

||a_{t}^{(N_{t−1})}||^{2} ≤ C_{t}||a_{t}^{(0)}||^{2}

where

C_{t} = [(1 + α)/(1 − α)]^{−(2t−5)} < 1.565

and

α = \sqrt{1.006}α_{0} .  (4.8)

Proof. See the proof of [21, Lemma 9]. Here we use Lemma 3.1, so in the proof of [21, Lemma 9], instead of the term μ = 1/(1 − b) we now have μ = (1 + b)/(1 − b), where

b = max \{\frac{|g_{i(k),j(k)}^{(k)}|}{\sqrt{g_{i(k),i(k)}^{(k)}g_{j(k),j(k)}^{(k)}}} , 0 ≤ k < N_{t−1} \} .

We obtain, in exactly the same way as in the proof of [21, Lemma 9], the relation

||a_{t}^{(N_{t−1})}||^{2} ≤ μ^{2t−5}||a_{t}^{(0)}||^{2} = (\frac{1 + b}{1 − b})^{2t−5} ||a_{t}^{(0)}||^{2} .  (4.9)

Using again the inequality (1 + x)^{m} < 1/(1 − mx), we have

(\frac{1 + b}{1 − b})^{2t−5} ≤ (1 + \frac{2b}{1 − b})^{2(n−1)} ≤ (1 − \frac{2(n − 1)b}{1 − b})^{−2}
= (1 + \frac{2(n − 1)b}{1 + b − 2nb})^{2} ≤ (1 + \frac{2nb}{1 − 2nb})^{2} < 1.565 .

In the last inequality we have used Lemma 4.1 and the asymptotic assumption to estimate nb,

nb ≤ nα ≤ nα_{0}\sqrt{1.006} ≤ \frac{1}{10}\sqrt{1.006} .

5 An Application

Here we sketch how the estimates from earlier sections can be used in proving the quadratic convergence of scaled iterates by the serial Kogbetliantz method for triangular matrices. A complete proof togetether with numerical tests will be published elsewhere.

Asymptotic assumptions

Let the initial upper triangular matrix B ∈C^{n×n} satisfy the following asymptotic assumptions (cf. the assumptions (A1) and (A2) from [21]).

(B1)  α_{0} ≤ \frac{1}{10} min\{\frac{1}{n}, θ\} , n ≥ 3 ,  and

(B2) b_{11} > b_{22} > … > b_{nn} > 0 ,

where α_{0} and θ are defined by the relations (2.12) and (1.6), respectively. It is clear that in the assumptions (B2) the elements b_{tt} can be replaced by g_{tt} for every 1 ≤ t ≤ n. Note that α_{0} is also defined by G^{(0)}. The assumptions (B1) and (B2) are sufficient conditions for proving the quadratic convergence of scaled iterates per cycle. The proof uses the technique from [21]. We present here only the main facts without proof.

Auxilliary Results

First, we find fixed intervals that contain the diagonal elements during the whole process and then we estimate the rotation angles. We recall that i = i(k) and j = j(k) stand for pivot indices and k nubers the steps.

Lemma 5.1 Let the sequence G^{(k)} = (g_{lm}^{(k)}), k ≥ 0, be obtained by the associated Kogbetliantz process. If G^{(0)} satisfies the asymptotic assumptions (B1) and (B2), then the following relations hold for 0 ≤ k ≤ N,

(i) (1 − \frac{θ}{49})σ_{t} < g_{tt}^{(k)} < (1 + \frac{θ}{49})σ_{t}, 1 ≤ t ≤ n ,
(ii) rg(g_{tt}^{(k)}, g_{qq}^{(k)}) > \frac{24}{25}θ, t ≠ q ,

(iii) | tan 2ψ^{(k)}| ≤ \frac{2|g_{ij}^{(k)}|}{g_{ii}^{(k)} − g_{jj}^{(k)}} ,

(iv) max\{| tan ψ^{(k)}|, | tan φ^{(k)}|\} ≤ \frac{|g_{ij}^{(k)}|}{g_{ii}^{(k)} − g_{jj}^{(k)}} ≤ \frac{25|a_{ij}^{(k)}|}{48θ} ,

.

Here rg(·, ·) and a_{ij}^{(k)} are defined by the relations (1.3) and (2.11), respectively.

Next, we estimate elements of column t, when the annihilations in this column take place.

Lemma 5.2 Let B satisfy the assumptions (B1) and (B2). Let the sequence B^{(k)}, k ≥ 0 be generated by the column-cyclic Kogbetliantz method. Let t ∈ {2, …, n} and ν = N_{t−1}. Then

(i) a_{kt}^{(ν+k)} = 0, k = 1, …, t − 1,
(ii) |a_{lt}^{(ν+k)}| ≤ \sqrt{1.006}(|a_{lt}^{(ν)}| + \frac{25}{24θ} ∑_{r=1}^{k} |a_{lr}^{(ν)}a_{rt}^{(ν+r−1)}|),
k = 1, …, l − 1, 2 ≤ l ≤ t − 1,
(iii) |a_{lt}^{(ν+k)}| ≤ \frac{1.045}{θ} ∑_{r=l+1}^{k} |a_{rt}^{(ν+r−1)}| · (|a_{lr}^{(ν)}| + \frac{0.27}{θ}
·|a_{lt}^{(ν+l−1)}a_{rt}^{(ν+l−1)}|), k = l + 1, …, t − 2, 1 ≤ l ≤ t − 2,
(iv) |a_{lm}^{(ν+k)}| ≤ |a_{lm}^{(ν)}| + \frac{25}{48θ}(|a_{lt}^{(ν+l−1)}a_{mt}^{(ν+l−1)}| + |a_{lt}^{(ν+m−1)}a_{mt}^{(ν+m−1)}|),
k = max{l, m}, …, t − 1, 1 ≤ l ≠ m ≤ t − 2.

Using Lemma 5.2 we can estimate the elements of the t’th column prior to and after heir annihilations. We use the following notation

A_{t}^{(k)}: A_{t}^{(k)} = E_{t}^{T} A^{(k)}E_{t} where E_{t} = [e_{1}, …, e_{t}], 2 ≤ t ≤ n. A_{t}^{(k)} is the leading principal submatrix of A^{(k)} of order t;

a_{t}^{(k)}: a_{t}^{(k)} = [a_{1t}^{(k)}, …, a_{t−1,t}^{(k)}]^{T} is the upper-triangular part of column t of A^{(k)} (that is, the upper-triangular part of the last column of A_{t}^{(k)}).

Lemma 5.3 Let B satisfy the assumptions of Theorem 5.4. If ν = N_{t−1}, then

(i) ∑_{l=1}^{t−1}(a_{lt}^{(ν+p_{l})})^{2} ≤ ρ_{t}^{2}∥a_{t}^{(ν)}∥^{2},

provided that 0 ≤ p_{l} ≤ l − 1 holds for 1 ≤ l ≤ t − 1;

(ii) ∑_{l=1}^{t−1}(a_{lt}^{(ν+p_{l})})^{2} ≤ \frac{0.55}{θ^{2}}ρ_{t}^{2}∥a_{t}^{(ν)}∥^{2} (∥A_{t−1}^{(ν)})∥_{F} + \frac{0.39}{θ}ρ_{t}^{2}∥a_{t}^{(ν)})∥^{2})^{2},

provided that l ≤ p_{l} ≤ t − 1 holds for 1 ≤ l ≤ t − 1.

Here

ρ_{t} = \frac{\sqrt{1.006}}{1 − \frac{0.74}{θ} ∥A_{t−1}^{(ν)}∥_{F}}  (5.1)

Using Lemma 5.1, Lemma 5.2 and Lemma 5.3 we can derive quadratic convergence bound for scaled matrices.

The main Theorem

We state here the main quadratic convergence result.

Theorem 5.4 Let B ∈C^{n×n} satisfy the asymptotic assumptions (B1) and (B2). Let the sequence B^{(0)} = B, B^{(1)}, …, B^{(N)} be generated by the columncyclic Kogbetliantz method. Then

\frac{α_{N}}{θ} ≤ (\frac{11}{10} · \frac{α_{0}}{θ} )^{2}

where α_{0}, α_{N} and θ are defined by the relations (2.12) and (1.6) respectively.

We can see that the convergence of scaled iterates in Kogbetliantz method for triangular matrices is quadratic per cycle as well as in the symmetric Jacobi method. Asymptotic assumptions that guarantee such behaviour are also of the same type: the off-norm of scaled initial matrix is enough small and the diagonal elements are in nonincreasing block-wise order. Note that this analogy has been used in the proof of classic quadratic convergence results (see [3, 12, 13]).

References

[1] Barlow J., Demmel J.W. (1990) Computing Accurate Eigensystems of Scaled Diagonally Dominant Matrices , SIAM J.Num.Anal. 27, 762-791.

[2] Brent R. P., Luk F. T. (1985) The Solution of Singular-value and Symmetric Eigenvalue Problems on Multiprocessor Arrays, SIAM J. Sci. Stat. 6, 69-84.

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

[4] Charlier J.P., Vanbegin M., Van Dooren P. (1988) On Efficient Implementation of Kogbetliantz’s Algorithm for Computing the Singular Value Decomposition, Numer Math. 52, 279-300.

[5] De Rijk P.P.M. (1989) A One-sided Jacobi Algorithm for Computing the Singular Value Decomposition on a Vector Computer, SIAM J. Sci. Stat. Comp. 10, 359-371.

[6] Demmel J.W., Veselić K. (1992) Jacobi’s Method is more Accurate then QR, SIAM J. Matrix Anal. Appl. 13, 1204-1245.

[7] Drmač Z., (1999) A Posteriori Computation of the Singular Vectors in a preconditioned Jacobi’s SVD Algorithm, To appear in IMA J. Num. Anal.

[8] Fernando K. V. (1989) Linear Convergence of the Row–cyclic Jacobi and Kogbetliantz Methods, Num. Math. 56, 71–91.

[9] Forsythe G. E., Henrici P. (1960) The cyclic Jacobi method for computing the principal values of a complex matrix, Trans. Amer. Math. Soc. 94, 1– 23.

[10] Hansen E.R. (1963) On Cyclic Jacobi Methods, SIAM J. Appl.Math. 11, 449-459. SIAM J. Matrix Anal. Appl. Vol. 18. No. 4, 1000–1012.

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

[12] Hari V. (1989) On the Quadratic Convergence Bounds of the Serial Singular Value Decomposition Jacobi Methods for Triangular Matrices, SIAM J. Sci. Stat. Comput. 10, 1076-1096.

[13] Hari V. (1991) On Sharp Quadratic Convergence Bounds for the Serial Jacobi Methods, Numer.Math. 60, 375-406.

[14] Hari V, Veselić K. (1987) On Jacobi methods for singular value decompositions, SIAM J. Sci. Stat. Vol. 8, No. 5, 741–754.

[15] Hari V., Drmač Z. (1997) On Scaled Almost Diagonal Hermitian Matrix Pairs, SIAM J. MAA Vol. 18, No. 4, 1000–1012.

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

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

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

[19] Mascarenhas W.F. (1993) On the Convergence of the Jacobi Method for Arbitrary Orderings, University of Minnesota, Minneapolis.

[20] Matejaš J. (1996) Quadratic Convergence of Scaled Iterates by Diagonalization Methods, University of Zagreb, Ph.D. Thesis (Croatian language).

[21] Matejaš J. (2000) Convergence of Scaled Iterates by Jacobi Method, Numer. Math. 87, 171–199.

[22] Matejaš J., Hari V. (1998) Scaled Almost Diagonal Matrices with Multiple Singular Values, ZAMM 78, 2, 121–131.

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

[24] Rhee N., Hari V. (1993) On the Global and Cubic Convergence of a Quasi-cyclic Jacobi Method, Numer.Math. 66, 97-122.

[25] Voevodin V.V. (1966) Cislennye metody linejnoj algebry, Nauka, Moscow (in Russian).

[26] Wilkinson J.H. (1962) Note on the Quadratic Convergence of the Cyclic Jacobi Process, Num. Math. 4, 296-300.