Accurate polynomial root–finding methods for
symmetric tridiagonal matrix eigenproblems
L. Gemignani
Dipartimento di Informatica, Universit`a di Pisa, Largo Bruno Pontecorvo, 3 - 56127 Pisa, Italy
Abstract
In this paper we consider the application of polynomial root-finding methods to the solution of the tridiagonal matrix eigenproblem. All considered solvers are based on evaluating the Newton correction. We show that the use of scaled three-term recurrence relations complemented with error free transformations yields some compensated schemes which significantly improve the accuracy of computed results at a modest increase in computational cost. Numerical ex-periments illustrate that under some restriction on the conditioning the novel iterations can approximate and/or refine the eigenvalues of a tridiagonal matrix with high relative accuracy.
Keywords: Polynomial zeros, tridiagonal matrix, matrix eigenvalues, three-term recurrence, floating-point arithmetic, accuracy.
2010 MSC: 65F15
1. Introduction
Polynomial root-finding algorithms can be applied for the solution of struc-tured matrix eigenproblems. Most of the methods including the Newton method for eigenvalue refinement and the Ehrlich-Aberth iteration for simultaneous eigenvalue computation [3] need at each step to evaluate only the ratio f (z)/f0(z) –generally referred as the Newton correction– between the value of the charac-teristic polynomial and of its first derivative. It is an immediate observation that the function value and the derivative might overflow/underflow while the ratio may still be a reasonable machine number. Numerically reliable polyno-mial methods should be able to exploit the structure of the matrix eigenproblem for the efficient and accurate evaluation of the Newton correction.
In this paper we focus on the symmetric tridiagonal eigenproblem. It is well known that in some cases the efficiency of the polynomial solver can be coupled with the high accuracy of the computed approximations. Theoretical and computational results have been already established in the literature for the
important subclass of real symmetric tridiagonal matrices with zero diagonal en-tries. Such matrices arise naturally both in the framework of divide-and-conquer methods for bidiagonal singular value problems [12, 15, 19] and in the approxi-mation theory for the computation of Gauss-type quadrature rules for symmetric weight functions [20, 13]. Since symmetric tridiagonal matrices with zero diag-onal specify their eigenvalues with high relative accuracy independently of their magnitudes [6] numerical methods can possibly compute these eigenvalues at the same relative accuracy they are determined by the input data. Relatively accurate polynomial zerofinders based on Laguerre’s iteration are considered in [19, 24] while GR-type matrix methods are devised in [6, 8]. Similar results do not hold for a general symmetric tridiagonal whose entries do not determine its eigenvalues to high relative accuracy. Higher (multi)precision computation can be recommended to increase the accuracy of the computed approximations with some timing penalties.
It is a classical result that the characteristic polynomial of a tridiagonal ma-trix together with its derivatives can efficiently be evaluated by using three-term recurrences [25]. Although such recurrences are computationally appealing and straightforward to implement in practice the resulting scheme can be prone to numerical difficulties. Due to overflow and underflow occurrences in real ap-plications the computation needs to incorporate some normalization or scaling techniques [26]. In addition, the three-term sequence computation is backward stable but this does not imply any accuracy in the evaluation of the polyno-mial and its derivative and, a fortiori, of the corresponding Newton correction. According to the classical rule of thumb the (relative) forward error depends both on the (relative) backward error and the condition number. Wilkinson analyzed the three-term recurrence computation [25] by proving that the eval-uation of the characteristic polynomial is relatively backward stable for points close to the origin. Nevertheless, quite commonly computing the determinant of a symmetric tridiagonal matrix is an ill-conditioned problem.
A similar situation also occurs with the Ruffini-Horner algorithm generally used to evaluate polynomials and incorporated in the multiprecision polyno-mial rootfinder MPSolve [2]. Though named for Paolo Ruffini (1765-1822) and William Horner (1786-1837), two European mathematicians who described it in the early 1800s, the Ruffini-Horner method had first appeared in mathemat-ical texts from both Arab and Chinese medieval mathematicians [4] and then rediscovered in 1669 by Isaac Newton (see [21]). Very recently an accurate vari-ant of the Ruffini-Horner scheme has been proposed in [10] which is capable to compute a result of the same quality as if computed using twice the working precision and then rounded to the working precision. This variant makes use of some modified algorithms –called error-free transformations in [22]– for eval-uating the sum and the product of two floating point numbers introduced by Knuth [17] and Dekker–Veltkamp [5], respectively.
In this contribution we combine error-free transformations and scaled three-term recurrence relations to produce an efficient and accurate algorithm for evaluating both the characteristic polynomial of a symmetric tridiagonal ma-trix and its first derivative. By ”accurate” we mean that the computed
an-swers have relative errors as they were computed in twice the working preci-sion. This means that we achieve full precision accuracy, apart from severely ill-conditioned computations, without timing penalties required by multipreci-sion environments. Then the algorithm is incorporated in the Newton method for testing purposes. By using a result in [23] the accurate computation of the characteristic polynomial implies that the same property holds for the approxi-mation of the eigenvalues. Our numerical experience suggests that the resulting rootfinder is typically able to approximate matrix eigenvalues at high relative accuracy independently of their magnitude.
The paper is organized as follows. In Section 2 we introduce and analyze the compensated variants of the classical schemes making use of three-term re-currences for evaluating the characteristic polynomial, as well as its first deriva-tive, of tridiagonal matrices. In Section 3 we illustrate the results of numerical experiments confirming the potential high relative accuracy of an eigenvalue refinement method based on the Newton method complemented with the com-pensated techniques for computing the function values. Finally, conclusion and future work are drawn in Section 4.
2. Accurate three-term recurrence computation
Let T ∈ Rn×n be a symmetric unreduced tridiagonal matrix, i.e.,
T = α1 β1 β1. .. . .. . .. . .. β n−1 βn−1 αn , βi, αi∈ R, βi6= 0, 1 ≤ i ≤ n − 1.
The characteristic polynomial
fn(λ) = det(λIn− T )
can be computed by the three-term recurrence relations f0(λ) = 1, f1(λ) = λ − α1;
fj(λ) = (λ − αj)fj−1(λ) − βj−12 fj−2(λ), j = 2, 3, . . . , n.
By differentiating the relations we obtain a second recurrence for the evaluation of the first derivative fn0(λ), namely,
f00(λ) = 0, f10(λ) = 1;
fj0(λ) = fj−1(λ) + (λ − αj)fj−10 (λ) − β2j−1fj−20 (λ), j = 2, 3, . . . , n.
The MatLab1 function evalpoly1 (Algorithm 1) [9] computes the function
values fn(λ) and fn0(λ) for a given λ and returns the value of the Newton
correction given by r =fn(λ) f0
n(λ)
.
Algorithm 1: Evaluating the characteristic polynomial and its derivative
function r=evalpoly1(λ, α, β); n=length(α); f1s=0; f1=1; f2s=1; f2=λ − α(1); for k=1:n-1 f0s=f1s; f0=f1; f1s=f2s; f1=f2; β = β(k); β = β*β; γ = λ − α(k + 1); f2s=f1+ γ*f1s-β*f0s; f2=γ*f1-β*f0; end r=f2/f2s;
The previous Algorithm 1 in the iterative phase only performs additions and multiplications. As has been noticed by several authors (see [5] and the references given therein) the errors generated by a floating point addition and multiplication are always floating point numbers. Specifically, let F be the set of floating point numbers, is the machine precision and, as usual, let f l(·) denote the result of a floating point computation. Then the elementary rounding error e generated in the computation of f l(a ◦ b), a, b ∈ F , ◦ ∈ {+, −, ∗}, namely,
e = (a ◦ b) − f l(a ◦ b)
satisfies e ∈ F . The algorithms TwoSum [17] and TwoProduct [5] given in input two floating point numbers a and b return as output the pair of floating numbers f l(a ◦ b) and e for ◦ = + and ◦ = ∗, respectively. The properties of these algorithms are summarized in the following theorem [22].
Theorem 2.1. Let a, b ∈ F and let x, y ∈ F be such that [x, y] = TwoSum(a, b). Then
a + b = x + y, x = f l(a + b), |y| ≤ |x|, |y| ≤ |a + b|. The algorithm TwoSum requires 6 flops.
Let a, b ∈ F and let x, y ∈ F be such that [x, y] = TwoProduct(a, b). Then a ∗ b = x + y, x = f l(a ∗ b), |y| ≤ |x|, |y| ≤ |a ∗ b|.
The algorithm TwoProduct requires 17 flops.
Now, for the sake of simplicity let us assume that the input data (λ, α, β) in Algorithm 1 are floating point numbers and the function evalpoly1 is mod-ified to return just only the value f2 of the characteristic polynomial. Scaling
the matrix T by a diagonal similarity transform yields b T = α1 β21 1. .. . .. . .. . .. β2 n−1 1 αn ,
which says that f2 is really a function of λ, αi and β2i. For the sake of
sim-plicity also suppose that β2
j ∈ F for j = 1, 2, . . . , n − 1. Then the function
g(λ, α, ˆβ) : = evalpoly1(λ, α, β), with ˆβ = β12, . . . , βn−12 , is computed by means of an algorithm ˆg using intermediate quantities g1, . . . , gN with
corre-sponding elementary rounding errors y1, . . . , yN and returning gN +1 as output.
Thus we can write gN +1 = ˆg(λ, α, ˆβ, y), y = [y1, . . . , yN]. By a first-order
analysis since g(λ, α, ˆβ) = ˆg(λ, α, ˆβ, 0) it follows that
∆ = g(λ, α, ˆβ) − ˆg(λ, α, ˆβ, y) = − N X i=1 ∂ ˆg ∂yi (λ, α, ˆβ, y)yi+ O(k y k2∞). (2.1)
The approach pursued by the compensated schemes proposed in [18, 10, 16] consists of computing the correcting term ˆy = −
N X i=1 ∂ ˆg ∂yi (λ, α, ˆβ, y)yi which
gives the first-order approximation of ∆ and then returning the corrected result ˜
g defined by
˜
g = f l(gN +1+ ˆy).
A compensated variant of Algorithm 1 should work as described in the next Algorithm 2. A slightly different version can be found in [11].
The following observation motivates our analysis.
Remark 2.2. As long as we assume that βj, βj2∈ F for j = 1, 2, . . . , n−1, then
it is easily seen that the values of Γ and ∆ returned as output by Algorithm 2 provide first-order approximations of the global forward error generated in the computation of the characteristic polynomial and its first derivative, respectively. In addition, if we look at the zero diagonal case where αj= 0, 1 ≤ j ≤ n, then
the global forward errors are linear function of the elementary rounding errors so that the big O term in (2.1) is zero and the linear terms gives the exact corrections.
To support theoretically the intuitive argument in favor of the compensa-tion technique we present in the sequel a forward rounding error analysis of Algorithm 2. A forward error analysis of three-term recurrences is somehow customary. We outline below the main points by taking in mind the application of Algorithm 2 to polynomial rootfinding.
Let (δ0, δ2, δ3, δ4) : = (δ (k) 0 , δ (k) 2 , δ (k) 3 , δ (k) 4 ), k = 1, 2, . . . , n−1, be the
Algorithm 2: Compensated variant of Algorithm 1 function rc=evalpoly1c(λ, α, β); n=length(α); f1s=0; f1=1; f2s=1; [f2,δ0]=TwoSum[λ, −α(1)]; ∆1= 0; ∆ = 0; Γ1= δ0; Γ = 0; for k=1:n-1 ∆0= ∆1; ∆1= ∆; Γ0= Γ1; Γ1= Γ; f0s=f1s; f0=f1; f1s=f2s; f1=f2; β = β(k); β = β*β; [γ, δ0]=TwoSum[λ, −α(k + 1)]; [r0s,δ2]=TwoProduct[β,f0s]; [r1s, δ3]=TwoProduct[γ,f1s]; [r2s, δ4]=TwoSum[f1,r1s]; [f2s, δ5]=TwoSum[r2s, -r0s]; ∆ = Γ1+ γ ∗ ∆1+ δ0∗ f1s − β ∗ ∆0+ δ3+ δ4+ δ5− δ2; [r0, δ2]=TwoProduct[β,f0]; [r1, δ3]=TwoProduct[γ,f1]; [f2, δ4]=TwoSum[r1, -r0]; Γ = γ ∗ Γ1+ δ0∗ f1 − β ∗ Γ0+ δ3+ δ4− δ2; end f2=f2+Γ; f2s=f2s +∆; rc=f2/f2s;
computation of the value of the characteristic polynomial. Set ˆfk(λ) = f l(fk(λ))
and µk= δ (k) 0 fˆk(λ) + δ (k) 3 + δ (k) 4 − δ (k)
2 . From Theorem 2.1 by calling
Γk = fk(λ) − ˆfk(λ), k = 0, 1, . . . , n, we obtain Γ0= 0, Γ1= µ0= δ (0) 0 ; Γk+1= (λ − αk+1)Γk− β2kΓk−1+ µk, k = 1, 2, . . . , n − 1.
The computation of the sequence Γk can be recasted in matrix form as the
solution of the following banded linear system with coefficient matrix F ∈ R(n+1)×(n+1), F Γ = µ, 1 αn− λ βn−12 . .. . .. . .. . .. . .. β2 1 . .. α 1− λ 1 Γn Γn−1 .. . Γ1 Γ0 = µn−1 .. . µ1 µ0 0 . (2.2) The matrix characterization yields the next result.
Theorem 2.3. Let us define the sequence of complementary orthogonal poly-nomials given by
ρ0(λ) = 1, ρ1(λ) = λ − αn;
ρj(λ) = (λ − αn−j+1)ρj−1(λ) − βn−j+12 ρj−2(λ), j = 2, 3, . . . , n − 1.
Then we find that
Γn= n−1 X j=0 µn−1−jρj(λ). (2.3) Furthermore, we have |Γk| ≤ 3 Γ∗+ O(2), Γ∗= M k F−1 k∞, k = 0, 1, . . . , n, where M = max k {(|λ| + |αk+1|)|fk(λ)| + β 2 k|fk−1(λ)|}.
Proof. Let us consider the persymmetric partitioning of F defined by F = e1 Tˆn 0 eT n .
The first characterization of Γnfollows by using Schur complementation applied
to this partitioning in order to compute a block representation of the inverse of F . Concerning the second estimate let us observe that from Theorem 2.1 we obtain that
|µk| ≤ 3(|λ − αk+1|| ˆfk(λ)| + βk2| ˆfk−1(λ)|) + O(2), k = 1, 2, . . . , n − 1,
and, hence,
|µk| ≤ 3M + O(2), k = 1, 2, . . . , n − 1.
Then from (2.2) it follows that at the first order
|Γk| ≤ 3M k F−1k∞= 3Γ∗, k = 0, 1, . . . , n.
Equation (2.3) describes the connection between three-term recurrences and Clenshaw’s algorithm for the summation of certain finite series. A related for-ward error analysis of Clenshaw’s algorithm can be found in [7, 1]. The final value of f2 returned by Algorithm 2 satisfies
f2 = f l( ˆfn(λ) + f l(Γn)) = ( ˆfn(λ) + f l(Γn))(1 + 1), |1| ≤ .
A forward error analysis of the algorithm for evaluating Γn can be derived
similarly as above. By setting
we obtain
γ0= 0, γ1= 0;
γk+1= (λ − αk+1)γk− β2kγk−1+ νk, k = 1, 2, . . . , n − 1,
where
|νk| ≤ 3(|λ − αk+1||Γk| + βk2|Γk−1| + |µk|) + O(3), k = 1, 2, . . . , n − 1.
Hence, from Theorem 2.3 it is found that
γn= n−2 X j=0 νn−1−jρj(λ), and, moreover, |νk| ≤ 92M k F−1 k∞(|λ − αk+1| + βk2+ k F k∞) + O(3), k = 1, 2, . . . , n − 1.
In this way, we finally arrive at the following estimate
f2 = ( ˆfn(λ) + Γn− γn)(1 + 1) = fn(λ)(1 + 1) − γn(1 + 1), |1| ≤ , and, equivalently, |f2 − fn(λ)| ≤ |fn(λ)| + |γn| + O(3), (2.4) where |γn| ≤ 92Γ∗( n−2 X j=0 (|λ − αn−1−j| + βn−1−j2 + k F k∞)|ρj(λ)|).
It is worth mentioning that the value of Γ∗determines the conditioning of the
zero–finding problem for the polynomial fn(λ). Indeed, if we consider relative
perturbations of the values β2
i → βi2(1 + i) and αi → αi(1 + 0i) |i|, |0i| ≤ 00,
and the corresponding perturbed characteristic polynomial ˜fn(λ) then it can be
shown that for any simple root ξ of fn(λ) and a sufficiently small 00 there is a
simple root ˜ξ of ˜fn(λ) such that
| ˜ξ − ξ| |ξ| ≤ 3 Γ∗ |ξ||f0 n(ξ)| + O(2).
Hence by applying corollary 2.3 in [23] we obtain the following result.
Theorem 2.4. Assume that fn(ξ) = 0, fn0(ξ) 6= 0, ξ ∈ R, and, moreover, there
exists I = [ξ − δ, ξ + δ], δ ≥ 0, such that ∀λ ∈ I we have |f l(f 0 n(λ)) − fn0(λ)| |f0 n(λ)| ≤ 1/8,
and
maxλ∈I|fn00(λ)|
|f0 n(ξ)|
|λ − ξ| ≤ 1/8.
Let us consider the Newton method applied in floating point arithmetic for the solution of fn(λ) = 0 by making use of Algorithm2 for computing the function
values. Suppose that no premature underflow condition occurs for initial guesses ξ0 ∈ I. Then there exists I0 ⊂ I such that ∀ξ0 ∈ I0 the method applied with
starting point ξ0 generates a sequence {ξk} whose relative error decreases until
the first k for which
|ξk− ξ| |ξ| ' + 9 2N Γ∗ |ξ||f0 n(ξ)| , where N = max λ∈I n−2 X j=0 (|λ − αn−1−j| + βn−1−j2 + k F k∞)|ρj(λ)|.
Incorporating scaling techniques in Algorithm2 can be useful in order to prevent underflow/overflow situations and to keep N of moderate magnitude. This leads to the following modified version –referred as to Algorithm 3– which will be tested experimentally in the next section.
It is remarkable to notice that the value of the Newton correction is indepen-dent of the scaling factor so that there is no need to compute back the “exact” evaluations of the characteristic polynomial and its first derivative.
3. Numerical Results
We have designed a numerical method for eigenvalue refinement of sym-metric tridiagonal matrices based on the Newton iteration complemented with Algorithm 3 for the evaluation of the function values. The resulting algo-rithm named New cs –acronym of Newton’s method with compensation and scaling– have been tested in Matlab. For comparison purposes we have also im-plemented a variant called New s making use of Algorithm 1 comim-plemented with the same scaling strategy as employed in Algorithm 3. Numerical results are shown to illustrate the differences between the compensated algorithm and this latter variant.
To measure the relative error of a computed approximation bξ we rely upon the following well known inclusion theorem for polynomial roots (see Corollary 6.4g in [14]). Assume that bξ 6= 0 and fn0(bξ) 6= 0 then there exists a root ξ of fn(λ) such that |bξ − ξ| |bξ| ≤ n |fn(bξ)| |f0 n(bξ)||bξ| .
The relative approximation error app err of a computed nonzero approximation b ξ is therefore defined as app err : = n |fn(bξ)| |f0 n(bξ)||bξ| .
Algorithm 3: Compensated variant of Algorithm 1 with scaling function rcs=evalpoly1c(λ, β, Ms, Mi);
n=length(β); n=n+1; f1s=0; f1=1; f2s=1; [f2,δ0]=TwoSum[λ, −α(1)]; ∆1= 0; ∆ = 0; Γ1= δ0; Γ = 0; for k=1:n-1 ∆0= ∆1; ∆1= ∆; Γ0= Γ1; Γ1= Γ; f0s=f1s; f0=f1; f1s=f2s; f1=f2; β = β(k); β = β*β; [γ, δ0]=TwoSum[λ, −α(k + 1)]; [r0s,δ2]=TwoProduct[β,f0s]; [r1s, δ3]=TwoProduct[γ,f1s]; [r2s, δ4]=TwoSum[f1,r1s]; [f2s, δ5]=TwoSum[r2s, -r0s]; ∆ = Γ1+ γ ∗ ∆1+ δ0∗ f1s − β ∗ ∆0+ δ3+ δ4+ δ5− δ2; [r0, δ2]=TwoProduct[β,f0]; [r1, δ3]=TwoProduct[γ,f1]; [f2, δ4]=TwoSum[r1, -r0]; Γ = γ ∗ Γ1+ δ0∗ f1 − β ∗ Γ0+ δ3+ δ4− δ2; w=max{|f1|, |f2|}; if (w ≥ Ms) w=Ms/w; w=ceil(log2(w)); w=2w; f1=f1∗w; f2=f2∗w; f1s=f1s∗w; f2s=f2s∗w; ∆ = ∆∗w; ∆1 = ∆1∗w; Γ = Γ∗w; Γ1 = Γ1∗w; else if (w ≤ Mi) w=Msi/w; w=floor(log2(w)); w=2w; f1=f1∗w; f2=f2∗w; f1s=f1s∗w; f2s=f2s∗w; ∆ = ∆∗w; ∆1 = ∆1∗w; Γ = Γ∗w; Γ1 = Γ1∗w; end; end; end; f2=f2+Γ; f2s=f2s +∆; rcs=f2/f2s;
where the Newton correction is evaluated by Algorithm 1 carried out in high (128 digits) precision arithmetic. Both algorithms New cs and New s are stopped whenever the relative error between two consecutive iterates is less than in magnitude or the number of iterations exceed a given fixed maxit value. According to [26] the values of Ms and Mi used in Algorithm 3 for scaling are set to 234and 2−34, respectively, in our implementations.
Out test suite consists of the following examples:
1. The tridiagonal reduction of the rosser matrix, that is, T = hess(rosser). The rosser matrix is a small 8 × 8 classical test for matrix eigenvalue al-gorithms. The matrix, and thus also T , has a numerically zero eigenvalue.
2. Random symmetric tridiagonal matrices Tn ∈ Rn×nwith eigenvalues λ1=
, λi= 1+(i−2)
√
, 2 ≤ i ≤ n. The matrices are obtained by Householder tridiagonal reduction of random dense symmetric matrices that have the given eigenvalue distribution.
3. Tridiagonal Toeplitz matrices Tn= (ti,j) ∈ Rn×n with
ti,j =
1 if |i − j| = 1;
2 − (π/(n + 1))2 if |i − j| = 0. These matrices have one small eigenvalue of order 1/n4.
4. Shifted Wilkinson tridiagonal matrices Tn(α) ∈ Rn×n generated by
Tn(α) = wilkinson(n) − α · eye(n).
5. Symmetric tridiagonal matrices Tn ∈ Rn×n, Tn= Tn(α, β), n = 2k, with
zero diagonal and subdiagonal entries defined by
β2j−1= α ∈ {2−10, 1}, β2j= β = {1, 4n}, j = 1, 2, . . . , k.
These matrices are encountered when computing the SVD of bidiagonal Toeplitz matrices [8]. The eigenvalues occur in pairs (−λ, λ) with typically two paired eigenvalues very close to the origin.
In all the tests performed we start the iterative refinement using the approx-imation of the eigenvalue of minimum modulus returned by the function eig applied to the input matrix.
In Example 1 both algorithms New cs and New s stop in three iterations. The approximation error is app err = 4.6e−17 for the approximation returned by New cs and app err = 4.3e−2 for the approximation returned by New s.
For the input matrices of Example 2 algorithm New s does not generally fulfill the stopping condition on the relative error by thus performing maxit iterations in all the tests considered without any significant improvement of the accuracy. Differently algorithm New cs stops in a few (less than 5) iterations. In next Figure 1 we show the approximation errors measured at the end of execution of algorithm New cs.
Similar results can be found for the matrices in Example 3. In Figure 2 we plot the approximation errors measured at the end of execution of algorithm New cs. Observe that the accuracy of the approximation returned by the compensated scheme is quite independent of its magnitude.
Wilkinson’s eigenvalue test matrices are symmetric tridiagonal matrices with pairs of nearly equal eigenvalues and unit subdiagonal entries. We consider the following two classes of shifted matrices:
1. To= wilkinson(21 + 20 · k) − 6 · eye(21 + 20 · k), k = 1, 2, . . .;
0 2 4 6 8 10 12 14 16 10−15 10−10 10−5 100 105 New s Newcs
Figure 1: Relative errors of approximation returned by New s and New cs for test matrices as in Example 2 of size n = 20 + 20 · k, k = 1, 2, . . . , 16. The figure plots app err versus the integer k. 0 5 10 15 20 10−16 10−14 10−12 10−10 10−8 10−6 10−4 10−2 New s New cs
Figure 2: Relative errors of approximation returned by New s and New cs for test matrices as in Example 3 of size n = 32 + 20 · k, k = 1, 2, . . . , 20. The figure plots app err versus the integer k.
0 2 4 6 8 10 12 10−15 10−14 10−13 10−12 10−11 T o Te
Figure 3: Relative approximation errors returned by New cs for Wilkinson’s type matrices of size n = {21, 32} + 20 · k, k = 1, 2, . . . , 11. The figure plots app err versus the integer k.
Each matrix To and Te has two small eigenvalues of order 1.0e−6 and
1.0e−10, respectively. In Figure 3 we show the plot of the approximation error generated by New cs.
However for harder tests algorithm New cs can even fail. The matrix Te = wilkinson(62) − 18.5 ∗ eye(62) has two eigenvalues of order 1.0e−16
and New cs fails to resolve the coalescence of these eigenvalues. It is found that the condition number of computing the determinant of Te is about 1.0e34
and therefore quadruple precision is not enough.
Finally we consider tridiagonal matrices with zero diagonal generally used to check the behavior of algorithms for computing the SVD of bidiagonal matrices. For the matrix T of order 48 with α = 2−10 and β = 1 the function eig returns one positive and one negative eigenvalue of order 1.0e−16. Algorithm New cs starts to refine the positive root and after 179 iterations it finds a new approximation of order 1.0e−73 having the approximation error of the same order of the machine precision. The Newton method exhibits a quadratic convergence just only in the last three or four iterations. For most of the steps the iteration shows a linear convergence since the two very close roots are seen as one single multiple root lying at the origin. This makes the refinement process not competitive with faster matrix–based methods [8] which may converge in a few iterations. In Figure 4 we illustrate the convergence history by plotting the relative error rel err : = |ξj+1− ξj|/|ξj|, 1 ≤ j ≤ 178, between two consecutive
iterates.
For the input matrix T of order 64 with α = 1 and β = 256 our algorithm returns after 194 iterations the approximation σ32= 2.210 825 415 070 759e−75
which is correct to full machine precision. However, it is worth noticing that for tridiagonals with zero diagonal there are no appreciable differences between New cs and New s. This is in accordance with the classical rule of thumb that the forward error is of order of the backward error multiplied by the conditioning of the problem. From [6] we know that the problem is almost perfectly well
160 162 164 166 168 170 172 174 176 178 10−14 10−12 10−10 10−8 10−6 10−4 10−2 100 rel err
Figure 4: Relative errors between two consecutive iterates at the end of the refinement iterative process. The figure plots rel err versus the iteration index.
conditioned and, moreover, the three-term recurrence computation is backward stable.
4. Conclusion and future work
We have presented a compensated scheme using error free transformations for evaluating the characteristic polynomial and its first derivative of a symmet-ric tridiagonal matrix. This scheme has been used in conjunction with Newton’s method to get a better approximation of matrix eigenvalues. Numerical exper-iments show that the resulting algorithm generally makes it possible to refine a good initial guess to yield an eigenvalue approximation as accurate as if com-puted with twice the working precision.
Future work will be directed towards a generalization of the results for the case where the customary Newton method is replaced by the Ehrlich-Aberth iteration for simultaneous eigenvalue computation. This iteration can still be derived as a Newton method applied to a sequence of rational functions de-pending on the simultaneously computed approximations of the eigenvalues. The application of the resulting algorithm for the solution of the bidiagonal SVD computation is also an ongoing research.
Funding
This work was partially supported by GNCS-INDAM and University of Pisa. [1] R. Barrio. Rounding error bounds for the Clenshaw and Forsythe algo-rithms for the evaluation of orthogonal polynomial series. J. Comput. Appl. Math., 138(2):185–204, 2002.
[2] D. A. Bini and G. Fiorentino. Design, analysis, and implementation of a multiprecision polynomial rootfinder. Numer. Algorithms, 23(2-3):127–173, 2000.
[3] D. A. Bini and V. Noferini. Solving polynomial eigenvalue problems by means of the Ehrlich-Aberth method. Linear Algebra Appl., 439(4):1130– 1149, 2013.
[4] C. Bossut. A general history of mathematics from the earliest times to the middle of the eighteenth century. Tr. from the French of John Bossut ... To which is affixed a chronological table of the most eminent mathematicians. London : J. Johnson, 1803.
[5] T. J. Dekker. A floating-point technique for extending the available preci-sion. Numer. Math., 18:224–242, 1971/72.
[6] J. Demmel and W. Kahan. Accurate singular values of bidiagonal matrices. SIAM J. Sci. Statist. Comput., 11(5):873–912, 1990.
[7] D. Elliott. Error analysis of an algorithm for summing certain finite series. J. Austral. Math. Soc., 8:213–221, 1968.
[8] K. V. Fernando and B. N. Parlett. Accurate singular values and differential qd algorithms. Numer. Math., 67(2):191–229, 1994.
[9] W. Gander and P. Gonnet. Polynomial recurrence, Newton correction and polynomial fractions. Unpublished.
[10] S. Graillat. Accurate simple zeros of polynomials in floating point arith-metic. Comput. Math. Appl., 56(4):1114–1120, 2008.
[11] S. Graillat. Accurate computation of the determinant of a tridiagonal ma-trix. Personal Communication, 2015.
[12] M. Gu and S. C. Eisenstat. A divide-and-conquer algorithm for the bidi-agonal SVD. SIAM J. Matrix Anal. Appl., 16(1):79–92, 1995.
[13] N. Hale and A. Townsend. Fast and accurate computation of Gauss-Legendre and Gauss-Jacobi quadrature nodes and weights. SIAM J. Sci. Comput., 35(2):A652–A674, 2013.
[14] P. Henrici. Applied and computational complex analysis. Vol. 1. Wiley Classics Library. John Wiley & Sons, Inc., New York, 1988. Power series— integration—conformal mapping—location of zeros, Reprint of the 1974 original, A Wiley-Interscience Publication.
[15] E. R. Jessup and D. C. Sorensen. A parallel algorithm for computing the singular value decomposition of a matrix. SIAM J. Matrix Anal. Appl., 15(2):530–548, 1994.
[16] H. Jiang, S. Graillat, C. Hu, S. Li, X. Liao, L. Cheng, and F. Su. Accurate evaluation of the k-th derivative of a polynomial and its application. J. Comput. Appl. Math., 243:28–47, 2013.
[17] D. E. Knuth. The art of computer programming. Vol. 2. Addison-Wesley, Reading, MA, 1998. Seminumerical algorithms, Third edition [of MR0286318].
[18] P. Langlois. Automatic linear correction of rounding errors. BIT, 41(3):515– 539, 2001.
[19] T. Y. Li, N. H. Rhee, and Z. G. Zeng. An efficient and accurate parallel algorithm for the singular value problem of bidiagonal matrices. Numer. Math., 69(3):283–301, 1995.
[20] G. Meurant and A. Sommariva. Fast variants of the Golub and Welsch algorithm for symmetric weight functions in Matlab. Numer. Algorithms, 67(3):491–506, 2014.
[21] Isaac Newton. The mathematical papers of Isaac Newton. Vol. VIII. Cam-bridge University Press, CamCam-bridge, 1981. 1697–1722, Edited by D. T. Whiteside, With the assistance of A. Prag.
[22] T. Ogita, S. M. Rump, and S. Oishi. Accurate sum and dot product. SIAM J. Sci. Comput., 26(6):1955–1988, 2005.
[23] F. Tisseur. Newton’s method in floating point arithmetic and iterative refinement of generalized eigenvalue problems. SIAM J. Matrix Anal. Appl., 22(4):1038–1057 (electronic), 2001.
[24] C. Trefftz, C. C. Huang, P. K. McKinley, T.-Y. Li, and Z. Zeng. A scalable eigenvalue solver for symmetric tridiagonal matrices. Parallel Comput., 21(8):1213–1240, 1995.
[25] J. H. Wilkinson. The algebraic eigenvalue problem. Monographs on Numer-ical Analysis. The Clarendon Press, Oxford University Press, New York, 1988. Oxford Science Publications.
[26] J. Zhang. The scaled Sturm sequence computation. In Proceedings of the Eighth SIAM Conference on Applied Linear Algebra. The College of William and Mary, Williamsburg, VA, USA, SIAM, July 2003.
