Matejaš, J.; Hari, V.

Scaled Almost Diagonal Matrices with Multiple Singular Values

New estimates for relative distances between the singular values and the moduli of the appropriate diagonal elements of a scaled almost diagonal square matrix are derived. In case of a multiple singular value the bounds also estimate the structure of the diagonal block associated with that singular value. The bounds are expressed in terms of the off-diagonal elements of appropriately scaled matrix and relative gaps between singular values. The new estimates refine the existing ones which are based on the absolute gaps between singular values. They are especially appropriate for the smallest singular values. For triangular and essentially triangular matrices, the new bounds take simple and applicable form.

MSC (1991): 65f15

Key words and phrases: singular value, scaled almost diagonal matrix, relative gap.

0. Introduction

Let B be a complex matrix of order n. If its off-diagonal elements are small then moduli of the diagonal elements approximate the singular values. Estimates of such type of approximation can be found in [11, 10]. Sharper, quadratic estimates depend on squares of moduli of the off-diagonal elements and on the absolute gaps between the singular values of B (see [2, 6, 7]). Besides, such estimates yield insight in the structure of diagonal blocks of B corresponding to multiple singular values. This structure has major impact on the asymptotic rate of convergence of diagonalization methods for computing the singular value decomposition of B.

Usually, such estimates for the singular values are derived directly from the appropriate estimates for the eigenvalues of Hermitian matrices. A drawback of such approach is weak estimates for the smallest singular value (and the block corresponding to it, (see [6, 7])). In particular, if the singular values gather around zero, such estimates are useless. The cause for this shortcoming is the use of the absolute gaps between singular values.

In this paper we derive new quadratic estimates which can be used for approximation of the smallest singular values. They are deduced from the recent estimates [8] for the eigenvalues of Hermitian matrices which use relative gaps in the spectrum. Besides, the new estimates can be used to define proper stopping criteria for Kogbetliantz methods for triangular matrices [2, 3, 9, 7] and to anallyse quadratic convergence of scaled iterates by these methods (work in progress).

The paper is divided into three sections. In Section 1 we introduce notation and present recent results from [8]. In Section 2 we deduce the new estimates for the singular values and in Section 3 we provide some applications and numerical examples.

1. Scaled Almost Diagonal Hermitian Matrix

Let ^{|}C^{n×n} denote the space of n × n complex matrices. For B ∈ ^{|}C^{n×n}, let |B| denote the modulus of B, that is the matrix (|b_{ij}|), where B = (b_{ij}). By diag (B) is denoted the diagonal part of B, i.e. diag (b_{11}, …, b_{nn}). The off-diagonal part of B, B − diag (B) is denoted by Ω (B). The spectral and the Frobenius matrix norms are denoted by || · ||_{2} and || · ||_{F}, respectively.

Let H = (h_{ij}) ∈ ^{|}C^{n×n} be a Hermitian matrix with nonzero diagonal elements. Then Δ_{H} = |diag(H)| is nonsingular and H_{S} = Δ_{H}^{−1/2}HΔ_{H}^{−1/2} is well defined. Note that the diagonals of H_{S} have unit modulus. If there is a positive number α < 1 and a matrix norm || · || such that ||Ω(H_{S})|| ≤ α, then H is called (see [1]) α-scaled diagonally dominant (α-s.d.d.) with respect to that norm. In this paper we assume that scaled diagonal dominance is defined by the spectral norm. It is easily seen that an α-s.d.d. Hermitian matrix is nonsingular.

Let

λ_{1} = … = λ_{s_{1}} > λ_{s_{1}+1} = … = λ_{s_{2}} > … > λ_{s_{p−1}+1} = … = λ_{s_{p}} (1.1)

be the nonincreasing ordering of the eigenvalues of H. Here p is the number of different eigenvalues and for each 1 ≤ i ≤ p, n_{i} = s_{i} − s_{i−1} is the multiplicity of λ_{s_{i}} ( s_{p} = n, s_{0} = 0 ). The relative separation or gap of λ_{s_{i}} from the rest of the spectrum of H is defined by (cf. [8])

γ_{i} = min \{\frac{|λ_{s_{i}} − λ_{s_{j}}|}{|λ_{s_{i}}| + |λ_{s_{j}}|}, 1 ≤ j ≤ p, j ≠ i\} . (1.2)

The minimum relative gap is then

γ = min_{1≤i≤p} γ_{i} . (1.3)

If the diagonal elements of H satisfy

h_{11} ≥ h_{22} ≥ ⋯ ≥ h_{nn}, (1.4)

then each λ_{j} from (1.1) is approximated by h_{jj}. The condition (1.4) can be ensured by the similarity transformation with a suitable permutation matrix. According to the partition n = n_{1} + … + n_{p}, we define the block matrix partition (H_{ij}) whereH_{ii} is of order n_{i}, 1 ≤ i ≤ p, and the associated blocks and parts of H:

H = [ \begin{matrix}H_{11} & … & H_{1p} \\ ⋮ & ... & ⋮ \\ H_{p1} & … & H_{pp} \end{matrix} ] , \begin{matrix}π_{i}(H) & = & H_{ii}  the ith diagonal block \\ τ_{i}(H) & = & [H_{i1}, …, H_{i,i−1}, H_{i,i+1}, … H_{ip}] \\ π(H) & = & diag (H_{11}, …, H_{pp}) the block-diagonal part of H \\ τ(H) & = & X − π(H)  the block-off-diagonal part of H. \end{matrix}  (1.5)

The following result from [8] reveals the structure of an α - s.d.d. Hermitian matrix H. It shows that for small enough α each diagonal block of H_{S}, π_{i}(H_{S}), is approximated by λ_{s_{i}}π_{i}(Δ_{H}) with an error of order ∥τ_{i}^{2}(H_{S})∥_{F} /γ_{i}.

T h e o r e m 1. Let H ∈ ^{|}C^{n×n} be an α-s.d.d. Hermitian matrix satisfying the condition (1.4). Let the eigenvalues of H be ordered as in (1.1) and let γ_{i}, 1 ≤ i ≤ p and γ be given by the relations (1.2) and (1.3), respectively. If α < γ/(γ + 3), then

(i) ||π_{i}(H_{S} − λ_{s_{i}}Δ_{H}^{−1})||_{F} ≤ \frac{4}{γ_{i}} ||τ_{i}(H_{S})||_{F}^{2} , 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) ||π_{i}(H − λ_{s_{i}}I)||_{F} ≤ \frac{2}{γ_{i}} min\{ 2||τ_{i}(HΔ_{H}^{−1/2})||_{F}^{2} , \frac{||τ_{i}(H)||_{F}^{2}}{|λ_{s_{i}} |} \}, 1 ≤ i ≤ p

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

The condition (1.1) can be generalized by requiring such ordering that the diagonals affiliated with the same eigenvalue occupy successive positions on the diagonal.

2. Scaled Almost Diagonal Square Matrix

In this section we derive estimates for a scaled almost diagonal square matrix B. In contrast to the Hermitian case, here the singular values play the main role. If D_{L} and D_{R} are positive definite diagonal matrices, D_{L}BD_{R} is refered to as scaled matrix B. In case of one-sided scaling either D_{L} = I_{n} or D_{R} = I_{n} and the nontrivial scaling matrix is usually chosen to normalize the columns or rows of D_{L}BD_{R}. In this paper we consider two-sided scaling under the constraint D_{L} = D_{R} = D, where D is chosen to normalize the diagonal elements of DBD. Note that for such a scaling the notion of a scaled diagonally dominant matrix B is defined in the same way as in the case of a Hermitian matrix H ( see Section 1 ).

Let B ∈ ^{|}C^{n×n} and let

σ_{1} = … = σ_{s_{1}} > σ_{s_{1}+1} = … = σ_{s_{2}} > … > σ_{s_{p−1}+1} = … = σ_{s_{p}} ≥ 0 (2.1)

be the nonincreasing ordering of the singular values of B. As above, we have s_{p} = n, s_{0} = 0 and for 1 ≤ i ≤ p, n_{i} = s_{i} − s_{i−1} is the multiplicity of σ_{s_{i}}. In accordance with the relations (1.2), (1.3) and (2.1), we define the relative gaps between singular values

γ_{i} = min_{j≠i^{1≤j≤p}} \frac{| σ_{s_{i}} − σ_{s_{j}} |}{σ_{s_{i}} + σ_{s_{j}}}, 1 ≤ i ≤ p (2.2)

and the minimum relative gap

γ = min_{1≤i≤p} γ_{i} = min \{\frac{σ_{s_{i}} − σ_{s_{i+1}}}{σ_{s_{i}} + σ_{s_{i+1}}} , i = 1, …, p − 1\} . (2.3)

Note that Φ^{∗}B, where Φ = diag (e^{i arg(b_{11})}, …, e^{i arg(b_{nn})}), has nonnegative diagonal elements. Let P be a permutation matrix such that

B̃ = P^{∗}Φ^{∗}BP (2.4)

has nonincreasingly ordered diagonal elements. If J = [e_{n}, e_{n−1}, …, e_{1}], where I_{n} = [e_{1}, …, e_{n}], then JB̃J has nondecreasingly ordered diagonals. Now, consider the unitary matrix

U = [ \begin{matrix}Φ & 0 \\ 0 & I_{n} \end{matrix} ] \frac{1}{\sqrt{2}} [ \begin{matrix}I_{n} & −I_{n} \\ I_{n} & I_{n} \end{matrix} ] [ \begin{matrix}P & 0 \\ 0 & P J \end{matrix} ] = \frac{1}{\sqrt{2}} [ \begin{matrix}ΦP & −ΦP J \\ P & P J \end{matrix} ] (2.5)

and the Hermitian matrix

A = U^{∗} [ \begin{matrix}0 & B \\ B^{∗} & 0 \end{matrix} ] U. (2.6)

The eigenvalues of A are (cf. [5, Section 8.3])

σ_{1} = … = σ_{s_{1}} > ⋯ > σ_{s_{p−1}+1} = … = σ_{s_{p}} ≥ 0 ≥ −σ_{s_{p}} = ⋯ = −σ_{s_{p−1}+1} > ⋯ > −σ_{s_{1}} = ⋯ = −σ_{1}.(2.7)

Using the matrices B̃ and J defined above, we obtain from the relations (2.5) and (2.6)

A = \frac{1}{2} [ \begin{matrix}B̃ + B̃^{∗} & (B̃ − B̃^{∗})J \\ −J(B̃^{∗} − B̃) & −J(B̃ + B̃^{∗})J \end{matrix} ] . (2.8)

L e m m a 2. Let A be given by the relation (2.8).

(i) The diagonal elements of A are nonincreasingly ordered.

(ii) A is α-s.d.d. if and only if B is α-s.d.d. .

Proof. (i) By construction the diagonal elements of A are b̃_{11}, ⋯, b̃_{nn}, −b̃_{nn}, ⋯, −b̃_{11}, where B̃ = (b̃_{ij}). Now (i) follows from the definition (2.4) of B̃. (ii) It is enough to prove

||Ω(A_{S})||_{2} = ||Ω(B_{S})||_{2}, (2.9)

where B = Δ_{B}^{1/2}B_{S}Δ_{B}^{1/2}, Δ_{B} = |diag(B)| and A = Δ_{A}^{1/2}A_{S}Δ_{A}^{1/2}, Δ_{A} = |diag(A)|.

Let

D_{B}^{1/2} = [ \begin{matrix}Δ_{B}^{1/2} & 0 \\ 0 & Δ_{B}^{1/2} \end{matrix} ] , D_{A}^{1/2} = [ \begin{matrix}P^{∗}Δ_{B}^{1/2}P & 0 \\ 0 & JP^{∗}Δ_{B}^{1/2}P J \end{matrix} ] .

A streightforward calculation yields

D_{B}^{1/2}U = UD_{A}^{1/2}.

Hence

D_{A}^{−1/2}ADA^{−1/2} = D_{A}^{−1/2}U^{∗}D_{B}^{1/2} [ \begin{matrix}O & B_{S} \\ B_{S}^{∗} & O \end{matrix} ] D_{B}^{1/2}UD_{A}^{−1/2} = U^{∗} [ \begin{matrix}O & B_{S} \\ B_{S}^{∗} & O \end{matrix} ] U. (2.10)

The relations (2.10), (2.8), (2.6) and (2.5) imply that D_{A}^{−1/2}AD_{A}^{−1/2} has ones and minus ones on the diagonal. Therefore D_{A} = Δ_{A},

A_{S} = U^{∗} [ \begin{matrix}O & B_{S} \\ B_{S}^{∗} & O \end{matrix} ] U  and  Ω (A_{S}) = U^{∗} [ \begin{matrix}O & Ω (B_{S}) \\ Ω (B_{S})^{∗} & O \end{matrix} ] U,

implying the assertion (2.9). □

To simplify notation we shall further assume Φ = P = I_{n}, i.e. that B satisfies

b_{11} ≥ b_{22} ≥ ⋯ ≥ b_{nn} ≥ 0. (2.11)

If B is m × n, m ≥ n, than the condition (2.11) appears naturally after reducing it to n × n matrix via the QR factorization with column pivoting.

T h e o r e m 3. Let B ∈ ^{|}C^{n×n} be an α-s.d.d. matrix satisfying the condition (2.11) and let B = Δ_{B}^{1/2}B_{S}Δ_{B}^{1/2}, Δ_{B} = diag(B). Let the relations (2.1) – (2.3) hold and let B and B_{S} be partitioned according to the multiplicities of the singular values, as in the relation (1.5).

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

(i) ∥π_{i}(\frac{B_{S} + B_{S}^{∗}}{2} − σ_{s_{i}}Δ_{B}^{−1})∥_{F} ≤ \frac{1}{γ_{i}} [∥π_{i}(B_{S} − B_{S}^{∗})∥_{F}^{2} + 2∥τ_{i}(B_{S})∥_{F}^{2} + 2∥τ_{i}(B_{S}^{∗})∥_{F}^{2} ] , i = 1, …, p

(ii) ∑_{j=1}^{n} |1 − \frac{σ_{j}}{b_{jj}} |^{2} + ∥Ω(π(\frac{B_{S} + B_{S}^{∗}}{2} ))∥_{F}^{2} ≤ \frac{1}{γ^{2}} [∥π(B_{S} − B_{S}^{∗})∥_{F}^{2} + 2∥τ(B_{S})∥_{F}^{2} ]

· [∥π(B_{S} − B_{S}^{∗})∥_{F}^{2} + 4∥τ(B_{S})∥_{F}^{2} ]

(iii) ∥π_{i}(\frac{B + B^{∗}}{2} − σ_{s_{i}}I)∥_{F} ≤ \frac{1}{γ_{i}} min \{∥π_{i}((B − B^{∗})Δ_{B}^{−1/2})∥_{F}^{2} + 2∥τ_{i}(BΔ_{B}^{−1/2})∥_{F}^{2} + 2∥τ_{i}(B^{∗}Δ_{B}^{−1/2})∥_{F}^{2} ,

\frac{1}{2σ_{s_{i}}} [2∥τ_{i}(B)∥_{F}^{2} +2∥τ_{i}(B̃^{∗})∥_{F}^{2} + ∥π_{i}(B − B^{∗})∥_{F}^{2} ] \} , i = 1, …, p

(iv) ∑_{j=1}^{n} |b_{jj} − σ_{j}|^{2} + ∥Ω(π(\frac{B + B^{∗}}{2} ))∥_{F}^{2} ≤ \frac{1}{γ^{2}} min \{2∥τ(BΔ_{B}^{−1/2})∥_{F}^{2} + 2∥τ(B^{∗}Δ_{B}^{−1/2})∥_{F}^{2}

+ ∥π((B − B^{∗})Δ_{B}^{−1/2})∥_{F}^{4} , \frac{1}{4σ_{n}^{2}} [4||τ(B)||_{F}^{2} + ||π(B − B^{∗})||_{F}^{2} ]^{2} \} .

Proof. (i) Let A be defined by the relation (2.8) with B̃ replaced by B. If γ_{i}^{±} denotes the relative gap in the spectrum of A associated with ±σ_{s_{i}}, then by the relations (1.2), (2.2) and (2.7) we conclude that γ_{i}^{±} = γ_{i}. By Lemma 2 we see that A from the relation (2.8) is α-s.d.d. with α < γ/(γ + 3). Hence Theorem 1 (i) can be applied to obtain

∥π_{i}(A_{S} − σ_{s_{i}}Δ_{A}^{−1})∥_{F} ≤ \frac{4}{γ_{i}} ∥τ_{i}(A_{S})∥_{F}^{2} , 1 ≤ i ≤ p. (2.12)

Let E_{i} = [e_{s_{i−1}+1}, …, e_{s_{i}}] ∈ ^{|}C^{n×n_{i}}, 1 ≤ i ≤ p. Using unitary invariance of the Frobenius norm and the parallelogram law for the same norm, we obtain for 1 ≤ i ≤ p

4∥τ_{i}(A_{S})∥_{F}^{2} = 4∥τ_{i}(\frac{B_{S} + B_{S}^{∗}}{2} )∥_{F}^{2} + 4∥E_{i}^{∗} \frac{B_{S} − B_{S}^{∗}}{2} J∥_{F}^{2}
= ∥τ_{i}(B_{S} + B_{S}^{∗})∥_{F}^{2} + ∥τ_{i}(B_{S} − B_{S}^{∗})∥_{F}^{2} + ∥π_{i}(B_{S} − B_{S}^{∗})∥_{F}^{2}
= ∥τ_{i}(B_{S}) + τ_{i}(B_{S}^{∗})∥_{F}^{2} + ∥τ_{i}(B_{S}) − τ_{i}(B_{S}^{∗})∥_{F}^{2} + ∥π_{i}(B_{S} − B_{S}^{∗})∥_{F}^{2}
= 2∥τ_{i}(B_{S})∥_{F}^{2} + 2∥τ_{i}(B_{S}^{∗})∥_{F}^{2} + ∥π_{i}(B_{S} − B_{S}^{∗})∥_{F}^{2} .  (2.13)

Since π_{i}(A_{S} − σ_{s_{i}}Δ_{A}^{−1}) = π_{i}((B_{S} + B_{S}^{∗})/2 − σ_{s_{i}}Δ_{B}^{−1}), 1 ≤ i ≤ p, the assertion (i) follows by the relations (2.12) and (2.13).

(ii) For 1 ≤ i ≤ p holds

∥π_{i}(\frac{B_{S} + B_{S}^{∗}}{2} − σ_{s_{i}}Δ_{B}^{−1})∥_{F}^{2} = ∥π_{i}(Ω(\frac{B_{S} + B_{S}^{∗}}{2} ))∥_{F}^{2} + ∑_{j=s_{i−1}+1}^{s_{i}} |1 − \frac{σ_{i}}{b_{jj}} |^{2}.

Summing the right-hand side of the latest equality over 1 ≤ i ≤ p, one obtains the left-hand side of the inequality in (ii). Combining the bound in the assertion (i) with the inequalities

∥π_{i}(B_{S} − B_{S}^{∗})∥_{F}^{2} + 2∥τ_{i}(B_{S})∥_{F}^{2} + 2∥τ_{i}(B_{S}^{∗})∥_{F}^{2} ≤ ∥π(B_{S} − B_{S}^{∗})∥_{F}^{2} + 2∥τ(B_{S})∥_{F}^{2} , 1 ≤ i ≤ p

and

∑_{i=1}^{p} [∥π_{i}(B_{S} − B_{S}^{∗})∥_{F}^{2} + 2∥τ_{i}(B_{S})∥_{F}^{2} + 2∥τ_{i}(B_{S}^{∗})∥_{F}^{2} ] ≤ ∥π(B_{S} − B_{S}^{∗})∥_{F}^{2} + 4∥τ(B_{S})∥_{F}^{2} ,

one obtains the right-hand side of the inequality in (ii). This proves (ii). The remaining two assertions are obtained in the same fashion from the assertion (iii) of Theorem 1. □

Let ε = ∥Ω(B_{S})∥_{F}. From Theorem 3 we see that for small enough ε ( say, ε ≤ γ/4 ), π_{i}(B_{S}) = I_{n_{i}} + S_{n_{i}} + E_{n_{i}}, where S_{n_{i}} is skew-Hermitian and ∥E_{n_{i}}∥_{F} = O(ε^{2}). Thus, Theorem 3 describes and estimates the structure of the diagonal blocks in the partition (1.5) of B_{S} and provides additional information about the structure in B (see [6]). If the constraint (2.11) is removed then every appearance of B in Theorem 3 should be replaced by B̃.

3. Some Applications and Numerical Examples

Here we consider two immediate applications of the new estimates. The first provides a bound for the smallest singular value of multiplicity one. The second provides appropriate bounds for essentially triangular matrices. By two examples of matrices of order three we compare the existing and the new estimates.

Since σ_{s_{p}} (= σ_{n}) measures distance of B to the set of singular matrices (see [5, Theorem 2.5.2]) estimation of σ_{n} via b_{nn} can be useful. If a lower bound μ of σ_{s_{p−1}}/σ_{s_{p}} is available one can bound γ_{p} from below. Indeed

γ_{p} = \frac{σ_{s_{p−1}} − σ_{s_{p}}}{σ_{s_{p−1}} + σ_{s_{p}}} ≥ \frac{σ_{s_{p−1}} − \frac{1}{μ}σ_{s_{p−1}}}{σ_{s_{p−1}} + \frac{1}{μ}σ_{s_{p−1}}} = \frac{μ − 1}{μ + 1}. (3.1)

The relation (3.1) implies the following simple result.

C o r o l l a r y 4. Let B be as in Theorem 3. If σ_{n} is simple and σ_{n−1}/σ_{n} ≥ μ > 1, then

| b_{nn} − σ_{n}| ≤ 2\frac{μ + 1}{μ − 1} ∑_{j=1}^{n−1} \frac{|b_{jn}|^{2} + |b_{nj}|^{2}}{b_{jj}} .

Proof. Apply the assertion (i) ( or (iii) ) of Theorem 3 to B and use the lower bound for γ_{p} from (3.1). □ Newpara The assertions of Theorem 3 take simpler form provided that B is essentially triangular, i.e. if b_{ij}b_{ji} = 0 for all 1 ≤ i < j ≤ n. Such matrices appear in connection with certain serial and parallel Kogbetliantz methods for triangular matrices ( see [9, 4] ).

C o r o l l a r y 5. Let B be as in Theorem 3. If in addition, B is essentially triangular, then

(i) ∑_{j=s_{i−1}+1}^{s_{i}}|1 − \frac{σ_{s_{i}}}{b_{jj}} |^{2} + \frac{1}{2}∥Ω(π_{i}(B_{S}))∥_{F}^{2} ≤ \frac{4}{γ_{i}^{2}} [∥Ω(π_{i}(B_{S}))∥_{F}^{2} + ∥τ_{i}(B_{S})∥_{F}^{2} + ∥τ_{i}(B_{S}^{∗})∥_{F}^{2} ]^{2} , 1 ≤ i ≤ p.

(ii) ∑_{j=1}^{n} |1 − \frac{σ_{j}}{b_{jj}} |^{2} + \frac{1}{2}||Ω(π(B_{S}))||_{F}^{2} ≤ \frac{4}{γ^{2}} [∥Ω(B_{S})∥_{F}^{2} + ∥τ(B_{S})∥_{F}^{2} ] · ∥Ω(B_{S})∥_{F}^{2} .

Proof. (i) Note that B_{S} is also essentially triangular. The proof follows by modifying the both sides of the inequality in the assertion (i) of Theorem 3 by using

∥Ω(π_{i}(B_{S} ± B_{S}^{∗}))∥_{F} = ∥π_{i}(B_{S} − B_{S}^{∗})∥_{F} = \sqrt{2}∥Ω(π_{i}(B_{S}))∥_{F} , 1 ≤ i ≤ p.

(ii) The proof follows from (i) ( cf. the proof of Theorem 3(ii) ). □

If B is Hermitian, the bounds of Theorem 3 reduce to the bounds of [8, Corollary 3.1]. From [8, Example 3.3] we conclude that for Hermitian positive definite matrices the bounds in the assertions (i) and (iii) of Theorem 3 for the smallest and the largest singular value can be realistic. It looks like, as the departure from normality increases, the bounds are getting somewhat less accurate. This can be seen from the following example of an essentially triangular matrix of order three. In this example we show, using the existing and the new results, how good the diagonal elements approximate the singular values. We can notice that for the given matrix most of the existing results are either not applicable or yield poor estimates.

E x a m p l e 6. Let B and B_{S} = Δ_{B}^{−1/2}BΔ_{B}^{−1/2} be given by

B = [ \begin{matrix}1 & 10^{−7} & 0 \\ 0 & 10^{−6} & 10^{−11} \\ 10^{−9} & 0 & 10^{−8} \end{matrix} ] , B_{S} = [ \begin{matrix}1 & 10^{−4} & 0 \\ 0 & 1 & 10^{−4} \\ 10^{−5} & 0 & 1 \end{matrix} ] .

Then ∥Ω(B)||_{2} = 10^{−7} and α = ∥Ω(B_{S})||_{2} = 10^{−4}. Considering b_{ii} as an approximation of σ_{i}, the task is to calculate bounds for the relative errors r_{i} = | σ_{i} − b_{ii} | /σ_{i}, 1 ≤ i ≤ 3.

Solution. The classical perturbation theorem for the singular values yields | b_{ii} − σ_{i} | ≤ ∥Ω(B)||_{2}, 1 ≤ i ≤ 3. From this we conclude that the singular values are simple. We have r_{i} ≤ 10^{−7}/(b_{ii} −10^{−7}), provided that b_{ii} > 10^{−7}. We obtain r_{1} ≤ 1.00000011 · 10^{−7}, r_{2} ≤ 1/9 while r_{3} cannot be estimated.

Let us now apply more refined “quadratic estimates” based on the absolute gaps in the set of singular values (see [6, 7]). From [7, Lemma 2.1] ( or [6, Corollary 1] ) and the fact that the singular values are simple, one obtains

| b_{ii} − σ_{i} |≤ \frac{3}{4δ_{i}} ∑_{j≠i^{j=1}}^{3} (| b_{ij} |^{2} + | b_{ji} |^{2}) , 1 ≤ i ≤ 2, (3.2)

provided that 3∥Ω(B)∥_{2} < min{δ_{1}, δ_{2}}. Here δ_{1} = σ_{1} − σ_{2} and δ_{2} = σ_{2} − σ_{3}. From the classical estimates we have δ_{1} > 1 − 10^{−6} − 2 · 10^{−7} > 0.9999988, δ_{2} > 10^{−6} − 10^{−8} − 2 · 10^{−7} > 7.9 · 10^{−7}. Since obviously, 3∥Ω(B)∥_{2} < min{δ_{1}, δ_{2}}, we can use (3.2) to obtain | b_{11} − σ_{1} | < 7.50076 · 10^{−15} and | b_{22} − σ_{2} | < 9.493671 · 10^{−9}. This implies r_{1} ≤ 7.501 · 10^{−15} and r_{2} ≤ 9.585 · 10^{−3}. Since 2σ_{3} < 2 · 10^{−8} < min{δ_{1}, δ_{2}} and 3∥Ω(B)∥_{2} > 2σ_{3} the quadratic estimates from [7, Lemma 2.1] cannot be used to obtain a bound for r_{3}. Note also that [7, Lemma 2.3] cannot be applied to B since B is neither permutationally similar to a triangular matrix nor the last column or row of Ω(B) is zero.

To obtain a bound for r_{3} we can use Corollary 4. To check for the assumptions we first have to calculate the relative gaps. Since the quadratic estimates from [7, Lemma 2.1] are less known, we shall use the obtained bounds based on the classical perturbation theorem. We have

γ_{1} = \frac{| σ_{1} − σ_{2} |}{σ_{1} + σ_{2}} > \frac{b_{11} − b_{22}− | σ_{1} − b_{11} | − | σ_{2} − b_{22} |}{b_{11} + b_{22}+ | σ_{1} − b_{11} | + | σ_{2} − b_{22} |} > \frac{1 − 10^{−6} − 2 · 10^{−7}}{1 + 10^{−6} + 2 · 10^{−7}} > 0.99999760,
γ_{2} = γ_{3} = γ = \frac{| σ_{2} − σ_{3} |}{σ_{2} + σ_{3}} > \frac{10^{−6} − 10^{−8} − 2 · 10^{−7}}{10^{−6} + 10^{−8} + 2 · 10^{−7}} > 0.65289256.

Thus, α < γ/(γ + 3) and since σ_{3} is simple, we can apply Corollary 4 to B. To this end we first calculate μ,

\frac{σ_{2}}{σ_{3}} ≥ \frac{b_{22}− | σ_{2} − b_{22} |}{b_{33}} > \frac{10^{−6} − 10^{−7}}{10^{−8}} = 90 ≡ μ.

We have

| b_{33} − σ_{3} |≤ 2\frac{91}{89} (\frac{10^{−18}}{10^{−6}} + \frac{10^{−22}}{10^{−8}} ) < 2.0654 · 10^{−12},

which is the sharpest absolute distance between b_{33} and σ_{3} obtained so far. Hence we obtain

r_{3} < \frac{2.0654 · 10^{−12}}{10^{−8} − 2.0654 · 10^{−12}} < 2.066 · 10^{−4}.

Finally, let us apply Corollary 5(i) to B. Since we have already bounded relative gaps, we can calculate bounds for r̃_{i} where

r̃_{i} ≡ \frac{| σ_{i} − b_{ii} |}{b_{ii}} < \frac{2}{γ_{i}} [τ_{i}^{2}(B_{S}) + τ_{i}^{2}(B_{S}^{∗})] , 1 ≤ i ≤ 3.

One obtains r̃_{1} < 2.020005 · 10^{−8}, r̃_{2} < 6.126583 · 10^{−8} and r̃_{3} < 3.093924 · 10^{−8}. Using the relation r_{i} ≤ r̃_{i}/(1 − r̃_{i}) one finally obtains

r_{1} < 2.021 · 10^{−8}, r_{2} < 6.127 · 10^{−8}, r_{3} < 3.094 · 10^{−8}.

We see that the assertion (i) of Corollary 5 provides a weaker estimate for the largest singular value σ_{1}, than the existing result [7, Lemma 2.1]. However, the advantage is obvious for the tiny singular values σ_{2} and σ_{3}. The exact values of r_{i} rounded to three digits are r_{1} = 5.00 · 10^{−15}, r_{2} = 5.00 · 10^{−11} and r_{3} = 5.00 · 10^{−11}. □

In the following example the obtained results based on the new estimates are much sharper.

E x a m p l e 7. Let B and B_{S} = Δ_{B}^{−1/2}BΔ_{B}^{−1/2} be given by

B = [ \begin{matrix}1 & \sqrt{2} · 10^{−7} & 0 \\ 0 & 2 · 10^{−6} & \sqrt{2} · 10^{−10} \\ 10^{−8} & 0 & 10^{−6} \end{matrix} ] , B_{S} = [ \begin{matrix}1 & 10^{−4} & 0 \\ 0 & 1 & 10^{−4} \\ 10^{−5} & 0 & 1 \end{matrix} ] .

Using the same analysis as in Example 1 the task is to calculate the appropriate bounds.

Solution. The following table, in which the columns 2, 3 and 4 give uper bounds while the last column gives the rounded values of r_{i}, 1 ≤ i ≤ 3, is obtained.

estimates  r_{i}
i

classical, no gaps quadratic, absolute gaps quadratic, relative gaps

rounded to 5 digits

1 1.4143 · 10^{−7} 1.5076 · 10^{−14} 2.0201 · 10^{−8} 9.9920 · 10^{−15}
2 7.6092 · 10^{−2} 2.1363 · 10^{−2} 1.83104 · 10^{−7} 3.3333 · 10^{−9}
3 1.6472 · 10^{−1} 1.0462 · 10^{−4} 9.2468 · 10^{−8} 3.3332 · 10^{−9}

Again, we see that the estimates based on new results are especially appropriate for tiny singular values. □

Acknowledgements

The authors would like to thank Dr. Z. Drmač for reading the paper.

4. 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. P. Charlier and P. V. Dooren, On Kogbetliantz’s SVD algorithm in the presence of clusters, Linear Algebra Appl.,

95 (1987), pp. 135–160. 3 , A Jacobi–like algorithm for computing the generalized Schur form of a regular pencil, report, Phillips Research

Laboratory, Belgium, June 1988. 4 J. P. Charlier, M. Vanbegin, and P. V. Dooren, On efficient implementations of Kogbetliantz’s algorithm for computing

the singular value decomposition, Numer. Math., 52 (1988), pp. 279–300. 5 G. H. Golub and C. F. van Loan, Matrix Computations, The Johns Hopkins University Press, 1989. 6 V. Hari, On almost diagonal square matrices with multiple singular values, Radovi Matematički, 4 (1988), pp. 209–225. 7 , On the quadratic convergence of the serial SVD Jacobi methods for triangular matrices, SIAM J. Sci. Stat. Comp.,

10 (1989), pp. 1076–1096. 8 V. Hari and Z. Drmač, On scaled almost diagonal Hermitian matrix pairs. To appear in SIAM J. Matrix Anal. Appl.,

1994. 9 V. Hari and K. Veselić, On Jacobi methods for singular value decompositions, SIAM J. Sci. Stat. Comp., 8 (1987),

pp. 741–754. 10 R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1991. 11 G. W. Stewart and J. g. Sun, Matrix Perturbation Theory, Academic Press, 1990.

Addresses: Graduate Student Josip Matejaš, Faculty of Economics, Univ. of Zagreb, Kennedyjev trg 6, 10000 Zagreb, CROATIA; Prof. Dr. Vjeran Hari, Dept. of Mathematics, Univ. of Zagreb, Bijenička cesta 30, 10000 Zagreb, CROATIA, El. mail: hari@math.hr. 8