ON SCALED ALMOST DIAGONAL HERMITIAN MATRIX PAIRS

VJERAN HARI^{∗} AND ZLATKO DRMAČ^{†}

Abstract. This paper contains estimates concerning the block structure of Hermitian matrices H and M, which make a scaled diagonally dominant definite pair. The obtained bounds are expressed in terms of relative gaps in the spectrum of the pair (H, M) and norms of certain blocks of the matrices DHD and DMD, where D is either [|diag(H)|]^{− \frac{1}{2}} or [diag(M)]^{− \frac{1}{2}} . If either of the matrices H, M is diagonal, the new results assume simple and applicable form. For scaled diagonally dominant Hermitian matrices, the new estimates compare favourably with the existing ones for accurate location of the smallest eigenvalues.

Key words. almost diagonal matrices, scaled matrices, eigenvalue location

AMS subject classifications. 65F15, 65G05

0. Introduction. An almost diagonal Hermitian matrix has several important properties. First, its diagonal elements approximate its eigenvalues with an error which is quadratic in respect to the average off-diagonal element. Second, in the case of multiple eigenvalues, the matrix has a special block structure: those off-diagonal elements which link the diagonals which approximate the same eigenvalue are quadratically small. Hence, if a diagonalization method is applied to such a matrix, then this property has impact on the rate of convergence of the method and on the accuracy of the computed eigenvalues/eigenvectors (cf. [7, 14, 8]). These properties of an almost diagonal matrix have several generalizations [6, 5, 7, 4, 9], especially to the pairs of almost diagonal matrices. However, all these results make use of the absolute gaps in spectrum and are therefore less satifactory in the case of close eigenvalues.

In this paper we derive appropriate estimates for a definite pair (H, M) of Hermitian matrices which are almost diagonal in the scaled sense as defined in [1]. The obtained bounds depend on the relative gaps in spectrum, hence the new results are especially applicable when the eigenvalues of (H, M) cluster around the origin. The results are simplified provided H or M is diagonal. For example, if M = I_{n} and H = (h_{ij}) is Hermitian with h_{11} ≥ ⋯ ≥ h_{nn}, then for the nonincreasingly ordered eigenvalues of H we obtain

|h_{ii} − λ_{i}|/|λ_{i}| ≤ (C/γ) ω^{2}, 1 ≤ i ≤ n, C of order unity,

provided that ω < γ/4. Here

ω = ∥(diag H)^{−1/2}(H − diag H)(diag H)^{−1/2}∥_{2}, γ = min_{λ_{i}≠λ_{j}} |λ_{i} − λ_{j}|/(|λ_{i}| + |λ_{j}|).

The estimates of this type have already been derived for skew–Hermitian matrices [10] and for Hermitian positive definite matrix pairs [3]. The estimates presented in this paper have nice applications in the quadratic convergence theory of scaled iterates by Hermitian Jacobi methods.

∗ Department of Mathematics, University of Zagreb, Bijenička 30, 10000 Zagreb, Croatia. ( hari@math.hr ). The research of this author was supported by Croatian Ministry of Science grant No. 1-01-252.

† Department of Computer Science, University of Colorado, Boulder CO 80309–0430, USA. (zlatko@cs.colorado.edu). The research of this author was supported by National Science Foundation grant ASC–9357812, and Department of Energy Grant DE–FG03–94ER25215.

The paper is divided into three sections. In Section 1 we introduce notation and present some known results on almost diagonal and on scaled diagonally dominant matrices. In Section 2 we derive new estimates for the scaled diagonally dominant definite matrix pairs. Finally, in Section 3 we apply the new results to a single Hermitian matrix and provide two examples.

1. A pair of almost diagonal matrices. Consider the generalized eigenvalue problem

Hx = λMx, x ≠ 0, (1.1)

with Hermitian H and Hermitian positive definite M, both of order n. Let the eigenvalues of the pair (H, M), that is of the problem (1.1), be ordered nonincreasingly,

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

where s_{p} = n. Then for each 1 ≤ i ≤ p, n_{i} = s_{i} − s_{i−1}, (s_{0} =^{def} 0) is the multiplicity of λ_{s_{i}}, respectively. For the pair (H, M) we assume

\frac{h_{11}}{m_{11}} ≥ \frac{h_{22}}{m_{22}} ≥ ⋯ ≥ \frac{h_{nn}}{m_{nn}} , (1.3)

where H = (h_{ij}), M = (m_{ij}). To get such arrangement one can apply to H and M the congruence transformation with a suitably chosen permutation matrix. According to the partition n = n_{1} + ⋯ + n_{p} we define block matrix partition

X = (x_{ij}) = [ \begin{matrix}X_{11} & ⋯ & X_{1p} \\ ⋮ & ... & ⋮ \\ X_{p1} & ⋯ & X_{pp} \end{matrix} ] , X_{ii} ∈ C^{n_{i}×n_{i}}, 1 ≤ i ≤ p.

In order to move the block X_{ii} to the (1, 1) - position we make use of the permutation matrices P_{i}, defined by

P_{1} = I_{n}, P_{i} = [e_{s_{i−1}+1}, …, e_{s_{i}}, e_{1}, …, e_{s_{i−1}}, e_{s_{i}+1}, …] , 2 ≤ i ≤ p, (1.4)

where I_{n} = [e_{1}, …, e_{n}] is the identity matrix. Then

P_{i}^{∗}XP_{i} = [ \begin{matrix}π_{i}(X) & τ_{i}(X) \\ τ_{i}^{c}(X) & π_{i}^{c}(X) \end{matrix} ] \begin{matrix}\}n_{i} \\ \}n − n_{i} \end{matrix} ,

with

\begin{matrix}π_{i}(X) = X_{ii}, & τ_{i}(X) = [ X_{i1} … X_{i,i−1} X_{i,i+1} …] , \\ τ_{i}^{c}(X) = [ X_{1i} ; ⋮ ; X_{i−1,i} ; X_{i+1,i} ; ⋮ ] , & π_{i}^{c}(X) = [ \begin{matrix}X_{11} & ⋯ & X_{1,i−1} & X_{1,i+1} & ⋯ \\ ⋮ & ... & ⋮ & ⋮ & ⋮ \\ X_{i−1,1} & ⋯ & X_{i−1,i−1} & X_{i−1,i+1} \\ X_{i+1,1} & ⋯ & X_{i+1,i−1} & X_{i+1,i+1} \\ ⋮ & ⋯ & ⋯ & ⋯ & ... \end{matrix} ] . \end{matrix}

In the sequel we use the following notation: Ω(X) = X − diag(X) is the off-diagonal part of X, π(X) = diag(X_{11}, …, X_{pp}) is the block-diagonal and τ(X) = X − π(X) is the off-block-diagonal part of X. By ∥X∥_{F}, ∥X∥_{2} and ∥X∥_{∞} are denoted the Frobenius, the spectral (operator) and the infinity norm of X. As usual, X^{∗} = \overline{X}^{T}.

1.1. Structure of an almost diagonal pair. Let λ(H, M) denote the spectrum of (H, M). Then for each 1 ≤ i ≤ p

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

is the (absolute) gap or separation of λ_{s_{i}} from λ(H, M) \ {λ_{s_{i}}}. The minimum separation in the spectrum λ(H, M) is δ, where

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

Let M = Δ_{M}M_{S}Δ_{M} with Δ_{M} = [diag (M)]^{1/2} . The following result from [7, Theorem 3.1] reveals the special structure of an almost diagonal pair (H, M).

(R1) If ∥Ω(Δ_{M}^{−1}HΔ_{M}^{−1} − λ_{s_{i}}M_{S})∥_{2} ≤ \frac{1}{3}δ_{i}, 1 ≤ i ≤ p, then

∥π_{i} (Δ_{M}^{−1}HΔ_{M}^{−1} − λ_{s_{i}}M_{S}))∥_{F} ≤ \frac{3}{δ_{i}} ∥τ_{i} (Δ_{M}^{−1}HΔ_{M}^{−1} − λ_{s_{i}}M_{S}))∥_{F}^{2} , 1 ≤ i ≤ p.

In the case M = I_{n} this result has the refinement [7] which provides information on the location of the eigenvalues of H:

(R2) If ∥Ω(H)∥_{2} ≤ \frac{δ}{3}, then ∥H_{ii} − λ_{s_{i}}I_{n_{i}}∥_{F} ≤ \frac{1.32}{δ_{i}} ∑_{j≠i^{j=1}}^{p} ∥H_{ij}∥_{F}^{2} , 1 ≤ i ≤ p.

The both results played essential roles in deriving sharp quadratic convergence estimates for appropriate Jacobi methods (see [5, 8], [11, 4]). Note that for tiny δ_{i} the appropriate bounds in (R1) and (R2) become large and therefore useless.

1.2. Pair of scaled diagonally dominant matrices. Here we recall notion of scaled diagonally dominant matrices and matrix pairs from [1], and state some appropriate results. If A = D + N, where D is diagonal and N has zero diagonal, then A = (a_{ij}) is α–diagonally dominant with respect to a norm ∥ · ∥ if ∥N∥ ≤ α min_{1≤i≤n} |a_{ii}|, with 0 ≤ α < 1. Now, let A = D + N with |a_{ii}| = 1, 1 ≤ i ≤ n and let Δ_{1}, Δ_{2} be arbitrary nonsingular diagonal matrices. Then B = Δ_{1}AΔ_{2} is α–scaled diagonally dominant ( α–s.d.d.) with respect to a given norm, if A is α–diagonally dominant with respect to that norm. If B is Hermitian, it is presumed that Δ_{1} = Δ_{2}. Note that an α–s.d.d matrix has nonzero diagonal elements.

The pair (H, M) of Hermitian matrices is (α, β)–scaled diagonally dominant definite^{1} ( (α, β)–s.d.d.d.) with respect to a given norm if H is α–s.d.d., M is β–s.d.d., both with respect to that norm, and M is positive definite. If H is positive definite as well, (H, M) is (α, β)–s.d.d. positive definite ((α, β)–s.d.d.p.d.).

The spectral absolute value [H^{2}]^{\frac{1}{2}} of a Hermitian matrix H, is denoted as in [15] by ||||H||||. The standard absolute value of H is denoted by |H|, |H| = (|h_{ij}|). The following result [15, Theorem 2.1] has nice applications for (η_{H}, η_{M})–s.d.d.d. pairs.

(R3) Let (H, M) be a pair of Hermitian matrices such that M is positive definite. Let δH and δM be Hermitian matrices satisfying

| x^{∗}δHx |≤ η_{H}x^{∗}||||H||||_{M}x, η_{H} < 1 and | x^{∗}δMx |≤ η_{M}x^{∗}Mx, η_{M} < 1,

1 this is a slight modification of the definition from [1]

for all x ∈ C^{n}. Here ||||H||||_{M} = Z||||Z^{−1}HZ^{−∗}||||Z^{∗} where Z is any square matrix satisfying M = ZZ^{∗}. If λ_{1} ≥ ⋯ ≥ λ_{n} and λ′_{1} ≥ ⋯ ≥ λ′_{n} are the eigenvalues of (H, M) and (H +δH, M +δM), respectively, then for any 1 ≤ i ≤ n, either λ_{i} = λ′_{i} = 0 or

\frac{1 − η_{H}}{1 + η_{M}} ≤ \frac{λ′_{i}}{λ_{i}} ≤ \frac{1 + η_{H}}{1 − η_{M}} .

We recall yet the result [2, Proposition 2.10] which refines [1, Proposition 2] and also (R3) for the pair (diag(H), I_{n}) with perturbation (Ω(H), 0), provided that H is positive definite:

(R4) If H is positive definite and H_{S} = Δ_{H}^{−1}HΔ_{H}^{−1}, Δ_{H} = [diag(H)]^{\frac{1}{2}} , then

1 − ∥Ω(H_{S})∥_{2} ≤ λ_{min}(H_{S}) ≤ \frac{λ_{i}}{h_{ii}} ≤ λ_{max}(H_{S}) ≤ 1 + ∥Ω(H_{S})∥_{2}, 1 ≤ i ≤ n,

where λ_{min}(H_{S}) and λ_{max}(H_{S}) are the smallest and the largest eigenvalue of H_{S}, respectively.

The results (R3) and (R4) will be used in Section 2 and Section 3, respectively.

2. Scaled almost diagonal matrix pairs. Here we derive a result similar to (R1), but using scaled matrices and relative gaps in λ(H, M). Relative gaps are defined in a number of ways ( cf. [1], [15, 12],[10]). For technical reasons we use the following ( relative ) measure of eigenvalue separation

Definition 2.1. Let λ_{s_{i}}, 1 ≤ i ≤ p, be the eigenvalues of the pair (H, M), satisfying the condition (1.2). Relative gap of λ_{s_{i}} from λ(H, M) \ {λ_{s_{i}}} is

γ_{i} = min_{j≠i^{1≤j≤p}} \frac{| λ_{s_{i}} − λ_{s_{j}} |}{| λ_{s_{i}} | + | λ_{s_{j}} |}.

The minimum relative gap in λ(H, M) is

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

Note that γ_{i} ≤ 1, 1 ≤ i ≤ p and γ_{i} = 1 if either λ_{s_{i}} = 0 or λ_{s_{i}} is a single point of λ(H, M) in (−∞, 0) or (0, ∞).

The following theorem generalizes and improves [3, Theorem 2.24] which has been formulated for (α, α)–s.d.d.p.d. pairs.

Theorem 2.2. Let (H, M) be an (α, β)–s.d.d.d. pair satisfying the condition (1.3). Let H = Δ_{H}H_{S}Δ_{H}, M = Δ_{M}M_{S}Δ_{M} with Δ_{H} = (|diag (H)|)^{1/2}, Δ_{M} = (diag (M))^{1/2}. If

\frac{α + β}{1 − α} < \frac{1}{3} γ, (2.1)

then for each 1 ≤ i ≤ p holds

(i)  ∥π_{i} (H_{S} − λ_{s_{i}}Δ_{H}^{−1}MΔ_{H}^{−1}) ∥_{F} ≤ \frac{4}{γ_{i}} ∥τ_{i} (H_{S} − λ_{s_{i}}Δ_{H}^{−1}MΔ_{H}^{−1}) ∥_{F}^{2} ,
(ii)  ∥π_{i} (H − λ_{s_{i}}M) ∥_{F} ≤ \frac{4}{γ_{i}} ∥τ_{i} (HΔ_{H}^{−1} − λ_{s_{i}}MΔ_{H}^{−1}) ∥_{F}^{2} ,

(iii)  ∥π_{i} (λ_{s_{i}}^{−1}Δ_{M}^{−1}HΔ_{M}^{−1} − M_{S}) ∥_{F} ≤ \frac{2}{γ_{i}} ∥τ_{i} (λ_{s_{i}}^{−1}Δ_{M}^{−1}HΔ_{M}^{−1} − M_{S}) ∥_{F}^{2} ,
(iv)  ∥π_{i} (λ_{s_{i}}^{−1}H − M) ∥_{F} ≤ \frac{2}{γ_{i}} ∥τ_{i} (λ_{s_{i}}^{−1}HΔ_{M}^{−1} − MΔ_{M}^{−1}) ∥_{F}^{2} .

Proof. By the assumption we have

H_{S} = J_{n} + Ω(H_{S}), ∥Ω(H_{S})∥_{2} ≤ α < 1,
M_{S} = I_{n} + Ω(M_{S}), ∥Ω(M_{S})∥_{2} ≤ β < 1,

where J_{n} = I_{k} ⨁ −I_{n−k} for some 0 ≤ k ≤ n. Using substitutions y = Δ_{H}x and z = Δ_{M}x we obtain for arbitrary x ∈ C^{n}

(2.2) | x^{∗}Ω(H)x | = | x^{∗}Δ_{H}Ω(H_{S})Δ_{H}x |=| y^{∗}Ω(H_{S})y |≤ αy^{∗}y = αx^{∗}Δ_{H}^{2}x,
(2.3) | x^{∗}Ω(M)x | = | x^{∗}Δ_{M}Ω(M_{S})Δ_{M}x |=| z^{∗}Ω(M_{S})z |≤ βz^{∗}z = βx^{∗}Δ_{M}^{2}x.

Consider (H, M) as the perturbed pair (Δ_{H}J_{n}Δ_{H}, Δ_{M}^{2}). Since

||||Δ_{H}J_{n}Δ_{H}||||_{Δ_{M}^{2}} = Δ_{M}||||Δ_{M}^{−1}Δ_{H}J_{n}Δ_{H}Δ_{M}^{−1}||||Δ_{M} = Δ_{H}^{2},

the relations (2.2) and (2.3) imply that the result (R3) can be applied to the pair (Δ_{H}J_{n}Δ_{H}, Δ_{M}^{2}) with (Ω(H), Ω(M)) as perturbation. One obtains

\frac{1 − α}{1 + β} ≤ \frac{λ_{s_{i}}}{h_{jj}/m_{jj}} ≤ \frac{1 + α}{1 − β}, j ∈ S_{i}, 1 ≤ i ≤ p,

where S_{i} = { j; s_{i−1} + 1 ≤ j ≤ s_{i}}, 1 ≤ i ≤ p. Hence

\frac{| h_{jj}/m_{jj} − λ_{s_{i}} |}{| λ_{s_{i}} |} ≤ \frac{α + β}{1 − α} , j ∈ S_{i}, 1 ≤ i ≤ p. (2.4)

Now, consider the intervals

D_{i} = \{ξ : \frac{| ξ − λ_{s_{i}} |}{| λ_{s_{i}} |} < \frac{γ_{i}}{3} \} , 1 ≤ i ≤ p.

Since for ξ ∈ D_{k}, k ≠ i

(2.5)  \frac{|ξ − λ_{s_{i}}|}{|λ_{s_{i}}|} ≥ \frac{|λ_{s_{i}} − λ_{s_{k}}|}{|λ_{s_{i}}| + |λ_{s_{k}}|} (1 + \frac{|λ_{s_{k}}|}{|λ_{s_{i}}|}) − \frac{|ξ − λ_{s_{k}}|}{|λ_{s_{k}}|} \frac{|λ_{s_{k}}|}{|λ_{s_{i}}|}
≥ max\{γ_{i}, γ_{k}\} + \frac{2}{3} \frac{|λ_{s_{k}}|}{|λ_{s_{i}}|} max\{γ_{i}, γ_{k}\} ≥ max\{γ_{i}, γ_{k}\},

we see that ξ ∉ D_{i}. Thus, D_{i}, 1 ≤ i ≤ p are mutually disjoint. If (2.1) holds, then the relation (2.4) implies h_{jj}/m_{jj} ∈ D_{i}, j ∈ S_{i}, 1 ≤ i ≤ p.

Let i ∈ {1, …, p} be fixed. Consider C_{i} = H − λ_{s_{i}}M. If P_{i} is as in (1.4), then

P_{i}^{T} C_{i}P_{i} = [ \begin{matrix}π_{i}(C_{i}) & τ_{i}(C_{i}) \\ τ_{i}^{c}(C_{i}) & π_{i}^{c}(C_{i}) \end{matrix} ]

has rank n − n_{i} and the rank argument (cf. [7, 17]) implies

π_{i}(C_{i}) = τ_{i}(C_{i}) [π_{i}^{c}(C_{i})]^{−1} τ_{i}^{c}(C_{i}), (2.6) provided that π_{i}^{c}(C_{i}) is nonsingular.

Now we prove the assertions (i)—(iv) of the theorem.

(i) We use π_{i}(Δ_{H}^{−1}) and π_{i}^{c}(Δ_{H}^{−1}) as scaling matrices for modifying (2.6). We obtain

π_{i}(C̃_{i}) = τ_{i}(C̃_{i}) [π_{i}^{c}(C̃_{i})]^{−1} τ_{i}^{c}(C̃_{i}) (2.7)

with C̃_{i} = Δ_{H}^{−1}C_{i}Δ_{H}^{−1}. Note that π_{i}^{c}(C̃_{i}) = π_{i}^{c}(Δ_{H}^{−1})π_{i}^{c}(C_{i})π_{i}^{c}(Δ_{H}^{−1}) is nonsingular if and only if π_{i}^{c}(C_{i}) is nonsingular, hence (2.6) holds if and only if (2.7) holds. Let μ be the smallest by modulus eigenvalue of π_{i}^{c}(C̃_{i}). If we show

| μ |> \frac{γ_{i}}{4} , (2.8)

then (2.7) holds with ∥ [π_{i}^{c}(C̃_{i})]^{−1} ∥_{2} < 4/γ_{i}. Then applying the Frobenius matrix

norm to (2.7) and using τ_{i}^{c}(C̃_{i}) = τ_{i}(C̃_{i})^{∗} we obtain the assertion (i) of the theorem. Let π_{i}^{c}(C̃_{i})w = μw, w ≠ 0. This can be written as π_{i}^{c}(C_{i})w′ = μπ_{i}^{c}(Δ_{H}^{2})w′, w′ = π_{i}^{c}(Δ_{H}^{−1})w ≠ 0. Hence

[π_{i}^{c} (Δ_{H}(J_{n} − μI_{n})Δ_{H}) + Ω (π_{i}^{c}(H))] w′ = λ_{s_{i}} [π_{i}^{c}(Δ_{M}^{2}) + Ω (π_{i}^{c}(M))] w′,

implying that λ_{s_{i}} is an eigenvalue of the pair (π_{i}^{c}(H − μΔ_{H}^{2}) , π_{i}^{c}(M)), which depends on μ. If we let y = π_{i}^{c}(Δ_{H})x and z = π_{i}^{c}(Δ_{M})x, we have for arbitrary x ∈ C^{n−n_{i}}

| x^{∗}Ω (π_{i}^{c}(H)) x | = | y^{∗}Ω (π_{i}^{c}(H_{S})) y |≤ ∥Ω (π_{i}^{c}(H_{S})) ∥_{2}y^{∗}y ≤ ∥Ω(H_{S})∥_{2}y^{∗}y
≤ αy^{∗}y = αx^{∗}π_{i}^{c}(Δ_{H}^{2})x = \frac{α}{1 − |μ|}x^{∗} (1 − |μ|) π_{i}^{c}(Δ_{H}^{2})x
≤ \frac{α}{1 − |μ|}x^{∗}π_{i}^{c} (Δ_{H}|J_{n} − μI_{n}|Δ_{H}) x
= \frac{α}{1 − |μ|}x^{∗}||||π_{i}^{c} (Δ_{H}(J_{n} − μI_{n})Δ_{H}) ||||_{π_{i}^{c}(Δ_{M}^{2} )}x,
| x^{∗}Ω (π_{i}^{c}(M)) x | = | z^{∗}Ω (π_{i}^{c}(M_{S})) z |≤ ∥Ω (π_{i}^{c}(M_{S})) ∥_{2}z^{∗}z ≤ ∥Ω(M_{S})∥_{2}z^{∗}z
≤ βz^{∗}z = βx^{∗}π_{i}^{c}(Δ_{M}^{2})x.

Here we have used the inequality (1−|μ|)I_{n} ≤ |J_{n}−μI_{n}| and the fact that the spectral norm of a submatrix is not larger than the norm of the whole matrix. The latest two relations imply that the result (R3) can be applied to (π_{i}^{c}(Δ_{H}(J_{n} − μI_{n})Δ_{H}), π_{i}^{c}(Δ_{M}^{2})) with (Ω(π_{i}^{c}(H)), Ω(π_{i}^{c}(M))) as perturbation, provided that |μ| < 1 − α. If this is the case we obtain ( since λ_{s_{i}} is an eigenvalue of (π_{i}^{c}(H − μΔ_{H}^{2}) , π_{i}^{c}(M)) )

\frac{1 − \frac{α}{1 − |μ|}}{1 + β} ≤ \frac{λ_{s_{i}}}{\frac{h_{jj}}{m_{jj}} (1 − μ̃)} ≤ \frac{1 + \frac{α}{1 − |μ|}}{1 − β} for some j ∈ ⋃_{k≠i} S_{k},

with μ̃ = μ sign(h_{jj}). Using elementary calculus one obtains

\frac{|h_{jj}/m_{jj} − λ_{s_{i}}|}{|λ_{s_{i}}|} ≤ \frac{α + β + |μ|}{1 − α − |μ|} for some j ∈ ⋃_{k≠i} S_{k}. (2.9)

By (2.5) we have | h_{jj}/m_{jj} − λ_{s_{i}} | /|λ_{s_{i}}| > γ_{i}. Hence (2.9) and (2.1) imply

γ_{i} < \frac{α + β + |μ|}{1 − α − |μ|} < \frac{(1 − α)\frac{1}{3}γ + |μ|}{1 − α − |μ|}

and we obtain |μ| > (1 − α)\frac{3γ_{i}−γ}{3(γ_{i}+1)}. Since β ≥ 0 the assumption (2.1) implies 1 − α > 3/(3 + γ). We also have 3γ_{i} − γ ≥ 2γ_{i}. Hence |μ| > γ_{i}/4.

If |μ| ≥ 1 − α one obtains straightforwardly |μ| > 3/(3 + γ) ≥ 3/4 > γ_{i}/4. Since i is arbitrary the proof of the assertion (i) is completed. (ii) Here we scale only the right-hand side of (2.6) with π_{i}^{c}(Δ_{H}^{−1}) and obtain

π_{i}(C_{i}) = τ_{i}(C_{i}Δ_{H}^{−1}) [π_{i}^{c}(C̃_{i})]^{−1} τ_{i}^{c}(Δ_{H}^{−1}C_{i}). (2.10)

By the relation (2.8) we know that ∥ [π_{i}^{c}(C̃_{i})]^{−1} ∥_{2} ≤ 4/γ_{i}. We also have [τ_{i}(C_{i}Δ_{H}^{−1})]^{∗} = τ_{i}^{c}(Δ_{H}^{−1}C_{i}). Hence, (ii) follows by applying the Frobenius norm to (2.10).

(iii) We scale (2.6) with π_{i}(Δ_{M}^{−1}) and π_{i}^{c}(Δ_{M}^{−1}) and multiply the both sides of the obtained equality by λ_{s_{i}}^{−1}. We obtain

π_{i}(C′_{i}) = τ_{i}(C′_{i}) [π_{i}^{c}(C′_{i})]^{−1} τ_{i}^{c}(C′_{i}),

where C′_{i} = λ_{s_{i}}^{−1}Δ_{M}^{−1}HΔ_{M}^{−1} − M_{S}. Let ν be an eigenvalue of π_{i}^{c}(C′_{i}), such that 1/ | ν | = ∥[π_{i}^{c}(C′_{i})]^{−1}∥_{2}. Then π_{i}^{c}(C′_{i})v = νv for some v ≠ 0. With v′ = π_{i}^{c}(Δ_{M}^{−1})v we have

π_{i}^{c}(H)v′ = λ_{s_{i}} [(ν + 1)π_{i}^{c} (Δ_{M}^{2}) + Ω (π_{i}^{c}(M))] v′, v′ ≠ 0.

Thus λ_{s_{i}} is an eigenavalue of the pair (π_{i}^{c}(H) , π_{i}^{c}(M + νΔ_{M}^{2})). As above one can show that for an arbitrary x ∈ C^{n−n_{i}}

| x^{∗}Ω (π_{i}^{c}(H)) x | ≤ αx^{∗}π_{i}^{c}(Δ_{H}^{2})x = αx^{∗}||||π_{i}^{c} (Δ_{H}J_{n}Δ_{H}) ||||_{π_{i}^{c}((1+ν)Δ_{M}^{2} )}x,
| x^{∗}Ω (π_{i}^{c}(M)) x | ≤ \frac{β}{1 + ν} x^{∗}π_{i}^{c}( (1 + ν)Δ_{M}^{2})x.

If ν > β −1 one can apply (R3) to the pair (π_{i}^{c}(Δ_{H}J_{n}Δ_{H}), (1 + ν)π_{i}^{c}(Δ_{M}^{2})) with (Ω(π_{i}^{c}(H)) , Ω(π_{i}^{c}(M))) as perturbation, to obtain

\frac{1 − α}{1 + \frac{β}{ν + 1}} < \frac{λ_{s_{i}}}{\frac{h_{jj}}{(ν + 1)m_{jj}}} < \frac{1 + α}{1 − \frac{β}{ν + 1}} for some j ∈ ⋃_{k≠i} S_{k}.

The latest relation together with the condition (2.1) implies

\frac{|h_{jj}/m_{jj} − λ_{s_{i}}|}{|λ_{s_{i}}|} < \frac{α + β + ν}{1 − α} < \frac{1}{3}γ + \frac{ν}{1 − α}.

By (2.5), we obtain

γ_{i} − \frac{1}{3}γ < \frac{ν}{1 − α}, (2.11)

implying ν > 0. Since 1/(1 − α) < 1 + γ/3, we have ν/(1 − α) < (1 + γ/3)ν. This inequality together with (2.11) implies |ν| > γ_{i}/2.

If ν < β − 1, we have | ν |> 1 − β > 1 − γ/3 > 2/3 > γ_{i}/2. Hence, in any case | ν | > γ_{i}/2. This proves (iii) since i is arbitrary.

(iv) The proof follows the lines of the proof of (ii), only Δ_{M} and the assertion (iii) are used instead of Δ_{H} and the assertion (i), respectively.

Note that any unitarily invariant matrix norm can be applied to the both sides of (2.7). In case of the spectral norm one obtains ( cf. Example 3.3 Corollary 3.2 ) the claim on the first page of the paper.

If the both matrices H and M are positive definite, we can further improve the latest result.

Corollary 2.3. Suppose the pair (H, M) is (α, β)-s.d.d.p.d. and let H_{S}, Δ_{H}, M_{S} and Δ_{M} be as in Theorem 2.2.

(a) If in (2.1) the denumerator 1 − α is replaced by 1 − β, then the constants 4 and 2 in the assertions (i), (ii) and (iii), (iv), respectively, interchange their places.

(b) If in (2.1) the denumerator 1 − α is replaced by 1 − max {α, β}, then all the assertions of Theorem 2.2 hold with the same constant 2 on the right-hand sides.

Proof. (a) The pair (M, H) is (β, α)–s.d.d.p.d. with eigenvalues λ_{s_{p}}^{−1} = ⋯ = λ_{s_{p−1}+1}^{−1} > ⋯ > λ_{s_{1}}^{−1} = ⋯ = λ_{1}^{−1} and with the appropriate gaps γ_{j}(M, H) = γ_{p+1−j}(H, M), 1 ≤ j ≤ p. Hence the assertion (iii) of Theorem 2.2 for the pair (M, H) takes form

∥π_{j}((λ_{s_{j}}^{−1})^{−1}Δ_{H}^{−1}MΔ_{H}^{−1} − H_{S})∥ ≤ \frac{2}{γ_{j}} ∥τ_{j}((λ_{s_{j}}^{−1})^{−1}Δ_{H}^{−1}MΔ_{H}^{−1} − H_{S})∥_{F}^{2} , j = p, …, 1

and this is (i) with 4 replaced by 2. In the same way, starting with the assertion (i) of Theorem 2.2, one can prove that (iii) holds with the constant 4 instead of 2. The same argument applies to the asertions (ii) and (iv) as well.

(b) The proof follows directly from the assertions (iii) and (iv) of Theorem 2.2 and the assertion (a) of this corollary.

3. Some applications. When M or H is diagonal we can use the congruence transformation with Δ_{M} or Δ_{H}, to reduce it to I_{n} or J_{n}. This leads us to the pairs (Δ_{M}^{−1}HΔ_{M}^{−1}, I_{n}) and (Δ_{H}^{−1}MΔ_{H}^{−1}, J), that is to the estimates for Hermitian and J-Hermitian matrices. We shall consider in detail only the case of Hermitian matrices. The estimates for J-Hermitian matrices can be obtained in a similar way.

Scaled almost diagonal Hermitian matrix. Let λ_{j}, 1 ≤ j ≤ n be the eigenvalues of the Hermitian matrix H ordered nonincreasingly, as indicated by the relation (1.2). We further assume the nonincreasing ordering of the diagonal elements of H. This assumption corresponds to the relation (1.3). The sets S_{i} are defined as above. Note also the definition of π and τ just before the Subsection 1.1.

Corollary 3.1. Let H be an α-s.d.d. Hermitian matrix and let H = Δ_{H}H_{S}Δ_{H}, Δ_{H} = [|diag(H)|]^{\frac{1}{2}} . If α < γ/(γ + 3), then

(i) ∑_{j∈S_{i}} | 1 − \frac{λ_{s_{i}}}{h_{jj}} |^{2} +∥Ω (π_{i}(H_{S})) ∥_{F}^{2} ≤ \frac{16}{γ_{i}^{2}} ∥τ_{i}(H_{S})∥_{F}^{4} , 1 ≤ i ≤ p,

(ii) ∑_{j=1}^{n} | 1 − \frac{λ_{j}}{h_{jj}} |^{2} +∥Ω (π(H_{S})) ∥_{F}^{2} ≤ \frac{8}{γ^{2}} ∥τ(H_{S})∥_{F}^{4} ,

(iii) ∑_{j∈S_{i}} | h_{jj} − λ_{s_{i}} |^{2} +∥Ω (π_{i}(H)) ∥_{F}^{2} ≤ \frac{4}{γ_{i}^{2}} min \{4∥τ_{i}(HΔ_{H}^{−1})∥_{F}^{4} , \frac{∥τ_{i}(H)∥_{F}^{4}}{λ_{s_{i}}^{2}} \},

1 ≤ i ≤ p.

(iv) ∑_{j=1}^{n} | h_{jj} − λ_{j} |^{2} +∥Ω (π(H)) ∥_{F}^{2} ≤ \frac{2}{γ^{2}} min \{8∥τ(HΔ_{H}^{−1})∥_{F}^{4} , \frac{∥τ(H)∥_{F}^{4}}{min_{1≤i≤p} λ_{s_{i}}^{2}} \}.

Proof. (i) The proof follows directly from Theorem 2.2 by inserting M = M_{S} = Δ_{M} = I_{n}. (ii) If we sum the left- and right- hand side of the inequality in (i) and use γ_{i} ≥ γ, ∥τ_{i}(H_{S})∥^{2} ≤ ∥τ(H_{S})∥^{2}/2 for 1 ≤ i ≤ p, we obtain (ii). (iii) The proof follows by combining the assertions (ii) and (iii) (or (ii) and (iv)) of Theorem 2.2. (iv) The proof is similar to the proof of (ii). We use (iii) and the fact that ∥τ_{i}(HΔ_{H}^{−1})∥ ≤ ∥τ(HΔ_{H}^{−1})∥, 1 ≤ i ≤ p.

If λ_{s_{i}} is simple, than the terms ∥Ω (π_{i}(H_{S})) ∥_{F}^{2} and ∥Ω (π_{i}(H)) ∥_{F}^{2} in (i) and (iii) are omitted. Similarly, if all the eigenvalues of H are simple, then ∥Ω (π(H_{S})) ∥_{F}^{2} and ∥Ω (π(H)) ∥_{F}^{2} in (ii) and (iv) are omitted. We have included in (iii) and (iv) the term containing the eigenvalue(s) λ_{s_{i}} because knowledge of rough lower bound(s) for λ_{s_{i}} may considerably improve the bound (see Example 3.3 below). If H is in addition positive definite, we can further sharpen the latest result.

Corollary 3.2. Let H be α-s.d.d. Hermitian positive definite matrix and let H = Δ_{H}H_{S}Δ_{H}, Δ_{H} = [diag(H)]^{\frac{1}{2}} . If α < γ/3 then

(i) ∑_{j∈S_{i}} | 1 − \frac{λ_{s_{i}}}{h_{jj}} |^{2} +∥Ω (π_{i}(H_{S})) ∥_{F}^{2} ≤ \frac{4}{γ_{i}^{2}} ∥τ_{i}(H_{S})∥_{F}^{4} , 1 ≤ i ≤ p,

(ii) ∑_{j=1}^{n} | 1 − \frac{λ_{j}}{h_{jj}} |^{2} +∥Ω (π(H_{S})) ∥_{F}^{2} ≤ \frac{2}{γ^{2}} ∥τ(H_{S})∥_{F}^{4} .

If α < γ/(γ + 3), then

(iii) ∑_{j∈S_{i}} | h_{jj} − λ_{s_{i}} |^{2} +∥Ω (π_{i}(H)) ∥_{F}^{2} ≤ \frac{4}{γ_{i}^{2}} min \{∥τ_{i}(HΔ_{H}^{−1})∥_{F}^{4} , \frac{∥τ_{i}(H)∥_{F}^{4}}{λ_{s_{i}}^{2}} \},

1 ≤ i ≤ p,

(iv) ∑_{j=1}^{n} | h_{jj} − λ_{j} |^{2} +∥Ω (π(H)) ∥_{F}^{2} ≤ \frac{2}{γ^{2}} min \{2∥τ(HΔ_{H}^{−1})∥_{F}^{4} , \frac{∥τ(H)∥_{F}^{4}}{min_{1≤i≤p} λ_{s_{i}}^{2}} \}.

Proof. Consider the pairs (H, I_{n}) and (I_{n}, H) and apply already derived estimates (or equivalently, use the corollaries 2.3 and 3.1).

In the following example we shall comparatively investigate to what relative accuracy the diagonals of H reveal the eigenvalues of H if the results (R2), (R4) and Corollary 3.2 are applied.

Example 3.3. Let (Cf. [3, Example 2.8])

H = [ \begin{matrix}1 & 10^{−8} & 10^{−8} \\ 10^{−8} & 10^{−6} & 10^{−11} \\ 10^{−8} & 10^{−11} & 10^{−8} \end{matrix} ] , M = I_{3}.

Since ∥Ω(H)∥_{2} ≤ ∥Ω(H)∥_{∞} = 2 · 10^{−8} the perturbation theorem for the eigenvalues of symmetric matrices (or simply the Gerschgorin theorem) implies | λ_{i} − h_{ii} | ≤ 2 · 10^{−8}. Hence the absolute gaps can be bounded from below using the formula δ_{i} ≥ min_{j, j≠i} |h_{ii} − h_{jj}| − 2 · (2 · 10^{−8}). One obtains δ_{1} > 9.999 · 10^{−1}, δ_{2} = δ_{3} = δ > 9.500 · 10^{−7}. Therefore, the result (R2) implies

| λ_{1} − h_{11} |< 1.321 · 10^{−16}, max{| λ_{2} − h_{22} |, | λ_{3} − h_{33} |} < 1.390 · 10^{−10}. (3.1)

Let r_{i} =| λ_{i} − h_{ii} | /λ_{i}, 1 ≤ i ≤ 3. Since λ_{1} > h_{11} − 1.321 · 10^{−16} and λ_{j} > h_{jj} − 1.390 · 10^{−10}, 2 ≤ j ≤ 3, the relation (3.1) implies

r_{1} < 1.322 · 10^{−16}, r_{2} < 1.31 · 10^{−4}, r_{3} < 1.410 · 10^{−2}.

Thus, only two (four) significant digits of λ_{3} (λ_{2}) can be revealed.

Let us now apply the result (R4) to H. Since

H_{S} = Δ_{H}^{−1}HΔ_{H}^{−1} = [ \begin{matrix}1 & 10^{−5} & 10^{−4} \\ 10^{−5} & 1 & 10^{−4} \\ 10^{−4} & 10^{−4} & 1 \end{matrix} ],

we have ∥Ω(H_{S})∥_{2} ≤ ∥Ω(H_{S})∥_{∞} = 2 · 10^{−4} ≡ α. Hence 1 − α < λ_{i}/h_{ii} < 1 + α, 1 ≤ i ≤ 3, implying

\frac{| λ_{i} − h_{ii} |}{λ_{i}} < \frac{2 · 10^{−4}}{1 − 2 · 10^{−4}} < 2.001 · 10^{−4}, 1 ≤ i ≤ 3.

The result (R4) enables to reveal two more digits in λ_{3} than (R2). However, for the largest eigenvalue λ_{1} the result (R2) yields better information than (R4).

Consider now the estimates based on Gerschgorin disks^{2} for DHD^{−1}, where D is a suitably chosen diagonal matrix ( see [16, Sections 2.14, 2.15] or [13, Section IV 2.2] ). In particular, if D = diag(d_{1}, 1, 1), then the smallest value of d_{1} for which the disk around 1 remains isolated from other disks is approximately 1.00000100001 · 10^{−8}. The Gerschgorin theorem applied to DHD^{−1} yields r_{1} < 2.0000021 · 10^{−16}. If D = diag(1, d_{2}, 1),, then the optimal value for d_{2} is approximately 1.02040826962 · 10^{−5} and it yields r_{2} < 1.02143 · 10^{−7}. Finally, if D = diag(1, 1, d_{3}), then the optimal value for d_{3} is again 1.02040826962 · 10^{−5} and it yields r_{3} < 1.02144 · 10^{−5}. We see that this technique yields better bounds than the result (R4) and, except for r_{1}, much better bounds than the result (R2).

Let us apply the estimates of Corollary 3.2 to H. The basic estimates | λ_{i} − h_{ii} | ≤ 2 · 10^{−8}, 1 ≤ i ≤ 3 yield the following lower bounds for the relative gaps in the spectrum of H:

γ_{1} = \frac{λ_{1} − λ_{2}}{λ_{1} + λ_{2}} > \frac{h_{11} − h_{22}− | λ_{1} − h_{11} | − | λ_{2} − h_{22} |}{h_{11} + h_{22}+ | λ_{1} − h_{11} | + | λ_{2} − h_{22} |} > 0.9999979,
γ = γ_{2} = γ_{3} = \frac{λ_{2} − λ_{3}}{λ_{2} + λ_{3}} > \frac{h_{22} − h_{33}− | λ_{2} − h_{22} | − | λ_{3} − h_{33} |}{h_{22} + h_{33}+ | λ_{2} − h_{22} | + | λ_{3} − h_{33} |} > 0.9047619.

Consider first the estimates based on Corollary 3.2 (iii). Using the above bounds for γ_{i} we obtain

| h_{11} − λ_{1} | ≤ \frac{2}{γ_{1}} min \{(10^{−10} + 10^{−8}), \frac{10^{−16} + 10^{−16}}{1 − 2 · 10^{−8}} \} < 4.00001 · 10^{−16},
| h_{22} − λ_{2} | ≤ \frac{2}{γ_{2}} min \{10^{−16} + 10^{−14}, \frac{10^{−16} + 10^{−22}}{10^{−6} − 2 · 10^{−8}} \} < 2.23264 · 10^{−14},
| h_{33} − λ_{3} | ≤ \frac{2}{γ_{3}} (10^{−16} + 10^{−16}) < 4.42106 · 10^{−16}.

2 The authors would like to thank one of the referees for reminding them of this tecnique.

All these bounds are pretty sharp and, except for | h_{11} − λ_{1} |, much better than those based on the result (R2). Let us now apply Corollary 3.2 (i) to H. Since (2/γ_{1})(1 + 10^{−2}) · 10^{−8} < 2.021 · 10^{−8}, we have

| \frac{λ_{1}}{h_{11}} − 1 |< 2.021 · 10^{−8} implying r_{1} < \frac{2.021 · 10^{−8}}{1 − 2.021 · 10^{−8}} < 2.022 · 10^{−8}.

In a similar way we obtain

r_{2} < 2.23263 · 10^{−8}, r_{3} < 4.422 · 10^{−8}.

These estimates are realistic. The latest two bounds might easily be improved had γ_{2} = γ_{3} been computed via the estimates (3.1). In that case we would have obtained r_{j} < 2.063 · 10^{−8}, 2 ≤ j ≤ 3. Since^{3} (λ_{3} − h_{33})/λ_{3} ≈ −2.01008085848 · 10^{−8} the bound for the smallest eigenvalue is very sharp. We see that the first (third) assertion of Corollary 3.2 yields sharp bounds for the smallest (largest) eigenvalues of positive definite matrices.

The next example shows how good are the new estimates when H is two by two.

Example 3.4. Let

H = [ \begin{matrix}a & b \\ b̄ & c \end{matrix} ] , a ≥ c,

be a two by two Hermitian matrix. Since

\begin{matrix}λ_{1} = a+ | b | tan φ \\ λ_{2} = c− | b | tan φ \end{matrix} , tan 2φ = \frac{2 | b |}{a − c}, | φ |≤ \frac{π}{4} ,

we can calculate exactly

1 − \frac{λ_{1}}{a} = −\frac{| b |}{a} tan φ = −\frac{2 | b |^{2}}{a [a − c + \sqrt{(a − c)^{2} + 4 | b |^{2}}]} if a ≠ 0,

1 − \frac{λ_{2}}{c} = \frac{| b |}{c} tan φ = \frac{2 | b |^{2}}{c [a − c + \sqrt{(a − c)^{2} + 4 | b |^{2}}]} if c ≠ 0.

Suppose first that H is definite, that is a and c are of the same sign and ac >| b |^{2}. The latest relations show that

| 1 − \frac{λ_{1}}{a} |≤ \frac{1}{| a |} \frac{| b |^{2}}{a − c}, | 1 − \frac{λ_{2}}{c} |≤ \frac{1}{| c |} \frac{| b |^{2}}{a − c}.

On the other hand, since

γ_{1} = γ_{2} = γ = \frac{| λ_{1} − λ_{2} |}{| λ_{1} | + | λ_{2} |} = \frac{a − c + 2 | b | tan φ}{| a + c |},

the requirement ∥Ω(H_{S})∥_{2} ≡ α < γ/3 of Corollary 3.2 reads

3\frac{| b |}{\sqrt{ac}} < \frac{a − c}{| a + c |} + 2\frac{| b | tan φ}{| a + c |}.

MATHEMATICA.

3 We have computed the eigenvalues of H with accuracy 10^{−80} by the interactive system

If the latest inequality holds, Corollary 3.2(i) implies

max \{| 1 − \frac{λ_{1}}{a} | , | 1 − \frac{λ_{2}}{c} |\} ≤ 2\frac{| a + c |}{a − c} \frac{| b |^{2}}{ac} = 2\frac{| a + c |}{ac} \frac{| b |^{2}}{a − c}.

Since

max \{\frac{1}{| a |} , \frac{1}{| c |}\} ≤ \frac{1}{2} \{2\frac{| a + c |}{a − c}\} ,

the bound of Corollary 3.2(i) is at least twice as large as the actual bound. Note also that the condition α < γ/3 is superfluous.

Consider yet the case a > 0 > c. Now H is indefinite and therefore γ_{1} = γ_{2} = γ = 1. Hence the requirement α < γ/(γ + 3) of Corollary 3.1, reads 4 | b |< \sqrt{a | c |}. So, under that condition Corollary 3.1(i) implies

max \{| 1 − \frac{λ_{1}}{a} | , | 1 − \frac{λ_{2}}{c} |\} ≤ \frac{4}{1} \frac{| b |^{2}}{a | c |}.

Since

max \{\frac{| b |^{2}}{a^{2} + a | c |} , \frac{| b |^{2}}{c^{2} + a | c |}\} ≤ \frac{| b |^{2}}{a | c |},

the bound in Corollary 3.1(i) can be sharp. However, the requirement α < γ/(γ + 3) appears to be superfluous.

Remark 3.5. Our estimates can easily be applied to a class of non-hermitian matrices which are Hermitian up to diagonal scaling. More precisely, we refer to H ∈ C^{n×n} as hidden Hermitian if H = D_{1}AD_{2} for some nonsingular real diagonal matrices D_{1}, D_{2} and Hermitian A. Since the eigenvalue problem Hx = λx is equivalent to the generalized eigenvalue problem for the Hermitian pair (A, D_{1}^{−1}D_{2}^{−1}), our results can be applied provided that either A or D_{1}D_{2} is positive definite.

REFERENCES

[1] J. Barlow and J. Demmel, Computing accurate eigensystems of scaled diagonally dominant matrices, SIAM J. Num. Anal., 27 (1990), pp. 762–791.

[2] J. Demmel and K. Veselić, Jacobi’s method is more accurate than QR, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 1204–1245.

[3] Z. Drmač, Computing the Singular and the Generalized Singular Values, PhD thesis, Lehrgebiet Mathematische Physik, Fernuniversität Hagen, 1994.

[4] Z. Drmač and V. Hari, On the quadratic convergence of the J–symmetric Jacobi method, Numer. Math., 64 (1993), pp. 147–180.

[5] V. Hari, On Cyclic Jacobi Methods for the Positive Definite Generalized Eigenvalue Problem, PhD thesis, Fernuniversität Hagen, 1984.

[6] , On almost diagonal square matrices with multiple singular values, Radovi Matematički, 4 (1988), pp. 209–225.

[7] , On pairs of almost diagonal matrices, Linear Algebra Appl., 148 (1991), pp. 193–223.

[8] , On sharp quadratic convergence bounds for the serial Jacobi methods, Numer. Math., 60 (1991), pp. 375–406.

[9] V. Hari and N. H. Rhee, A matrix pair of an almost diagonal skew–symmetric matrix and a symmetric positive definite matrix, Linear Algebra Appl., 148 (1993), pp. 82–117.

[10] E. Pietzsch, Genaue Eigenwertberechnung nichtsingulärer schiefsymmetrischer Matrizen mit einem Jacobi–änlichen Verfahren, PhD thesis, Lehrgebiet Mathematische Physik, Fernuniversität Hagen, 1993.

[11] I. Slapničar and V. Hari, On the quadratic convergence of the Falk–Langemeyer method, SIAM J. Math. Anal., 12 (1991), pp. 84–114.

[12] I. Slapničar and K. Veselić, Perturbations of the eigenprojections of a factorised Hermitian matrix, Linear Algebra Appl., 218 (1995), pp. 273–280.

[13] G. W. Stewart and J. guang Sun, Matrix Perturbation Theory, Academic Press, INC., 1990.

[14] H. P. M. van Kempen, On quadratic convergence of the special cyclic Jacobi method, Numer. Math., 9 (1966), pp. 19–22.

[15] K. Veselić and I. Slapničar, Floating-point perturbations of Hermitian matrices, Linear Algebra Appl., 195 (1993), pp. 81–116.

[16] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Springer, Berlin Heidelberg New York, 1965.

[17] , Almost diagonal matrices with multiple or close eigenvalues, Linear Algebra Appl., 1 (1968), pp. 1–12.

14 V. HARI AND Z. DRMAČ

Appendix for the Referees. Proof of the relation 2.9

Since 1 − μ̃ > 0 the latest relation is equivalent to

−l ≡ −\frac{−μ̃ + \frac{1−μ̃}{1−|μ|}α + β}{1 − μ̃ + \frac{1−μ̃}{1−|μ|}α} ≤ \frac{\frac{h_{jj}}{m_{jj}} − λ_{s_{i}}}{λ_{s_{i}}} ≤ \frac{μ̃ + \frac{1−μ̃}{1−|μ|}α + β}{1 − μ̃ − \frac{1−μ̃}{1−|μ|}α} ≡ u.

If μ̃ = |μ|, then

l = \frac{−|μ| + α + β}{1 − |μ| + α} ≤ \frac{α + β + |μ|}{1 − α − |μ|} = u.

If μ̃ = −|μ|, then we have

l = \frac{α + \frac{1−|μ|}{1+|μ|} (β + |μ|)}{1 − |μ| + α} ≤ \frac{α + β + |μ|}{1 − α − |μ|}

and

u = \frac{t + β}{1 − t} with t = \frac{1 + |μ|}{1 − |μ|}α − |μ|.

Since the condition α/(1 − |μ|) < 1 is equivalent to t < α + |μ|, we obtain

u ≤ \frac{α + β + |μ|}{1 − α − |μ|}.

Hence in both cases we have proven

\frac{|h_{jj}/m_{jj} − λ_{s_{i}}|}{|λ_{s_{i}}|} ≤ \frac{α + β + |μ|}{1 − α − |μ|} for some j ∈ ⋃_{k≠i} S_{k}.