On Quadratic Convergence Bounds for the Serial Jacobi Methods for J–symmetric matrices

Zlatko Drmač and Vjeran Hari, Department of Mathematics, University of Zagreb, P.O.Box 187, Yu-41000 Zagreb, Yugoslavia

Summary. This paper deals with quadratic convergence estimates for the serial J–symmetric Jacobi method recently proposed by Veselić. The method is characterized by the use of orthogonal and hyperbolic plane rotations. Using a new technique recently introduced by Hari we prove sharp quadratic convergence bounds in the general case of multiple eigenvalues.

Subject Classifications: AMS (MOS): 65F15; CR: 5.14

Introduction. Recent advances in parallel computing as well as the new results in error analysis [2] made of matrix diagonalization methods attractive area of research. In this paper we consider asymptotic quadratic convergence of a recently proposed diagonalization method for the generalized eigenvalue problem Ax = λJx. Here A ∈ R^{n×n} is symmetric matrix, J = I_{m} ⊕ (−I_{n−m}) and for some real μ the linear combination A − μJ is positive definite. In another words the matrix pair (A, J) is positive definite. In the case of a negative definite pair (A, J) we can work with (−A, −J) which is positive definite. The method is due to Veselić [13] and it has gathered almost all nice properties of the standard symmetric Jacobi method. It has simple angle formulas and many other nice features as shown in [13]. Its nontrivial part makes use of nonorthogonal transformations which involve hyperbolic sine and cosine. The method generates the sequence of equivalent pairs ((A^{(k)}, J), k ≥ 1) by the rule

A^{(k+1)} = C_{k}^{τ}A^{(k)}C_{k}, k ≥ 1

where A^{(1)} = A. Here C_{k}, k ≥ 1 are special plane matrices from the multiplicative group of J–orthogonal matrices. Each C_{k} is defined by a pair of indices (r(k), s(k)) called pivot pair, where r(k) < s(k), and by a two by two matrix Ĉ_{k},

Ĉ_{k} = \{ \begin{matrix}[ \begin{matrix}cosh ϑ_{k} & sinh ϑ_{k} \\ sinh ϑ_{k} & cosh ϑ_{k} \end{matrix} ] , & 1 ≤ r(k) ≤ m < s(k) ≤ n \\ [ \begin{matrix}cos ϑ_{k} & − sin ϑ_{k} \\ sin ϑ_{k} & cos ϑ_{k} \end{matrix} ] , & otherwise, \end{matrix}

which we call pivot submatrix of C_{k}. The matrix C_{k} differ from the identity matrix only in the four elements on the intersections of rows and columns r(k) and s(k), and these four elements make Ĉ_{k}. Let

A^{(k)} = [ \begin{matrix}A_{1}^{(k)} & A_{2}^{(k)} \\ A_{2}^{(k)}^{τ} & A_{3}^{(k)} \end{matrix} ] , k ≥ 1

The parameter ϑ_{k} is chosen to annihilate the pivot element a_{r(k)s(k)}^{(k+1)}. From the definition of Ĉ_{k} we see that an ordinary rotation is used when the pivot element lies within the diagonal blocks A_{1}^{(k)} and A_{3}^{(k)}. However, when a_{r(k)s(k)}^{(k)} is from A_{2}^{(k)} hyperbolic transformation should be used. Here Veselić’s method differs from the usual Jacobi method and this difference originates from the fundamental symmetry J. Namely, the problem Ax = λJx is equivalent to JAx = λx and the matrices JA^{(k)} are not symmetric but J–symmetric. One nice feature of the method are simple angle formulas

tan 2ϑ_{k} = \frac{2 · a_{r(k)s(k)}^{(k)}}{a_{r(k)r(k)}^{(k)} − a_{s(k)s(k)}^{(k)}} , −\frac{π}{4} < ϑ_{k} ≤ \frac{π}{4} ,  (0.1)

tanh 2ϑ_{k} = \frac{−2 · a_{r(k)s(k)}^{(k)}}{a_{r(k)r(k)}^{(k)} + a_{s(k)s(k)}^{(k)}} .  (0.2)

This method proved to be well defined for definite pairs (A, J) (see [13]). Because of its resemblance with the standard Jacobi method we shall call it J–symmetric Jacobi method. We can let it operate on JA or on the pair (A, J). The later means that it operates on the symmetric matrix A. For technical reasons this will be our choice. The first quadratic convergence considerations of Jacobi methods go back to Schönhage [11], Wilkinson [14] and Van Kempen [7]. Later Ruhe [10], Hari [4], Paige and Van Dooren [8], Charlier and Van Dooren [1], Hari [6], Slapničar and Hari [12] etc. studied quadratic convergence of various Jacobi– type processes. Our work uses the new quadratic convergence techique from [6]. It enables us to obtain very sharp quadratic convergence bounds in the general case of multiple eigenvalues which quite correspond to the symmetric case studied in [14], [7] and [6]. The content of this paper is a part of a M. S. Thesis [3] made under the supervision of Professor V. Hari. The authors would like to thank Professor K. Veselić for suggesting the problem and reading this paper as well as for helpful discussions and useful comments.

1 Almost Diagonal J–symmetric Matrices

In order to study the asymptotic convergence of the J–symmetric Jacobi method we need information on the magnitude of matrix elements when A is almost diagonal and the pair (A, J) has multiple eigenvalues. If A is almost diagonal then the diagonal elements of JA approximate the eigenvalues of JA which are actually the eigenvalues of (A, J). As is known from the convergence theory of Jacobi methods for the pair (A, I), with identity matrix I, one of the sufficient conditions for the quadratic convergence of the serial Jacobi processes is that the diagonal elements of A which approximate the same multiple eigenvalue occupy successive positions along the diagonal. A similar condition is needed when I is replaced by J. We first assume the following ordering of the diagonal elements of A = [a_{ij}]:

a_{11} ≥ ⋯ ≥ a_{mm} > −a_{m+1,m+1} ≥ ⋯ ≥ −a_{nn}.  (1.1)

To get such arrangement we use the positive definiteness of the pair (A, J) which implies that

a_{rr} > μ > −a_{ss}, 1 ≤ r ≤ m < s ≤ n,

holds for some real μ. Therefore we get (1.1) by ordering the first m and the last n − m elements of diag(A) = diag(a_{11}, …, a_{nn}). If P is a permutation matrix which makes diag(A) ordered as in (1.1), then P is J-orthogonal, i.e. P^{τ}JP = J and after the substitution (A, J) ← (P^{τ}AP, J) the relation (1.1) will be fulfiled. Setting Ã = JA = (ã_{ij}) we can read the relation (1.1) as

ã_{11} ≥ ⋯ ≥ ã_{mm} > ã_{m+1,m+1} ≥ ⋯ ≥ ã_{nn}

and the application of permutation matrix P means the similarity transformation on Ã via J-orthogonal matrix. Thus, the J-symmetry is preserved. Let the eigenvalues of (A, J) that is of Ã be

λ_{1} = ⋯ = λ_{s_{1}} > λ_{s_{1}+1} = ⋯ = λ_{s_{2}} > ⋯ > λ_{s_{p−1}+1} = ⋯ = λ_{s_{p}}, (1.2)

and let w ∈ {1, …, p − 1} be such that s_{w} = m. The existence of w follows from the existence of a gap in the spectrum of (A, J). This gap which separates the ”positive” from the ”negative” part of the spectrum is implied by the definiteness of the pair (A, J) (see [13]). Note that the case p = 1 is impossible, so p ≥ 2. Furthermore, we define:

δ_{0} = \frac{1}{3} · (λ_{s_{w}} − λ_{s_{w}+1}),  (1.3)
δ_{i} = \frac{1}{3} · min_{j≠i^{1≤j≤p}} |λ_{s_{i}} − λ_{s_{j}}|, 1 ≤ i ≤ p,  (1.4)
δ = min_{1≤i≤p} δ_{i},  (1.5)
n_{i} = s_{i} − s_{i−1}, 1 ≤ i ≤ p (s_{0} =^{def} 0).  (1.6)

Thus, 3·δ is the minimal distance between two distinct eigenvalues of (A, J), 3 · δ_{0} is the gap between first m and last n − m eigenvalues, 3 · δ_{i} is the distance of λ_{s_{i}} to the rest of the spectrum and n_{i} is the multiplicity of λ_{s_{i}}. To measure the departure from the diagonal form we use the function

S(X) = ∥X − diag (X)∥_{F} , X ∈ R^{n×n}.

Here ∥ · ∥_{F} is the Euclidean (Shur or Frobenius) matrix norm. Note that S(Ã) = S(A). The function S(A) is sometimes called the departure from the diagonal form or the ”off-norm” of A. For sufficiently small S(A) we shall estimate the off-norm of the diagonal blocks in the partition

A = [ \begin{matrix}A_{11} & … & A_{1w} & … & A_{1p} \\ ⋮ & ... & ⋮ & & ⋮ \\ A_{w1} & … & A_{ww} & … & A_{wp} \\ ⋮ & & ⋮ & ... & ⋮ \\ A_{p1} & … & A_{pw} & … & A_{pp} \end{matrix} ] \begin{matrix}dim (A_{ii}) = n_{i} i = 1, …, p \\ ∑_{i=1}^{w} n_{i} = m, \\ ∑_{i=1}^{p} n_{i} = n. \end{matrix} (1.7)

We also assume the same partition of Ã.

Lemma 1.1 Let the assumptions (1.1) and (1.2) hold. If

S(A) < \frac{δ}{η}  (1.8)

with η ≥ 1, then for all i ∈ {1, …, p}

S(A_{ii}) ≤ ∥σ_{i}A_{ii} − λ_{s_{i}}I_{n_{i}}∥_{F}
≤ \frac{η}{3 · η − 2} · \frac{1}{δ_{i}} · ∑_{j≠i^{j=1}}^{p} ∥A_{ij}∥_{F}^{2}  (1.9)

≤ \frac{η}{6 · η − 4} · \frac{S^{2}(A)}{δ_{i}},

where

σ_{i} = \{ \begin{matrix}1, & i ∈ \{1, …, w\} \\ −1, & i ∈ \{w + 1, …, p\}. \end{matrix}

Proof The proof is quite similar to the one of Lemma2.1 from [5] (see also [6]), but for the sake of completeness, we shall present it in details. Let i ∈ {1, …, p} and let B_{i} = A − λ_{s_{i}}J. We can find a permutation matrix P_{i} such that

A_{i} = P_{i}^{τ}B_{i}P_{i} = \{ \begin{matrix}[ \begin{matrix}A_{ii} − λ_{s_{i}}I_{n_{i}} & G_{i} \\ G_{i}^{τ} & K_{i} \end{matrix} ] , & i ≤ w \\ [ \begin{matrix}K_{i} & G_{i}^{τ} \\ G_{i} & A_{ii} + λ_{s_{i}}I_{n_{i}} \end{matrix} ] , & i > w \end{matrix}

holds. Here

G_{i} = \{ \begin{matrix}[A_{12}, …, A_{1p}] , & i = 1 \\ [A_{i1}, …, A_{i,i−1}, A_{i,i+1}, …, A_{ip}] , & 2 ≤ i ≤ p − 1, p > 2 \\ [A_{p1}, …, A_{p,p−1}] , & i = p \end{matrix}

and P_{i} is J-orthogonal matrix with the following structure:

P_{i} = \{ \begin{matrix}I_{n}, & i ∈ \{1, p\} \\ [e_{s_{i−1}+1}, .., e_{s_{i}}, e_{1}, .., e_{s_{i−1}}, e_{s_{i}+1}, .., e_{s_{p}}] , & 2 ≤ i ≤ w, w > 1 \\ [e_{1}, .., e_{s_{i−1}}, e_{s_{i}+1}, .., e_{s_{p}}, e_{s_{i−1}+1}, .., e_{s_{i}}] , & w < i ≤ p − 1, p > 2. \end{matrix}

Let β_{j}^{(i)}, 1 ≤ j ≤ n be the eigenvalues of B_{i}. Since A_{i} is symmetric and similar to B_{i}, there exists an ordering β_{1}^{(i)}, …, β_{n}^{(i)} such that for all 1 ≤ j ≤ n holds

|β_{j}^{(i)} − (a_{jj} − τ_{j} · λ_{s_{i}})| ≤ ∥B_{i} − diag (B_{i})∥_{2} ≤ ∥B_{i} − diag (B_{i})∥_{F}
= S(B_{i}) = S(A) < \frac{δ}{η} .  (1.10)

Here

τ_{j} = \{ \begin{matrix}1, & 1 ≤ j ≤ m \\ −1, & m < j ≤ n. \end{matrix}  (1.11)

Since rank of B_{i} is n − n_{i}, the relation (1.10) implies that for at least n_{i} values of the index j holds

|a_{jj} − τ_{j} · λ_{s_{i}}| = |τ_{j} · a_{jj} − λ_{s_{i}}| < \frac{δ}{η} .

Let S_{i} = \{j ∈ \{1, …, n\}; |τ_{j} · a_{jj} − λ_{s_{i}}| < \frac{δ}{η}\}, 1 ≤ i ≤ p. Note that i ≠ k implies |λ_{s_{i}} − λ_{s_{k}}| ≥ 3 · max\{δ_{i}, δ_{k}\}. So, if i ≠ k and |x − λ_{s_{i}}| < \frac{δ_{i}}{η} we have |x − λ_{s_{k}}| ≥ 2 · max\{\frac{δ_{i}}{η} , \frac{δ_{k}}{η} \}, which means S_{i} ⋂ S_{k} = ∅. Since each S_{k} contains at least n_{k} elements and ∑_{k=1}^{p} n_{k} = n, we conclude that the cardinality |S_{i}| of S_{i} is exactly n_{i}. Now the conditions (1.1) and (1.2) imply that S_{k} = {s_{k−1} + 1, …, s_{k}}, 1 ≤ k ≤ p. Next we show that for each i, K_{i} is invertibile and find an upper bound for ∥K_{i}^{−1}∥_{2}. Here ∥ · ∥_{2} stands for the spectral (operator) norm. Let us denote the eigenvalues of K_{i} by κ_{j}^{(i)}, j ∈ S \ S_{i}, 1 ≤ i ≤ p, where S = ⋃_{k=1}^{p} S_{k}. For j ∈ S_{k}, k ≠ i the perturbation theorem for symmetric matrices yields

|κ_{j}^{(i)} − (a_{jj} − τ_{j} · λ_{s_{i}})| ≤ ∥K_{i} − diag (K_{i})∥_{2} ≤ ∥K_{i} − diag (K_{i})∥_{F}
≤ S(K_{i}) ≤ S(A) < \frac{δ}{η} .

Hence

|κ_{j}^{(i)}| = |κ_{j}^{(i)} − (a_{jj} − τ_{j} · λ_{s_{i}}) + (a_{jj} − τ_{j} · λ_{s_{i}})|
> |τ_{j} · a_{jj} − λ_{s_{i}}| − \frac{δ}{η}
≥ |λ_{s_{k}} − λ_{s_{i}}| − |τ_{j} · a_{jj} − λ_{s_{k}}| − \frac{δ}{η}
≥ 3 · δ_{i} − 2 · \frac{δ}{η}
≥ \frac{3 · η − 2}{η} · δ_{i}, j ∈ S_{k}, k ≠ i,

and consequently

∥K_{i}^{−1}∥_{2} = \frac{1}{minσ(K_{i}) |κ_{j}^{(i)}|} < \frac{η}{3 · η − 2} · \frac{1}{δ_{i}} .

Here σ(K_{i}) denotes the spectrum of K_{i}. Now, let us compute F_{i}^{τ}A_{i}F_{i} with

F_{i}^{τ} = \{ \begin{matrix}[ \begin{matrix}I & −G_{i}K_{i}^{−1} \\ Θ & I \end{matrix} ] , & 1 ≤ i ≤ w \\ [ \begin{matrix}I & Θ \\ −G_{i}K_{i}^{−1} & I \end{matrix} ] , & w < i ≤ p, \end{matrix}

where Θ stands for the null matrix. If 1 ≤ i ≤ w (the case w < i ≤ p is treated similarly) we have

F_{i}^{τ}A_{i}F_{i} = [ \begin{matrix}A_{ii} − λ_{s_{i}}I_{n_{i}} − G_{i}K_{i}^{−1}G_{i}^{τ} & Θ \\ Θ & K_{i} \end{matrix} ] .

Since K_{i} is invertible, the rank argument implies that

A_{ii} − λ_{s_{i}}I_{n_{i}} = G_{i}K_{i}^{−1}G_{i}^{τ}.  (1.12)

Hence

∥A_{ii} − λ_{s_{i}}I_{n_{i}}∥_{F} ≤ ∥G_{i}K_{i}^{−1}∥_{2} · ∥G_{i}^{τ}∥_{F}
≤ ∥G_{i}∥_{F} · ∥G_{i}^{τ}∥_{F} · ∥K_{i}^{−1}∥_{2}
< \frac{η}{3 · η − 2} · \frac{1}{δ_{i}} · ∥G_{i}∥_{F}^{2} , 1 ≤ i ≤ p,

or equivalently

∥A_{ii} − λ_{s_{i}}I_{n_{i}}∥_{F} < \frac{η}{3 · η − 2} · \frac{1}{δ_{i}} · ∑_{j≠i^{j=1}}^{p} ∥A_{ij}∥_{F}^{2}

≤ \frac{η}{6 · η − 4} · \frac{S^{2}(A)}{δ}, 1 ≤ i ≤ p.

The relation (1.9) shows that under the assumptions (1.1), (1.2) and (1.8) diagonal blocks from the partition (1.7) of JA can be used as approximations of σ(JA) and gives an error estimate. Assumptions (1.1) and (1.2) seem to be somewhat restrictive. We can make them more general by assuming the enumeration of eigenvalues

λ_{1} = ⋯ = λ_{s_{1}}, λ_{s_{1}+1} = ⋯ = λ_{s_{2}}, ⋯, λ_{s_{p−1}+1} = ⋯ = λ_{s_{p}}  (1.13)

where λ_{s_{1}}, …, λ_{s_{p}} is not necessairly a monotonic sequence, and by assuming the proper affiliation of the diagonal elements. The latter means

|σ_{i} · a_{jj} − λ_{s_{i}}| < δ, s_{i−1} + 1 ≤ j ≤ s_{i}, 1 ≤ i ≤ p.  (1.14)

Here we have used Lemma 1.1. In the relation (1.13) we also require the existence of gap between the first s_{w} = m and the rest n − m eigenvalues, counting multiplicities. Note that the estimate (1.9) quite corresponds to the one for the pair (A, I) (cf. [6]). In the relation (1.9) the function S^{2}(A) can be replaced by τ^{2}(A), where

τ^{2}(A) = ∑_{i=1}^{p} ∑_{j≠i^{j=1}}^{p} ∥A_{ij}∥_{F}^{2} .

2 The Growth of S(A^{(k)})

In Jacobi algorithm we use J–orthogonal transformations hence the sequence S(A^{(k)}), k ≥ 1 is not necessairly decreasing. Here we examine carefully the influence of hyperbolic transformations upon the growth of S(A^{(k)}) when S(A^{(k)}) is sufficiently small. We assume that A = (a_{ij}) is a symmetric matrix such that the pair (A, J) is positive definite. First we estimate the hyperbolic parameter (angle) ϑ.

Lemma 2.1 Let

tanh 2ϑ = −\frac{2 · a_{rs}}{a_{rr} + a_{ss}} , 1 ≤ r ≤ m < s ≤ n.  (2.1)

If for some η ≥ 1

S(A) < \frac{δ_{0}}{η}  (2.2)

then

| tanh ϑ| ≤ \frac{1}{3} · \frac{|a_{rs}|}{δ_{0}} ≤ \frac{\sqrt{2}}{6 · η} .  (2.3)

Proof Let t = tanh ϑ, ξ = tanh 2ϑ. Then the well known relations ξ = \frac{2·t}{1+t^{2}} and |t| ≤ |ξ| < 1 give t = \frac{ξ}{1+\sqrt{1−ξ^{2}}} . So the relation (2.1) and (2.2)

imply

t = \frac{−2 · a_{rs}}{a_{rr} + a_{ss} + \sqrt{(a_{rr} + a_{ss})^{2} − 4 · a_{rs}^{2}}}

and

|t| ≤ \frac{2 · |a_{rs}|}{6 · δ_{0}} = \frac{|a_{rs}|}{3 · δ_{0}} ≤ \frac{1}{3 · δ_{0}} · \frac{S(A)}{\sqrt{2}} < \frac{\sqrt{2}}{6} · \frac{1}{\sqrt{η}} .

In the last relation we have used (see [13])

\sqrt{(a_{rr} + a_{ss})^{2} − 4 · a_{rs}^{2}} ≥ 3 · δ_{0}, 1 ≤ r ≤ m < s ≤ n.  (2.4)

and the inequality |a_{rs}| ≤ S(A)/\sqrt{2}.

Lemma 2.2 Let Ĉ = [ \begin{matrix}cosh ϑ & sinh ϑ \\ sinh ϑ & cosh ϑ \end{matrix} ]. Then

∥Ĉ∥_{2} = cosh ϑ + | sinh ϑ| = \frac{1 + | tanh ϑ|}{\sqrt{1 − tanh^{2} ϑ}}.  (2.5)

Proof Since

[ −\frac{\sqrt{2}}{2} \frac{\sqrt{2}}{2}^{\frac{\sqrt{2}}{2}  \frac{\sqrt{2}}{2}} ] [ \begin{matrix}cosh ϑ & sinh ϑ \\ sinh ϑ & cosh ϑ \end{matrix} ] [ \frac{\sqrt{2}}{2} −\frac{\sqrt{2}}{2}_{\frac{\sqrt{2}}{2}  \frac{\sqrt{2}}{2}} ] =
[ \begin{matrix}cosh ϑ + sinh ϑ & 0 \\ 0 & cosh ϑ − sinh ϑ \end{matrix} ] ,

for the spectrum of Ĉ holds σ(Ĉ) = {cosh ϑ + sinh ϑ, cosh ϑ − sinh ϑ}.

In the ensuing Lemma we estimate the change of S(A) after a hyperbolic congruence transformation.

Lemma 2.3 Let A′ = C^{τ}AC where C is a hyperbolic rotation which annihilates a_{rs}. Then

S^{2}(A′) ≤ ∥C∥_{2}^{2} · (S^{2}(A) − 2 · a_{rs}^{2}).  (2.6)

Proof Let

a_{r} = (a_{1r}, .., a_{r−1,r}, .., a_{r+1,r}, .., a_{s−1,r}, a_{s+1,r}, a_{nr})^{τ},
a_{s} = (a_{1s}, .., a_{r−1,s}, .., a_{r+1,s}, .., a_{s−1,s}, a_{s+1,s}, a_{ns})^{τ}.  (2.7)

The vectors a_{r}, a_{s} (a_{r}^{τ}, a_{s}^{τ}) are parts of the columns (rows) of A. Let a′_{r}, a′_{s} be defined in the same way, but from the elements of A′. Since

[ a′_{r}, a′_{s} ] = [ a_{r}, a_{s} ] Ĉ

the known norm–inequality yields

∥[ a′_{r}, a′_{s} ]∥_{F}^{2} ≤ ∥[ a_{r}, a_{s} ]∥_{F}^{2} · ∥Ĉ∥_{2}^{2}.

Hence,

S^{2}(A′) = S^{2}(A) − 2 · ∥a_{r}∥^{2} − 2 · ∥a_{s}∥^{2} − 2 · a_{rs}^{2} +
+ 2 · ∥a′_{r}∥^{2} + 2 · ∥a′_{s}∥^{2}
≤ S^{2}(A) − 2 · a_{rs}^{2} + (∥Ĉ∥_{2}^{2} − 1) · (S^{2}(A) − 2 · a_{rs}^{2})
= (S^{2}(A) − 2 · a_{rs}^{2}) · ∥Ĉ∥_{2}^{2}.

Finally, we note that ∥Ĉ∥_{2} = ∥C∥_{2}.

In general, (nonorthogonal) hyperbolic congruence transformation can increase the off–norm of the current matrix. In that case we have

Lemma 2.4 Let A′ = C^{τ}AC where C is a hyperbolic rotation which annihilates a_{rs}. If the relations (2.2) and

Δ = S^{2}(A′) − S^{2}(A) > 0

hold, then

sign a_{rs} = −sign (a_{r}, a_{s}),  (2.8)
|a_{rs}| < \frac{4}{3} · \frac{18 · η^{2} − 1}{18 · η^{2} − 3} · \frac{|(a_{r}, a_{s})|}{δ_{0}},  (2.9)
Δ < \frac{8}{3} · |a_{rs}| · \frac{|(a_{r}, a_{s})|}{δ_{0}},  (2.10)

where a_{r} and a_{s} are defined by the relation (2.7).

Proof First, we determine Δ. For the vectors a′_{r}, a′_{s} defined by the elements of A′, we have

a′_{r} = cosh ϑ · a_{r} + sinh ϑ · a_{s}
a′_{s} = cosh ϑ · a_{s} + sinh ϑ · a_{r}.

Thus

∥a′_{r}∥^{2} = cosh^{2} ϑ · ∥a_{r}∥^{2} + sinh^{2} ϑ · ∥a_{s}∥^{2} + sinh 2ϑ · (a_{r}, a_{s})
∥a′_{s}∥^{2} = cosh^{2} ϑ · ∥a_{s}∥^{2} + sinh^{2} ϑ · ∥a_{r}∥^{2} + sinh 2ϑ · (a_{r}, a_{s})

and

Δ = 2 · (∥a′_{r}∥^{2} − ∥a_{r}∥^{2} + ∥a′_{s}∥^{2} − ∥a_{s}∥ − a_{rs}^{2})
= 2 · [2 · sinh^{2} ϑ · (∥a_{r}∥^{2} + ∥a_{s}∥^{2}) + 2 · sinh 2ϑ · (a_{r}, a_{s}) − a_{rs}^{2}].

Now Δ > 0 implies

a_{rs}^{2} < 2 · sinh^{2} ϑ · (∥a_{r}∥^{2} + ∥a_{s}∥^{2}) + 2 · sinh 2ϑ · (a_{r}, a_{s}).  (2.11)

Using Lemma 1.1 we have

sinh^{2} ϑ = \frac{tanh^{2} ϑ}{1 − tanh^{2} ϑ} ≤ \frac{a_{rs}^{2}}{9 · δ_{0}^{2} − a_{rs}^{2}} < \frac{a_{rs}^{2}}{9 · δ_{0}^{2} − \frac{δ_{0}^{2}}{2·η^{2}}} = \frac{a_{rs}^{2}}{δ_{0}^{2}} · \frac{2 · η^{2}}{18 · η^{2} − 1},

2 · sinh^{2} ϑ · (∥a_{r}∥^{2} + ∥a_{s}∥^{2}) ≤ sinh^{2} ϑ · S^{2}(A) < a_{rs}^{2} · \frac{2}{18 · η^{2} − 1}

and

− sinh 2ϑ = \frac{2 · a_{rs}}{\sqrt{(a_{rr} + a_{ss})^{2} − 4 · a_{rs}^{2}}} = \frac{a_{rs}}{α_{rs}} ,

where α_{rs} = 0.5 · \sqrt{(a_{rr} + a_{ss})^{2} − 4 · a_{rs}^{2}} ≥ 1.5 · δ_{0}. Here we have used the inequality (2.4). So, we have

a_{rs}^{2} < \frac{2}{18 · η − 1} · a_{rs}^{2} − 2 · \frac{a_{rs}}{α_{rs}} · (a_{r}, a_{s})

or equivalently

(1 − \frac{2}{18 · η^{2} − 1}) · a_{rs}^{2} < −2 · \frac{a_{rs}}{α_{rs}} · (a_{r}, a_{s}).

This relation immediately implies (2.8), so the right–hand side above is simply 2 · |a_{rs}| · |(a_{r}, a_{s})|/α_{rs} and after dividing by |a_{rs}| we have

|a_{rs}| < \frac{4}{3} · \frac{18 · η^{2} − 1}{18 · η^{2} − 3} · \frac{|(a_{r}, a_{s})|}{δ_{0}}.

Moreover, we have

Δ < \frac{4}{18 · η^{2} − 1} · a_{rs}^{2} + 2 · [\frac{−2 · a_{rs}}{α_{rs}} · (a_{r}, a_{s})] − 2 · a_{rs}^{2}
≤ \frac{8}{3} · |a_{rs}| · \frac{|(a_{r}, a_{s})|}{δ_{0}}.

Lemma 2.4 shows that increase of S(A^{(k)}) indicates an ε^{2}–small pivot element, where ε = S(A^{(k)}). This information can be used to obtain sharper quadratic convergence bounds. In the following lemmas we shall often use the assumption

S(A) < \frac{δ_{0}}{M}  (2.12)

where M > 1 is an integer. In the Section 3 we shall specify M = m·(n−m), and therefore M ≥ 2 because the case M = 1 implies n = 2, m = 1, and the diagonal form is obtained after the hyperbolic rotation at the pivot position (1, 2).

Lemma 2.5 Let the sequence A^{(1)} = A, A^{(2)}, … A^{(K+1)}, K > M be generated by J–symmetric Jacobi method under any pivot strategy. If M hyperbolic transformations have been involved, and if the assumption (2.12) holds then

S(A^{(k)}) ≤ C_{M} · S(A), 1 ≤ k ≤ K + 1  (2.13)

where

C_{M} < 1.07, M ≥ 2.  (2.14)

Proof Since trigonometric transformations do not increase the off–norm we consider only the hyperbolic transformations. Let h_{1} < ⋯ < h_{M}, be indices of the hyperbolic transformations and ϑ_{h_{1}}, …, ϑ_{h_{M}} the corresponding angles. Let

τ_{i} = | tanh ϑ_{h_{i}}|, ν_{i} = ∥C_{h_{i}}∥_{2}^{2}, 1 ≤ i ≤ M.

From Lemma 2.2 we conclude that for 1 ≤ i ≤ M

2 · τ_{i} < 1 implies ν_{i} = \frac{1 + τ_{i}}{1 − τ_{i}} ≤ \frac{1}{1 − 2 · τ_{i}}  (2.15)

and from Lemma 2.3 we have

S^{2}(A^{(h_{i}+1)}) ≤ ν_{i} · [S^{2}(A^{(h_{i})}) − 2 · (a_{r(h_{i})s(h_{i})}^{(h_{i})})^{2}] , 1 ≤ i ≤ M.  (2.16)

Not all transformations C_{h_{i}} will increase S^{2}(A^{(h_{i})}). Since we are interested in those transformations C_{h_{i}} which do increase S^{2}(A^{(h_{i})}), we define

S̃ = {i ∈ {1, …, M}; S(A^{(h_{i}+1)}) > S(A^{(h_{i})})}.

Let M̃ = |S̃| > 0 and let i_{1} < … < iM̃ be the increasing ordering of S̃. Let I_{0} = [1, M] and

ω(η) = \frac{18 · η^{2} − 1}{18 · η^{2} − 3} · \frac{2}{9} · \frac{1}{M^{2}} , η ∈ I_{0}.

We shall prove the existence of η_{∗}, 1 < η_{∗} < M, such that for 1 ≤ j ≤ M̃ holds (i)

S^{2}(A^{(k)}) ≤ \frac{δ_{0}^{2}}{η_{∗}^{2}} , 1 ≤ k ≤ h_{i_{j}},

(ii)

S^{2}(A^{(k)}) ≤ \frac{S^{2}(A)}{1 − (j − 1) · ω(η_{∗})}, 1 ≤ k ≤ h_{i_{j}}.

Let

η_{∗}^{2} = \frac{P_{1}(M) + \sqrt{P_{2}(M)}}{324}, η_{∗} > 0,

where

P_{1}(x) = 162 · x^{2} − 36 · x + 27
P_{2}(x) = (P_{1}(x))^{2} − 648 · (27 · x^{2} − 2 · x).

Simple calculation yields P_{1}(M) = 162·M^{2}·(1− \frac{36}{162·M})+27 ≥ 144·M^{2}+27 ≥ 603 and P_{2}(M) ≥ (162 · M^{2} − 36 · M − 27)^{2} − 2 · 27 · 48 · M ≥ 296217. Hence η_{∗}^{2} > 3.54 and η_{∗} > 1.88. Since M > 1, P_{1}(M) < 162 · M^{2} and P_{2}(M) < (P_{1}(M))^{2}, so η_{∗} < M^{2}. To prove (i) and (ii) for j = 1, …, M̃ we use induction with respect to j. For j = 1 the relations (i) and (ii) trivially hold. Assume that (i) and (ii) hold with j satisfying 1 < j < M̃. By Lemma 2.1, the assertion (2.9) of Lemma 2.4 and the Cauchy–Schwarz inequality we obtain

2 · τ_{i_{j}} ≤ \frac{2}{3} · \frac{|a_{r(h_{i_{j}})s(h_{i_{j}})}^{(h_{i_{j}})}|}{δ_{0}} ≤ \frac{2}{3 · δ_{0}} · \frac{4}{3} · \frac{18 · η_{∗}^{2} − 1}{18 · η_{∗}^{2} − 3} · \frac{|(a_{r(h_{i_{j}})}^{(h_{i_{j}})}, a_{s(h_{i_{j}})}^{(h_{i_{j}})})|}{δ_{0}}
≤ \frac{18 · η_{∗}^{2} − 1}{18 · η_{∗}^{2} − 3} · \frac{8}{9 · δ_{0}^{2}} · (∥a_{r(h_{i_{j}})}^{(h_{i_{j}})}∥ · ∥a_{s(h_{i_{j}})}^{(h_{i_{j}})}∥)

≤ \frac{18 · η_{∗}^{2} − 1}{18 · η_{∗}^{2} − 3} · \frac{4}{9 · δ_{0}^{2}} · (∥a_{r(h_{i_{j}})}^{(h_{i_{j}})}∥^{2} + ∥a_{s(h_{i_{j}})}^{(h_{i_{j}})}∥^{2})
≤ \frac{18 · η_{∗}^{2} − 1}{18 · η_{∗}^{2} − 3} · \frac{2}{9} · \frac{S^{2}(A^{(h_{i_{j}})})}{δ_{0}^{2}}.  (2.17)

Using the part (ii) of the induction hypothesis we obtain

2 · τ_{i_{j}} ≤ \frac{18 · η_{∗}^{2} − 1}{18 · η_{∗}^{2} − 3} · \frac{2}{9} · \frac{1}{1 − (j − 1) · ω(η_{∗})} · \frac{S^{2}(A)}{δ_{0}^{2}}
< \frac{ω(η_{∗})}{1 − (j − 1) · ω(η_{∗})} < 1.

Hence by the relations (2.15), (2.16) and (ii) we have

S^{2}(A^{(h_{i_{j}} +1)}) ≤ \frac{1}{1 − 2 · τ_{i_{j}}} · S^{2}(A^{(h_{i_{j}})})
< \frac{1}{1 − \frac{ω(η_{∗})}{1−(j−1)·ω(η_{∗})}} · \frac{1}{1 − (j − 1) · ω(η_{∗})} · S^{2}(A)

= \frac{S^{2}(A)}{1 − j · ω(η_{∗})}.  (2.18)

This proves (ii) since

S(A^{(k)}) ≤ S(A^{(h_{i_{j}} +1)}), h_{i_{j}} + 1 ≤ k ≤ h_{i_{j+1}}.

To prove (i) it suffices to show

S^{2}(A^{(h_{i_{j}} +1)}) < \frac{δ_{0}^{2}}{η_{∗}^{2}} .

Using the inequality (2.18) we see that it suffices to prove

\frac{S^{2}(A)}{1 − j · ω(η_{∗})} ≤ \frac{δ_{0}^{2}}{η_{∗}^{2}} .

The last inequality is implied by

\frac{1}{M^{2}} · \frac{η_{∗}^{2}}{1 − M · ω(η_{∗})} ≤ 1.

This inequality can be solved by elementary means. We set (see (ii))

C_{M}^{2} = \frac{1}{1 − M · ω(η_{∗})}

and get the relation (2.13). An easy computation shows that for M ≥ 2, C_{M} ≤ 1.0629.

In the following lemma we assume the notation used in the proof of Lemma 2.5.

Lemma 2.6 Let the assumptions of Lemma 2.5 hold. Then

(i)

∑_{k=1}^{K} (a_{r(k)s(k)}^{(k)})^{2} ≤ C′_{M} · S^{2}(A)  (2.19)
where for M ≥ 2, C′_{M} < 1.003.

(ii)

∑_{i=1}^{M} sinh^{2} ϑ_{h_{i}} ≤ C′′_{M} · \frac{S^{2}(A)}{δ_{0}^{2}}  (2.20)
where for M ≥ 2, C′′_{M} < 0.12.

Proof Since ν_{k} = max{1, ∥C_{k}∥_{2}^{2}}, the relation (2.6) implies

S^{2}(A^{(k+1)}) ≤ ν_{k} · S^{2}(A^{(k)}) − 2 · (a_{r(k)s(k)}^{(k)})^{2} , 1 ≤ k ≤ K.

Repeated application of the last inequality yields

S^{2}(A^{(K+1)}) ≤ [ ∏_{k=1}^{K} ν_{k}] · S^{2}(A) − 2 · ∑_{k=1}^{K} (a_{r(k)s(k)}^{(k)})^{2} .

Hence

∑_{k=1}^{K} (a_{r(k)s(k)}^{(k)})^{2} ≤ \frac{1}{2} · [ ∏_{k=1}^{K} ν_{k}] · S^{2}(A).

Note that ∏_{k=1}^{K} ν_{k} = ∏_{i=1}^{M} ν_{h_{i}}, where h_{1} < … < h_{M} are the indices of the hyper-

bolic transformations. In the proof of Lemma 2.5 we have shown that

τ_{i} = | tanh ϑ_{h_{i}}| < \frac{1}{2}, 1 ≤ i ≤ M.

By Lemma 2.1 and the assertion (2.13) of Lemma 2.5 we have

ν_{h_{i}} ≤ \frac{1}{1 − 2 · ^{\frac{|a_{r(h_{i})s(h_{i})}^{(h_{i})}|}{3·δ_{0}}}} ≤ \frac{1}{1 − \frac{2}{3·δ_{0}} · \frac{S(A^{(h_{i})})}{\sqrt{2}}}

≤ \frac{1}{1 − \frac{\sqrt{2}}{3} · C_{M} · \frac{S(A)}{δ_{0}}} = \frac{1}{1 − ω_{M}} , 1 ≤ i ≤ M  (2.21)

where ω_{M} = \frac{\sqrt{2}}{3} · \frac{C_{M}}{M}. Let ν^{(i)} = ν_{h_{1}} ⋯ ν_{h_{i}}, 1 ≤ i ≤ M. We shall prove that

ν^{(i)} ≤ \frac{1}{1 − i · ω_{M}} , 1 ≤ i ≤ M.  (2.22)

Really, for i = 1 (2.22) is implied by (2.21). To step from i to i + 1 for a fixed i < M we use the relations (2.21) and (2.22). We obtain

ν^{(i+1)} = ν^{(i)} · ν_{h_{i+1}} ≤ \frac{1}{1 − i · ω_{M}} · \frac{1}{1 − ω_{M}} ≤ \frac{1}{1 − (i + 1) · ω_{M}}

which proves the induction step. Now we can take

C′_{M} = \frac{1}{2} · \frac{1}{1 − M · ω_{M}} = \frac{3}{6 − 2 · \sqrt{2} · C_{M}} .  (2.23)

The upper bound for C′_{M} is obtained by using the relation (2.14). This proves (i). To prove (ii) we use Lemma 2.1, Lemma 2.4 and Lemma 2.5. We obtain

sinh^{2} ϑ_{h_{i}} = \frac{tanh^{2} ϑ_{h_{i}}}{1 − tanh^{2} ϑ_{h_{i}}} ≤ \frac{(a_{r(h_{i})s(h_{i})}^{(h_{i})})^{2}}{9 · δ_{0}^{2} − (a_{r(h_{i})s(h_{i})}^{(h_{i})})^{2}}

≤ \frac{(a_{r(h_{i})s(h_{i})}^{(h_{i})})^{2}}{δ_{0}^{2}} · \frac{1}{9 − \frac{1}{2} · \frac{S^{2}(A^{(h_{i})})}{δ_{0}^{2}}}

≤ \frac{(a_{r(h_{i})s(h_{i})}^{(h_{i})})^{2}}{δ_{0}^{2}} · \frac{1}{9 − \frac{1}{2} · (\frac{C_{M}}{M})^{2}} , 1 ≤ i ≤ M.

Combining this inequality with the assertion (i) we obtain

∑_{i=1}^{M} sinh^{2} ϑ_{h_{i}} ≤ \frac{C′_{M}}{9 − \frac{1}{2} · (\frac{C_{M}}{M})^{2}} · \frac{S^{2}(A)}{δ_{0}^{2}}
= C′′_{M} · \frac{S^{2}(A)}{δ_{0}^{2}}.

The upper estimate for C′′_{M} is obtained from the relations (2.14) and (2.23).

Next we show that under the assumptions of Lemma 2.5 and the additional

condition S(A) < \frac{δ}{M} the diagonal elements cannot change their affiliation during the Jacobi process. In the case of the trigonometric transformation we have

a_{r(k)r(k)}^{(k+1)} − a_{r(k)r(k)}^{(k)} = −(a_{s(k)s(k)}^{(k+1)} − a_{s(k)s(k)}^{(k)}) = a_{r(k)s(k)}^{(k)} · tan ϑ_{k},

| tan ϑ_{k} · a_{r(k)s(k)}^{(k)}| ≤ \frac{C_{M}}{\sqrt{2}} · \frac{δ}{M} < 0.38 · δ, M ≥ 2,

while in the case of hyperbolic transformation we have

a_{r(k)r(k)}^{(k+1)} − a_{r(k)r(k)}^{(k)} = a_{s(k)s(k)}^{(k+1)} − a_{s(k)s(k)}^{(k)} = a_{r(k)s(k)}^{(k)} · tanh ϑ_{k},

| tanh ϑ_{k} · a_{r(k)s(k)}^{(k)}| ≤ \frac{(a_{r(k)s(k)}^{(k)})^{2}}{3 · δ_{0}} ≤ \frac{C_{M}^{2}}{6 · M^{2}} · δ < 0.048 · δ, M ≥ 2

By Lemma 2.5 and Lemma 1.1 we conclude that if a_{jj}^{(k)} is affiliated with λ_{s_{i}}, then

|σ_{i} · a_{jj}^{(k)} − λ_{s_{i}}| ≤ \frac{C_{M}^{2}}{M · (6 · M − 4 · C_{M})} · δ < 0.075 · δ, M ≥ 2.

This inequality holds for any k, 1 ≤ k ≤ K +1. Since every diagonal element of JA^{(k)} is affiliated with one eigenvalue, all diagonal elements lie in disks of radius 0.075 · δ around the eigenvalues. On the other hand the change of the diagonal elements is bounded by 0.25 · δ. This precludes any jump of the diagonal elements from one disk to another since the gap between two adjacent disks is at last (3 − 2 · 0.075) · δ = 2.85 · δ. So, the affiliation is preserved at least for 1 ≤ k ≤ K + 1. Note that |τ_{j} · a_{jj}^{(k)} − τ_{l} · a_{ll}^{(k)}| is either smaller than \frac{2 · C_{M}^{2} · δ}{M · (6 · M − 4 · C_{M})}, or larger than D_{M} · δ, where

D_{M} = 3 − \frac{2 · C_{M}^{2}}{M · (6 · M − 4 · C_{M})} ≥ 2.84, M ≥ 2.  (2.24)

In the sequel we shall use notation

si(ϑ_{k}) = \{ \begin{matrix}sinh ϑ_{k}, & 1 ≤ r(k) ≤ m < s(k) ≤ n, \\ sin ϑ_{k}, & othervise. \end{matrix}  (2.25)

and

M = {k : 1 ≤ k ≤ K + 1, |τ_{r(k)} · a_{r(k)r(k)}^{(k)} − τ_{s(k)} · a_{s(k)s(k)}^{(k)}| > D_{M} · δ}, where τ_{j}, 1 ≤ j ≤ n are defined by (1.11). Lemma 2.7 Let the assumptions of Lemma 2.5 hold. If in addition

S(A) < \frac{δ}{M}

then

∑_{k∈M} si^{2}(ϑ_{k}) ≤ K_{M} · \frac{S^{2}(A)}{δ^{2}},  (2.26)

where K_{M} < 0.13 if M ≥ 2. Proof In the case of a trigonometric transformation with the angle ϑ_{k}, k ∈ M, we have

| sin ϑ_{k}| ≤ | tan ϑ_{k}| ≤ \frac{1}{2} · | tan 2ϑ_{k}| < \frac{|a_{r(k)s(k)}^{(k)}|}{D_{M} · δ},

hence Lemma 2.5 implies

∑_{k∈M} si^{2}(ϑ_{k}) = ∑_{τ_{r(k)}=τ_{s(k)}^{k∈M}} sin^{2} ϑ_{k} + ∑_{τ_{r(k)}≠τ_{s(k)}^{k∈M}} sinh^{2} ϑ_{k}
≤ \frac{1}{D_{M}^{2}} · \frac{1}{δ^{2}} · ∑_{τ_{r(k)}=τ_{s(k)}^{k∈M}} (a_{r(k)s(k)}^{(k)})^{2}

+ \frac{C′′_{M}}{C′_{M}} · \frac{1}{δ^{2}} · ∑_{τ_{r(k)}≠τ_{s(k)}^{k∈M}} (a_{r(k)s(k)}^{(k)})^{2}

≤ max\{\frac{1}{D_{M}^{2}} , \frac{C′′_{M}}{C′_{M}} \} · \frac{1}{δ^{2}} · ∑_{k∈M} (a_{r(k)s(k)}^{(k)})^{2}
≤ max\{\frac{1}{D_{M}^{2}} , \frac{C′′_{M}}{C′_{M}} \} · \frac{1}{δ^{2}} · C′_{M} · S^{2}(A)
≤ K_{M} · \frac{S^{2}(A)}{δ^{2}},

where

K_{M} = C′_{M} · max\{\frac{1}{D_{M}^{2}} , \frac{C′′_{M}}{C′_{M}} \}.

To bound K_{M} one uses relations (2.14), (2.23) and (2.24).

3 Asymptotic Quadratic Convergence

Using tools developed in previous sections, we are ready to prove the quadratic convergence of the J–symmetric Jacobi method. To obtain sharp bounds we shall use the new technique introduced in [6]. We make the following asymptotic assumptions (cf. [4], [6])

AA1 S(A) < \frac{δ}{M}, M = m · (n − m),

AA2 The diagonal elements of JA which approximate the same multiple eigenvalue of JA occupy successive positions along the diagonal.

Using the partition (1.7) we can write

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

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

where N = \frac{n · (n − 1)}{2} and generally

Γ_{i}^{(k)} = S^{2}(A_{ii}^{(k)}) + 2 · ∑_{j=i+1}^{p} ∥A_{ij}^{(k)}∥_{F}^{2} , 1 ≤ i ≤ p − 1, k ≥ 1.

First we estimate the quantities Γ_{i}^{(N+1)}, 1 ≤ i ≤ p − 1. To this end we introduce notation and some auxiliary quantities (cf. [6]):

• The sequence A^{(1)} = A, A^{(2)}, … generated by the row–cyclic J–symmetric Jacobi method.

• The partition

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

derived from the partition (1.7).

• The row–vectors

a_{t}^{(k)} = (a_{t,t+1}^{(k)}, …, a_{tn_{1}}^{(k)}) , 1 ≤ t ≤ n_{1} − 1,
y_{tr}^{(k)} = (a_{t+1,r}^{(k)}, …, a_{n_{1}r}^{(k)}) , 1 ≤ t ≤ n_{1} − 1, n_{1} + 1 ≤ r ≤ n,
g_{t}^{(k)} = (a_{t,n_{1}+1}^{(k)}, …, a_{tn}^{(k)}) , 1 ≤ t ≤ n_{1}.

Note that g_{t}^{(k)}, a_{t}^{(k)} and (y_{tr}^{(k)})^{τ} are the rows of G_{1}^{(k)}, parts of the rows of A_{11}^{(k)} and parts of the columns of G_{1}^{(k)}, respectively.

• The sets

P_{n} = {(i, j) : 1 ≤ i < j ≤ n},
M_{1} = {k : k ∈ M, k ≤ N}
G_{1} = {(t, r) : 1 ≤ t ≤ n_{1}, n_{1} + 1 ≤ r ≤ n} \ {(n_{1}, n_{1} + 1)}.

• The superscripts \begin{matrix}q_{0} = 1, q_{t} = q_{t−1} + (n − t), 1 ≤ t < n; \\ q′_{i} = q_{s_{i−1}}, 1 ≤ i < p; \\ q̃_{0} = 1, q̃_{t} = q̃_{t−1} + (n_{1} − t), 1 ≤ t < n_{1}. \end{matrix}

The meaning of these numbers is the following: q_{t} The superscript q_{t} is associated with the matrix obtained after the

transformation at the pivot position (t, n);

q′_{i} The superscript q′_{i} is associated with the matrix just before operating on the i-th block–row according to the partition (1.7);

q̃_{t} These superscripts have the same meaning as q_{t}’s, but for the row– cyclic strategy within the block A_{11} from the partition (1.7).

In Figure 1 we have displayed the first block–row of A, together with vectors a_{t}, g_{t} and y_{tr}, in the case n = 14, n_{1} = 6 and m = 8.

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 m 9 10 11 12 13 14 Figure 1: n = 14, n^{1} = 6, m = 8

Since we consider the first cycle only, we use notation ϑ_{ij} and ν_{ij} for ϑ_{k} and ν_{k},respectively with r(k) = i, s(k) = j. We also use si(ϑ_{ij}) defined by (2.25) and co(ϑ_{ij}) = \sqrt{1 ∓ si^{2}(ϑ_{ij})}, where − (+) is chosen for trigonometric (hyperbolic) angle. To estimate Γ_{1}^{(N+1)} we consider three cases: n_{1} = 1, n_{1} = 2 and n_{1} ≥ 3.

Lemma 3.1 If n_{1} = 1 then

Γ_{1}^{(N+1)} ≤ [∏_{i=1}^{M} ν_{h_{i}}] · [ ∏_{l=m+1}^{n} cosh ϑ_{1l}]^{2} · S^{2}(A) · ∑_{(t,r)∈G_{1}} si^{2}(ϑ_{tr}).

Proof First we shall bound

Γ_{1}^{(n)} = 2 · ∥g_{1}^{(n)}∥^{2} = 2 · ∑_{j=2}^{n−1} (a_{1j}^{(n)})^{2} .

For j ∈ {2, …, n − 1} consider the changes of the element at the position (1, j) from the moment of its zeroing till the end of pivoting in the first row. We obtain

a_{1j}^{(j)} = 0
a_{1j}^{(k)} = a_{1j}^{(k−1)} · co(ϑ_{1,k}) + a_{k,j}^{(k−1)} · si(ϑ_{1,k}), j + 1 ≤ k ≤ n. (3.1)

The relation (3.1) implies

|a_{1j}^{(n)}| ≤ cosh ϑ_{1n} · |a_{1j}^{(n−1)}| + | sinh ϑ_{1n}| · |a_{nj}^{(n−1)}| ≤

≤ co(ϑ_{1n}) · [|co(ϑ_{1,n−1})| · |a_{1j}^{(n−2)}| + |si(ϑ_{1,n−1})| · |a_{n−1,j}^{(n−2)}|] +

+|si(ϑ_{1n})| · |a_{nj}^{(n−1)}| = co(ϑ_{1n}) · |co(ϑ_{1,n−1})| · |a_{1j}^{(n−2)}| +

+ [co(ϑ_{1n}) · |si(ϑ_{1,n−1})| · |a_{n−1,j}^{(n−2)}| + | sinh ϑ_{1n}| · |a_{nj}^{(n−1)}|] ≤ ⋯

≤ ∑_{k=j+1}^{n} [|a_{k,j}^{(k−1)}| · |si(ϑ_{1,k})| · ( ∏_{l≥m+1^{l≥k+2}}^{n} cosh ϑ_{1l})] .

Squaring and using the inequality of Cauchy and Schwarz we obtain for 2 ≤ j ≤ n − 1

(a_{1j}^{(n)})^{2} ≤ [ ∏_{k=m+1}^{n} cosh ϑ_{1k}]^{2} · [ ∑_{k=j+1}^{n} (a_{k,j}^{(k−1)})^{2}] · [ ∑_{k=j+1}^{n} si^{2}(ϑ_{1,k})] .

Since a_{1n}^{(n)} = 0 we have

∑_{j=2}^{n} (a_{1j}^{(n)})^{2} ≤ [ ∏_{k=m+1}^{n} cosh ϑ_{1k}]^{2} · [∑_{k=3}^{n} si^{2}(ϑ_{1,k})] · [∑_{j=2}^{n−1} ∑_{i=j+1}^{n} (a_{i,j}^{(i−1)})^{2}] .

The last factor on the right–hand side can be transformed as follows

∑_{j=2}^{n−1} ∑_{i=j+1}^{n} (a_{i,j}^{(i−1)})^{2} = ∑_{i=3}^{n} ∑_{j=2}^{i−1} (a_{i,j}^{(i−1)})^{2} = ∑_{j=3}^{n} ∑_{i=2}^{j−1} (a_{ji}^{(j−1)})^{2} =

= ∑_{j=3}^{n} ∑_{i=2}^{j−1} (a_{i,j}^{(j−1)})^{2} = ∑_{j=3}^{n} ∑_{i=2}^{j−1} (a_{i,j}^{(i)})^{2} .

Here we have used the symmetry

a_{ij}^{(k)} = a_{ji}^{(k)}, 1 ≤ i, j ≤ n, k ≥ 1,

and the special annihilation ordering which implies

a_{ij}^{(i)} = a_{ij}^{(j−1)}, 1 < i < j ≤ n.

To bound ∑_{i=2}^{j−1} (a_{ij}^{(i)})^{2} for j ∈ {3, …, n} we write

∥[ \begin{matrix}a_{1j}^{(i)} \\ a_{ij}^{(i)} \end{matrix} ]∥^{2} = ∥Ĉ_{i−1}^{τ} [ \begin{matrix}a_{1j}^{(i−1)} \\ a_{ij}^{(i−1)} \end{matrix} ]∥^{2} ≤ ν_{i−1} · ∥[ \begin{matrix}a_{1j}^{(i−1)} \\ a_{ij}^{(i−1)} \end{matrix} ]∥^{2} , \begin{matrix}2 ≤ i ≤ j − 1, \\ 3 ≤ j ≤ n, \end{matrix}

where ν_{k} = ∥C_{k}∥_{2}^{2}, k ≥ 1. We obtain

(a_{1j}^{(2)})^{2} + (a_{2j}^{(2)})^{2} ≤ ν_{1} · ((a_{1j}^{(1)})^{2} + (a_{2j}^{(1)})^{2})
(a_{1j}^{(3)})^{2} + (a_{3j}^{(3)})^{2} ≤ ν_{2} · ((a_{1j}^{(2)})^{2} + (a_{3j}^{(2)})^{2})
⋮
(a_{1j}^{(j−2)})^{2} + (a_{j−2,j}^{(j−2)})^{2} ≤ ν_{j−3} · ((a_{1j}^{(j−3)})^{2} + (a_{j−2,j}^{(j−3)})^{2})
(a_{1j}^{(j−1)})^{2} + (a_{j−1,j}^{(j−1)})^{2} ≤ ν_{j−2} · ((a_{1j}^{(j−2)})^{2} + (a_{j−1,j}^{(j−2)})^{2}) .

Multiplying the first inequality by ν_{2} ⋯ ν_{j−2}, the second one by ν_{3} ⋯ ν_{j−2}, etc. and adding the obtained inequalities we obtain

∑_{i=2}^{j−1} (a_{ij}^{(i)})^{2} ≤ [ ∏_{k=1}^{j−2} ν_{k}] · (a_{1j}^{(1)})^{2} + ∑_{i=2}^{j−1} [ ∏_{k=i−1}^{j−2} ν_{k}] · (a_{ij}^{(i−1)})^{2} , 3 ≤ j ≤ n.

Summing over 3 ≤ j ≤ n and using the fact that a_{ij}^{(i−1)} = a_{ij}^{(1)}, 2 ≤ i < j ≤ n, we obtain

∑_{j=3}^{n} ∑_{i=2}^{j−1} (a_{ij}^{(i)})^{2} ≤ ∑_{j=3}^{n} [ ∏_{k=1}^{j−2} ν_{k}] · ∑_{i=1}^{j−1} (a_{ij}^{(i−1)})^{2} ≤ [ ∏_{k=1}^{n−2} ν_{k}] · ∑_{j=3}^{n} ∑_{i=1}^{j−1} (a_{ij}^{(1)})^{2} ≤

≤ [ ∏_{k=m}^{n−2} ν_{k}] · (\frac{1}{2} · S^{2}(K_{1}) + ∥g_{1}∥^{2}).

Γ_{1}^{(n)} ≤ [ ∏_{k=m}^{n−2} ν_{k}] · [ ∏_{k=m+1}^{n} cosh ϑ_{1k}]^{2} · S^{2}(A) · ∑_{r=3}^{n} si^{2}(ϑ_{1,r}).  (3.2)

During the next N −(n−1) transformations the elements of the first row will couple among themselves, and because of the presence of J-orthogonal congruences the bound in the estimate (3.2) will be increased. We can estimate those changes by the following inequalities

(a_{1r(k)}^{(k+1)})^{2} + (a_{1s(k)}^{(k+1)})^{2} ≤ ν_{k} · [(a_{1r(k)}^{(k)})^{2} + (a_{1s(k)}^{(k)})^{2}] , n ≤ k ≤ N.

An easy computation gives

∑_{j=2}^{n} (a_{1j}^{(N+1)})^{2} ≤ [ ∏_{k=n}^{N} ν_{k}] · ∑_{j=2}^{n} (a_{1j}^{(n)})^{2} ,

hence we obtain

Γ_{1}^{(N+1)} ≤ [∏_{i=1}^{M} ν_{h_{i}}] · [ ∏_{k=m+1}^{n} cosh ϑ_{1k}]^{2} · S^{2}(A) · ∑_{(t,r)∈G_{1}} si^{2}(ϑ_{tr}).

Lemma 3.2 If n_{1} = 2 then

Γ_{1}^{(N+1)} ≤ [∏_{i=1}^{M} ν_{h_{i}}] · max { ∏_{l=m+1}^{n} cosh^{2} ϑ_{1l}, ∏_{l=m+1}^{n} cosh^{2} ϑ_{2l}} ·
· S^{2}(A) · ∑_{(t,r)∈G_{1}} si^{2}(ϑ_{tr}).

Proof In this case we have

Γ_{1}^{(N+1)} = 2 · ∥a_{1}^{(N+1)}∥^{2} + 2 · (∥g_{1}^{(N+1)}∥^{2} + ∥g_{2}^{(N+1)}∥^{2}) .

The sum

2 · (∥a_{1}^{(N+1)}∥^{2} + ∥g_{1}^{(N+1)}∥^{2}) = 2 · ∑_{j=2}^{n} (a_{1j}^{(N+1)})^{2}

is estimated in the same way as in the previous case. To estimate ∥g_{2}^{(N+1)}∥^{2} we can apply the above analysis to the first row of the (n − 1) × (n − 1) principal right bottom submatrix of A^{(n)}. We obtain

2 · ∥g_{2}^{(N+1)}∥^{2} = 2 · ∑_{j=3}^{n} (a_{2j}^{(N+1)})^{2}

≤ [ ∏_{h_{i}≥n^{i=1}}^{M} ν_{h_{i}} ] · [ ∏_{l=m+1}^{n} cosh ϑ_{2l}]^{2} · S^{2}(A^{(n)}) · ∑_{r=4}^{n} si^{2}(ϑ_{2r}).

Since S^{2}(A^{(n)}) ≤ ν_{m} ⋯ ν_{n−1} · S^{2}(A), we obtain

Γ_{1}^{(N+1)} = 2 · (∥a_{1}^{(N+1)}∥^{2} + ∥g_{1}^{(N+1)}∥^{2})^{2} + 2 · ∥g_{2}^{(N+1)}∥^{2}

≤ [∏_{i=1}^{M} ν_{h_{i}}] · [ ∏_{k=m+1}^{n} cosh ϑ_{1k}]^{2} · S^{2}(A) · ∑_{(1,r)∈G_{1}} si^{2}(ϑ_{1r})

+ [∏_{i=1}^{M} ν_{h_{i}}] · [ ∏_{k=m+1}^{n} cosh ϑ_{2k}]^{2} · S^{2}(A) · ∑_{(2,r)∈G_{1}} si^{2}(ϑ_{2r})

≤ [∏_{i=1}^{M} ν_{h_{i}}] · max { ∏_{k=m+1}^{n} cosh^{2} ϑ_{1k}, ∏_{k=m+1}^{n} cosh^{2} ϑ_{2k}} ·

·S^{2}(A) · ∑_{(t,r)∈G_{1}} si^{2}(ϑ_{tr}).

Lemma 3.3 If n_{1} ≥ 3 then

Γ_{1}^{(N+1)} ≤ [∏_{i=1}^{M} ν_{h_{i}}] · max_{1≤t≤n_{1}} [ ∏_{k=m+1}^{n} cosh ϑ_{tk}]^{2} · {(1 + γ) · S^{2}(A_{11})+

+ (1 + \frac{1}{γ}) · S^{2}(A) · ∑_{(t,r)∈G_{1}} si^{2}(ϑ_{tr})\} .  (3.3)

Proof In this case we must pay full attention to many details. As in [6] we replace the row–cyclic ordering O_{R} by the equivalent ordering Õ_{R} = O_{R,1,n_{1}} ⊕ Õ_{R,1,n_{1}} ⊕ O_{R,n_{1}+1,n} where ⊕ concatinates the row–wise orderings defined on A_{11}, G_{1} and K_{1} respectively (see Figure 2). All quantities computed during the process defined by Õ_{R} we denote by attaching˜ , e.g. Ã^{(k)} = [ã_{ij}^{(k)}], G̃_{1}^{(k)}, K̃_{1}^{(k)}, etc. In [6] it has been shown that ϑ_{tr} = ϑ̃_{tr} for (t, r) ∈ P_{n} and Ã^{(k)} = A^{(k)}, q_{n_{1}} +1 ≤ k ≤ N +1. After the first cycle within A_{11} defined by O_{R,1,n_{1}} is completed we have (note that n_{1} ≤ m)

S^{2}(Ã_{11}^{(q̃_{n_{1}−1})}) ≤ S^{2}(A_{11}),
∥G̃_{1}^{(q̃_{n_{1}−1})}∥_{F} = ∥G_{1}∥_{F} ,  (3.4)
K̃_{1}^{(q̃_{n_{1}})} = K_{1}.

[figure: Õ_{R,1,n_{1}} is the row-wise; ordering of the set; {(i, j); 1 ≤ i ≤ n_{1}, n_{1} + 1 ≤ j ≤ n}; O_{R,n_{1}+1,n} is the row-wise; ordering of the set; {(i, j); n_{1} + 1 ≤ i < j ≤ n}; O_{R,1,n_{1}} is the row-wise ordering of the set; {(i, j); 1 ≤ i < j ≤ n_{1}}]

Figure 2: The orderings O_{R,1,n_{1}}, Õ_{R,1,n_{1}} and O_{R,n_{1}+1,n}

Thus, Ã^{(q̃_{n_{1}})} satisfies the same assumptions as A and for our analysis the essential quantities S(A_{11}) and ∥G_{1}∥_{F} have not increased. To simplify notation we shall shift the upper index q̃_{n_{1}−1} by −q̃_{n_{1}−1}. So, in the following analysis which deals with transformations folloving Õ_{R,1,n_{1}}, Ã^{(q̃_{n_{1}−1}+k)} is replaced by Ã^{(k)}. If we set n̄_{1} = n − n_{1} then an analysis similar to the one above implies

∥g̃_{t}^{(tn̄_{1})}∥^{2} ≤ [ ∏_{r=m+1}^{n−1} ν_{tr}] · [ ∏_{r=m+1}^{n} cosh ϑ_{tr}]^{2} · (\frac{1}{2} · S^{2}(K̃_{1}^{((t−1)n̄_{1})}) +

+ ∥g̃_{t}^{((t−1)n̄_{1})}∥^{2}) · ∑_{r>t+1^{r=n_{1}+1}}^{n} si^{2}(ϑ_{tr}), 1 ≤ t ≤ n_{1}.  (3.5)

A similar analysis yields for 1 ≤ t ≤ n_{1} − 1 (cf. [6])

|ã_{t}^{(tn̄_{1})}| ≤ [ ∏_{r=m+1}^{n} cosh ϑ_{tr}] · [|ã_{t}^{((t−1)n̄_{1})}| + ∑_{r=n_{1}+1}^{n} |ỹ_{tr}^{((t−1)n̄_{1})}| · |si(ϑ_{tr})|]

= [ ∏_{r=m+1}^{n} cosh ϑ_{tr}] · [|ã_{t}| + ∑_{r=n_{1}+1}^{n} |ỹ_{tr}^{((t−1)n̄_{1})}| · |si(ϑ_{tr})|] . (3.6)

Here |x| ≤ |y| for vectors x = (x_{i}), y = (y_{i}) means |x_{i}| ≤ |y_{i}| for all i. We have used the fact that transformations with angles ϑ_{lr}, 1 ≤ l ≤ t − 1, n_{1} + 1 ≤ r ≤ n do not change ã_{t}. We shall often use the inequality

(α + β)^{2} ≤ (1 + γ) · α^{2} + (1 + \frac{1}{γ}) · β^{2}, γ ≥ 0  (3.7)

in which equality holds for γ = \frac{β}{α}. Using (3.7) and the inequality of Cauchy and Schwarz and using the same γ for all 1 ≤ t ≤ n_{1} − 1, we obtain

∥ã_{t}^{(tn̄_{1})}∥^{2} ≤ [ ∏_{r=m+1}^{n} cosh ϑ_{tr}]^{2} · [(1 + γ) · ∥ã_{t}∥^{2}+

+ (1 + \frac{1}{γ}) · ∑_{r=n_{1}+1}^{n} ∥ỹ_{tr}^{((t−1)n̄_{1})}∥^{2} · ∑_{r=n_{1}+1}^{n} si^{2}(ϑ_{tr})]

≤ [ ∏_{r=m+1}^{n} cosh ϑ_{tr}]^{2} · [(1 + γ) · ∥ã_{t}∥^{2} +  (3.8)

+ (1 + \frac{1}{γ}) · (∥G̃_{1}^{((t−1)n̄_{1})}∥_{F}^{2} − ∑_{l=1}^{t} ∥g̃_{l}^{((t−1)n̄_{1})}∥^{2}) · ∑_{r=n_{1}+1}^{n} si^{2}(ϑ_{tr})] .

Applying the transformation with pivot pairs from O_{R,n_{1}+1,n} we obtain for 1 ≤ t ≤ n_{1} − 1

∥a_{t}^{(N+1)}∥^{2} + ∥g_{t}^{(N+1)}∥^{2} ≤ [ ∏_{i=t+1}^{m} ∏_{j=m+1}^{n} ν_{ij}] · (∥ã_{t}^{(tn̄_{1})}∥^{2} + ∥g̃_{t}^{(tn̄_{1})}∥^{2}) , (3.9)

and for t = n_{1}

∥g_{n_{1}}^{(N+1)}∥^{2} ≤ [ ∏_{i=n_{1}+1}^{m} ∏_{j=m+1}^{n} ν_{ij}] · ∥g̃_{n_{1}}^{(n_{1}n̄_{1})}∥^{2}.  (3.10)

The relations (3.5)-(3.10) imply

Γ_{1}^{(N+1)} = 2 · ∑_{i=1}^{n_{1}−1} ∥a_{t}^{(N+1)}∥^{2} + 2 · ∑_{t=1}^{n_{1}} ∥g_{t}^{(N+1)}∥^{2}

= 2 · ∑_{t=1}^{n_{1}−1} (∥a_{t}^{(N+1)}∥^{2} + ∥g_{t}^{(N+1)}∥^{2}) + 2 · ∥g_{n_{1}}^{(N+1)}∥^{2}

≤ 2 · ∑_{t=1}^{n_{1}−1} [ ∏_{i=t+1}^{m} ∏_{j=m+1}^{n} ν_{ij}] · (∥ã_{t}^{(tn̄_{1})}∥^{2} + ∥g̃_{t}^{(tn̄_{1})}∥^{2}) +

+2 · [ ∏_{i=n_{1}+1}^{m} ∏_{j=m+1}^{n} ν_{ij}] · ∥g̃_{n_{1}}^{(n_{1}n̄_{1})}∥^{2}

≤ 2 · ∑_{t=1}^{n_{1}−1} [ ∏_{i=t+1}^{m} ∏_{j=m+1}^{n} ν_{ij}] · ∥ã_{t}^{(tn̄_{1})}∥^{2} + 2 · ∑_{t=1}^{n_{1}} [ ∏_{i=t+1}^{m} ∏_{j=m+1}^{n} ν_{ij}] · ∥g̃_{t}^{(tn̄_{1})}∥^{2}

≤ 2 · ∑_{t=1}^{n_{1}−1} [ ∏_{i=t+1}^{m} ∏_{j=m+1}^{n} ν_{ij}] · [ ∏_{r=m+1}^{n} cosh ϑ_{tr}]^{2} · {(1 + γ) · ∥ã_{t}∥^{2}+

+(1 + \frac{1}{γ}) · (∥G̃_{1}^{((t−1)n̄_{1})}∥_{F}^{2} − ∑_{l=1}^{t} ∥g̃_{l}^{((t−1)n̄_{1})}∥^{2}) · ∑_{r>t+1^{r=n_{1}+1}}^{n} si^{2}(ϑ_{tr})\} +

+2 · ∑_{t=1}^{n_{1}} [ ∏_{i=t+1}^{m} ∏_{j=m+1}^{n} ν_{ij}] · [ ∏_{r=m+1}^{n} ν_{tr}] ·

· [ ∏_{r=m+1}^{n} cosh ϑ_{tr}]^{2} · (\frac{1}{2} · S^{2}(K̃_{1}^{((t−1)n̄_{1})}) + ∥g̃_{t}^{((t−1)n̄_{1})}∥^{2}) · ∑_{r>t+1^{r=n_{1}+1}}^{n} si^{2}(ϑ_{tr}).

Since

∥G̃_{1}^{((t−1)n̄_{1})}∥_{F}^{2} − ∑_{l=1}^{t} ∥g̃_{l}^{((t−1)n̄_{1})}∥^{2} + \frac{1}{2} · S^{2}(K̃_{1}^{((t−1)n̄_{1})}) +
+ ∥g̃_{t}^{((t−1)n̄_{1})}∥^{2} ≤ \frac{1}{2} · S^{2}(Ã^{((t−1)n̄_{1})})

and

S^{2}(Ã^{((t−1)n̄_{1})}) ≤ [∏_{i=1}^{t−1} ∏_{j=m+1}^{n} ν_{ij}] · S^{2}(Ã),

we have

Γ^{(N+1)} ≤ 2 · max_{1≤t≤n_{1}} [ ∏_{r=m+1}^{n} cosh ϑ_{tr}]^{2} · {[∏_{i=1}^{M} ν_{h_{i}}] · (1 + γ) · ∑_{t=1}^{n_{1}−1} ∥ã_{t}∥^{2}+

+(1 + \frac{1}{γ}) · \frac{1}{2} · ∑_{t=1}^{n_{1}} [∏_{i=t}^{m} ∏_{j=m+1}^{n} ν_{ij}] · S^{2}(Ã^{((t−1)n̄_{1})}) · ∑_{r>t+1^{r=n_{1}+1}}^{n} si^{2}(ϑ_{tr}) \}

≤ [∏_{i=1}^{M} ν_{h_{i}}] · max_{1≤t≤n_{1}} [ ∏_{r=m+1}^{n} cosh ϑ_{tr}]^{2} · {(1 + γ) · S^{2}(Ã_{11})+

+(1 + \frac{1}{γ}) · S^{2}(Ã) · ∑_{(t,r)∈G_{1}} si^{2}(ϑ_{tr}) \} ,

and Lemma 3.3 follows by the relations (3.4). To bound Γ_{i}^{(N+1)} for all 1 ≤ i ≤ p − 1 we define G_{i} = {(t, r) : s_{i−1} + 1 ≤ t ≤ s_{i}, s_{i} + 1 ≤ r ≤ n} \ {(s_{i}, s_{i} + 1)}, 1 ≤ i ≤ p − 1, and

Υ_{i} = [ ∏_{l=s_{i−1}+1}^{m} ∏_{j=m+1}^{n} ν_{lj}] · max_{s_{i−1}+1≤t≤s_{i}} [ ∏_{r=m+1}^{n} cosh ϑ_{tr}]^{2} , 1 ≤ i ≤ w, (3.11)

with w defined in the Section 1. Lemma 3.4 Let i ∈ {1, …, p − 1}. If n_{i} ≤ 2, then

Γ_{i}^{(N+1)} ≤ \{ \begin{matrix}Υ_{i} · S^{2}(A^{(q′_{i})}) · ∑_{(t,r)∈G_{i}} si^{2}(ϑ_{tr}), & i ≤ w \\ S^{2}(A^{(q′_{i})}) · ∑_{(t,r)∈G_{i}} si^{2}(ϑ_{tr}), & i > w. \end{matrix}

If n_{i} ≥ 3, then for any γ > 0

Γ_{i}^{(N+1)} ≤ \{ \begin{matrix}Υ_{i} [(1 + γ)S^{2}(A_{ii}^{(q′_{i})}) + (1 + \frac{1}{γ})S^{2}(A^{(q′_{i})}) ∑_{(t,r)∈G_{i}} si^{2}(ϑ_{tr})], i ≤ w \\ (1 + γ) · S^{2}(A_{ii}^{(q′_{i})}) + (1 + \frac{1}{γ}) · S^{2}(A^{(q′_{i})}) ∑_{(t,r)∈G_{i}} si^{2}(ϑ_{tr}), i > w. \end{matrix}

Proof If i ≤ w then we can apply the same analysis to the first block–row of the matrix B^{[i]} from the partition

A^{(q′_{i})} = [ \begin{matrix}\begin{matrix}A_{11}^{(q′_{i})} & … & A_{1,i−1}^{(q′_{i})} \\ ⋮ & ... & ⋮ \\ A_{i−1,1}^{(q′_{i})} & … & A_{i−1,i−1}^{(q′_{i})} \end{matrix} & … A_{1p}^{(q′_{i})} ; ⋮ ; … A_{i−1,p}^{(q′_{i})} \\ \begin{matrix}⋮ & ⋮ & ⋮ \\ A_{p,1}^{(q′_{i})} & … & A_{p,i−1}^{(q′_{i})} \end{matrix} & B^{[i]} \end{matrix} ]

Note that B_{11}^{[i]} = A_{ii}^{(q′_{i})} and that only transformations C_{k}, q′_{i} ≤ k ≤ N are met in the analysis. That is why Υ_{i} enters in the estimates. If i > w then only trigonometric transformations are met, and the result follows from Lemma 2.6 in [6]. It can also be derived from the above analysis since ν_{lj} = 1 for m < l < j ≤ n and only trigonometric rotation are used.

Our next aim is to bound the sum ∑_{i=1}^{p−1} Γ_{i}^{(N+1)}. From Lemma 3.4 we see that we have to bound ∑_{i=1}^{p} S^{2}(A_{ii}^{(q′_{i})}). To this end we use Lemma 1.1 and Lemma 2.5 to obtain

S^{2}(A_{ii}^{(q′_{i})}) ≤ L_{M} · \frac{S^{2}(A^{(q′_{i})})}{δ_{i}} · 2 · L_{M} · \frac{1}{δ_{i}} · ∑_{j≠i^{j=1}}^{p} ∥A_{ij}^{(q′_{i})}∥_{F}^{2}

= 2 · L_{M}^{2} · \frac{S^{2}(A^{(q′_{i})})}{δ_{i}^{2}} · ∑_{j≠i^{j=1}}^{p} ∥A_{ij}^{(q′_{i})}∥_{F}^{2}

with

L_{M} = M/(6 · M − 4 · C_{M})  (3.12)

and C_{M} from Lemma 2.5. Let us define 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. Then we have

S^{2}(A_{ii}^{(q′_{i})}) ≤ 2 · L_{M}^{2} · C_{M}^{2} · \frac{S^{2}(A)}{δ_{i}^{2}} · [ ∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q′_{i})}∥^{2} − S^{2}(A_{ii}^{(q′_{i})})] (3.13)

and consequently

S^{2}(A_{ii}^{(q′_{i})}) ≤ \frac{2 · [L_{M} · C_{M} · \frac{S(A)}{δ_{i}}]^{2}}{1 + 2 · [L_{M} · C_{M} · \frac{S(A)}{δ_{i}}]^{2}} · ∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q′_{i})}∥^{2}, 1 ≤ i ≤ p. (3.14)

First we shall bound ∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q′_{i})}∥^{2} for 1 ≤ i ≤ p. Set

L′_{M} = 1 + 2 · (\frac{L_{M} · C_{M}}{M} )^{2}  (3.15)
Ω_{M}(A) = L′_{M} · \frac{(L_{M} · C_{M} · \frac{S(A)}{δ})^{2}}{1 + 2 · (L_{M} · C_{M} · \frac{S(A)}{δ})^{2}}  (3.16)

with L_{M} from (3.12). Lemma 3.5 Let the asymptotic assumptions AA1 and AA2 hold.

(i) If i ∈ {1, …, w}, then for any β > 0

∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q′_{i})}∥^{2} ≤ \frac{1}{2} · L′_{M} · [ ∏_{l=m+1}^{n} ∏_{k=1}^{s_{i−1}} ν_{kl}] · \{(1 + β) · Γ_{i}+
+ (1 + \frac{1}{β}) · S^{2}(A) · ∑_{t=s_{i−1}+1}^{s_{i}} ∑_{r=1}^{s_{i−1}} si^{2}(ϑ_{rt})\}

(ii) If i ∈ {w + 1, …, p}, then for any β > 0

∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q′_{i})}∥^{2} ≤ \frac{1}{2} · L′_{M} · [∏_{i=1}^{M} ν_{h_{i}}] · max_{s_{i−1}+1≤t≤s_{i}} [∏_{r=1}^{m} cosh ϑ_{rt}]^{2} ·

· \{(1 + β) · Γ_{i} + (1 + \frac{1}{β}) · S^{2}(A) · ∑_{t=s_{i−1}+1}^{s_{i}} ∑_{r=1}^{s_{i−1}} si^{2}(ϑ_{rt})\}

Proof (i) In this case we have s_{i} ≤ m. Let t ∈ {s_{i−1} + 1, …, s_{i}} and note that all the transformations which affect ∥x_{t}^{(k)}∥, 1 ≤ k ≤ q′_{i} can be divided into three groups:

• orthogonal transformations which do not rotate the t-th column,

• orthogonal transformations which do rotate the t-th column

• the remaining hyperbolic transformations.

Note that the sequence (∥x_{t}^{(k)}∥, k = 1, …, q′_{i}) is much easier to bound if some equivalent column–wise strategy is used. Therefore we use the result from [6] which states that the row–wise ordering O_{R,s_{i−1}} and the column– wise ordering O_{C,s_{i−1}} of P_{s_{i}} = {(t, r) : 1 ≤ t ≤ s_{i−1}, i + 1 ≤ r ≤ n} are equivalent. Let the sequence Ā^{(1)} = A, Ā^{(2)}, …, Ā^{(q′_{i})} be generated by the J– symmetric Jacobi algorithm following the strategy O_{C,s_{i−1}}. Let the vectors x̄_{t}^{(k)} be defined analogous to x_{t}^{(k)}, but using the elements of Ā^{(k)}. According to Lemma 1.1 from [6] we have Ā^{(q′_{i}+1)} = A^{(q′_{i}+1)} and ϑ̄_{tr} = ϑ_{tr} for all (t, r) from P_{s_{i}}. Set

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

Note that the pivot elements of Ā^{(w_{t})} and Ā^{(w_{t+1})} are ā_{1t}^{(w_{t})} and ā_{1,t+1}^{(w_{t+1})} (see Figure 3).

We have

∥x_{t}^{(q′_{i})}∥^{2} ≤ [ ∏_{l=m+1}^{n} ∏_{k=1}^{s_{i−1}} ν_{kl}] · ∥x̄_{t}^{(w_{t+1})}∥^{2}, s_{i−1} + 1 ≤ t ≤ s_{i}.

Let us divide each x̄_{t}^{(k)} into three components, so that holds (cf. [6])

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

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

s_{i−1} + 1

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

t

r

x̄_{t}

x̄_{r}

s_{i}

x̄_{s_{i}}

m

[figure] [figure]

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

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

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

where ⊕ denotes direct (or orthogonal) sum, and Θ_{k} stands for the null matrix of order k, 1 ≤ k ≤ n. Obviosly

x_{t}^{(1)}(Θ_{s_{i}} ⊕ I_{n−s_{i}}) = x̄_{t}^{(k)}(Θ_{s_{i}} ⊕ I_{n−s_{i}}), 1 ≤ k ≤ w_{s_{i}+1},  (3.17)

and the usual analysis yields

|x̄_{t}^{(w_{t+1})}(Θ_{s_{i}} ⊕ I_{n−s_{i}})| ≤ |x̄_{t}^{(w_{t})}(Θ_{s_{i}} ⊕ I_{n−s_{i}})| +
+ ∑_{r=1}^{s_{i−1}} |x̄_{r}^{(w_{t}+r−1)}(Θ_{s_{i}} ⊕ I_{n−s_{i}})| · |si(ϑ_{rt})|.

Because we are pivoting in the t-th column we have (x̄_{t}^{(w_{t}+r)})_{r} = 0, 1 ≤ r ≤ s_{i−1} and therefore

|x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ Θ_{n−s_{i−1}})| ≤ ∑_{r=1}^{s_{i−1}} |x̄_{r}^{(w_{t}+r−1)}(I_{r} ⊕ Θ_{n−r})| · |si(ϑ_{rt})|.

The last two inequalities and the equality (3.17) imply

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

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

≤ (1 + β) · ∥x_{t}^{(1)}(Θ_{s_{i}} ⊕ I_{n−s_{i}})∥^{2} + (1 + \frac{1}{β}) · \frac{1}{2} · S^{2}(A) · ∑_{r=1}^{s_{i−1}} si^{2}(ϑ_{rt}),

for an arbitrary β > 0. The last term on the right–hand side is obtained using the relations

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

= ∥x̄_{r}^{(w_{t})}(I_{r} ⊕ Θ_{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} ⊕ Θ_{s_{i−1}−r} ⊕ I_{n−s_{i−1}})∥^{2} ≤ \frac{1}{2} · S^{2}(Ā^{(w_{t})}) ≤ \frac{1}{2} · S^{2}(A). (3.18)

In order to bound ∥x̄_{t}^{(w_{t+1})}(Θ_{s_{i−1}} ⊕ I_{n_{i}} ⊕ Θ_{n−s_{i}})∥, s_{i−1} + 1 ≤ t ≤ s_{i} we use the proof of Lemma 1.1. From the relation (1.12), that is

Ā_{ii}^{(w_{t+1})} − σ_{i}λ_{s_{i}}I_{n_{i}} = Ḡ_{i}^{(w_{t+1})} \left[{ \atop K̄_{i}^{(w_{t+1})}}\right]^{−1} \left[{ \atop Ḡ_{i}^{(w_{t+1})}}\right]^{τ} ,

we obtain

∥x̄_{t}^{(w_{t+1})}(Θ_{s_{i−1}} ⊕ I_{n_{i}} ⊕ Θ_{n−s_{i}})∥ ≤ ∥e_{t−s_{i−1}}^{τ}(Ā_{ii}^{(w_{t+1})} − σ_{i}λ_{s_{i}}I_{n_{i}})∥ =

= ∥ (e_{t−s_{i−1}}^{τ}Ḡ_{i}^{(w_{t+1})}) \left[{ \atop K̄_{i}^{(w_{t+1})}}\right]^{−1} \left[{ \atop Ḡ_{i}^{(w_{t+1})}}\right]^{τ} ∥ ≤

≤ 2 · L_{M} · \frac{∥Ḡ_{i}^{(w_{t+1})}∥_{F}}{δ_{i}} · ∥x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ Θ_{n_{i}} ⊕ I_{n−s_{i}})∥ ≤

≤ \frac{\sqrt{2} · L_{M} · C_{M}}{M} · ∥x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ Θ_{n_{i}} ⊕ I_{n−s_{i}})∥.

Here we have used the relation (3.12) and the inequalities

∥Ḡ_{i}^{(w_{t+1})}∥_{F} ≤ \frac{\sqrt{2}}{2} · S(Ā^{(w_{t+1})}) ≤ \frac{\sqrt{2}}{2} · C_{M} · \frac{δ}{M} .

The unit vector e_{t−s_{i−1}} is from the canonical base of R^{n_{i}}. Assuming the same β for all s_{i−1} + 1 ≤ t ≤ s_{i} we obtain

∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q′_{i})}∥^{2} ≤ [ ∏_{l=m+1}^{n} ∏_{k=1}^{s_{i−1}} ν_{kl}] · ∑_{t=s_{i−1}+1}^{s_{i}} ∥x̄_{t}^{(w_{t+1})}∥^{2} ≤

≤ [ ∏_{l=m+1}^{n} ∏_{k=1}^{s_{i−1}} ν_{kl}] · L′_{M} · ∑_{t=s_{i−1}+1}^{s_{i}} ∥x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ Θ_{n_{i}} ⊕ I_{n−s_{i}})∥^{2} ≤

≤ [ ∏_{l=m+1}^{n} ∏_{k=1}^{s_{i−1}} ν_{kl}] · L′_{M} · [(1 + β) · ∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(1)}(Θ_{s_{i}} ⊕ I_{n−s_{i}})∥^{2}+

+(1 + \frac{1}{β}) · \frac{1}{2} · S^{2}(A) · ∑_{t=s_{i−1}+1}^{s_{i}} ∑_{r=1}^{s_{i−1}} si^{2}(ϑ_{rt})] ≤

≤ [ ∏_{l=m+1}^{n} ∏_{k=1}^{s_{i−1}} ν_{kl}] · \frac{1}{2} · L′_{M} · [(1 + β) · Γ_{i}+

+(1 + \frac{1}{β}) · S^{2}(A) · ∑_{t=s_{i−1}+1}^{s_{i}} ∑_{r=1}^{s_{i−1}} si^{2}(ϑ_{rt})] ,

with L′_{M} as defined above and for arbitrary i ∈ {2, …, w} and arbitrary real β > 0. Note that the case i = 1 is trivial. (ii) In this case the estimates are similar, but some bounds are worse because of the position of the i–th diagonal block.We only point out the important differences. First, we note that

∥x_{t}^{(q′_{i})}∥^{2} ≤ [ ∏_{k=1}^{m} ∏_{k=t+1}^{n} ν_{kl}] · ∥x̄_{t}^{(w_{t+1})}∥^{2}, s_{i−1} + 1 ≤ t ≤ s_{i}

S^{2}(Ā^{(w_{t})}) ≤ [ ∏_{k=1}^{m} ∏_{l=m+1}^{t−1} ν_{kl}] · S^{2}(A).

In addition, we have for s_{i−1} + 1 ≤ t ≤ s_{i}

|x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ Θ_{n−s_{i−1}})| ≤ [∏_{r=1}^{m} cosh ϑ_{rt}] ∑_{r=1}^{s_{i−1}} |x̄_{r}^{(w_{t}+r−1)}(I_{r} ⊕ Θ_{n−r})||si(ϑ_{rt})|
|x̄_{t}^{(w_{t+1})}(Θ_{s_{i}} ⊕ I_{n−s_{i}})| ≤ [∏_{r=1}^{m} cosh ϑ_{rt}] · [|x̄_{t}^{(w_{t})}(Θ_{s_{i}} ⊕ I_{n−s_{i}})|+

+ ∑_{r=1}^{s_{i−1}} |x̄_{r}^{(w_{t}+r−1)}(Θ_{s_{i}} ⊕ I_{n−s_{i}})| · |si(ϑ_{rt})|] ,

and for 0 ≤ k ≤ r − 1, 1 ≤ r ≤ s_{i−1}

∥x̄_{r}^{(w_{t}+k)}(I_{r} ⊕ Θ_{s_{i}−r} ⊕ I_{n−s_{i}})∥^{2} ≤ [∏_{j=1}^{m} ν_{jt}] · ∥x̄_{r}^{(w_{t})}(I_{r} ⊕ Θ_{s_{i−1}−r} ⊕ I_{n−s_{i−1}})∥^{2}.

Using the above inequalities and the relations (3.17), (3.18) we have

∑_{t=s_{i−1}+1}^{s_{i}} ∥x_{t}^{(q′_{i})}∥^{2} ≤ ∑_{t=s_{i−1}+1}^{s_{i}} [ ∏_{k=1}^{m} ∏_{l=t+1}^{n} ν_{kl}] · ∥x̄_{t}^{(w_{t+1})}∥^{2} ≤

≤ L′_{M} · ∑_{t=s_{i−1}+1}^{s_{i}} [ ∏_{k=1}^{m} ∏_{l=t+1}^{n} ν_{kl}] · ∥x̄_{t}^{(w_{t+1})}(I_{s_{i−1}} ⊕ Θ_{n_{i}} ⊕ I_{n−s_{i}})∥^{2} ≤ L′_{M} ·

· ∑_{t=s_{i−1}+1}^{s_{i}} [ ∏_{k=1}^{m} ∏_{l=t+1}^{n} ν_{kl}] · [∏_{r=1}^{m} cosh ϑ_{rt}]^{2} · [(1 + β) · ∥x_{t}^{(1)}(Θ_{s_{i}} ⊕ I_{n−s_{i}})∥^{2}+

+ [∏_{j=1}^{m} ν_{jt}] · (1 + \frac{1}{β}) · \frac{1}{2} · S^{2}(Ā^{(w_{t})}) · ∑_{r=1}^{s_{i−1}} si^{2}(ϑ_{rt})] ≤

≤ [∏_{i=1}^{M} ν_{h_{i}}] · max_{s_{i−1}+1≤t≤s_{i}} [∏_{r=1}^{m} cosh ϑ_{rt}]^{2} · \frac{1}{2} · L′_{M} · [(1 + β) · Γ_{i}+

+ (1 + \frac{1}{β}) · S^{2}(A) · ∑_{t=s_{i−1}+1}^{s_{i}} ∑_{r=1}^{s_{i−1}} si^{2}(ϑ_{rt})] ,

which proves (ii). In our final estimates we shall need the bound

∏_{i=1}^{M} ν_{h_{i}} ≤ P_{M},

where P_{M} = 2·C′_{M} is obtained from the proof of Lemma 2.6, and the following auxiliary result. Lemma 3.6 If the assumptions AA1 and AA2 hold, then

max { max_{1≤t≤m} ∏_{r=m+1}^{n} cosh^{2} ϑ_{tr}, max_{m<t≤n} ∏_{r=1}^{m} cosh^{2} ϑ_{rt}} ≤ C_{H},  (3.19)

where

C_{H} = \frac{1}{1 − \frac{C_{M}^{2}}{18·M·min\{m,n−m\}}} .  (3.20)

Proof From Lemma 2.1, Lemma 2.5 and the assumption AA1 we have

cosh^{2} ϑ_{h_{i}} ≤ \frac{1}{1 − (\frac{C_{M} ·S(A)}{3·\sqrt{2}·δ})^{2}} ≤ \frac{1}{1 − \frac{C_{M}^{2}}{18} · \frac{1}{M^{2}}} , 1 ≤ i ≤ M.

Using induction with respect to r we easily obtain

∏_{r=m+1}^{n} cosh^{2} ϑ_{tr} ≤ \frac{1}{1 − (n − m) · \frac{C_{M}^{2}}{18·M^{2}}} = \frac{1}{1 − \frac{C_{M}^{2}}{18·M·m}} , 1 ≤ t ≤ m,

∏_{r=1}^{m} cosh^{2} ϑ_{rt} ≤ \frac{1}{1 − m · \frac{C_{M}^{2}}{18·M^{2}}} = \frac{1}{1 − \frac{C_{M}^{2}}{18·M·(n−m)}} , m < t ≤ n.

Hence

max \{ max_{1≤t≤m} ∏_{r=m+1}^{n} cosh^{2} ϑ_{tr}, max_{m<t≤n} ∏_{r=1}^{m} cosh^{2} ϑ_{rt}\} ≤ \frac{1}{1 − \frac{C_{M}^{2}}{18·M·min\{m,n−m\}}} .

Finally, we state our main theorem.

Theorem 3.7 Let the sequence A^{(1)} = A, A^{(2)}, … be generated by applying to (A, J) the J–symmetric Jacobi method defined by a strategy which is equivalent to the row–cyclic one. If the assumptions AA1 and AA2 hold, then

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

Proof Using Lemma 3.4 we obtain

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

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

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

+ ∑_{i=1}^{w} Υ_{i} [(1 + γ) · S^{2}(A_{ii}^{(q′_{i})}) + (1 + \frac{1}{γ}) · S^{2}(A^{(q′_{i})}) · ∑_{(t,r)∈G_{i}} si^{2}(ϑ_{tr})] +

+ ∑_{i=w+1}^{p−1} [(1 + γ) · S^{2}(A_{ii}^{(q′_{i})}) + (1 + \frac{1}{γ}) · S^{2}(A^{(q′_{i})}) · ∑_{(t,r)∈G_{i}} si^{2}(ϑ_{tr})]

≤ (1 + γ) · Ω_{1} + (1 + \frac{1}{γ}) · Ω_{2},

where

Ω_{1} = ∑_{i=1}^{w} Υ_{i} · S^{2}(A_{ii}^{(q′_{i})}) + ∑_{i=w+1}^{p} S^{2}(A_{ii}^{(q′_{i})})

Ω_{2} = ∑_{i=1}^{w} Υ_{i} · S^{2}(A^{(q′_{i})}) · ∑_{(t,r)∈G_{i}} si^{2}(ϑ_{tr}) + ∑_{i=w+1}^{p−1} S^{2}(A^{(q′_{i})}) · ∑_{(t,r)∈G_{i}} si^{2}(ϑ_{tr}).

Using the relations (3.13)–(3.16), Lemma 2.7, Lemma 3.5 and Lemma 3.6 we obtain

Ω_{2} ≤ P_{M} · C_{H} · S^{2}(A) · ∑_{i=1}^{p−1} ∑_{(t,r)∈G_{i}} si^{2}(ϑ_{tr}) ≤ P_{M} · C_{H} · K_{M} · \frac{S^{4}(A)}{δ^{2}},

and

Ω_{1} ≤ Ω_{M}(A) · ∑_{i=1}^{w} Υ_{i} · [ ∏_{k=1}^{s_{i−1}} ∏_{l=m+1}^{n} ν_{kl}] · [(1 + β) · Γ_{i}+

+ (1 + \frac{1}{β}) · S^{2}(A) · ∑_{t=s_{i−1}+1}^{s_{i}} ∑_{r=1}^{s_{i−1}} si^{2}(ϑ_{rt})] +

+Ω_{M}(A) · P_{M} · ∑_{i=w+1}^{p} { max_{s_{i−1}+1≤t≤s_{i}} [∏_{r=1}^{m} cosh ϑ_{rt}]^{2} · [(1 + β) · Γ_{i}+

+ (1 + \frac{1}{β}) · S^{2}(A) · ∑_{t=s_{i−1}+1}^{s_{i}} ∑_{r=1}^{s_{i−1}} si^{2}(ϑ_{rt})]\}

≤ P_{M} · C_{H} · Ω_{M}(A) · ∑_{i=1}^{p} [(1 + β) · Γ_{i}+

+ (1 + \frac{1}{β}) · S^{2}(A) · ∑_{t=s_{i−1}+1}^{s_{i}} ∑_{r=1}^{s_{i−1}} si^{2}(ϑ_{rt})] .

Choosing an optimal β and using Lemma 2.7 we obtain

∑_{i=1}^{p} [(1 + β) · Γ_{i} + (1 + \frac{1}{β}) · S^{2}(A) · ∑_{t=s_{i−1}+1}^{s_{i}} ∑_{r=1}^{s_{i−1}} si^{2}(ϑ_{rt})] ≤

≤ (1 + β) · ∑_{i=1}^{p} Γ_{i} + (1 + \frac{1}{β}) · S^{2}(A) · ∑_{i∈M_{1}} si^{2}(ϑ_{i}) ≤

≤ S^{2}(A) · [(1 + β) + (1 + \frac{1}{β}) · K_{M} · \frac{S^{2}(A)}{δ^{2}}]

≤ S^{2}(A) · (1 + \sqrt{K_{M}} · \frac{S(A)}{δ})^{2}.

Using the relations (3.15) and (3.16) we obtain

Ω_{1} ≤ P_{M} · C_{H} · L′_{M} · (L_{M} · C_{M})^{2} · \frac{S^{4}(A)}{δ^{2}} · \frac{(1 + \sqrt{K_{M}} · \frac{S(A)}{δ})^{2}}{1 + 2 · (L_{M} · C_{M} · \frac{S(A)}{δ})^{2}}

≤ P_{M} · C_{H} · Ω̄_{1} · \frac{S^{4}(A)}{δ^{2}},

where

Ω̄_{1} = L′_{M} · (L_{M} · C_{M})^{2} · sup_{0<x≤ \frac{1}{M}} \frac{(1 + \sqrt{K_{M}} · x)^{2}}{1 + 2 · (L_{M} · C_{M} · x)^{2}} .  (3.21)

Finally, we have

S^{2}(A^{(N+1)}) ≤ (1 + γ) · Ω_{1} + (1 + \frac{1}{γ}) · Ω_{2}
≤ P_{M} · C_{H} · \{(1 + γ) · Ω̄_{1} + (1 + \frac{1}{γ}) · K_{M} \} · \frac{S^{4}(A)}{δ^{2}},

and optimal choice of γ > 0 yields

S^{2}(A^{(N+1)}) ≤ P_{M} · C_{H} · (\sqrt{Ω̄_{1}} + \sqrt{K_{M}})^{2} · \frac{S^{4}(A)}{δ^{2}}.  (3.22)

To obtain sharper bound we first consider the case when the spectrum of JA contains an eigenvalue with multiplicity greater than two. In that case m ≥ 3 or n − m ≥ 3. Hence M ≥ 3 and for the constants C_{M}, P_{M}, K_{M}, … we can obtain somewhat smallerbounds, i.e. C_{M} < 1.04, P_{M} < 1.97, K_{M} < 0.12 and C_{H} can be bounded by

C_{H} ≤ \frac{1}{1 − \frac{C_{M}^{2}}{54}} .

Using (3.21) and (3.22) we obtain

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

If all multiplicities in the spectrum of JA are at most two (which includes the case M = 2) then we can get much sharper bound using Lemma 3.4 and the fact that S(A_{pp}^{(N+1)}) = 0. We obtain

S^{2}(A^{(N+1)}) ≤ Ω_{2}

which implies

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

This completes the proof of Theorem 3.7.

4 Numerical Examples

We shall demonstrate the quadratic convergence of the J–symmetric Jacobi method on some examples from [13]. In the following tables we have displayed the evolution of the sequence (S(A^{(k·N+1)}), k ≥ 1) during 7 sweeps and the asymptotic assumption AA1 for each test matrix.

1. The oscillator ladder matrix (Example 5.3 from [13])

AA1  k S(A^{(k·N+1)}) <
1 4.3
2 2.6 · 10^{−5}
S(A^{(k·N+1)}) < 8.2 · 10^{−8} 3 6.5 · 10^{−6}
4 1.2 · 10^{−6}
5 2.7 · 10^{−10}
6 2.1 · 10^{−21}
7 1.3 · 10^{−48}

2. Random matrix (Example 5.1 from [13])

AA1  k S(A^{(k·N+1)}) <
1 1.2
2 7.6 · 10^{−1}
S(A^{(k·N+1)}) < 3.9 · 10^{−8} 3 1.7 · 10^{−1}
4 4.8 · 10^{−3}
5 6.7 · 10^{−7}
6 1.7 · 10^{−14}
7 1.4 · 10^{−28}

3. A is perturbed random dyadic 40 × 40 matrix, m = 20, and the spectrum of JA contains two clusters of width ≃ 10^{−13} with 4 eigenvalues each, and the rest of the spectrum is well separated.

AA1  k S(A^{(k·N+1)}) <
1 14
2 3.9
S(A^{(k·N+1)}) < 0.9 · 10^{−15} 3 7.7 · 10^{−1}
4 1.8 · 10^{−1}
5 1.4 · 10^{−2}
6 1.1 · 10^{−6}
7 2.8 · 10^{−13}
8 5.4 · 10^{−15}
9 1.9 · 10^{−21}
10 1.4 · 10^{−42}
11 2.3 · 10^{−114}
12 5.2 · 10^{−247}
13 7.6 · 10^{−494}

The presence of clusters spoiled the quadratic convergence during the eighth and nineth sweep. This behavior is understood since we could apply a similar technique as in [6]. However, the proofs would be even more complicated than those in the case of multiple eigenvalues.

References

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

[2] J. Demmel and K. Veselić: Jacobi’s Method is More Accurate than QR. Courant Institute of Mathematical Sciences, Department of Computer Science, New York University, 1989

[3] Z. Drmač: The Eigenvalue Problem for J–symmetric Matrices. M. S. Thesis, Department of Mathematics, University of Zagreb, YU-41001 Zagreb, P. O. Box 187, Yogoslavia, 1991. ( In Croatian. )

[4] V. Hari: On Cyclic Jacobi Methods for the Positive Definite Generalized Eigenvalue Problem. University of Hagen 1984.

[5] V. Hari: On Pairs of Almost Diagonal Matrices. Linear Algebra and Its Applications 148 (1991) 193—223.

[6] V. Hari: On Sharp Quadratic Convergence Bounds for the Serial Jacobi Methods. Technical Report, Department of Mathematics, University of Zagreb YU-41001 Zagreb, P.O. Box 187, Yugoslavia, 1990.

[7] H. P. M. Van Kempen: On the Quadratic Convergence of the Serial Cyclic Jacobi Method, Numerische Mathematik 9 (1966) 19-22.

[8] 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.

[9] N. H. Rhee and V. Hari: On the Global and Cubic Convergence of a Quasi–Cyclic Jacobi Method. Techical Report, 1990

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

[11] A. Schönhage: Zur Konvergenz des Jacobi–Verfahrens. Numerische Mathematik 3 (1961) 374-380.

[12] I. Slapničar and V. Hari: On the Quadratic Convergence of the Falk– Langemeyer Method for Definite Matrix Pairs. SIAM J. MAA, Vol 12, Issue 01, 01/91.

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

[14] J. H. Wilkinson: Note on the Quadratic convergence of the Cyclic Jacobi Process. Numerische Mathematik 4 (1962) 296-300.

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